Results 1 to 2 of 2

Math Help - inclusion & exclusion question help

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

    inclusion & exclusion question help

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    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.
    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
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 16th 2010, 11:44 PM
  3. inclusion-exclusion question check solution help
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 16th 2010, 06:16 AM
  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