# Find the number of integers solutions

How many solutions are there to the equation $$x_1+x_2+x_3+x_4=39,$$

I) where $x_1,x_2,x_3,x_4$ are nonnegative integers,

II) where $x_1,x_2,x_3,x_4$ are nonnegative integers such that $3 \leq x_1,x_2,x_3 \leq 12$ and $0 \leq x_4$.

I) There is a 1-1 correspondence between the solutions and reordering of 39 ones and 3 zeros. Hence the answer is $\binom{42}{3}$

I did not understand very well this type of solution. What about the second case?

For I. This problem is equivalent to number of solutions of equation $c_1+c_2+\cdots+c_k=n$ with $c\geq 0$ and $c$ integer, you can use the "generating function" (see book of combinatorial of Brualdi or Grimaldi), the number of posibilities is the coeficient in $(1+x+x^2+x^3+\cdots x^n+\cdots)^k$ of $x^n$, $$(1+x+x^2+\cdots x^{n-1}+x^n+\cdots)^k=\frac{1}{(1-x)^k}=\sum_{i=0}^\infty\binom{k+i-1}{i}x^i$$

Then the number posibilities is $\binom{k+n-1}{n}$.

for the second, the generating function is $$(x^3+x^4+\cdots x^{12})^3(1+x+x^2+\cdots)=x^9(1+x+x^2+\cdots +x^9)^3(1+x+x^2+\cdots)$$

I. A solution to this equation can be thought of this way: Take 39 1's, all in a row, and divide the row into four sections. The number of 1's in each section are the values for $x_1, x_2, x_3, x_4$. The sections are separated by placing some 0's amongst the 1's. For example, the solution 3+8+20+8=39 corresponds to:

111011111111011111111111111111111011111111,

and the solution 30+0+0+9=39 corresponds to:

111111111111111111111111111111000111111111.

• Thanks, that was really useful. – Jeybe Jul 10 '14 at 16:12
• Sorry but i can't figure out how to solve the second case – Jeybe Jul 10 '14 at 22:34
• Yeah, case II is harder. The generating function trick works, but I'm trying to think of a more traditional combinatorial approach. :/ – G Tony Jacobs Jul 11 '14 at 15:20

For Part II, you can substitute $y_i=x_i-3$ for $1\le i\le4$. (Notice that $x_1+x_2+x_3\le36$, so $x_4\ge3$.)

Then $x_1+x_2+x_3+x_4=39$ gives

$y_1+y_2+y_3+y_4=27$ where $y_i\ge0$ for $1\le i\le4$ and $y_i\le9$ for $1\le i\le3$.

As in Part I, the number of solutions to this equation in nonnegative integers is given by $\binom{30}{3}$;

so if we subtract the number of solutions with $y_i\ge10$ for some $i$ with $1\le i\le3$ we get

$\;\;\;\;\;\displaystyle\binom{30}{3}-3\binom{20}{3}+3\binom{10}{3}$

(since, for example, there are $\binom{20}{3}$ solutions with $y_1\ge10$

and there are $\binom{10}{3}$ solutions with $y_1\ge10$ and $y_2\ge10$).

Assume $a$ as a real number, such that $0<a <1$

I.
The number of integral solutions should be the same as:

The coefficient of $a ^ {39}$ in
$\left(1+a + a^{2} + a^{3} + ... \right)^4$

Which is coeffient of $a^{39}$ in the series for $\left(1-a\right)^{-4}$

which is $\binom{39+4}{3}$

II.
Answer is same as the coefficient of $a ^ {39}$ in
$\left(a^{3} + a^{4} + a^{5} + a^{6} + ... + a^{12} \right)^3\left(1+a + a^{2} + a^{3} + ... \right)$

= coeffient of $a^{30}$ in
$\left(1+a+a^2+a^3+ ... + a^{9} \right)^3\left(1+a + a^{2} + a^{3} + ... \right)$

= coeffient of $a^{30}$ in
$\left(1-a^{10}\right)^3\left(1-a\right)^{-4}$

= coeffient of $a^{30}$ in
$\left(1-3a^{10} + 3a^{20} -a^{30}\right)\left(1-a\right)^{-4}$

Since $\left(1-a\right)^{-4}$ is
$1 +\binom{3+1}{3}a+\binom{3+2}{3}a^3+\binom{3+3}{3}a^3+ ...$

Ignore all powers more than 30

Answer $= \binom{33}{3}-3\binom{23}{3}+3\binom{13}{3}-\binom{3}{3}$