3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ this seems to be related to integer partitions $\endgroup$ – Mirko Dec 13 '14 at 23:35
  • 1
    $\begingroup$ 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. $\endgroup$ – hardmath Dec 14 '14 at 0:08
2
$\begingroup$

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

| cite | improve this answer | |
$\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.