# Counting additive decompositions of $32$ with some restrictions

Does anyone know how to do this following question using a "change of variables"?

Q:Determine the number of integer solutions of $x_1 + x_2 + x_3 + x_4 = 32$ where $x_i ≥ -2, 1 ≤ i ≤ 4$.

So I've done these sort of questions where $x_i ≥ 1$ or $0$, but now that there is a negative number in the restriction I am not sure how to go about solving this.. My teacher gave us a hint and said to use a "change of variable" to solve this, but I have no idea how to do this. Can someone shed some light and show me how to deal with cases with negative restrictions?

• set $f_i=x_i+2$, so that $f_i \ge 0, 1 \le i \le 4$ – tpb261 Jun 3 '14 at 5:07
• What is the logic behind doing that? – Jack Jun 3 '14 at 5:09
• You know how to solve for $f_i \ge 1 or 0$, but $x_i \ge -2$, so replace with a variable that satisfies for the condition we want. Since, $x_i + 2 \ge 0$, if we let $f_i = x_i +2$, then $f_i \ge 0$. – tpb261 Jun 3 '14 at 5:12
• I see, thanks and what if the constraints were x1, x2, x3 > 0, and 0 < x4 ≤ 25? I am mainly confused about the last restriction placed on x4 – Jack Jun 3 '14 at 5:17
• I am not sure. I'd proceed like this: since $x_4 \gt 0$ solve the equations as you normally would and then check if $x_4 \le 25$, if yes, you are done, if not it means the equations don't have a solution. – tpb261 Jun 3 '14 at 5:24

For each $i$, write $y_i=x_i+2$. Then, you have to find the number of solutions of $$(y_1-2)+(y_2-2)+(y_3-2)+(y_4-2)=32$$ or $$y_1+y_2+y_3+y_4=40$$ but now $y_i\geq 0$.

If you prefer that $y_i\geq 1$ instead of $y_i\geq 0$, the change would be $y_i=x_i+3$.

$\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{\down}{\downarrow} \newcommand{\ds}[1]{\displaystyle{#1}} \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]{\vphantom{\large A}\,#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} \newcommand{\wt}[1]{\widetilde{#1}}$ Since this question appears frequently, we'll calculate a general case: $${\large% x_{1} + x_{2} + \cdots + x_{n} = S\,,\qquad x_{i} \geq 0}$$

The solution is given by: \begin{align} {\cal N}_{n}\pars{S}&= \sum_{x_{1} = 0}^{\infty}\sum_{x_{2} = 0}^{\infty}\ldots\sum_{x_{n} = 0}^{\infty} \delta_{x_{1} + x_{2} + \cdots +x_{n},S} \\[3mm]&=\sum_{x_{1} = 0}^{\infty}\sum_{x_{2} = 0}^{\infty}\ldots \sum_{x_{n} = 0}^{\infty} \int_{\verts{z}\ =\ 1}{1 \over z^{-x_{1} - x_{2} - \cdots - x_{n} + S + 1}} \,{\dd z \over 2\pi\ic} =\int_{\verts{z}\ =\ 1}{1 \over z^{S + 1}} \pars{\sum_{x = 0}^{\infty}z^{x}}^{n}\,{\dd z \over 2\pi\ic} \\[3mm]&=\int_{\verts{z}\ =\ 1}{\pars{1 - z}^{-n}\over z^{S + 1}} \,{\dd z \over 2\pi\ic} =\sum_{k = 0}^{\infty}\pars{-1}^{k}{-n \choose k}\ \overbrace{\int_{\verts{z}\ =\ 1}{z^{k}\over z^{S + 1}} \,{\dd z \over 2\pi\ic}}^{\ds{=\ \delta_{kS}}} =\pars{-1}^{S}{-n \choose S} \\[3mm]&=\pars{-1}^{S}\bracks{\pars{-1}^{S}{n + S - 1 \choose S}} \end{align}

$$\color{#44f}{\large{\cal N}_{n}\pars{S} = {n - 1 + S \choose n - 1}}\,,\qquad n \geq 1\,,\quad S \geq 0$$

In the particular case $\ds{\quad n = 4\,,\quad x_{i} \geq - 2\,,\quad S = 32 \quad}$ it's equivalent to $$\pars{x_{1} + 2} + \pars{x_{2} + 2} +\pars{x_{3} + 2} +\pars{x_{4} + 2}=40$$ So, we have to calculate $\ds{{\cal N}_{4}\pars{40}}$: $$\color{#c00000}{\large% {\cal N}_{4}\pars{40}} = {43 \choose 3} ={43 \times 42 \times 41 \over 3 \times 2} = \color{#c00000}{\large 12341}$$

• This does not answer the question, which is about a change of variables. – Marc van Leeuwen Jun 3 '14 at 9:16
• @MarcvanLeeuwen It's not so clear what does it means. I guess it suggests to write something likes $\large y_{i} = x_{i} + 2$ such that $\large y_{i} \geq 0$. Maybe... – Felix Marin Jun 3 '14 at 9:19
• OK, I see you got the correct result at the end. But really, one does not need to use contour integrals to get the result. – Marc van Leeuwen Jun 3 '14 at 9:28

You can use generating functions:

For each $x_i$ the generating function of the $x_i$ as integer greater or equal to $-2$ is $x^{-2}(1+x+x^2+...)$ therefore for the 4 variables you get the generating function $f(x)=x^{-8}\frac{1}{(1-x)^4}=x^{-8}\sum_{k=0}^{\infty}CC_4^kx^k$

Now to find the solution of $x_1+x_2+x_3+x_4=32$ under the terms, you need to find $k$ s.t $x^{k-8} = x^{32}$ and the solution is given by this $k$ corresponding cofficient. Therefore you get that the solution is given by:

$CC^{40}_4 = $${40+4-1}\choose{40} In this case just put y_i=x_i+2 for i=1,2,3,4, for which one has the condition y_1+y_2+y_3+y_4=40. I suppose you know that this number is$$ (-1)^{40}\binom{-4}{40} = \binom{40+4-1}{40} = \binom{43}3 = 12341.$\$