# inclusion & exclusion question help

• May 17th 2010, 12:02 AM
jvignacio
inclusion & exclusion question help
Hey guys can you check to see if my answer is correct? Thanks!!

Question:
Use inclusion-exclusion to find the number of solutions in the non-negative integers to

$\displaystyle X_1 + X_2 +$ .... $\displaystyle + X_6 = 45$ with the conditions $\displaystyle X_j < 6$, $\displaystyle j = 1,2,3,4.$

Step 1: Find solutions with no conditions first.

$\displaystyle \binom{n+k-1}{k}$ $\displaystyle = \binom{6+45-1}{45}$ $\displaystyle = \binom{50}{45}$

Step 2: Get solutions for less than conditions

Condition 1: $\displaystyle X_j < 6 \Rightarrow X_j \leq 5 \Rightarrow X_j + 5$

Let:

$\displaystyle X_j = V_j + 5$

So: $\displaystyle (V_1 + 5) + (V_2 + 5) + (V_3 + 5) + (V_4 + 5) + X_5 + X_6 = 45$

$\displaystyle V_1 + V_2 + V_3 + V_4 + X_5 + X_6 = 25$

Therefore Solutions:$\displaystyle \binom{6+25-1}{25} = \binom{30}{25}$

THEREFORE FINAL SOLUTION $\displaystyle = \binom{50}{45} - \binom{30}{25}$

Is this correct? thanks
• May 17th 2010, 07:49 AM
Plato
Actually it is not correct.
I suspect the actual answer will surprise you: $\displaystyle \sum\limits_{k = 0}^4 {\left( { - 1} \right)^k\binom{4}{k}\binom{50-6k}{5}}$
That is repeated use of inclusion/exclusion rule.
We find the number of ways that at least one of $\displaystyle X_1,~X_2,~ X_3,~ X_4$ is greater than or equal to six.
Then subtract that from the total.