Problem solving a word problem using a generating function

Question

How many ways are there to hand out 24 cookies to 3 children so that they each get an even number, and they each get at least 2 and no more than 10? Use generating functions.

So the first couple steps are easy.

The coefficient is $x^{24}$

$g(x) = x^6(1+x^2+x^4+x^6+x^8)^3$ or what I got was $x^6 (1 + (x^2)^1 +...+ (x^2)^4)^3$

now finding the closed formula is where I am having problems

My answer: using the fact that $\dfrac{1-x^{n+1}}{1- x}$

I get $x^6\left(\dfrac{1-x^9}{1-x}\right)$ which is wrong

The correct answer: $x^6\left(\dfrac{1-x^{10}}{1-x^2}\right)$

If someone could explain in some detail on how to get the correct formula would be much appreciated. Thanks!

Answer 1

When computing $1+x^2+(x^2)^2+(x^2)^3+(x^2)^4$, the series is in powers of $x^2$ not $x$. So the proper expression is $$1+x^2+(x^2)^2+(x^2)^3+(x^2)^4=\frac{1-(x^2)^5}{1-(x^2)}=\frac{1-x^{10}}{1-x^2}.$$ By contrast, $$\frac{1-x^{9}}{1-x}=1+x^1+x^2+\cdots +x^8$$ which differs from the above series in it has both odd and even powers of $x$.

Answer 2

Here is variation of the theme which might be helpful when doing the calculation. It's convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series.

We obtain \begin{align*} [x^{24}]&(x^2+x^4+x^6+x^8+x^{10})^3\tag{1}\\ &=[x^{24}]x^6(1+x^2+x^4+x^6+x^8)^3\\ &=[x^{18}]\left(\frac{1-x^{10}}{1-x^2}\right)^3\tag{2}\\ &=[x^{18}](1-x^{10})^{3}\sum_{n=0}^\infty\binom{-3}{n}(-x^2)^n\tag{3}\\ &=[x^{18}](1-3x^{10})\sum_{n=0}^\infty\binom{n+2}{2}x^{2n}\tag{4}\\ &=\left([x^{18}]-3[x^8]\right)\sum_{n=0}^\infty\binom{n+2}{2}x^{2n}\tag{5}\\ &=\binom{11}{2}-3\binom{6}{2}\tag{6}\\ &=10 \end{align*}

Comment:

• In (1) we respect that an even number of at least $2$ and at most $10$ cookies is to distribute to three children. The coefficient of operator selects the coefficient of $x^{24}$ which gives the wanted number.

• In (2) we use the rule \begin{align*} [x^{p+q}]A(x)=[x^p]x^{-q}A(x) \end{align*} and apply the finite geometric series with argument $x^2$.

• In (3) we use the binomial series expansion for $\frac{1}{(1-x^2)^3}$

• In (4) we expand $(1-x^{10})^3$ and take the first two terms only since all other therms have powers greater than $18$. We also use the binomial identity \begin{align*} \binom{-p}{q}=\binom{p+q-1}{p-1}(-1)^q \end{align*}

• In (5) we use the linearity of the coefficient of operator and apply the rule stated in the comment of (2).

• In (6) we select the coefficients of $x^{18}$ and $x^{8}$ by taking $n=9$ and $n=4$.

Answer 3

Your expression $g(x) = x^6 (1+x^2+\cdots+x^8)^3$ is correct, but the geometric series formula needs to be used correctly. Recall the geometric series formula for the sum of 5 terms: $a+ar+\cdots+ar^4 = \frac{a(1-r^5)}{1-r}$. In our case, $r=x^2$ and $a=1$. So $1+x^2+\cdots+x^8$ simplifies to $\frac{1-(x^2)^5}{1-x^2} = \frac{ 1-x^{10}}{1-x^2}$.

Hence, the number of ways in question is the coefficient of $x^{24}$ in $x^6 \left(\frac{1-x^{10}}{1-x^2} \right)^3$. Notice some differences with your answer: the denominator has $x^2$ (not $x$) since the common ratio of the geometric series is $x^2$; the geometric series formula with $n$ terms has an $n$ (not $n+1$) in the exponent. Also, don't forget to take the third power.