0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

$\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} $$
$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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}$? $\endgroup$ – Oria Gruber Dec 9 '13 at 23:41
  • $\begingroup$ @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$. $\endgroup$ – Nick Peterson Dec 9 '13 at 23:48
0
$\begingroup$

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.

$\endgroup$

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.