1
$\begingroup$

The number of ways in which $5$ distinct objects can be distributed into $3$ identical boxes such that each box contains any number of objects.

What I have tried:

I have used stars and bar method.

We have $5$ stars and we have to distribute into $3$ persons and each person get any number of objects.

$*\;\;|\;\;\;|\;*\;\;|\;\;*\;\;*\;\;*$

we have $\displaystyle \frac{8!}{3!\times 5!}=56$

but answer given is $36$.

Help required with how to solve the problem.

$\endgroup$
  • $\begingroup$ As pointed out in an answer, stars and bars is an incorrect method for this problem. But you should also be more careful how you do stars and bars in the future: you have used too many bars. $\endgroup$ – David K Sep 22 '18 at 14:21
  • $\begingroup$ The actual answer is $41$. $\endgroup$ – N. F. Taussig Sep 22 '18 at 14:32
1
$\begingroup$

The technique you used is for placing identical objects into distinct boxes.

What matters here is which objects are in the same box. We consider cases.

Case 1: All five objects are placed in the same box.

Since the boxes are indistinguishable, this can be done in $$\binom{5}{5} = 1$$ way.

Case 2: Four objects are placed in one box and the other object is placed in another box.

There are $$\binom{5}{4} = 5$$ ways to choose which four objects are placed in the same box and one way to place the other object in another box.

Case 3: Three objects are placed in one box and the other two objects are placed in another box.

There are $$\binom{5}{3} = 10$$ ways to choose which three objects are placed in the same box and one way to place the remaining two objects in another box.

Case 4: Three objects are placed in one box and one object each is placed in the other boxes.

There are $$\binom{5}{3} = 10$$ ways to choose which three objects are placed in the same box. That leaves two objects which must be placed in the two empty boxes. Since those boxes are indistinguishable, there is only one way to place them in separate boxes.

Case 5: Two objects are placed in one box, two other objects are placed in another box, and the remaining box receives one object.

There are five ways to choose which object is placed by itself in a box. Place one of the remaining four objects in an empty box. There are three ways to choose which of the other objects will be placed in the box with it. The remaining two objects must be placed in the remaining box. Thus, there are $$\binom{5}{1}\binom{3}{1} = 15$$ ways to distribute five distinct objects to three indistinguishable boxes in this case.

Total: The number of ways five distinct objects can be distributed to three indistinguishable boxes if boxes may be left empty is $$\binom{5}{5} + \binom{5}{4} + \binom{5}{3} + \binom{5}{3} + \binom{5}{1}\binom{3}{1} = 1 + 5 + 10 + 10 + 15 = 41$$ so the answer stated in your book is wrong.

To compare my result with that of @sc_, case 1 is $S(5, 1)$, cases 2 and 3 total to $S(5, 2)$, and cases 4 and 5 total to $S(5, 3)$. If you check the table of values on the linked Stirling numbers of the second kind page, you will see that $S(5, 1) + S(5, 2) + S(5, 3) = 1 + 15 + 25 = 41$.

$\endgroup$
2
$\begingroup$

In your approach, you are actually taking distinct boxes and identical objects.

The required answer will be $$ \Sigma_{j=1}^{3} S(5,j) $$

where $S(n,k)$ are the Stirling Numbers of the Second kind

$\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.