Thread: inclusion-exclusion question check solution help

1. inclusion-exclusion question check solution help

Hey guys, can someone please check my solution if its correct for the following question thankyou!!!

QUESTION:

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

$\displaystyle X_1 + X_2 + X_3 + X_4 + X_5 = 73$ with the conditions $\displaystyle X_2 \leq 30$, $\displaystyle 5 \leq X_3 \leq 40$, $\displaystyle X_4 \geq 7$.

MY SOLUTION

STEP 1: Solutions for greater than conditions.

Condition 1: $\displaystyle 5 \leq X_3 = X_3 \geq 5$
Condition 2: $\displaystyle X_4 \geq 7$

Let

$\displaystyle X_3 = Y_3 + 5$
$\displaystyle X_4 = Y_4 +7$

Therefore:

$\displaystyle X_1 + X_2 + (Y_3 + 5) + (Y_4 + 7) + X_5 = 73$
$\displaystyle X_1 + X_2 + Y_3 + Y_4 + X_5 = 61$

So $\displaystyle \binom{n+k-1}{k} = \binom{5+61-1}{61} = + \binom{65}{61}$

STEP 2: Solutions for less than conditions.

Condition 1: $\displaystyle X_2 \leq 30 \Rightarrow X_2 \geq 31$
Condition 2: $\displaystyle 5 \leq X_3 \Rightarrow X_3 = Y_3 + 5$

$\displaystyle \Rightarrow 5 \leq Y_3 + 5 \leq 40$ $\displaystyle = 0 \leq Y_3 \leq 35 =$ $\displaystyle Y_3 \leq 35 \Rightarrow Y_3 \geq 36$

Condition 1:

Let

$\displaystyle X_2 = Y_2 + 31$

Therefore:

$\displaystyle X_1 + (Y_2 + 31) + X_3 + X_4 + X_5 = 61$
$\displaystyle X_1 + Y_2 + X_3 + X_4 + X_5 = 30$

So $\displaystyle \binom{n+k-1}{k} = \binom{5+30-1}{30} = - \binom{34}{30}$

Condition 2:

Let

$\displaystyle X_3 = Y_3 + 36$

Therefore:

$\displaystyle X_1 + X_2 + (Y_3 + 36) + X_4 + X_5 = 61$
$\displaystyle X_1 + X_2 + Y_3 + X_4 + X_5 = 25$

So $\displaystyle \binom{n+k-1}{k} = \binom{5+25-1}{25} = - \binom{29}{25}$

Now we need to find solutions for

$\displaystyle Y_2, Y_3 \Rightarrow Y_2 + 31, Y_3 + 36$

Therefore:

$\displaystyle X_1 + (Y_2 + 31) + (Y_3 + 36) + X_4 + X_5 = 61$
$\displaystyle X_1 + Y_2 + Y_3 + X_4 + X_5 = -6$

NO SOLUTIONS SINCE RHS IS A NEGATIVE INTEGER.......

therefore final solutions:

$\displaystyle \binom{65}{61} -(\binom{34}{30} + \binom{29}{25})$

2. That looks right to me.

3. Originally Posted by awkward
That looks right to me.
Awesome! thank you...