inclusion & exclusion question help

**jvignacio** · May 17th 2010, 12:02 AM

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

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

My Answer:

Step 1: Find solutions with no conditions first.

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

Step 2: Get solutions for less than conditions

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

Let:

$X_j = V_j + 5$

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

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

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

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

Is this correct? thanks

**Plato** · May 17th 2010, 07:49 AM

Actually it is not correct.
I suspect the actual answer will surprise you: $\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 $X_1,~X_2,~ X_3,~ X_4$ is greater than or equal to six.
Then subtract that from the total.

Thread: inclusion & exclusion question help

LinkBack

Thread Tools

Display

inclusion & exclusion question help

Similar Math Help Forum Discussions

Inclusion and exclusion question

inclusion-exclusion question

inclusion-exclusion question check solution help

inclusion-exclusion principle question

inclusion/exclusion question

Search Tags