2
$\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$
1
  • $\begingroup$ to whoever randomly downvoted this 4 year old question i just have to say lmao cope h arder $\endgroup$
    – Max0815
    Mar 10, 2023 at 2:44

1 Answer 1

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$
2
  • $\begingroup$ Thank you for your help :P $\endgroup$
    – Max0815
    Sep 21, 2018 at 17:14
  • $\begingroup$ it took me some time to understand, but i eventually got it. Thanks. Max0815 $\endgroup$
    – Max0815
    Sep 21, 2018 at 17:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .