Using generating functions to find number of ways to divide 15 indistinguishable balls into 10 distinguishable non empty cells?

349 Views Asked by At

After thinking about this problem and looking online for a bit, I have come to think that the answer is the coefficient of $x^{15}$ for generating function $$G(x) = (x+x^2+\cdots)^{10}.$$

I chose to remove the $1$ from each term because the boxes cannot be empty. But what I am confused at is why the term inside the parentheses should be an infinite sum? This part I found in a few texts but could not find an explanation that has helped.

Thanks

1

There are 1 best solutions below

1
On BEST ANSWER

One of the reasons to use infinite series is many times for counting problems they have succinct representations, e.g., $$ \frac{1}{1-x} = 1 + x + x^2 + x^3 + ... $$ This series is useful for representing sequences of "singletons" of "weights" $0, 1, 2, 3, \ldots$. The neat thing is that many common transformations on the succinct representation (adding, subtracting, multiplying, etc.) can be tied to counting items.

In your problem, for example, let the exponent ("weight") be the number of balls in a cell. There is one way to have 1 ball in a cell (since the balls are indistinguishable), one way to have 2 balls in a cell, etc. You can represent a single cell as $$ x + x^2 + x^3 + \ldots $$ where I like to read this as a cell can have 1 ball ($x$) or 2 balls ($x^2$) or 3 balls ($x^3$), etc. Suppose now we have two cells; then the ball counts in each cells can be represented using the series above $$ (x + x^2 + x^3 + \ldots)(x + x^2 + x^3 + \ldots) $$ I like to read this as: the first cell has 1 ball or 2 balls or 3 balls, etc. AND the second cells has 1 ball or 2 balls or 3 balls etc. Notice that multiplying both series allows us to talk about the two cells together. Now if we carry out the multiplication we have $$ x^2 + 2x^3 + 3x^4 + \ldots $$ The exponent (weight) gives us the total number of balls distributed among the two cells while the coefficient gives us the number of ways. If we have only two balls then there is exactly one way to distribute the balls into the two cells $\{(1,1)\}$. If we have 3 balls then there are two ways to distribute the balls into the two cells $\{(1,2), (2,1)\}$.

Now the really cool thing is that we don't have to work with the expanded form for the series; we can use the same reasoning on the succinct forms. First note that $$ x + x^2 + x^3 + \ldots = x(1 + x + x^2 + \ldots) = \frac{x}{1-x} $$ which means that $$ (x + x^2 + x^3 + \ldots)(x + x^2 + x^3 + \ldots) = \left ( \frac{x}{1-x} \right ) ^2 = \frac{x^2}{(1-x)^2} $$ People have developed a bunch of observations about coefficients of common series used for counting. For example, $$ \frac{1}{(1-x)^2} = \sum_{n \geq 1}^\infty nx^{n-1} $$ which means that $$ \frac{x^2}{(1-x)^2} = \sum_{n \geq 1}^\infty nx^{n+1} = x^2 + 2x^3 + 3x^4 + \ldots $$ So far, it might not seem that we have made a lot of progress. But for you specific problem where we have 15 balls and 10 cells we want to coefficient of $x^{15}$ in $$ \left ( \frac{x}{1-x} \right )^{10} = \frac{x^{10}}{(1-x)^{10}} $$ You now can use the fact that $$ \frac{1}{(1-x)^{k}} = \sum_{n \geq 0} {n + k - 1 \choose n} x^n $$ to conclude that $$ \left ( \frac{x}{1-x} \right )^{k} = \frac{x^k}{(1-x)^{k}} = \sum_{n \geq 0} {n + k - 1 \choose n} x^{n + k} = \sum_{n \geq k} {n - 1 \choose n - k} x^{n} = \sum_{n \geq k} {n - 1 \choose k - 1} x^{n} $$ You can now substitute for your problem and pattern match to find that the coefficient is ${14 \choose 9}$.

You can do something similar using the polynomials $(x + x^2 + \ldots x^6)$ but it would make the generating function manipulations more cumbersome.