Results 1 to 3 of 3

Math Help - 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:

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

    MY SOLUTION

    STEP 1: Solutions for greater than conditions.

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

    Let

    X_3 = Y_3 + 5
    X_4 = Y_4 +7

    Therefore:

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

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

    STEP 2: Solutions for less than conditions.

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

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

    Condition 1:

    Let

     X_2 = Y_2 + 31

    Therefore:

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

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

    Condition 2:

    Let

     X_3 = Y_3 + 36

    Therefore:

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

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

    Now we need to find solutions for

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

    Therefore:

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

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

    therefore final solutions:

    \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: April 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: February 8th 2010, 06:39 AM
  5. inclusion/exclusion question
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 3rd 2009, 07:31 PM

Search Tags


/mathhelpforum @mathhelpforum