Question

Use generating functions to determine the number of different ways 12 identical action figures can be given to five children so that each child receives at most three action figures.

Short answer

There are then 35 ways to give 12 action figures to each of the four 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 most 3 action figures each, the series representing one child should then contain only terms with a power of at most 3:

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

There are five children is given by:

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

By further simplification:

\(\begin{array}{} &= \sum\limits_{m = 0}^{ + \infty } {\left( {\begin{array}{{}{}}5\\m\end{array}} \right)} {\left( { - {x^4}} \right)^m} \cdot \sum\limits_{k = 0}^{ + \infty } {\left( {\begin{array}{{}{}}{ - 5}\\k\end{array}} \right)} {( - x)^k}\\ &= \sum\limits_{m = 0}^{ + \infty } {\left( {\begin{array}{{}{}}5\\m\end{array}} \right)} {( - 1)^m}{x^{4m}} \cdot \sum\limits_{k = 0}^{ + \infty } {\left( {\begin{array}{{}{}}{ - 5}\\k\end{array}} \right)} {( - 1)^k}{x^k}\;\;\;\;\;\\ &= \sum\limits_{m = 0}^{ + \infty } {{b_m}} {x^{4m}} \cdot \sum\limits_{k = 0}^{ + \infty } {{c_k}} {x^k}\end{array}\)

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

The coefficient of \({x^{12}}\) which is obtained if \(4m + k = 12\)

Since \(m\) and \(k\) are non-negative:

\(\begin{array}{c}m = 0,k = 12{\rm{ }}\\{\rm{or }}m = 1,k = 8{\rm{ }}\\{\rm{or }}m = 2,k = 4{\rm{ }}\\{\rm{or }}m = 3,k = 0\end{array}\)

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

\(\begin{aligned}{}{a_{12}} = {b_0}{c_{12}} + {b_1}{c_8} + {b_2}{c_4} + {b_3}{c_0}\\ = \left( {\begin{aligned}{{}{}}5\\0\end{aligned}} \right){( - 1)^0}\left( {\begin{aligned}{{}{}}{ - 5}\\{12}\end{aligned}} \right){( - 1)^{12}} + \left( {\begin{aligned}{{}{}}5\\1\end{aligned}} \right){( - 1)^1}\left( {\begin{aligned}{{}{}}{ - 5}\\8\end{aligned}} \right){( - 1)^8}\\ + \left( {\begin{aligned}{{}{}}5\\2\end{aligned}} \right){( - 1)^2}\left( {\begin{aligned}{{}{}}{ - 5}\\4\end{aligned}} \right){( - 1)^4} + \left( {\begin{aligned}{{}{}}5\\3\end{aligned}} \right){( - 1)^1}\left( {\begin{aligned}{{}{}}{ - 5}\\0\end{aligned}} \right){( - 1)^0}\\ = 1820 - 2475 + 700 - 10\\ = 35\end{aligned}\)

Thus, there are then 35 ways to give 12 action figures to each of four children such that each child receives at most 3 action figures.