1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

Does this help you think about part II?

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

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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