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.

Find the number of soultion to this equation: $$x_1+x_2+x_3+x_4+x_5+x_6= 20$$ $$1 <= x_1, x_2, \ldots, x_6 \leq 4 $$

I know that at the start we need to define:

$y_1=x_1-1$

$y_2=x_2-1$

$y_3=x_3-1$

$y_4=x_4-1$

$y_5=x_5-1$

$y_6=x_6-1$

So we end up with this:

$$y_1+y_2+y_3+y_4+y_5+y_5=14$$

and now I need to use the "Inclusion–exclusion principle" but how?

share|improve this question
    
Did you mean to say that each $x_1, \ldots, x_6$ is an integer between 1 and 4 inclusive? –  Sasha Sep 28 '13 at 17:57
    
For the start, we want $y_i=x_i-1$. –  André Nicolas Sep 28 '13 at 17:58
    
@Sasha Yes that what I mean –  Gil Sep 28 '13 at 18:00
    
I would suggest $z_i = 4-x_i$ instead. –  Calvin Lin Sep 28 '13 at 18:02
    
@CalvinLin What is z? –  Gil Sep 28 '13 at 18:06
show 1 more comment

1 Answer 1

up vote 3 down vote accepted

For each solution set $x_i$, we consider the change of variables $ z_i = 4 - x_i$.

Then, the conditions become $z_1 + z_2 + z_3 + z_4 + z_5 + z_6 = 4$ and $0 \leq z_i \leq 3$.

Ignoring the upper bound on $z_i$, there are ${ 6+4 - 1 \choose 4 } =126$ solutions by the technique Stars and Bars.

There are 6 solutions where (at least) one of $z_i$ is strictly greater than 3. By the Inclusion and Exclusion principle, there are 120 solutions in total.


Of course, you could apply the technique PIE directly initially, but that is slightly tedious. Though that can be good practice too. Let $P_i$ be the sets of solutions where $x_i \geq 5$. Observe that at most 3 of them can be greater than or equal to 5.

Recall that the number of positive integer solutions by stars and bars to

$$ x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = n $$

is ${n-1 \choose 5} $. Let's evaluate $|P_i|, |P_i \cap P_j|$ and $|P_i \cap P_j \cap P_k|$.

$P_1$ corresponds to solutions with $x_1 \geq 5$. using the change of variables $a_1 = 4 + x_1$, we thus have

$$ a_1 + x_2 + x_3 + x_4+ x_5 + x_6 = 16. $$

There are ${ 15 \choose 5}$ solutions in this case.

Similarly, $|P_i \cap P_j| = {11 \choose 5}, |P_i \cap P_j \cap P_k | = {7 \choose 5}$.

Hence, by PIE,

$$|\cup P_i | = {6 \choose 1} {15 \choose 5} - { 6\choose 2} { 11 \choose 5} + {6 \choose 3} { 7 \choose 5} = 11508.$$

Hence, the number of solutions is ${19 \choose 5 } - 11508 = 120 $ (Phew!)

share|improve this answer
add comment

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.