# (Probability) How many integer solutions are there to the inequality $x_1 + x_2 + x_3 \le 17$

How many integer solutions are there to the inequality

$$x_1 + x_2 + x_3 \leqslant 17$$

if we require that

$$x_1 \geqslant 1,\; x_2\geqslant2,\; x_3\geqslant 3$$

My first approach to this problem was to see 3 boxes: $x_1, x_2,x_3 .$ After putting the minimum amount into each box (1 for $x_1$, 2 for $x_2$ and 3 for $x_3$) we have 11 choices left. Using the star and bars method I got 11 spaces for the variables and 2 for the bars, giving me a final answer of:

$$\dbinom{13}{2}$$

However, the second way to solve this problem would be to find the total amount of combinations without the restrictions, then to subract for when $x_1 <1, x_2 <2$ or $x_3 < 3$.

$$\dbinom{19}{2}$$ for the first part where 17 is for the places of the integers and 2 are for the separators, but how do we find the restrictions? I am wondering if this has anything to do with a slack variable, our professor hinted at it and I do not know how to apply it to this problem.

Thank you.

• For clarity of language, you want to subtract when $x_1<1,x_2<2$ or $x_3<3$. That "or" is important. – Thomas Andrews Jan 28 '16 at 20:13
• The correct answer via the first approach is $\binom{11+3}{3}$. This is because there is an inequalty - if it was $=17$, the answer would be $\binom{11+2}{2}$, not $\binom{11}{2}$. (Sorry I got that wrong in my first comment.) – Thomas Andrews Jan 28 '16 at 20:16
• Thank you for explaining, it's much clearer now! Ill edit the "or" into it right away. – drossy11 Jan 28 '16 at 20:19
• Introduce one new variable, which you can name $u$ (for unused). We want the number of solutions of $y_1+y_2+y_3+u=11$ in non-negative integers. Now routine Stars and Bars. – André Nicolas Jan 28 '16 at 20:20
• The second way requires something called "inclusion-exclusion." You'd start with $\binom{17+3}{3}$ (again, not $\binom{19+2}{2}$,) and then adjust. But inclusion-exclusion is going to get unpleasant for this sort of problem. There is also a "generating function" approach, which is essential equivalent to Inclusion/Exclusion. – Thomas Andrews Jan 28 '16 at 20:24

The inclusion-exclusion answer. The number of solutions to:

$$y_1+y_2+y_3+y_4=17$$ is $\binom{17+3}{3}$.

Let $A_1$ be the set of solutions with $y_1<1$, let $A_2$ be the set of solutions with $y_2<2$ and let $A_3$ be the set of solutions with $y_3<3$. Then you want to subtract $|A_1\cup A_2\cup A_3|$. Inclusion/exlusion says:

$$|A_1\cup A_2\cup A_3| = |A_1|+|A_2|+|A_3|-|A_1\cap A_2|-|A_1\cap A_3|-|A_2\cap A_3| + |A_1\cap A_2\cap A_3|$$

Counting these is going to be a pain:

\begin{align}|A_1|&=\binom{17+2}{2}\\ |A_2|&=\binom{17+2}{2}+\binom{16+2}{2}\\ |A_3|&=\binom{17+2}{2}+\binom{16+2}{2}+\binom{15+2}{2} \end{align}

It gets even worse for the others, because there are more cases. The worst is $|A_2\cap A_3|$, because it requires $6$ cases.

\begin{align}|A_1\cap A_2|&=\binom{17+1}{1}+\binom{16+1}{1}\\ |A_1\cap A_3|&=\binom{17+1}{1}+\binom{16+1}{1}+\binom{15+1}{1}\\ |A_2\cap A_3|&=\binom{17+1}{1}+2\binom{16+1}{1} + 2\binom{15+1}{1}+\binom{14+1}{1} \end{align}

The "generating function" approach might make it clearer what is going on.

We are seeking the coefficient of $x^{17}$ in:

$$(1+x+x^2+\cdots)(x+x^2+x^3+\cdots)(x^2+x^3+x^4+\cdots)(x^3+x^4+x^5+\cdots)$$

Which can be written:

$$\frac{1}{1-x}\frac{x}{1-x}\frac{x^2}{1-x}\frac{x^3}{1-x}=\frac{x^6}{(1-x)^4}$$

The "simple" solution is just knowing that $$\frac{1}{(1-x)^4}= \sum_{k=0}^\infty\binom{k+3}{3}x^k$$

The inclusion-exclusion approach rather rewrites:

$$\frac{x^i}{1-x} = \frac{1}{1-x} - (1+x+\dots+x^{i-1})$$

And then takes the product. That's gonna get ugly. Writing $p_i(x)=1+x+\cdots+x^{i-1}$, we get:

$$\frac{1}{1-x}\cdot\left(\frac{1}{1-x}-p_1(x)\right)\left(\frac{1}{1-x}-p_2(x)\right)\left(\frac{1}{1-x}-p_3(x)\right)$$

You get:

