Results 1 to 2 of 2

Thread: 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

    $\displaystyle X_1 + X_2 + $ .... $\displaystyle + X_6 = 45 $ with the conditions $\displaystyle X_j < 6$, $\displaystyle j = 1,2,3,4.$

    My Answer:

    Step 1: Find solutions with no conditions first.

    $\displaystyle \binom{n+k-1}{k}$ $\displaystyle = \binom{6+45-1}{45}$ $\displaystyle = \binom{50}{45}$

    Step 2: Get solutions for less than conditions

    Condition 1: $\displaystyle X_j < 6 \Rightarrow X_j \leq 5 \Rightarrow X_j + 5$

    Let:

    $\displaystyle X_j = V_j + 5$

    So: $\displaystyle (V_1 + 5) + (V_2 + 5) + (V_3 + 5) + (V_4 + 5) + X_5 + X_6 = 45$

    $\displaystyle V_1 + V_2 + V_3 + V_4 + X_5 + X_6 = 25$

    Therefore Solutions:$\displaystyle \binom{6+25-1}{25} = \binom{30}{25}$

    THEREFORE FINAL SOLUTION $\displaystyle = \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
    21,742
    Thanks
    2814
    Awards
    1
    Actually it is not correct.
    I suspect the actual answer will surprise you: $\displaystyle \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 $\displaystyle 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: Apr 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: 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