1
$\begingroup$

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?

4 Answers 4

3

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.

  • 0
    @SSumner: You’re welcome.2012-11-21
2

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\ .$

  • 0
    You’re welcome.2012-11-20
1

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

1

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.