# Generating function problem, and distributing candy to kids.

Here is the problem: Determine how many ways I can distribute $$80$$ candies to $$3$$ kids, such that:

$$\bullet$$ The first kid receives an arbitrary number of candies (possibly $$0$$).

$$\bullet$$ The second kid receives an even positive number of candies.

$$\bullet$$ The third kid receives $$0$$, $$2$$, or $$5$$ candies.

$$\bullet$$ Every candy is distributed.

Okay, so since this is a generating function problem... or at least I think so, I do all my generating function stuff and get to where I have $$\frac{2x + 2x^3 + 2x^6}{-x^3 + 3x^2 - 3x + 1}$$. How can I find the $$x^{80}$$ coefficient from here? Hints would be appreciated!

Thanks,

Max0815

## 1 Answer

If the option to receive $$k$$ candies is worth $$x^k$$ the options of the first child sum to $$1+x+x^2+\ldots$$, the options of the second child sum to $$x^2+x^4+x^6+\ldots$$, and the options of the third child sum to $$1+x^2+x^5$$. In such a situation the function $$f(x)=(1+x+x^2+\ldots)(x^2+x^4+x^6+\ldots)(1+x^2+x^5)$$ (your $$f$$ looks different to me) is the generating function for this problem: Multiplying the RHS distributively produces for each legal allocation of $$n_1+n_2+n_3=:n$$ candies a term $$x^{n_1}\cdot x^{n_2}\cdot x^{n_3}=x^n$$. It follows that the number of legal allocations of $$80$$ candies to the three children is equal to the coefficient of $$x^{80}$$ in $$f(x)$$, when terms have been collected. A partial fraction decomposition (produced for me by Mathematica) gives \eqalign{f(x)&={x^2(1+x^2+x^5)\over(1-x)(1-x^2)}\cr &=4+3x+2x^2+x^3+x^4-{23\over4}{1\over1-x}+{3\over2}{1\over(1-x)^2}+{1\over4}{1\over 1+x}\ .\cr} Since $${1\over(1-x)^2}=\sum_{k=0}^\infty(k+1)x^k$$ the coefficient we are after is given by $$[x^{80}]=-{23\over4}+{3\over2}\cdot81+{1\over4}(-1)^{80}=116\ .$$

• Thank you for your help :P – Max0815 Sep 21 '18 at 17:14
• it took me some time to understand, but i eventually got it. Thanks. Max0815 – Max0815 Sep 21 '18 at 17:15