# Determining the number of solutions using Generating functions

I have the equation

$u_1 + u_2 + ... + u_5 = 24$

with the restrictions

$1 \le u_i \le 7, i = 1,...5$

I've managed to work up to the point of finding the coefficient of $x^{24}$ in

$(X+X^2+...X^7)^5 = X^5(1+X+...X^6)^5$

I know my final answer will need to be in binomial form similar to this $\binom{10}{5}$

However I am unsure where to go, or if this is even correct. Any help would be greatly appreciated.

• Does it help (simplify the calculation, I mean) to write the GF as $X^5 \frac{(1-X^7)^{5}}{(1-X)^{5}}$ ? – ancientmathematician May 1 '17 at 9:35
• @ancientmathematician I believe so! Would that correctly equate to $g(X)\sum_{i=0}^\infty \binom{5 + i -1}{i} X^i$? – Arnaud Van Wyk May 1 '17 at 10:14
• Yes - the infinite sum is the binomial expansion of $(1-X)^{-5}$ so you have $g(X)=X^5(1-X^7)^5$. To find the coefficient of $X^{24}$ you will have to add three terms from this series. – gandalf61 May 1 '17 at 10:28
• @gandalf61I'm very sorry, but I'm not entirely sure what you mean by this? Is this correct - $g(X) = 1 - 5X^7 + 10X^{14} - 10X^{21} + 5X^{28} - X^{35}$? Or have I made a mistake? – Arnaud Van Wyk May 1 '17 at 10:33
• You're right but doing unnecessary work! To get 19 the only possibilities are (i) 0 from $g(X)$ and 19 from the $(1-X)^{-5}$; (ii) 7 from $g(X)$ and 12 from the $(1-X)^{-5}$ (iii) 14 from $g(X)$ and 5 from the $(1-X)^{-5}$. There's no need to work out any other term. – ancientmathematician May 1 '17 at 12:14

Everything is fine with your generating function. It is convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ in a series.

We obtain \begin{align*} [x^{24}]&(x+x^2+\cdots+x^7)^5\\ &=[x^{24}]x^5(1+x+\cdots+x^6)^5\\ &=[x^{19}]\left(\frac{1-x^{7}}{1-x}\right)^5\tag{1}\\ &=[x^{19}](1-x^7)^5\cdot\frac{1}{(1-x)^5}\\ &=[x^{19}](1-5x^{7}+10x^{14})\sum_{n=0}^\infty\binom{-5}{n}(-x)^n\tag{2}\\ &=\left([x^{19}]-5[x^{12}]+10[x^5]\right)\sum_{n=0}^\infty\binom{n+4}{4}x^n\tag{3}\\ &=\binom{23}{4}-5\binom{16}{4}+10\binom{9}{4}\tag{4}\\ &=1015 \end{align*}

Comment:

• In (1) we use the geometric series formula and apply the rule \begin{align*} [x^{p-q}]A(x)=[x^p]x^qA(x) \end{align*}

• In (2) we use the binomial series expansion and expand $(1-x^7)^5$. We skip terms with exponent $21$ and greater since they do not contribute to $[x^{19}]$.

• In (3) we use the linearity of the coefficient of operator, apply again the rule as in (1) and we use the binomial identity $$\binom{-p}{q}=\binom{p+q-1}{p-1}(-1)^q$$

• In (4) we select the coefficients accordingly.

• This was an incredible help! Thank you! – Arnaud Van Wyk May 2 '17 at 2:27
• @ArnaudVanWyk: You're welcome! Good to see the answer is useful. :-) – Markus Scheuer May 2 '17 at 6:32