3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.