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.
On
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.
On
$\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$
$\ds{u_{1} + u_{2} + u_{3} + u_{4} = 20\quad\mbox{where}\quad 1 \leq u_{i} \leq 5\,,\ i = 1,\ldots,4}$.
How do I solve this question $\ds{\underline{\texttt{step-by-step}}}$ ?.
The "$\ds{\underline{\texttt{step-by-step}}}$" answer is given by \begin{align} \sum_{u_{1} = 1}^{5}\sum_{u_{2} = 1}^{5}\sum_{u_{3} = 1}^{5} \sum_{u_{4} = 1}^{5} \overbrace{\qquad\qquad\bracks{z^{20}}z^{u_{1} + u_{2} + u_{3} + u_{4}}\qquad\qquad} ^{\ds{\substack{% \ds{= 1}\,\,\, \mbox{if}\,\,\, u_{1} + u_{2} + u_{3} + u_{4} = 20 \\[2mm] \ds{\ds{= 0}\,\,\, \mbox{otherwise}}}}} \end{align} The multiple sum adds $\ds{1}$ each time it encounters the case $\ds{u_{1} + u_{2} + u_{3} + u_{4} = 20}$. Otherwise, it adds 'nothing' which means it adds $\ds{0}$. That makes the whole job. Then, \begin{align} &\sum_{u_{1} = 1}^{5}\sum_{u_{2} = 1}^{5}\sum_{u_{3} = 1}^{5} \sum_{u_{4} = 1}^{5}\bracks{z^{20}}z^{u_{1} + u_{2} + u_{3} + u_{4}} = \bracks{z^{20}}\sum_{u_{1} = 1}^{5}z^{u_{1}} \sum_{u_{2} = 1}^{5}z^{u_{2}}\sum_{u_{3} = 1}^{5}z^{u_{3}} \sum_{u_{4} = 1}^{5}z^{u_{4}} = \bracks{z^{20}}\pars{\sum_{u = 1}^{5}z^{u}}^{4} \\[5mm] = &\ \bracks{z^{20}}\pars{z\,{z^{5} - 1 \over z - 1}}^{4} = \bracks{z^{20}}z^{\color{red}{\large 4}}\,{\pars{1 - z^{5}}^{4} \over \pars{1 - z}^{4}} \\[5mm] = &\ \bracks{z^{20 - \color{#f00}{\large 4}}}\pars{1 - 4z^{\color{#f00}{5}} + 6z^{\color{#f00}{10}} - 4z^{\color{#f00}{15}} + z^{\color{#f00}{20}}}\pars{1 - z}^{-4} \\[5mm] = &\ \bracks{z^{16}}\pars{1 - z}^{-4} - 4\bracks{z^{16 - \color{#f00}{5}}}\pars{1 - z}^{-4} + 6\bracks{z^{16 - \color{#f00}{10}}}\pars{1 - z}^{-4} \\[2mm] - &\ 4\bracks{z^{16 - \color{#f00}{15}}}\pars{1 - z}^{-4} + \bracks{z^{16 - \color{#f00}{20}}}\pars{1 - z}^{-4} \\[4mm] = &\ {-4 \choose 16}\pars{-1}^{16} - 4{-4 \choose 11}\pars{-1}^{11} + 6{-4 \choose 6}\pars{-1}^{6} - 4{-4 \choose 1}\pars{-1}^{1} + {-4 \choose -4}\pars{-1}^{-4} \\[5mm] = & {19 \choose 3} - 4{14 \choose 11} + 6{9 \choose 6} -4{4 \choose 1} + {1 \choose -4} \\[5mm] = &\ 969 - 4 \times 364 + 6 \times 84 - 4 \times 4 + 0 = \bbx{1} \end{align}
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$.