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$

Question

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?

Answer 1

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.

Answer 2

$\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}