inclusion-exclusion question check solution help

Oct 2007
517
6
Santiago
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})\)
 
Last edited: