Number of solutions of a simple equation

Question

Problem How to count the number of distinct integer solutions $(x_1,x_2,\dots,x_n)$ of the equations like :

$$|x_1| + |x_2| + \cdots + |x_n| = d $$

the count gives the number of coordinate points in the $n$-dimensional space which are at distance equal to $d$ [a non-negative-integer] from the origin [ where we are only allowed to move along the grid lines ]. That is distance between $2$ points $x$ and $y$ is defined as $|x_1-y_1|+\dots +|x_n-y_n|$.

I know how to calculate for non-negative solutions for the equation :

$$x_1 + x_2 + \dots+ x_n = d $$

which is$^{n+d-1}C_{n-1}$, i.e. $x_i \geq 0$ but in the new problem we have upper and lower bounds as well i.e. $x_n\in [-d,d]$.

I don't know that there is any formula for this or not ?

Also I want to know the number of distinct solutions for the equation for large $n$ efficiently :

$$|x_1| + |x_2| + \dots + |x_n| \leq d.$$

Thank you in advance.

Answer 1

Hint. Recall what is multinomial coefficient and slightly upgrade formula to take into account negative integers too.

Answer 2

Given that, $|x_1| + |x_2| + \cdots + |x_n| = d$

---

Intuition.

Let's say we have, $|x|+|y|+|z|=10$, there will be $^{3+10-1}C_{3-1}$=$^{12}C_{2}$=$66$ combination.

we choose one of them, as; 1,7,2, now we have 2 combinations for each position -1 and 1, -7 and7, -2 and 2. so there are there are $2^3$ total combinations for this set only but we have a total of $^{3+10-1}C_{3-1}$ sets. So we will have to multiply it by total possible sets of solutions we will get $2^3\cdot^{3+10-1}C_{3-1} $

---

Part 1.

For general, if we have, $|x_1| + |x_2| + \cdots + |x_n| = d$, then total no. of sets of solutions is

$2^n\cdot^{n+d-1}C_{n-1}$.

---

Part 2.

For $|x_1| + |x_2| + \dots + |x_n| \leq d$, let us introduce a dummy variable $|x_{n+1}|$ which will equate LHS and RHS. so that, $|x_1| + |x_2| + \dots + |x_n| +|x_{n+1}|=d$ now we just have to put n $\rightarrow$ n+1 in our previous result,i.e.

$2^{n+1}\cdot^{(n+1)+d-1}C_{(n+1)-1}$.

.

---

Update :when $|x_i| \geq 0$ i.e some $|x_i|$ can be 0. In that case we need to multiply 2 only for positive $|x_i|$ . My approach is that I assign k variables out of n the value 0 and solve the remaining equation for positive solutions for the remaining variables.

$\sum_{i=0}^{n-1} \cdot^{n}C_{k} * 2^{n-k}\cdot^{(n-k)+d-1}C_{(n-k)-1}$

This gives the complete answer for this case.