Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

4 Answers 4

up vote 3 down vote accepted

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.

share|improve this answer
    
Thanks! I think I get this type of problem now –  SSumner Nov 20 '12 at 0:25
    
@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
1  
@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

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

share|improve this answer

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

share|improve this answer
    
@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

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.