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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How many ways are there to hand out 24 cookies to 3 children so that they each get an even number, and they each get at least 2 and no more than 10? Use generating functions.

So the first couple steps are easy.

The coefficient is $x^{24}$

$g(x) = x^6(1+x^2+x^4+x^6+x^8)^3$ or what I got was $x^6 (1 + (x^2)^1 +...+ (x^2)^4)^3$

now finding the closed formula is where I am having problems

My answer: using the fact that $\dfrac{1-x^{n+1}}{1- x}$

I get $x^6\left(\dfrac{1-x^9}{1-x}\right)$ which is wrong

The correct answer: $x^6\left(\dfrac{1-x^{10}}{1-x^2}\right)$

If someone could explain in some detail on how to get the correct formula would be much appreciated. Thanks!

share|cite|improve this question
up vote 5 down vote accepted

When computing $1+x^2+(x^2)^2+(x^2)^3+(x^2)^4$, the series is in powers of $x^2$ not $x$. So the proper expression is $$1+x^2+(x^2)^2+(x^2)^3+(x^2)^4=\frac{1-(x^2)^5}{1-(x^2)}=\frac{1-x^{10}}{1-x^2}.$$ By contrast, $$\frac{1-x^{9}}{1-x}=1+x^1+x^2+\cdots +x^8$$ which differs from the above series in it has both odd and even powers of $x$.

share|cite|improve this answer
    
thanks i got it now – Rishi Dholliwar yesterday

Here is variation of the theme which might be helpful when doing the calculation. It's convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series.

We obtain \begin{align*} [x^{24}]&(x^2+x^4+x^6+x^8+x^{10})^3\tag{1}\\ &=[x^{24}]x^6(1+x^2+x^4+x^6+x^8)^3\\ &=[x^{18}]\left(\frac{1-x^{10}}{1-x^2}\right)^3\tag{2}\\ &=[x^{18}](1-x^{10})^{3}\sum_{n=0}^\infty\binom{-3}{n}(-x^2)^n\tag{3}\\ &=[x^{18}](1-3x^{10})\sum_{n=0}^\infty\binom{n+2}{2}x^{2n}\tag{4}\\ &=\left([x^{18}]-3[x^8]\right)\sum_{n=0}^\infty\binom{n+2}{2}x^{2n}\tag{5}\\ &=\binom{11}{2}-3\binom{6}{2}\tag{6}\\ &=10 \end{align*}

Comment:

  • In (1) we respect that an even number of at least $2$ and at most $10$ cookies is to distribute to three children. The coefficient of operator selects the coefficient of $x^{24}$ which gives the wanted number.

  • In (2) we use the rule \begin{align*} [x^{p+q}]A(x)=[x^p]x^{-q}A(x) \end{align*} and apply the finite geometric series with argument $x^2$.

  • In (3) we use the binomial series expansion for $\frac{1}{(1-x^2)^3}$

  • In (4) we expand $(1-x^{10})^3$ and take the first two terms only since all other therms have powers greater than $18$. We also use the binomial identity \begin{align*} \binom{-p}{q}=\binom{p+q-1}{p-1}(-1)^q \end{align*}

  • In (5) we use the linearity of the coefficient of operator and apply the rule stated in the comment of (2).

  • In (6) we select the coefficients of $x^{18}$ and $x^{8}$ by taking $n=9$ and $n=4$.

share|cite|improve this answer

Your expression $g(x) = x^6 (1+x^2+\cdots+x^8)^3$ is correct, but the geometric series formula needs to be used correctly. Recall the geometric series formula for the sum of 5 terms: $a+ar+\cdots+ar^4 = \frac{a(1-r^5)}{1-r}$. In our case, $r=x^2$ and $a=1$. So $1+x^2+\cdots+x^8$ simplifies to $\frac{1-(x^2)^5}{1-x^2} = \frac{ 1-x^{10}}{1-x^2}$.

Hence, the number of ways in question is the coefficient of $x^{24}$ in $x^6 \left(\frac{1-x^{10}}{1-x^2} \right)^3$. Notice some differences with your answer: the denominator has $x^2$ (not $x$) since the common ratio of the geometric series is $x^2$; the geometric series formula with $n$ terms has an $n$ (not $n+1$) in the exponent. Also, don't forget to take the third power.

share|cite|improve this answer

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.