# Not getting the required answer via generating function

What is the coefficient of $$x^{20}$$ in $$(x^0 + x^1 + ... + x^8)^6$$

Greetings! I was solving this question:

How many solutions are there to the equation $$x_1+x_2+x_3+x_4+x_5+x_6=20$$where each $$x_i$$ is an integer, $$0 \leq x_i \leq 8$$?

For solving this problem, I tried to use a generating function which led to the problem on the top.

Here's how I did it.

$$(x^0 + x^1 + ... + x^8)^6 = (1 - x^9)^6 (1-x)^{-6}$$. Hence, it suffices to find the coefficient of $$x^9$$ in the first term and $$x^{11}$$ in the second term. And to find the $$x^{18}$$ in the first term and $$x^2$$ in the second term.

I found the coefficient to be $${6 \choose 1}{-6 \choose 11} + {6 \choose 2}{-6 \choose 2}$$ which evaluated to be $$-25893$$ which is (i) negative and (ii) not the correct answer. I know I am making a silly mistake here. The correct answer is $$27237$$. Everything was found out via WolframAlpha so there should be no computational error.

Regards

EDIT: As pointed out, I just missed one term and that term made all the difference. These kind of mistakes are bad and I'll try my best to avoid these. It's amazing how small things like this lead to some pretty different answers. Thanks to everybody who helped. I really appreciate it.

• You are missing the case where the first term is a coefficient of $x^0$, and the second term is a coefficient of $x^{20}$. – Toby Mak Jul 27 at 5:06

You just missed one term! Since $$20=0\cdot 9+20=1\cdot 9+11=2\cdot 9+2$$, it should be $$[x^{20}](1 - x^9)^6 (1-x)^{-6}= \color{blue}{{6 \choose 0}{-6 \choose 20}}+{6 \choose 1}{-6 \choose 11} + {6 \choose 2}{-6 \choose 2}=27237.$$

• Thanks Robert Z! – Vasu090 Jul 27 at 5:49
• You are welcome! – Robert Z Jul 27 at 5:51

Find the coefficient of $$x^{20}$$ in $$(x^0 + x^1 + x^2 + x^3 + x^ 4 + x^5 + x^6 + x^7 + x^8)^6 = \left(x^2+x+1\right)^6 \left(x^6+x^3+1\right)^6$$

The OP missed one term...

$$27,237$$

• Thank you David. I missed the case where $20 = 0 + 20$. – Vasu090 Jul 27 at 5:50

You are basically right. Let me show the exact calculations.

You are required to find the coefficient of $$x^{20}$$ in $$(1-x^9)^6 (1-x)^{-6} = (1 - 6x^9 + 15x^{18} - \ldots)(1-x)^{-6}$$

Notice that you need to consider the first three terms of the expansion of $$(1-x^9)^6$$ since these three terms contribute to $$x^{20}$$ and these three terms are $$x^0 = 1, x^9, x^{18}$$.

So you need to compute the coefficients of the corresponding three terms of $$(1-x)^{-6}$$ viz., $$x^{20}, x^{11}, x^2$$ respectively.

Finally the coefficient is given by

$$\binom{25} {5} - 6*\binom{16} {5} + 15*\binom{7} {5} = 27237$$

• Thanks PTDS for helping! – Vasu090 Jul 27 at 5:50