# Permutations and combinations problem , need help

How many ways can we distribute 5 different balls into 3 identical boxes such that there is at least one ball in each box ?

My try

By Stars and Bars Method

$x+y+z=5$

$C(7,5)=C (7,2)=21$

Assume the balls are labeled $A,B,C,D,E$. Since the boxes are indistinguishable we remark that, say, $(ABC,D,E)$ is the same as $(ABC, E,D)$ and $(AB,CD,E)$ is the same as $(CD,AB,E)$.

Pattern I: $(3,1,1)$. There are $\binom 53=10$ ways to choose the three. The other two can be put in either order so $\boxed {10}$ cases.

Pattern II: $(2,2,1)$. There are $\binom 52=10$ ways to choose the first two, and then $\binom 32=3$ ways to choose the other two. As we can switch the two pairs we must divide by $2$. Hence there are $\frac 12\times 10\times 3=\boxed {15}$ cases

Hence there are $\boxed {25}$ cases in total.

• Is casework a necessary evil for this problem? – Tiwa Aina Nov 29 '17 at 20:00
• @TiwaAina I believe so, yes. The number of ways to populate each pattern depends strongly on the nature of the pattern. That said, there are sometimes alternate ways of looking at a combinatorics problem which give rise to different counting methods so I wouldn't swear that there isn't a better way. – lulu Nov 29 '17 at 20:02
• Are you considering (ABC, D, E), (ACB, D, E), (CAB, D, E), (CBA, D, E), (BCA, D, E) and (BAC, D, E) same? As the balls are different they are making different combinations of themselves. I have got a doubt here as you have not considered this. – NewBee Nov 29 '17 at 20:53

To solve such problems, I use the multinomial formula,
with correction for cases with more than one urn having the same number of balls.

The only possible patterns here are $2-2-1$ and $3-1-1$,
thus $\binom{5}{2,2,1}/2! + \binom{5}{3,1,1}/2! = 25$

Note that the division correction applies only to occupied bins, so for patterns with empty bins, e.g. $5-0-0$ the answer would simply be $\binom{5}{5,0,0}$

For a more complex example, say distributing $13$ balls in $8$ bins,
for pattern $3-3-3-2-2-0-0-0$, the answer would be $\dfrac{\binom{13}{3,3,3,2,2,0,0,0}}{3!2!}$

Hint: you can consider an equivalent problem with 5 balls and 2 separators

the 2 separators are equivalent to the three boxes if you assume that the space between the 2 separators are the central box

• Would have to then substract the situations in which the separators are at the start and end of the permutation, or are consecutive. Seems like a lot of work considering work woth disjoint cases – Francisco José Letterio Nov 30 '17 at 5:31

Since the 3 boxes are identical so the order of selecting the boxes doesn't matter.

Now we can have two combinations of distributing the 5 balls : (3,1,1) or (2,2,1)

CASE I :

Ways of selecting 3 balls: 5C3

Ways of selecting 1 ball: 2C1

Ways of selecting the last ball: 1C1

Total no. of ways: 5C3 x 2C1 x 1C1 = 20

CASE II :

Ways of selecting 2 balls: 5C2

Ways of selecting 2 balls: 3C2

Ways of selecting the last ball: 1C1

Total no. of ways: 5C2 x 3C2 x 1C1 = 30

Thus required ways: 20+30 = 50

• In each case you are neglecting a symmetry. In case I, there is no difference between the two boxes containing one ball, so $(ABC,D,E)$ is the same as $(ABC,E,D)$ as the boxes are indistinguishable. Similarly, in the second case, $(AB,CD,E)$ is the same as $(CD,AB,E)$. Thus you have to divide through by $2$ in each case. – lulu Nov 29 '17 at 20:49
• @lulu Are you considering (ABC, D, E), (ACB, D, E), (CAB, D, E), (CBA, D, E), (BCA, D, E) and (BAC, D, E) same? As the balls are different they are making different combinations of themselves. I have got a doubt here as you have not considered this. Asked the same question as a comment in your reply. – NewBee Nov 29 '17 at 20:55
• Yes, I consider all those to be the same. Nothing in the question suggests that the arrangement inside the box is relevant. Of course, one could easily handle the case where the arrangement did matter...just multiply the case I solution by $3!$ and the case II solution by $2!\times 2!$. – lulu Nov 29 '17 at 21:08