\begin{align}\frac{1}{(1-x)^4} &- (p_1(x)+p_2(x)+p_3(x))\frac{1}{(1-x)^3}\\ &+ (p_1(x)p_2(x)+p_1(x)p_3(x)+p_2(x)p_3(x))\frac{1}{(1-x)^2}\\& + p_1(x)p_2(x)p_3(x)\frac{1}{1-x}\end{align}

This is all, terrifyingly, going to get you:

\begin{align}\binom{17+3}{3}&-\left(3\binom{17+2}{2}+2\binom{16+2}{2}+\binom{15+2}{2}\right) \\ &+\left(3\binom{17+1}{1}+4\binom{16+1}{1}+3\binom{15+1}{1}+\binom{14+1}{1}\right)\\ & -\left(1+2+2+1\right) \end{align}

This gives the correct answer, $364=\binom{11+3}{3}$, by a very circuitous rout.

• Thank you for your great answer! – drossy11 Feb 2 '16 at 0:58

Define $y_1:=x_1-1,\, y_2:=x_2-2,\,y_3:=x_3-3.$

Thus you make all $y_i$'s non-negative. And now you need to encounter the problem $$y_1+y_2+y_3\le11, \;\; y_1,y_2,y_3\ge 0.$$

Now, define a $y_4=11-n,$ where $0\le n\le 11$.

So, now you need to solve that $$y_1+y_2+y_3+y_4= 11$$

So, this can be done in $$\binom{11+4-1}{4-1}=\binom{14}{3}$$ ways(for the first problem).

You can also count the number of solutions of the equations $$y_1+y_2+y_3=n,\;\; n\in\{0,1,2,\dots,10,11\}.$$

So, this is $$\binom 22+\binom 32+\binom 42+\dots+\binom {12}2+\binom {13}{2}=\binom {14}{3},$$ using the identity $$\binom kk+\binom {k+1}k+\binom {k+2}k+\dots +\binom nk=\binom {n+1}{k+1}.$$

• Thanks for your answer! I wish I could pick multiple solutions. – drossy11 Feb 2 '16 at 2:23

Introduce a dummy variable $x_0\geq0$. Then we we have to count the solutions of $$x_0+x_1+x_2+x_3=17$$ satisfying $$x_0\geq0,\quad x_1\geq1,\quad x_2\geq2,\quad x_3\geq3\ .$$ Put $$x_k:=y_k+k\qquad(0\leq k\leq 3)\ .$$ Then we have to count the solutions of $$y_0+y_1+y_2+y_3=11$$ in nonnegative integers. This is a standard stars and bars problem. The solution is $${11+4-1\choose 4-1}={14\choose 3}=364\ .$$

We wish to solve the inequality $$x_1 + x_2 + x_3 \leq 17 \tag{1}$$ subject to the restrictions that $x_1 \geq 1$, $x_2 \geq 2$, and $x_3 \geq 3$. Let \begin{align*} y_1 & = x_1 - 1\\ y_2 & = x_2 - 2\\ y_3 & = x_3 - 3 \end{align*} Then $y_1, y_2, y_3$ are non-negative integers. Substituting $y_1 + 1$ for $x_1$, $y_2 + 2$ for $x_2$, and $y_3 + 3$ for $x_3$ in inequality yields \begin{align*} y_1 + 1 + y_2 + 2 + y_3 + 3 & \leq 17\\ y_1 + y_2 + y_3 & \leq 11 \tag{2} \end{align*} which is an inequality in the non-negative integers. Inequality is equivalent to the equation $$y_1 + y_2 + y_3 + y_4 = 11 \tag{3}$$ where the slack variable $y_4 = 17 - y_1 - y_2 - y_3$. Observe that $y_4$ is a non-negative integer. A particular solution of equation 3 corresponds to inserting three addition signs in a row of $11$ ones. For instance, $$1 1 + 1 1 1 + 1 1 1 1 1 1 +$$ corresponds to the solution $y_1 = 2$, $y_2 = 3$, $y_3 = 6$, and $y_4 = 0$, while $$1 1 1 1 + 1 1 + 1 1 1 + 1 1$$ corresponds to the solution $y_1 = 4$, $y_2 = 2$, $y_3 = 3$, and $y_4 = 2$. Thus, the number of solutions of equation 3 is the number of ways we can insert three addition signs in a row of eleven ones, which is $$\binom{11 + 3}{3} = \binom{14}{3}$$ since we must choose which three of the fourteen symbols (eleven ones and three addition signs) will be addition signs.

• Thank you for your answer! I'm wondering how adding $y_4$ to the formula changes it from an inequality to an equality. I've been staring at it for about half an hour and maybe I'm missing the background to grasp it. – drossy11 Jan 28 '16 at 21:39
• Notice that $y_4 = 11 - y_1 - y_2 - y_3$ is the difference between $11$ and the sum $y_1 + y_2 + y_3$. Thus, $y_1 + y_2 + y_3 + y_4 = 11$. The variable $y_4$ is specifically defined so that we obtain an equality. – N. F. Taussig Jan 28 '16 at 21:43
• Ah, got it. Thank you! – drossy11 Jan 28 '16 at 21:50