# How many distinct integer solutions does the inequality $|x_{1}|+|x_{2}|+…+|x_{n}| \leq t$ have?

How many distinct integer solutions does the inequality $|x_{1}|+|x_{2}|+...+|x_{n}| \leq t$ have?

We know that: $x_{i} \in Z,\ \forall i \ 0\leq i \leq n \ and \ t\geq0.\$

I know that if we have this type of equation: $x_{1}+x_{2}+...+x_{n} = t$ where $x_{i} \in Z \ and \ x_{i}\geq 0 \ \forall i\ \ 0\leq i \leq n.$ The number of distinct integer solutions will be $_{t+n-1}C_{n-1}$ where $_{n}C_{k} = \frac{n!}{k!(n-k)!}$ (Stars and bars (combinatorics))

Then for this $|x_{1}|+|x_{2}|+...+|x_{n}| = t$. I think the number of distinct solutions will be $_{t+n-1}C_{n-1} * 2^n$(each of $x_{i}$ can be negative or positive), but this is wrong answer, because I've considered the solution where $x_{i} = 0 \ and \ x_{j} > 0 \ i \ne j$ twice and the solution $x_{i} = 0, x_{j} = 0 \ and \ x_{k} > 0 \ i \ne j \ i\ne k \ j\ne k$ four time ..... this is my mistake: $0 = 0*-1 = 0*+1$

Maybe, you know how to find out the number of solutions for this inequality without solving this problem for each of equation ($|x_{1}|+|x_{2}|+...+|x_{n}| = t_i \ 0\leq t_i\leq t \ and \ t_i \in Z$).

Do you have any idea how to solve this? Thank you for your time.

• this seems to be related to integer partitions – Mirko Dec 13 '14 at 23:35
• As you've noted in the Question, the difficulty is accounting for zero summands. One approach is to let the problem be divided into subcases according to the number of nonzero summands. – hardmath Dec 14 '14 at 0:08

For $k=1,\ldots,n$ there are $\binom{n}k$ ways to choose $k$ positions to be non-zero, $2^k$ ways to assign algebraic signs to those positions, and $\binom{s-1}{k-1}$ ways to assign non-zero absolute values to those positions to get a sum of $s$. Letting $s$ range from $1$ to $t$, and adding $1$ for the all-zero solution with sum $0$, we get a total of
\begin{align*} 1+\sum_{s=1}^t\sum_{k=1}^n2^k\binom{s-1}{k-1}\binom{n}k&=1+\sum_{k=1}^n2^k\binom{n}k\sum_{s=1}^t\binom{s-1}{k-1}\\\\ &=1+\sum_{k=1}^n2^k\binom{n}k\binom{t}k\\\\ &=\sum_{k=0}^n2^k\binom{n}k\binom{t}k \end{align*}
solutions, which is at least a bit simpler to work with. I’ve not been able to find a closed form for this, however, even in the special case $t=n$ (and the sequence that results in that case is unknown to OEIS).