Using generating functions in combinatorics I know these questions get asked a lot but I cannot figure it out. It requires the use of generating functions to find the number of solutions (coefficient) to the equation:
$u_i+u_2+u_3+u_4 = 20$, where $1 \leq u_i \leq 5, i = 1,...,4$
How do I solve this question step-by-step?
Thanks.
 A: I will take the case of equation $u_1+u_2+u_3+u_4+u_5=20$ because it provides a more interesting challenge.
The main idea is to transfer this issue into an issue about exponents, namely:
$$\tag{1}\underbrace{(x^1+x^2+x^3+x^4+x^5) \times (x^1+x^2+x^3+x^4+x^5) \times 
 \cdots }_{5 \ \text{factors}}=$$
$$\tag{2}(x+x^2+x^3+x^4+x^5)^5$$
It suffices now to expand (2) (using a CAS = Computer Algebra System) 
$$\tag{3}x^5+5x^6+15x^7+\cdots+121x^{20}+\cdots+15x^{23}+5x^{24}+x^{25}.$$
and collect the coefficient of $x^{20}$... 
Why that ? Because the number of times one obtains $x^{20}$ is the number of times, by picking, in relationship (1), a certain $x^{u_1}$ inside the first parenthesis, a certain $x^{u_2}$ in the second parenthesis, etc. In this way, one gets a $x^{u_1+u_2+...}$ and we are interested in those that sum up to $20$...
Remark: In each factor of (1), the range of exponents, i.e., $\{1,2,3,4,5\}$ corresponds to the domain constraints: $ \ 1 \leq u_i \leq 5$.
A: 
The constraint $1\leq u_i \leq 5$ can be encoded using the finite geometric series formula as
  \begin{align*}
z^1+z^2+z^3+z^4+z^5=\frac{z\left(1-z^5\right)}{1-z}\tag{1}
\end{align*}
Since (1) holds for each $u_i, 1\leq i\leq 4$ all possible configurations can be encoded as
  \begin{align*}
\left(\frac{z\left(1-z^5\right)}{1-z}\right)^4\tag{2}
\end{align*}

We want to find the number of non-negative integer solutions of
\begin{align*}
u_1+u_2+u_3+u_4=20
\end{align*}
with the constraints given above.

In the following we denote with $[z^n]$ the coefficient of $z^n$. According to (2) we are looking for 
  \begin{align*}
[z^{20}]&z^4\frac{\left(1-z^5\right)^4}{(1-z)^4}\tag{3}\\
&=[z^{16}]\frac{\left(1-z^5\right)^4}{(1-z)^4}\tag{4}\\
&=[z^{16}]\left(1-4z^5+6z^{10}-4z^{15}\right)\sum_{k=0}^\infty\binom{-4}{k}(-z)^k\tag{5}\\
&=\left([z^{16}]-4[z^{11}]+6[z^{6}]-4[z]\right)\sum_{k=0}^\infty\binom{k+3}{3}z^k\tag{6}\\
&=\binom{19}{3}-4\binom{14}{3}+6\binom{9}{3}-4\binom{4}{3}\tag{7}\\
&=969-4\cdot364+6\cdot84-4\cdot 4\\
&=1
\end{align*}
in accordance with the obvious single solution $u_1=u_2=u_3=u_4=5$.

Comment:


*

*In (3) we select the coefficient of $[z^{20}]$ of the product of the generating function (2) which correspond to the valid ranges specified for $u_i$ with   $1\leq i \leq 4$.

*In (4) we apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.

*In (5) we multiply out the numerator and skip terms with powers greater than $16$ since they do not contribute to $[z^{16}]$. We also apply the binomial series expansion.

*In (6) we use the linearity of the coefficient of operator, apply the same rule as in (4) four times and use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{p-1}(-1)^q$.

*In (7) we select the coefficients accordingly.
