Using generating function to find number of ways to distribute $r$ objects

Question

Use generating function to find the number of ways to distribute $r$ beans among $8$ children if each child gets an even number of beans.

So I know this is like a weak composition where some children can receive $0$ objects. But I don't know how to account for the even requirement. My guess for the generating function is $$ (1 + x^2 + x^4 + \ldots + x^{r-2} + x^r)^8. $$ But even still, I'm not sure how to determine the possible number of ways to distribute.

Answer 1

You’re doing fine so far; you just haven’t gone far enough. First, while it’s true that you’re not interested in any of the terms $z^n$ with $n>r$, it’s easier to include them and look at $\left(\sum_{k\ge 0}z^{2k}\right)^8$, because then you can replace the infinite series by a simple generating function to get

$$\frac1{\left(1-z^2\right)^8}\;,$$

from which you want the coefficient of $z^r$. Note that this does no harm: the extra terms in the infinite series cannot contribute to the $z^r$ term anyway.

A useful generating function to know is

$$\frac1{(1-z)^{n+1}}=\sum_{k\ge 0}\binom{n+k}kz^k=\sum_{k\ge 0}\binom{n+k}nz^k\;.$$

Substitute $z^2$ for $z$ and take $n=7$, and you get

$$\frac1{\left(1-z^2\right)^8}=\sum_{k\ge 0}\binom{k+7}7z^{2k}\;.$$

In particular, the coefficient of $z^r$ is clearly $0$ if $r$ is odd, and if $r$ is even it’s $\dbinom{7+\frac{r}2}7$.

Answer 2

Your generating function is given by:

• The number of ways one child can get an even number of items is $1 + z^2 + z^4 + \ldots = (1 - z^2)^{-1}$
• For 8 children it is then $(1 - z^2)^{-8}$

The result you are looking for is the coefficient of $z^r$: $$ [x^r] (1 - z^2)^{-8} = \begin{cases} (-1)^{r / 2} \binom{-8}{r / 2} = \binom{r / 2 + 7}{7} & \text{if \(r\) is even} \\ 0 & \text{if \(r\) is odd} \end{cases} $$