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
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\ .$$