3
$\begingroup$

I will be very happy to understand how to solve this problem with generating function: How many solutions are there to the equation $$x_1 + x_2 + x_3 + x_4 + x_5 = 31$$ where $x_i$ is a nonnegative integer, and $x_2$ is even and $x_3$ is odd?

thanks!

$\endgroup$
2
$\begingroup$

Non-negative $x_1$ corresponds to $\frac{z}{1 - z}$, $x_2$ even gives rise to $\frac{1}{1 - z^2}$, odd $x_3$ means $\frac{z}{1 - z^2}$, non-restriced $x_4$, $x_5$ are $\frac{1}{1 - z}$ each: \begin{align} [z^{31}] &\frac{z}{1 - z} \cdot \frac{1}{1 - z^2} \cdot \frac{z}{1 - z^2} \cdot \frac{1}{(1 - z)^2} \\ &= [z^{31}] \frac{z^2}{(1 - z)^3 (1 - z^2)^2} \\ &= [z^{29}] \left( \frac{5}{64 (1 + z)} + \frac{1}{32 (1 + z)^2} + \frac{5}{64 (1 - z)} + \frac{1}{8 (1 - z)^2} + \frac{3}{16 (1 - z)^3} + \frac{1}{4 (1 - z)^4} + \frac{1}{4 (1 - z)^5} \right) \end{align} Use the fact that $\binom{-n}{k} = (-1)^k \binom{k + n - 1}{n - 1}$: \begin{align} [z^{31}] &\frac{z^2}{1 - z} \cdot \frac{1}{1 - z^2} \cdot \frac{z}{1 - z^2} \cdot \frac{1}{(1 - z)^2} \\ &= \frac{5}{64} \binom{-1}{29} + \frac{1}{32} \binom{-2}{29} + \frac{5}{64} \binom{-1}{29} (-1)^{29} + \frac{1}{8} \binom{-2}{29} (-1)^{29} + \frac{3}{16} \binom{-3}{29} (-1)^{29} + \frac{1}{4} \binom{-4}{29} (-1)^{29} + \frac{1}{4} \binom{-5}{29} (-1)^{29} \\ &= 11560 \end{align}

$\endgroup$
  • $\begingroup$ thank you very much :) but one thing I don't understand.. why x1 is diffrent from x4 and x5? they all have the same conditions $\endgroup$ – sapir Apr 19 '14 at 22:15
  • $\begingroup$ @sapir, sorry. It seems I misread the condition on $x_i$ as a condition on $x_1$. I solved it assuming $x_1 \ge 1$, $x_4, x_5 \ge 0$. $\endgroup$ – vonbrand Apr 19 '14 at 22:53
1
$\begingroup$

The generating function is $(1/(1-x))^3 \times 1/(1-x^2) \times x/(1-x^2)$. (Why?) The coefficient of $x^{31}$ in the series expansion gives you your answer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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