4
$\begingroup$

Use Inclusion-Exclusion to determine the number of integer solutions to the equation

$$x_1+x_2+x_3+x_4=14$$

Where $0{\leq}x_1{\leq}8; 0{\leq}x_2{\leq}5; x_3, x_4{\geq}0$.

My thought process:

I can disregard the last two restrictions because those two are given since the combination gives the number of nonnegative integer solutions.

Have

A= # solutions given $0{\leq}x_1{\leq}8$

B= # solutions given $0{\leq}x_2{\leq}5$

Which means $A^c$ is the number of solutions for $9{\leq}x_1{\leq}14$.

*Would the possible solutions for $A^c$ then be partitioning 9+1+1+1+1+1=14? Or rather, give us ${6+4-1\choose 4-1}$?

*And $B^c$ is the number of solutions for $6{\leq}x_2{\leq}14$, so we would have $6+1+1+1+1+1+1+1+1=14$ or ${9+4-1\choose 4-1}$?

If $x_1{\gt8}$ and $x_2{\gt}5$ then for $A^c{\cap}B^c$ we have $$9+6+0+0=15$$ or similar and we see there are no possible solutions for $x_1+x_2+x_3+x_4=14$.

Then $$A{\cap}B = A{\cup}B-A^c-B^c+A^c\cap B^c$$ $$={14+4-1\choose 4-1} - {6+4-1\choose 4-1}- {9+4-1\choose 4-1} +0$$ $$=376$$

*I'm a little nervous about my reasoning for $A^c$ and $B^c$. I always end up missing some crucial step in these kinds of problems. - resolved in comments

$\endgroup$
3
$\begingroup$

You have the right idea, but you’re a little off. The solutions that have $x_1\ge 9$ correspond to the non-negative solutions of $y+x_2+x_3+x_4=5$, where $y=x_1-9$, so there are $\binom{5+4-1}{4-1}$ of them, not $\binom{6+4-1}{4-1}$. Similarly, there are $\binom{8+4-1}{4-1}$ solutions with $x_2\ge 6$. The rest is fine.

$\endgroup$
  • $\begingroup$ Thank you!! I have a hard time wrapping my head around counting concepts. $\endgroup$ – Karen M. Feb 23 '15 at 22:19
  • $\begingroup$ @Karen: You’re welcome! You don’t seem to be doing too badly with them, judging by the questions that you’ve asked. $\endgroup$ – Brian M. Scott Feb 23 '15 at 22:21

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.