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

Question

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 ?

Answer 1

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.

Answer 2

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.

Answer 3

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$

Answer 4

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