Results 1 to 7 of 7

Math Help - Intuition for inclusion exclusion

  1. #1
    Member
    Joined
    Jul 2011
    Posts
    196

    Intuition for inclusion exclusion

    I have been doing inclusion exclusion questions and while, for the most part, I can see what I am doing in each step and which subsets I am adding/removing, the following type of question I can't seem to see exactly what is happening. I know how to do them, but I am just following a pattern that I have seen from doing a number of them - I can't visualise which subsets I am adding/removing as I do them. I was wondering if someone could tell me what's happening exactly as I do this problem:

    Find the number of solutions for the equation x_1 + x_2 + ... + x_9 = 24, where 4\leq x_1,x_2<9

    So, when x_1 and x_2 are 4 or greater, then the total number of solutions will be:

    {9+24-8-1\choose 9-1} = {24\choose 8}

    I can see what is going on here, every set that includes a value for x_1 and x_2 less than 4 is excluded. The next steps I do, I get a bit confused what is happening and why...

    Suppose: x_1 OR x_2 < 9 - 4 = 5

    Then: x_1 + x_2 + ... + x_9 = 16 - 5 = 11

    There are two choices so, there are 2\times {19\choose 8} ways this can happen.

    Subtract this from the total: {24\choose 8} - 2\times {19\choose 8}

    Finally I need to add the instance when both x_1 and x_2 are < 5 to give the final answer:

    {24\choose 8} - 2\times {19\choose 8}+{14\choose 8}

    I can do these questions, it's just I am doing them without knowing what's going on exactly. So, if the question format was changed up a bit, I might struggle. What has been counted/over-counted at what stage etc.?

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1581
    Awards
    1

    Re: Intuition for inclusion exclusion

    Quote Originally Posted by terrorsquid View Post
    Find the number of solutions for the equation x_1 + x_2 + ... + x_9 = 24, where 4\leq x_1,x_2<9.
    Do you understand how \binom{20+9-1}{20} is the number of solutions in which x_1\ge 4~?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jul 2011
    Posts
    196

    Re: Intuition for inclusion exclusion

    Quote Originally Posted by Plato View Post
    Do you understand how \binom{20+9-1}{20} is the number of solutions in which x_1\ge 4~?
    Yes, I feel comfortable with the initial step. If only x_1 \geq 4 then x_1 + x_2 + ... + x_9 = 24 - 1\times 4 = 20

    \therefore the total number of solutions = {28\choose 20} or {28\choose 8} ... same thing.
    Last edited by terrorsquid; October 9th 2011 at 05:11 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1581
    Awards
    1

    Re: Intuition for inclusion exclusion

    Quote Originally Posted by terrorsquid View Post
    Yes, I feel comfortable with the initial step. If only x_1 \geq 4 then x_1 + x_2 + ... + x_9 = 24 - 1\times 4 = 20
    \therefore the total number of solutions = {28\choose 20} or {28\choose 8} ... same thing.
    Of those \binom{11+9-1}{11} have x_2\ge 9.
    So remove that number from \binom{20+9-1}{20}~.

    BTW: this is not a problem for inclusion/exclusion.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jul 2011
    Posts
    196

    Re: Intuition for inclusion exclusion

    Why do we multiply the second step by two because there are two choices and we don't multiply the first step by two where x_1 and x_2 are 4?

    Quote Originally Posted by Plato View Post
    BTW: this is not a problem for inclusion/exclusion.
    My question asks to apply the principles of inclusion-exclusion to solve them :S
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1581
    Awards
    1

    Re: Intuition for inclusion exclusion

    Quote Originally Posted by terrorsquid View Post
    My question asks to apply the principles of inclusion-exclusion to solve them :S
    I have no intention of debating your instructor/textbook.
    If the question had asked for x_1\ge 4\text{ or }x_9>8 or even x_1\ge 4\text{ and }x_9>8 then clearly inclusion/exclusion would be called for. However, as stated this is a mixed problem.

    I have done it in three different ways getting the same answer each time.
    Here is a straightforward counting method:
    \sum\limits_{k = 0}^8 {\binom{27 - k}{20 - k}}  = {\text{3032523}}
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Jul 2011
    Posts
    196

    Re: Intuition for inclusion exclusion

    Maybe that's why I don't understand what's going on with the inclusion exclusion
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Inclusion/Exclusion
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 19th 2011, 03:49 AM
  2. inclusion & exclusion help
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: May 14th 2010, 09:57 AM
  3. Inclusion-Exclusion
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 15th 2010, 02:44 PM
  4. Inclusion/Exclusion
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 3rd 2009, 08:46 AM
  5. inclusion/exclusion
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 18th 2008, 10:31 PM

Search Tags


/mathhelpforum @mathhelpforum