# Combinatorics problem with negative possibilities

I know how to solve the basic number of solutions equations, such as "find the number of positive integer solutions to $x_1 + x_2 + x_3$ = 12, with ". But I have no clue how to do this problem:

Find the number of solutions of $x_1+x_2-x_3-x_4 = 0$ in integers between -4 and 4, inclusive.

If I try and solve it like the basic equations, I get $C(n+r-1,r)$$= C(0+9-1,9)$$ = C(8,9)$, which is obviously improper. Can someone point me in the right direction on how to solve this type of problem?

HINT: Let $y_1=x_1+4,y_2=x_2+4,y_3=-x_3+4$, and $y_4=-x_4+4$. Then

$$x_1+x_2-x_3-x_4=0\tag{1}$$ if and only if

$$y_1+y_2+y_3+y_4=16\;.\tag{2}$$

Moreover, there is a bijection between solutions of $(1)$ that satisfy $-4\le x_k\le 4$ for $k=1,2,3,4$ and solutions of $(2)$ that satisfy $0\le y_k\le 8$ for $k=1,2,3,4$.

Finding the number of solutions of $(2)$ that satisfy $0\le y_k\le 8$ for $k=1,2,3,4$ is a standard problem, although the upper bounds on the $y_k$ make it little messier than a basic stars-and-bars problem, since you’ll have to use an inclusion-exclusion argument as well.

• @SSumner: You’re welcome! – Brian M. Scott Nov 20 '12 at 0:26
• Okay, when I do the combination, I get $C(16+4-1,4) = C(19,4) = 3,876$. Then we have to take out cases where $y_k \geq 9$, so we do a combination $C(7+4-1,4) = C(10,4) = 210$. Since this can be for any of four cases, we subtract 4*210 = 840 from 3,876 to get 3,036. But this seems kind of high. Am I doing something wrong here? I shouldn't need to include/exclude any more cases, since only one time could any $y_k$ exceed 8. – SSumner Nov 20 '12 at 2:25
• @SSumner: Your formula is slightly off: it should be $$\binom{16+4-1}{4-1}-4\binom{7+4-1}{4-1}=\binom{19}3-4\binom{10}3=969-4\cdot120=489\;.$$ – Brian M. Scott Nov 20 '12 at 6:04
• I see! Thanks so much! – SSumner Nov 21 '12 at 0:09
• @SSumner: You’re welcome. – Brian M. Scott Nov 21 '12 at 0:13

Put $x_i+4=:y_i$. Then we have to solve $$y_1+y_2=y_3+y_4$$ in integers $y_i$ between $0$ and $8$ inclusive. For given $p\geq0$ the equation $y_1+y_2=p$ has $p+1$ solutions if $0\leq p\leq 8$, and $17-p$ solutions if $9\leq p\leq 16$. It follows that the total number $N$ of solutions is given by $$N=\sum_{p=0}^8(p+1)^2+\sum_{p=9}^{16}(17-p)^2=2\sum_{k=1}^8 k^2+ 9^2=489\ .$$

• @Brian M. Scott: Thank you. – Christian Blatter Nov 20 '12 at 9:03
• You’re welcome. – Brian M. Scott Nov 20 '12 at 9:04

Hints: (1). Let $y_1=x_1$, $y_2=x_2$, $y_3=-x_3$, $y_4=-x_4$. We want to solve $y_1+y_2+y_3+y_4=0$, with the $y_i\dots$.

(2) Let $z_i=y_i+4$. We want to solve $z_1+z_2+z_3+z_4=\dots$.

One may also solve this using generating functions.

Following the others' suggestion to consider the equation $y_1 + y_2 + y_3 + y_4 = 16$, you would want to find the coefficient of $x^{16}$ in the product $(1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8)^4$, which a computer algebra system can easily compute.

The general principle of using generating functions for combinatorial problems is simple. Suppose you want to find the number of solutions to $$\sum_{i=1}^n x_i = A,$$ where $a_i \leq x_i \leq b_i$ for $i = 1, \dots n$. Then, the number of solutions to the equation is the same as the coefficient of $x^A$ in the product

$$(x^{a_1} + \dots + x^{b_1})(x^{a_2} + \dots + x^{b_2}) \dots (x^{a_n} + \dots + x^{b_n}).$$

The reason this works is that finding a term in the product above which multiplies to $x^A$ amounts to finding $x^{c_1}, x^{c_2}, \dots, x^{c_n}$ where $a_i \leq c_i \leq b_i$ and $x^{c_1 + c_2 \dots + c_n} = x^A$. The advantage of the generating function approach is that computer algebra systems (like mathematica or sage) can easily handle polynomial multiplication.