Find the number of ways to distribute 10 pieces of candy using this generating function

Question

The question asks:

a) Find a generating function for the number of ways to distribute identical pieces of candy to 3 children so that no child gets more than 4 pieces. Write this generating function in closed form, as a quotient of polynomials. b) Find the number of ways to distribute 10 pieces of candy using this generating function.

I figured out for part a that $(1 + x + x^2 + x^3 + x^4)^3$ is represented as the generating function: $$f(x) = \left( \frac{1-x^5}{1-x} \right) ^3$$ But I don't know how to find the $a_{10}$ term. Please help.

Answer 1

Denoting with $[x^n]$ the coefficient of $x^n$ of a series we obtain \begin{align*} \color{blue}{a_{10}}&\color{blue}{=[x^{10}]\left( \frac{1-x^5}{1-x} \right)^3}\\ &=[x^{10}]\frac{1-3x^5+3x^{10}-x^{15}}{(1-x)^3}\tag{1}\\ &=[x^{10}]\left(1-3x^5+3x^{10}\right)\sum_{j=0}^\infty \binom{-3}{j}(-x)^j\tag{2}\\ &=\left([x^{10}]-3[x^5]+3[x^0]\right)\sum_{j=0}^\infty \binom{j+2}{2}x^j\tag{3}\\ &=\binom{12}{2}-3\binom{7}{2}+3\binom{2}{2}\tag{4}\\ &=66-3\cdot 21+3\\ &\,\,\color{blue}{=6} \end{align*}

Comment:

• In (1) we expand the numerator.

• In (2) we skip the terms of the numerator which do not contribute to $[x^{10}]$ and apply the binomial series expansion.

• In (3) we apply the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$ and use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{p-1}(-1)^q$.

• In (4) we select the coefficients accordingly.

Answer 2

You need to manipulate first term of $(1-x^5)^3 (1-x)^{-3}$ in such way that would allow you to find the coefficients. The coefficients up to $x^{10}$, i.e. $a_{10}$, will reveal you the different ways you may distribute.

Hint: Binomial theorem.

Answer 3

To solve this problem, we can use the technique of generating functions. We can represent the problem as finding the coefficient of $x^{10}$ in the expansion of the following generating function: $$ (1 + x + x^2 + x^3 + x^4)^3 $$ Each term in the expansion of this generating function represents a way of distributing the candies to the three children such that no child gets more than 4 pieces. The coefficient of $x^{10}$ represents the number of ways to distribute 10 identical pieces of candy to 3 children.

We can expand the generating function using the binomial theorem as follows: $$ (1 + x + x^2 + x^3 + x^4)^3 = (1 - x^5)^3 / (1 - x)^3 $$ We can then use the binomial theorem again to expand the numerator: $$ (1 - x^5)^3 = 1 - 3x^5 + 3x^{10} - x^{15} $$ Substituting this expansion into the original expression, we get: $$ (1 + x + x^2 + x^3 + x^4)^3 = (1 - 3x^5 + 3x^{10} - x^{15}) / (1 - x)^3 $$ The coefficient of $x^{10}$ in this expression is 3, so there are 3 ways to distribute 10 identical pieces of candy to 3 children so that no child gets more than 4 pieces.