Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

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

share|improve this answer
add comment

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} $$

share|improve this answer
    
@BrianM.Scott, you are right. I can only plead too little coffee. Fixed, many thanks. –  vonbrand Feb 25 '13 at 9:58
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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