# combinatorics - how many integer solutions

simple question.

we are given this equation $x_1+x_2+x_3+x_4=17$ when:

$0\leq x_2\leq 7$,

$0\leq x_3 \leq 13$

$0\leq x_4 \leq 13$

and for all $i$: $x_i \in \mathbb Z$

we are asked how many solutions are there to this equation when $x_1 \leq -2$

Obviously we need some sort of variable swap, so that all the variables will start from 0, but I'm having difficulties.


$$\mbox{where}\qquad I_{n} \equiv \oint_{\verts{z} = 1}{\dd z \over 2\pi\ic}\,{1 \over z^{n}}\, {\pars{1 - z^{14}}^{2} \over \pars{1 - z}^{4}}$$

Since $\ds{\pars{1 - z}^{4} = \sum_{\ell = 0}^{\infty}{-4 \choose \ell}\pars{-z}^{\ell} =\sum_{\ell = 0}^{\infty}\pars{-1}^{\ell}{-\pars{-4} + \ell - 1\choose \ell} \pars{-z}^{\ell} =\sum_{\ell = 0}^{\infty}{\ell + 3 \choose 3}z^{\ell}}$, \begin{align} I_{n} &=\oint_{\verts{z} = 1}{\dd z \over 2\pi\ic}\,{1 \over z^{n}}\, \sum_{\ell = 0}^{\infty}{\ell + 3 \choose 3}z^{\ell} \sum_{\ell' = 0}^{2}{2 \choose \ell'}\pars{-1}^{\ell'}z^{14\ell'} \sum_{m = 0}^{\infty}\delta_{m,\ell + 14\ell'} \\[3mm]&= \sum_{m = 0}^{\infty}\oint_{\verts{z} = 1}{\dd z \over 2\pi\ic}\, {1 \over z^{n - m}}\,\sum_{\ell' = 0}^{2}{2 \choose \ell'}\pars{-1}^{\ell'} \sum_{\ell = 0}^{\infty}{\ell + 3 \choose 3}\delta_{\ell,m - 14\ell'} \\[3mm]&= \sum_{m = 0}^{\infty}\oint_{\verts{z} = 1}{\dd z \over 2\pi\ic}\, {1 \over z^{n - m}}\, \sum_{\ell' = 0 \atop {\vphantom{\LARGE A}{m - 14\ell'\ \geq\ 0}}}^{2} {2 \choose \ell'}\pars{-1}^{\ell'}{m - 14\ell' + 3 \choose 3} \end{align}

$$I_{n} = \sum_{\ell = 0 \atop {\vphantom{\LARGE A}{n - 14\ell\ \geq\ 1}}}^{2} \pars{-1}^{\ell}{2 \choose \ell}{n - 14\ell + 2 \choose 3}$$

\begin{align} \color{#ff0000}{I_{34}}&={36 \choose 3} - 2{22 \choose 3} + {8 \choose 3} = \overbrace{12\times 35\times 34}^{14280} - \overbrace{2\times 22\times 7 \times 20}^{6160} + \overbrace{8\times 7\times 2}^{112} = \color{#ff0000}{8232} \\[3mm] \color{#ff0000}{I_{26}} &= {28 \choose 3} - 2{14 \choose 3} =\overbrace{28\times 9 \times 26}^{6552} - \overbrace{2\times 14\times 13\times 4}^{1456} = \color{#ff0000}{5096} \\[3mm] \color{#ff0000}{I_{19}} &={21 \choose 3} - 2{7 \choose 3}= \overbrace{7\times 20\times 19}^{2660} - \overbrace{2\times 7\times 2\times 5}^{140} =\color{#ff0000}{2520} \\[3mm] \color{#ff0000}{I_{11}} & = {13 \choose 3} = 13\times 4\times 11 = \color{#ff0000}{572} \end{align}

$$\color{#0000ff}{\LARGE ?} =8232 - 5096 - 2520 + 572 = \color{#0000ff}{\large 1188}$$

Hint:

If you know $x_1$, then you may be able to find the number of solutions $(x_2,x_3,x_4)$ to the system $$x_2+x_3+x_4=17-x_1,\qquad 0\leq x_2\leq 7,\ 0\leq x_3\leq 13,\ 0\leq x_4\leq 13.$$ This effectively partitions your set of solutions: for $k\leq -2$, let $N_k$ be the number of solutions $(x_1,\ldots,x_4)$ with $x_1=k$, and note that the total number of solutions is just $\sum_{k=-\infty}^{-2}N_k$.

(Note that we will only actually need finitely many values of $k$, as the biggest $x_2+x_3+x_4$ can be is $33$.)

• Is there any way I can do a variable switch so I can use the formula that: number of solution for $x_1+x_2+...+x_n=k$ = $\binom{n+k-1}{k}$? – Oria Gruber Dec 9 '13 at 23:41
• @OriaGruber I certainly don't think so; not when you've got bounds for your variables this way. That formula only works if each variable is allowed to take on every value between $0$ and $k$. – Nick Peterson Dec 9 '13 at 23:48

From your comment, I see that you know how to apply the technique of Stars and Bars.

Hint: Apply the technique of Principle of Inclusion and Exclusion.

Consider all solutions in non-negative integers where $x_1 + x_2 + x_3 + x_4 = 17$.

Consider all solutions in non-negative integers where $x_1 + (8+z_2) + x_3 + x_4 = 17$.

Consider all solutions in non-negative integers where $x_1 + x_2 + (14 + z_3) + x_4 = 17$.

Consider all solutions in non-negative integers where $x_1 + x_2 + x_3 + (14 + z_4) = 17$.

Show that no solution can violate 2 conditions.