Results 1 to 7 of 7

Thread: 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 $\displaystyle x_1 + x_2 + ... + x_9 = 24$, where $\displaystyle 4\leq x_1,x_2<9$

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

    $\displaystyle {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 $\displaystyle x_1$ and $\displaystyle x_2$ less than 4 is excluded. The next steps I do, I get a bit confused what is happening and why...

    Suppose: $\displaystyle x_1$ OR $\displaystyle x_2$ < 9 - 4 = 5

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

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

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

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

    $\displaystyle {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
    21,743
    Thanks
    2814
    Awards
    1

    Re: Intuition for inclusion exclusion

    Quote Originally Posted by terrorsquid View Post
    Find the number of solutions for the equation $\displaystyle x_1 + x_2 + ... + x_9 = 24$, where $\displaystyle 4\leq x_1,x_2<9$.
    Do you understand how $\displaystyle \binom{20+9-1}{20}$ is the number of solutions in which $\displaystyle 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 $\displaystyle \binom{20+9-1}{20}$ is the number of solutions in which $\displaystyle x_1\ge 4~?$
    Yes, I feel comfortable with the initial step. If only $\displaystyle x_1 \geq 4$ then $\displaystyle x_1 + x_2 + ... + x_9 = 24 - 1\times 4 = 20$

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

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,743
    Thanks
    2814
    Awards
    1

    Re: Intuition for inclusion exclusion

    Quote Originally Posted by terrorsquid View Post
    Yes, I feel comfortable with the initial step. If only $\displaystyle x_1 \geq 4$ then $\displaystyle x_1 + x_2 + ... + x_9 = 24 - 1\times 4 = 20$
    $\displaystyle \therefore$ the total number of solutions = $\displaystyle {28\choose 20}$ or $\displaystyle {28\choose 8}$ ... same thing.
    Of those $\displaystyle \binom{11+9-1}{11}$ have $\displaystyle x_2\ge 9$.
    So remove that number from $\displaystyle \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 $\displaystyle x_1$ and $\displaystyle 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
    21,743
    Thanks
    2814
    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 $\displaystyle x_1\ge 4\text{ or }x_9>8$ or even $\displaystyle 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:
    $\displaystyle \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: Jan 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: Apr 15th 2010, 02:44 PM
  4. Inclusion/Exclusion
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 3rd 2009, 08:46 AM
  5. inclusion/exclusion
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Nov 18th 2008, 10:31 PM

Search Tags


/mathhelpforum @mathhelpforum