0

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.

I'm not exactly sure how to proceed, because I'm fairly new to generating function. I know that the maximum degree of the generating function I need to make is $80$. I think the generating function for the first function is $1+x+x^2+x^3+x^4+\cdots +x^{80}$. The generating function for the second kid is $1+x^2+x^4+x^6+x^8+\cdots+x^{80}$. The generating function for the third kid is $1+x^2+x^5$. What should I do from here?

A Piercing Arrow
  • 953
  • 2
    Please edit your question to show what you have attempted. Have you written generating functions for each child? Where are you stuck? – N. F. Taussig Sep 16 '18 at 21:43

1 Answers1

1

When you multiply three power series $\sum_l a_l x^l$, $\sum_m b_m x^m$, $\sum_n c_n x^n$, the coefficient of $x^{80}$ is $$\sum_{l+m+n = 80} a_l b_m c_n, \tag{$*$}$$ where the sum is over all triples $(l, m, n)$ that add up to $80$.

Can you find a way to define the $a_0, a_1, \ldots$, $b_0, b_1, \ldots$, and $c_0, c_1, \ldots$ so that this sum ($*$) counts the number of ways you can distribute the candies?

Hint: You can think of $l$ as the number of candies the first child gets, $m$ as the number the second child gets, and so on. If $a_l = b_m = c_n = 1$ for all $l,m,n$, then the above sum ($*$) would equal the number of ways you can distribute 80 candies among three people (without restrictions). How can you adjust the definitions of the $a_l, b_m, c_n$ to incorporate the restrictions?

Your start is good. Multiply the three polynomials and compute the coefficient of $x^{80}$. (This is like a very big version of $(a+b)(c+d) = ac + bc + ad + bd$.)

To do this, you need to find how many ways you can multiply three terms (one from each polynomial) such that the powers of $x$ combine to get $x^{80}$. For example, you can take $x^{76}$ from the first polynomial, $x^2$ from the second, and $x^2$ from the third to get one copy of $x^{80}$. See if you can systematically count all possibilities. [Note that this problem does not really require generating functions; the computations you do here can be stated simply in terms of counting outcomes of the original problem.]

angryavian
  • 89,882