1
$\begingroup$

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 ?

$\endgroup$
0
1
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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 ? $\endgroup$
    – Fin27
    Sep 14 at 23:49
  • 2
    $\begingroup$ @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. $\endgroup$
    – Ned
    Sep 14 at 23:57
  • 1
    $\begingroup$ @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)$ $\endgroup$
    – Ned
    Sep 15 at 11:16
  • 1
    $\begingroup$ @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). $\endgroup$
    – Ned
    Sep 17 at 11:24
  • 1
    $\begingroup$ @Fin27 yes, exactly $\endgroup$
    – Ned
    Sep 19 at 0:49
1
$\begingroup$

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.

$\endgroup$
0
1
$\begingroup$

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$

$\endgroup$
0
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.