Q:

(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.

A:

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

A:

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

A:

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.

