# Distributing 5 distinct objects into 3 identical boxes such that a box can be empty

My approach :

I listed down the following cases :-

Case 1) 5 0 0 --> 5c5 = 1 way

Case 2) 4 1 0 --> 5c4 * 1c1 = 5 ways

Case 3) 3 2 0 --> 5c3 * 2c2 = 10 ways

Case 4) 3 1 1 --> 5c3 * 2c1 * 1c1 = 20 ways

Case 5) 2 2 1 --> 5c2 * 3c2 * 1c1= 30 ways

by adding all this I get 66 ways in which all possible combinations of selecting distinct objects is taken care of , and I feel that I don't need to arrange it further in boxes as all the boxes are identical

According to the solution provided for case 4 (i.e. 3,1,1) they have counted 10 ways and for case 5(i.e. 2,2,1) they have counted 15 ways , which makes their total to 41

can someone let me know where exactly am I going wrong with my approach ?

In Case 4) for example you have not considered that the 3 boxes are regarded as identical so once you have chosen the first 3 items that go in one box there is no other choice to be made . The other 2 boxes contain 1 item each and it is regarded as the same choice whichever way round you choose to place the 2 remaining items.

• In case 4 , when I did 5c3 * 2c1 * 1c1 = 20 ways , these 20 ways are all the combinations of 5 distinct objects listed , basically denoting the order in which each object would be filled in a box (example if the 5 objects are A,B,C,D,E one of the 20 combinations would be like ABCDE , or say BCDAE , which I guess is just denoting the order of filling up the boxes , like in arrangement BCDAE it states that B is filled before C , C before D .... so on) I did not take the box into account till here ? so how is it violating the condition of not taking boxes identical ? Sep 14 at 23:49
• @Fin27 You are counting, e.g. ABC | D | E as different than ABC | E | D whereas they should be counted as the same arrangement if the boxes are identical.
– Ned
Sep 14 at 23:57
• @Fin27 In the cases that have two identical sizes in a pair of boxes (i.e. $3,1,1$ and $2,2,1$) you must divide your answer by $2$ because because by doing multiplication principle box by box, you have implicitly ordered the two boxes that hold the same number of items -- as explained by many others in the answers here -- and so you overcount double as in the example I mentioned. Such over counting only occurs by $2$ with $5$ balls, $3$ boxes, but if you were putting $6$ balls into $3$ boxes, the case $2,2,2$ would overcoat by a factor of $3!=6$ if you just did $(C(6,2)C(4,2)C(2,2)$
– Ned
Sep 15 at 11:16
• @Fin because your original method, which is what the fix-up is about, does NOT count e.g. ABC | D | E as different than D |ABC | E, because you do NOT add in a term $C(5,1)C(4,3)C(1,1)$ etc. You already took care of that by listing the types in non-increasing order (i.e. 3,1,1 not 1,3,1).
– Ned
Sep 17 at 11:24
• @Fin27 yes, exactly
– Ned
Sep 19 at 0:49

Notice that the ones you got wrong are the ones where there are two boxes which contain the same non-zero number of balls. This happens because $${2 \choose 1} \times {1 \choose 1}$$ actually treats the boxes as if they were different.

To easily see this, consider 2 different balls and 2 identical boxes, and we want to put 1 ball in each box. Then the answer is 1, but with your method it is 2.

Here's a different approach. There are $$3^5 = 243$$ arrangements if the boxes are numbered. $$3$$ of these are "all balls in one box" arrangements, which corresponds to only $$1$$ "identical boxes" arrangement.

Every other identical box arrangement corresponds to $$3!=6$$ labeled box arrangements, since the contents of all three boxes are different in each of these "not-all-in-one-box" arrangements.

Thus the total number of identical box arrangements is $$1 + (243-3)/6 = 41$$

Distribution of distinguishable objects into indistinguishable subset call for Stirling Numbers of the Second Kind.

\begin{align} \left\{{5}\atop{1}\right\}+\left\{{5}\atop{2}\right\}+\left\{{5}\atop{3}\right\}&=1+15+25\\ &=41 \end{align}

From left to right: one non empty box, two non empty boxes, and three non empty boxes