Determine the number of ways $12$ identical action figures can be given to $5$ children so that each child receives at most $3$ action figures

Question

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

So far I have come up with the generating function of: $$(1 + x + x^2 + x^3)^5$$ To correspond to each child having either $0, 1, 2, $ or $3$ action figures with each child representing a factor. But, I am confused as to how to expand this. Any help is appreciated, thanks!

Answer 1

You're correct in forming the generating function

$$ F = (1 + x + x^2 + x^3)^5 $$

Now, you're looking for the coefficient of $x^{12}$ (Since each $x$ represents a figure, you want 12 of them. The coeffieint will tell you the number of ways $G$ produced the $12$ - which to us gives the number of ways to distribute $12$)

However, expanding it out makes us lose the advantage of using generating functions in the first place. Rather, we can notice that

$$ 1 + x + x^2 + x^3$$ is a geometric series starting from the term $1$, with common ratio $x$, and 4 total terms.

The formula for any geometric series with $n$ terms that has starting term $a$ and common difference $r$ is

$$ G = a + ar + ar^2 + \ldots + ar^n = a\times \frac{r^n - 1}{r - 1} $$

Hence, for us,

$$ a = 1 \\r = x \\ n = 3 $$

Hence,

$$F = \left (1 \times \frac{x^4 - 1}{x - 1}\right)^5 = \left (\frac{x^4 - 1}{x - 1}\right)^5 $$

Simplify $F$ using the binomal theorem and take the coefficient of $x^{12}$ to arrive at the answer

Answer 2

Enough has been said about the generating function approach in other comments and answers. Perhaps it's also worth mentioning that generating functions can easily be expanded using Wolfram|Alpha.

But in the present case generating functions are overkill. The most efficient solution to the problem is to note that you're looking for the number of ways of distributing $5\cdot3-12=3$ gaps among $5$ children without restrictions. This is $\binom{3+5-1}{5-1}=35$.

Answer 3

It is convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series.

We obtain \begin{align*} [x^{12}]&(1+x+x^2+x^3)^5\\ &=[x^{12}]\left(\frac{1-x^4}{1-x}\right)^5\tag{1}\\ &=[x^{12}]\left(\sum_{k=0}^{5}\binom{5}{k}(-1)^kx^{4k}\right)\left(\sum_{n=0}^\infty\binom{-5}{n}(-x)^n\right)\tag{2}\\ &=\left(\binom{5}{0}[x^{12}]-\binom{5}{1}[x^8]+\binom{5}{2}[x^4]-\binom{5}{3}[x^0]\right) \sum_{n=0}^\infty\binom{n+4}{4}x^n\tag{3}\\ &=\binom{5}{0}\binom{16}{4}-\binom{5}{1}\binom{12}{4}+\binom{5}{2}\binom{8}{4}-\binom{5}{3}\binom{4}{4}\tag{4}\\ &=1\cdot 1820-5\cdot 495+10\cdot 70-10\cdot 1\\ &=35 \end{align*}

Comment:

• In (1) we use the formula for the finite geometric series

• In (2) we use the binomial series expansion for the denominator

• In (3) we use the linearity of the coefficient of operator and the rule $[x^{p-q}]A(x)=[x^{p}]x^{q}A(x)$. Note that we only need to respect $4$ of the $6$ summands of the series, since terms with exponents greater than $12$ do not contribute. We also use in the right series the binomial identity \begin{align*} \binom{-p}{q}=\binom{p+q-1}{p-1}(-1)^q \end{align*}

• In (4) we select the coefficients from the right series accordingly to the coefficient of operator