Results 1 to 3 of 3

Thread: inclusion-exclusion question check solution help

  1. #1
    Super Member
    Joined
    Oct 2007
    From
    Santiago
    Posts
    517

    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})$
    Last edited by jvignacio; May 16th 2010 at 01:43 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    That looks right to me.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Oct 2007
    From
    Santiago
    Posts
    517
    Quote Originally Posted by awkward View Post
    That looks right to me.
    Awesome! thank you...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Inclusion and exclusion question
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Apr 19th 2011, 04:00 AM
  2. inclusion & exclusion question help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 17th 2010, 07:49 AM
  3. inclusion-exclusion question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 16th 2010, 11:44 PM
  4. inclusion-exclusion principle question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Feb 8th 2010, 06:39 AM
  5. inclusion/exclusion question
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Nov 3rd 2009, 07:31 PM

Search Tags


/mathhelpforum @mathhelpforum