0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ For clarity of language, you want to subtract when $x_1<1,x_2<2$ or $x_3<3$. That "or" is important. $\endgroup$ – Thomas Andrews Jan 28 '16 at 20:13
  • 1
    $\begingroup$ 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.) $\endgroup$ – Thomas Andrews Jan 28 '16 at 20:16
  • $\begingroup$ Thank you for explaining, it's much clearer now! Ill edit the "or" into it right away. $\endgroup$ – drossy11 Jan 28 '16 at 20:19
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Jan 28 '16 at 20:20
  • $\begingroup$ 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. $\endgroup$ – Thomas Andrews Jan 28 '16 at 20:24
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for your great answer! $\endgroup$ – drossy11 Feb 2 '16 at 0:58
3
$\begingroup$

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

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

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – drossy11 Jan 28 '16 at 21:39
  • 1
    $\begingroup$ 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. $\endgroup$ – N. F. Taussig Jan 28 '16 at 21:43
  • $\begingroup$ Ah, got it. Thank you! $\endgroup$ – drossy11 Jan 28 '16 at 21:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.