Results 1 to 3 of 3

Math Help - Inclusion - Exclusion Problem

  1. #1
    Newbie
    Joined
    Apr 2010
    Posts
    13

    Inclusion - Exclusion Problem

    Hi.

    I am having some difficulty with this inclusion-exclusion problem, and I would love some help.

    ************************************************** ******

    Determine the number of integer solutions to X1 + X2 + X3 + X4 = 19, where -5 ≤ Xi ≤ 10, for all 1 ≤ i ≤ 4.

    What I have done is create another equation to solve, since we already know how to solve non-negative integer solutions, C(n + r - 1, r), but I don't know whether I have done this step right.

    Let Y1 + Y2 + Y3 + Y4 = 24, where Xi ≤ 15, Yi = Xi + 5 for all 1 ≤ i ≤ 4. IS THIS RIGHT?

    If this is right, I am pretty sure I know how to go on from here, but I am unsure of this particular step.

    Thanks in advance
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,712
    Thanks
    1642
    Awards
    1
    Quote Originally Posted by purakanui View Post
    Determine the number of integer solutions to X1 + X2 + X3 + X4 = 19, where -5 ≤ Xi ≤ 10, for all 1 ≤ i ≤ 4.
    What I have done is create another equation to solve, since we already know how to solve non-negative integer solutions, C(n + r - 1, r), but I don't know whether I have done this step right.
    Let Y1 + Y2 + Y3 + Y4 = 24, where Xi ≤ 15, Yi = Xi + 5 for all 1 ≤ i ≤ 4.
    Your approach is correct. The difficulty is that upper limit of 10.
    This is one case where generating functions are useful.
    Expand the expression \left( {\sum\limits_{k = 0}^{15} {x^k } } \right)^4 . The coefficient of x^{24} is the answer.

    But if you must use inclusion/exclusion then the answer is:
    \binom{24+4-1}{4-1}-\left( {\sum\limits_{k = 16}^{24} {4 \cdot \binom{26-k}{2}} } \right)
    We remove all solutions in which a variable is at least 16.
    Last edited by Plato; April 14th 2010 at 12:32 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2010
    Posts
    13

    Thanks for your help

    I have used an online expander (the coefficient is 2265, do you blame me!) which is the same answer I got from the other approach (the inclusion exclusion way).

    The Y1 + Y2 + Y3 + Y4 = 24 was wrong because of Yi = Xi + 5, however there are 4 Values, so I should of added (5 x 4) = 20, so Y1 + ... + Y4 = 39.

    Thanks for your help, we are just covering generating functions now, and it's good to see both sides.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. A tough Inclusion-Exclusion problem..or...something else
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: July 16th 2010, 05:51 PM
  2. Inclusion-exclusion math problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 6th 2009, 08:28 PM
  3. problem on inclusion exclusion
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: November 23rd 2009, 01:10 AM
  4. help with inclusion/exclusion problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 12th 2009, 05:41 PM
  5. Inclusion Exclusion Dice Problem
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: August 30th 2009, 05:42 AM

Search Tags


/mathhelpforum @mathhelpforum