Suppose I want to distribute $30$ toys in $30$ boxes. Any number of toys (from the given toys) can be kept in any box.

In how many ways can this be done?

I know how to solve this problem using generating functions..

I will look for the coefficient of $x^{30} $ in $(1+x+ \cdots +x^{30})^{30}$

It comes out to be $\binom{59}{30}$.

Is there a more intuitive way, without using generating functions or the multinomial theorem, to arrive at this result?

Thank you.

  • $\begingroup$ Standard Stars and Bars, please see Wikipedia. Similar problems have been on MSE many times. $\endgroup$ – André Nicolas Sep 10 '14 at 5:34

It can be looked at as placing 59 (30+30-1) objects in a row and picking 29 objects out. Each of such picking outcome is equivalent to placing 30 toys in 30 boxes with the $i$-th box containing objects between the $(i-1)$-th picked object and $i$-th object, and the last box containing objects to the right of the last object picked. So, it is $\left(\begin{array}{c}59 \\ 30 \end{array}\right)$.

  • $\begingroup$ Why $59(30+30-1)$? $\endgroup$ – pkwssis Sep 10 '14 at 5:49
  • $\begingroup$ Note that by selecting $N-1$ objects out of $M+N-1$ objects, we have created a binning of $M$ objects (that are the left over objects after picking $N-1$ objects), where the boundaries of the binning are represented by the selected objects. And, in your question, $M=30$, $N=30$. $\endgroup$ – Shash Sep 10 '14 at 6:15
  • $\begingroup$ @Pkwssis - I expect Shash mean $59=30+30-1$. It is a stars and bars calculation $\endgroup$ – Henry Sep 10 '14 at 6:24

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.