How many integer solutions are there of the equation $|x_{1}|+|x_{2}|+\cdots +|x_{k}|=n$?

Question

How many solutions are there to the equation

$$|x_{1}|+|x_{2}|+\cdots +|x_{k}|=n$$

for $n,k\in \mathbb N$ and $\forall\ 1\leq i\leq k,\ x_{i}\in \mathbb Z$?

Any ideas? I don't know how to approach this question. (all I know that if my $ x_{i}$'s were in $\mathbb N$ the solution would be $\binom{n+k-1}{k-1}$ )

Answer 1

It is a simple variation on stars and bars. The number of solutions of $$ x_1+x_2+\ldots+x_k = n $$ with $x_i\in\mathbb{N}^+$ is given by the coefficient of $x^n$ in $\left(\frac{x}{1-x}\right)^k$, i.e. by $\binom{n-1}{k-1}$, so the number of solutions of $$\left|x_1\right|+\ldots +\left|x_k\right| = n$$

with $x_i\in\mathbb{Z}\setminus\{0\}$ is given by $2^k\binom{n-1}{k-1}$. If we take the number of zero variables as a parameter, we get that the number of solutions of $$ \left|x_1\right|+\ldots +\left|x_k\right| = n $$ with $x_i\in\mathbb{Z}$ is given by:

$$ \sum_{h=0}^{k}\binom{k}{k-h}\binom{n-1}{h-1}2^h. $$

The connection with the GFs found by Felix and Semiclassical lies here: $$\begin{eqnarray*}\sum_{h=0}^{k}\binom{k}{h}2^h [x^{n-h}]\left(\frac{x}{1-x}\right)^h &=& \sum_{h=0}^{k}\binom{k}{h}[x^n]\left(\frac{2x}{1-x}\right)^h\\&=&[x^n]\left(1+\frac{2x}{1-x}\right)^k\\&=&[x^n]\left(\frac{1+x}{1-x}\right)^k.\end{eqnarray*}$$

Answer 2

A generating-function solution is straightforward. For each $|x_j|$, every positive $n\in\mathbb{Z}$ occurs as both $x_j=n$ and $x_j=-n$; on the other hand, $|x_j|=0$ requires $x_j=0$. This sequence is generated by $$1+2t+2t^2+\cdots =(1+t)(1-t)^{-1}.$$ (This can be checked by multiplying both sides by $1-t$.)

Counting the solutions to $\sum_{j=1}^k |x_j|=n$ then amounts to finding the coefficient of $t^n$ in $\left(\dfrac{1+t}{1-t}\right)^k.$ But these can be found as the Cauchy product of the coefficients of $(1+t)^k$ and $(1-t)^{-k}$, each of which can be found by the binomial theorem. This should yield the same answer as obtained by Jack D'Aurizio; I leave the remaining details to the interested reader.

Answer 3

$\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{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Leftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

$\ds{\delta_{\ell\ell'}}$ is the Kronecker Delta which is equal to $\ds{1}$ if $\ds{\ell = \ell'}$ and $\ds{0}$ otherwise. The following multiple sum 'counts' $\ds{1}$ each time $\ds{\verts{x_{1}} + \cdots + \verts{x_{k}} = n}$. So,

\begin{align} &\color{#f00}{\sum_{x_{1} = -\infty}^{\infty}\cdots \sum_{x_{k} = -\infty}^{\infty} \delta_{\verts{x_{1}} + \cdots + \verts{x_{k}}\,,\,n}} = \sum_{x_{i} = -\infty}^{\infty}\cdots\sum_{x_{k} = -\infty}^{\infty}\ \overbrace{% \oint_{\verts{z} = 1^{-}}{1 \over z^{n + 1 - \verts{x_{1}} - \cdots - \verts{x_{k}}}}\,{\dd z \over 2\pi\ic}}^{\ds{\delta_{\verts{x_{1}} + \cdots + \verts{x_{k}}\,,\,n}}} \\[3mm] = &\ \oint_{\verts{z} = 1^{-}}{1 \over z^{n + 1}} \sum_{x_{1} = -\infty}^{\infty}z^{\verts{x_{1}}}\cdots \sum_{x_{k} = -\infty}^{\infty}z^{\verts{x_{k}}}\,{\dd z \over 2\pi\ic} = \oint_{\verts{z} = 1^{-}}{1 \over z^{n + 1}}\,\pars{1 + 2\,{z \over 1 - z}}^{k} \,{\dd z \over 2\pi\ic} \\[3mm] = &\ \oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{k} \over z^{n + 1}}\,\pars{1 - z}^{-k} \,{\dd z \over 2\pi\ic} = \oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{k} \over z^{n + 1}}\,\ \overbrace{\sum_{j = 0}^{\infty}{-k \choose j}\pars{-z}^{j}}^{\ds{\pars{1 - z}^{-k}}}\ \,{\dd z \over 2\pi\ic} \\[3mm] = &\ \sum_{j = 0}^{\infty}{-k \choose j}\pars{-1}^{j}\ \overbrace{% \oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{k} \over z^{n + 1 - j}}\,\ \,{\dd z \over 2\pi\ic}}^{\ds{{k \choose n - j}}} = \sum_{j = n - k}^{n}{k + j - 1 \choose j}\pars{-1}^{j}\pars{-1}^{j} {k \choose n - j} \\[3mm] & = \sum_{j = 0}^{k}{k + j + n - k - 1 \choose j + n - k} {k \choose n - j - n + k} = \color{#f00}{\sum_{j = 0}^{k}{j + n - 1 \choose k - 1}{k \choose j}} \end{align}