# Finding number of ways of distributing toys without generating function

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.

• Standard Stars and Bars, please see Wikipedia. Similar problems have been on MSE many times. – 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)$.
• Why $59(30+30-1)$? – pkwssis Sep 10 '14 at 5:49
• 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$. – Shash Sep 10 '14 at 6:15
• @Pkwssis - I expect Shash mean $59=30+30-1$. It is a stars and bars calculation – Henry Sep 10 '14 at 6:24