##### Example8.4

We already know that the number of ways to distribute \(n\) apples to \(5\) children so that each child gets at least one apple is \(C(n-1,4)\text{,}\) but it will be instructive to see how we can derive this result using generating functions. Let's start with an even simpler problem: how many ways are there to distribute \(n\) apples to *one* child so that each child receives at least one apple? Well, this isn't too hard, there's only one way to do it—give all the apples to the lucky kid! Thus the *sequence* that enumerates the number of ways to do this is \(\{a_n\colon n\geq 1\}\) with \(a_n=1\) for all \(n\geq 1\text{.}\) Then the generating function for this sequence is
\begin{equation*}
x+x^2+x^3+\cdots = x(1+x+x^2+x^3+\cdots) = \frac{x}{1-x}.
\end{equation*}
How can we get from this fact to the question of five children? Notice what happens when we multiply
\begin{equation*}
(x+x^2+\cdots)(x+x^2+\cdots)(x+x^2+\cdots)(x+x^2+\cdots)
(x+x^2+\cdots).
\end{equation*}

To see what this product represents, first consider how many ways can we get an \(x^6\text{?}\) We could use the \(x^2\) from the first factor and \(x\) from each of the other four, or \(x^2\) from the second factor and \(x\) from each of the other four, etc., meaning that the coefficient on \(x^6\) is \(5 = C(5,4)\text{.}\) More generally, what's the coefficient on \(x^n\) in the product? In the expansion, we get an \(x^n\) for every product of the form \(x^{k_1}x^{k_2}x^{k_3}x^{k_4}x^{k_5}\) where \(k_1+k_2+k_3+k_4+k_5 = n\text{.}\) Returning to the general question here, we're really dealing with distributing \(n\) apples to \(5\) children, and since \(k_i> 0\) for \(i=1,2,\dots,5\text{,}\) we also have the guarantee that each child receives at least one apple, so the product of the generating function for *one* child gives the generating function for *five* children.

Let's pretend for a minute that we didn't know that the coefficients must be \(C(n-1,4)\text{.}\) How could we figure out the coefficients just from the generating function? The generating function we're interested in is \(x^5/(1-x)^5\text{,}\) which you should be able to pretty quickly see satisfies \begin{align*} \frac{x^5}{(1-x)^5} \amp = \frac{x^5}{4!}\frac{d^4}{dx^4}\left(\frac{1}{1-x}\right) = \frac{x^5}{4!}\sum_{n=0}^\infty n(n-1)(n-2)(n-3)x^{n-4}\\ \amp =\sum_{n=0}^\infty \frac{n(n-1)(n-2)(n-3)}{4!}x^{n+1} = \sum_{n=0}^\infty \binom{n}{4}x^{n+1}. \end{align*} The coefficient on \(x^n\) in this series \(C(n-1,4)\text{,}\) just as we expected.