Question

Use generating functions to determine the number of different ways 15 identical stuffed animals can be given to six children so that each child receives at least one but no more than three stuffed animals.

Short answer

There are then 50 ways to give 15 stuffed animals to each of six children.

Step-by-step solution

Use Generating Function:

Generating function for the sequence\({a_0},{a_1}, \ldots ,{a_k}, \ldots \)of real numbers is the infinite series;

\(G(x) = {a_0} + {a_1}x + {a_2}{x^2} + \ldots + {a_k}{x^k} + \ldots = \sum\limits_{k = 0}^{ + \infty } {{a_k}} {x^k}\)

Extended binomial theorem:

\({(1 + x)^u} = \sum\limits_{k = 0}^{ + \infty } {\left( {\begin{array}{*{20}{l}}u\\k\end{array}} \right)} {x^k}\)

Each child receives at least 1 but at most 3 stuffed animals each, the series representing one child should then contain only terms with a power of at least 1 and at most 3:

\(x + {x^2} + {x^3}\)

There are six children is given by:

\(\begin{array}{c}{\left( {x + {x^2} + {x^3}} \right)^6} = {x^9}{\left( {1 + x + {x^2}} \right)^6}\\ = {x^6} \cdot {\left( {\sum\limits_{k = 0}^2 {{x^k}} } \right)^6}\\ = {x^6} \cdot {\left( {\frac{{1 - {x^3}}}{{1 - x}}} \right)^6}\\ = {x^6} \cdot \frac{{{{\left( {1 - {x^3}} \right)}^6}}}{{{{(1 - x)}^6}}}\\ = {x^6} \cdot {\left( {1 + \left( { - {x^3}} \right)} \right)^6} \cdot {(1 + ( - x))^{ - 6}}\end{array}\)

By further simplification:

\(\begin{array}{l} = {x^6} \cdot \sum\limits_{m = 0}^{ + \infty } {\left( {\begin{array}{*{20}{c}}6\\m\end{array}} \right)} {\left( { - {x^3}} \right)^m} \cdot \sum\limits_{k = 0}^{ + \infty } {\left( {\begin{array}{*{20}{c}}{ - 6}\\k\end{array}} \right)} {( - x)^k}\\ = {x^6} \cdot \sum\limits_{m = 0}^{ + \infty } {\left( {\begin{array}{*{20}{c}}6\\m\end{array}} \right)} {( - 1)^m}{x^{3m}} \cdot \sum\limits_{k = 0}^{ + \infty } {\left( {\begin{array}{*{20}{c}}{ - 6}\\k\end{array}} \right)} {( - 1)^k}{x^k}\\ = {x^6} \cdot \sum\limits_{m = 0}^{ + \infty } {{b_m}} {x^{3m}} \cdot \sum\limits_{k = 0}^{ + \infty } {{c_k}} {x^k}\end{array}\)

Let \({b_m} = \left( {\begin{array}{*{20}{c}}6\\m\end{array}} \right){( - 1)^m}\) and \({c_k} = \left( {\begin{array}{*{20}{c}}{ - 6}\\k\end{array}} \right){( - 1)^k}\)

The coefficient of \({x^{15}}\) which is obtained if \(6 + 3m + k = 15\). 

Since \(m\) and \(k\) are nonnegative:

\(\begin{array}{*{20}{r}}{m = 0,k = 9}\\{{\rm{ or }}m = 1,k = 6}\\{{\rm{ or }}m = 2,k = 3}\\{{\rm{ or }}m = 3,k = 0}\end{array}\)

The coefficient of \({x^{15}}\) is then the sum of the coefficients for each possible combination of \(m\) and\(k\):

\(\begin{array}{c}{a_{15}} = {b_0}{c_9} + {b_1}{c_6} + {b_2}{c_3} + {b_3}{c_0}\\ = \left( {\begin{array}{*{20}{l}}6\\0\end{array}} \right){( - 1)^0}\left( {\begin{array}{*{20}{c}}{ - 6}\\9\end{array}} \right){( - 1)^9} + \left( {\begin{array}{*{20}{l}}6\\1\end{array}} \right){( - 1)^1}\left( {\begin{array}{*{20}{c}}{ - 6}\\6\end{array}} \right){( - 1)^6}\\ + \left( {\begin{array}{*{20}{l}}6\\2\end{array}} \right){( - 1)^2}\left( {\begin{array}{*{20}{c}}{ - 6}\\3\end{array}} \right){( - 1)^3} + \left( {\begin{array}{*{20}{l}}6\\3\end{array}} \right){( - 1)^3}\left( {\begin{array}{*{20}{c}}{ - 6}\\0\end{array}} \right){( - 1)^0}\\ = 2002 - 2772 + 840 - 20\\ = 50\end{array}\)

Thus, there are then 50 ways to give 15 stuffed animals to each of six children such that each child receives at least 1 and at most 3 stuffed animals.