Number of combinations for which $x_1+x_2+x_3=100$ if for every $3\ge i\ge 1$, $x_i$ is a non negative integer with $40\ge x_i$ I recently came across the following question:
Find the number of combinations for which $x_1+x_2+x_3=100$ if for every $3\ge i\ge 1$, $x_i$ is a non negative integer with $40\ge xi$.
I solved it in the following way, splitting it up into different instances
If $x_1=20$: 1 solution ($x_2=40, x_3=40$)
If $x_1=21$: 2 solutions
If $x_1=22$: 3 solutions
$\ldots$
If $x_1=40$: 21 solutions
As the resulting total is the addition of an arithmetic progression, we have $1+2+\ldots+21=\frac{(1+21) \cdot 21}{2}=\frac{21 \cdot 22}{2}=231$
I found this question in a chapter relating to the inclusion-exclusion principle, however I can't think of how to solve it using the inclusion exclusion principle. Could someone please show me a neat solution of this question with the use of the inclusion-exclusion principle, explaining also how he intuitively thought of going on to each step?
 A: A particular solution of the equation
$$x_1 + x_2 + x_3 = 100 \tag{1}$$
corresponds to the placement of $3 - 1 = 2$ addition signs in a row of $100$ ones.  For instance, if we place the addition signs after the $20$th and $60$th ones, we obtain the solution $x_1 = 20$, $x_2 = 40$, $x_3 = 40$ (count the number of ones to the left of the first addition sign for the value of $x_1$, between the two addition signs for the value of $x_2$, and to the right of both addition signs for the value of $x_3$).  Therefore, the number of solutions of the equation in the nonnegative integers is
$$\binom{100 + 3 - 1}{3 - 1} = \binom{102}{2}$$
since we must choose which two of the $102$ positions required for $100$ ones and two addition signs will be filled with addition signs.
From these, we must subtract those cases in which one or more of the variables exceeds $40$.
A variable exceeds $40$:  There are three ways to choose which variable exceeds $40$.  Suppose it is $x_1$.  Then $x_1' = x_1 - 41$ is a nonnegative integer.  Substituting $x_1' + 41$ for $x_1$ in equation 1 yields
\begin{align*}
x_1' + 41 + x_2 + x_3 & = 100\\
x_1 + x_2 + x_3 & = 59 \tag{2}
\end{align*}
Equation 2 is an equation in the nonnegative integers with
$$\binom{59 + 3 - 1}{3 - 1} = \binom{61}{2}$$
solutions.  Hence, there are
$$\binom{3}{1}\binom{61}{2}$$
solutions in which the value of a variable exceeds $40$.
However, if we subtract this amount from the total, we will have subtracted each case in which two variables exceed $40$ twice, once for each way of designating one of those two variables as the variable that exceeds $40$.  We only want to subtract such cases once, so we must add them to the total.
Two variables exceed $40$:  There are $\binom{3}{2}$ ways to select which two variables exceed $40$.  Suppose they are $x_1$ and $x_2$.  Then $x_1' = x_1 - 41$ and $x_2' = x_2 - 41$ are nonnegative integers.  Substituting $x_1' + 41$ for $x_1$ and $x_2' + 41$ for $x_2$ in equation 1 yields
\begin{align*}
x_1' + 41 + x_2' + 41 + x_3 & = 100\\
x_1' + x_2' + x_3 & = 18 \tag{3}
\end{align*}
Equation 3 is an equation in the nonnegative integers with
$$\binom{18 + 3 - 1}{3 - 1} = \binom{20}{2}$$
solutions.  Hence, there are
$$\binom{3}{2}\binom{20}{2}$$
solutions in which two variables exceed $40$.
Thus, by the Inclusion-Exclusion Principle, the number of solutions of equation 1 in which no variable exceeds $40$ is
$$\binom{102}{2} - \binom{3}{1}\binom{61}{2} + \binom{3}{2}\binom{20}{2} = 231$$
as you found.
A: $\newcommand{\bbx}[1]{\,\bbox[15px,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}$
By $\ds{\ \underline{definition}}$, the answer is given by:
\begin{align}
&\bbox[5px,#ffd]{\sum_{x_{1} = 1}^{40}
\sum_{x_{2} = 1}^{40}\sum_{x_{3} = 1}^{40}\
\overbrace{\bracks{z^{100}}z^{x_{1}\ +\ x_{2}\ +\ x_{3}}}
^{\ds{\delta_{x_{1}\ +\ x_{2}\ +\ x_{3}{\large ,} 100}}}\ =\
\bracks{z^{100}}\pars{\sum_{x = 1}^{40}z^{x}}^{3}}
\\[5mm] = &\
\bracks{z^{100}}\pars{z\,{z^{40} - 1 \over z - 1}}^{3}
\\[5mm] = &\
\bracks{z^{97}}\pars{1 - z^{40}}^{3}\pars{1 - z}^{-3} =
\bracks{z^{97}}\pars{1 - 3z^{40} + 3z^{80}}\pars{1 - z}^{-3}
\\[5mm] = &\
\bracks{z^{97}}\pars{1 - z}^{-3} -
3\bracks{z^{57}}\pars{1 - z}^{-3} + 
3\bracks{z^{17}}\pars{1 - z}^{-3}
\\[5mm] = &\
{-3 \choose 97}\pars{-1}^{97} -
3{-3 \choose 57}\pars{-1}^{57} +
3{-3 \choose 17}\pars{-1}^{17}
\\[5mm] = &\
\underbrace{{99 \choose 97}}_{\ds{4851}}\ -\
3\ \underbrace{{59 \choose 57}}_{\ds{1711}}\ +\
3\ \underbrace{{19 \choose 17}}_{\ds{171}}\ =\
\bbx{\large 231} 
\end{align}
