4
$\begingroup$

Consider the equation $x_1+x_2+x_3+x_4+x_5=10$.
How many non-negative integer solutions if $x_1 > x_2$?

Apparently counting $x_1$ and $x_2$ one by one is too slow, and impractical if the sum is not 10 but 100 instead. Is there a general way to solve this kind of problems?

$\endgroup$
  • 1
    $\begingroup$ There are infinitely many non-integer solutions. You probably mean integer solutions. In that case, you may rewrite equation as $x_1'+2x_2+x_3+x_4+x_5 = 9$. $\endgroup$ – Abstraction Nov 15 '16 at 10:59
  • $\begingroup$ non-integer solutions are $\infty^5$ . Are you looking for integral or non integral solutions ? and maybe for integral non-negative? $\endgroup$ – G Cab Nov 15 '16 at 11:00
  • $\begingroup$ @Abstraction I'm sorry for the typo. I meant non-negative integers :( $\endgroup$ – Lon Edwards Nov 15 '16 at 11:10
2
$\begingroup$

Hint. By Stars-and-Bars, the number of non-negative integer solutions of $$x_1+x_2+x_3+x_4+x_5=10$$ is $\binom{10+(5-1)}{5-1}$. The numbers of non-negative integer solutions of $$k+k+x_3+x_4+x_5=10$$ that is $$x_3+x_4+x_5=10-2k$$ for $k=0,1,\dots ,5$ is $\binom{10-2k+(3-1)}{3-1}$. Can you take it from here?

Finally you should find that the number you are looking for is $420$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ That means by finding out $\binom{14}{4}$ first, and subtract by the number of solutions for $x_3+x_4+x_5=10-2k$, since if two integers have different values it must mean that one of them is larger than the other. Is my interpretation correct? $\endgroup$ – Lon Edwards Nov 15 '16 at 11:20
  • $\begingroup$ @Lon Edwards Yes. Then after the subtraction you have to divide the result by two. In one half $x_1>x_2$, in the other one $x_2>x_1$. $\endgroup$ – Robert Z Nov 15 '16 at 11:28

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.