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.

$\newcommand{\+}{^{\dagger}}% \newcommand{\angles}[1]{\left\langle #1 \right\rangle}% \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace}% \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack}% \newcommand{\ceil}[1]{\,\left\lceil #1 \right\rceil\,}% \newcommand{\dd}{{\rm d}}% \newcommand{\ds}[1]{\displaystyle{#1}}% \newcommand{\equalby}[1]{{#1 \atop {= \atop \vphantom{\huge A}}}}% \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}% \newcommand{\fermi}{\,{\rm f}}% \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}% \newcommand{\half}{{1 \over 2}}% \newcommand{\ic}{{\rm i}}% \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow}% \newcommand{\isdiv}{\,\left.\right\vert\,}% \newcommand{\ket}[1]{\left\vert #1\right\rangle}% \newcommand{\ol}[1]{\overline{#1}}% \newcommand{\pars}[1]{\left( #1 \right)}% \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}}% \newcommand{\root}[2][]{\,\sqrt[#1]{\,#2\,}\,}% \newcommand{\sech}{\,{\rm sech}}% \newcommand{\sgn}{\,{\rm sgn}}% \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}}% \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ \begin{align} \color{#ff0000}{{\Large ?}}&=\sum_{x_{1} = -16}^{-2}\sum_{x_{2} = 0}^{7} \sum_{x_{3} = 0}^{13}\sum_{x_{4} = 0}^{13}\delta_{x_{1} + x_{2} + x_{3} + x_{4}, 17} = \!\!\!\!\!\!\sum_{x_{1} = -16}^{-2}\sum_{x_{2} = 0}^{7} \sum_{x_{3} = 0}^{13}\sum_{x_{4} = 0}^{13}\oint_{\verts{z} = 1}{\dd z \over 2\pi\ic}\, {1 \over z^{18 - x_{1} - x_{2} - x_{3} - x_{4}}} \\[3mm]&= \oint_{\verts{z} = 1}{\dd z \over 2\pi\ic}\,{1 \over z^{18}}\, \sum_{x_{1} = -16}^{-2}z^{x_{1}}\sum_{x_{2} = 0}^{7}z^{x_{2}} \pars{\sum_{x_{} = 0}^{13}z^{x}}^{2} \\[3mm]&= \oint_{\verts{z} = 1}{\dd z \over 2\pi\ic}\,{1 \over z^{18}}\, {z^{-16}\pars{z^{15} - 1} \over z - 1}\,{z^{8} - 1 \over z - 1} \pars{z^{14} - 1 \over z - 1}^{2} \\[3mm]&= \oint_{\verts{z} = 1}{\dd z \over 2\pi\ic}\,{1 \over z^{34}}\, {\pars{1 - z^{15}}\pars{1 - z^{8}}\pars{1 - z^{14}}^{2} \over \pars{1 - z}^{4}} = \color{#ff0000}{I_{34} - I_{26} - I_{19} + I_{11}} \end{align}

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