Intuition for inclusion exclusion

Printable View

October 9th 2011, 04:23 AM
terrorsquid

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.
October 9th 2011, 04:38 AM
Plato

Re: Intuition for inclusion exclusion

Quote:

Originally Posted by terrorsquid

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~?$
October 9th 2011, 04:48 AM
terrorsquid

Re: Intuition for inclusion exclusion

Quote:

Originally Posted by Plato

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.
October 9th 2011, 05:12 AM
Plato

Re: Intuition for inclusion exclusion

Quote:

Originally Posted by terrorsquid

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.
October 9th 2011, 05:13 AM
terrorsquid

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

BTW: this is not a problem for inclusion/exclusion.

My question asks to apply the principles of inclusion-exclusion to solve them :S
October 9th 2011, 06:13 AM
Plato

Re: Intuition for inclusion exclusion

Quote:

Originally Posted by terrorsquid

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}}$
October 9th 2011, 06:28 AM
terrorsquid

Re: Intuition for inclusion exclusion

Maybe that's why I don't understand what's going on with the inclusion exclusion :D