Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
I am finding it very difficult to understand the inclusion exclusion principle and how to apply it in even simple combinatorics problems.
Can someone please supply the intuition behind this principle with the help of a simple problem and tell where I should use this principle?
In general, the principle is to count everything without worrying if anything is double counted. Then subtract any double counting that may occur. If you throw away anything more than once (double counting the throw-away's) then add these back and so on. All this double counting etc. is best expressed in the language of intersection of sets.
In response to OP's request
Here is a simple example: How many numbers (exluding zero) less than 33are divisible by $2$, $3$ or $5$?
There are 16 numbers divisible by 2: 2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32 There are 10 numbers divisible by 3: 3,6,9,12,15,18,21,24,27,30 There are 6 numbers divisible by 5: 5, 10, 15,20,25,30
There are 5 numbers divisible by 2 and 3: 6, 12, 18,24,30 There is 3 number divisible by 2 and 5: 10, 20, 30 There is 2 number divisible by 3 and 5: 15, 30
There is 1 number divisible by all 3: 30
So if you add all the numbers divisible by 2 ,3 or 5 without worrying about double counting you get $$16+10+6 = 32$$ Numbers divisible by two or more get counted twice, so we have to subtract $5 + 3 + 2 = 10$
Now the number 30 gets thrown out so add it back So the final answer is $32 - 10 + 1 = 23$
Here they are: $$1,3,5,6,7,9,10,11,12,13,15,17,18,19,20,21,23,24,25,27,29,30, 31$$
Suppose we wanted to, out of the integers from $1$ to $12$, count how many are divisible by either $2, 3,$ or $4$.
To start, we might try counting how many are divisible by $2$, how many by $3$, and how many by $4$, and adding these up: there are $6$ integers from $1$ to $12$ divisible by $2$, $4$ divisible by $3$, and $3$ divisible by $4$, so we might guess that the desired number is $6+4+3=13.$ But that can't be right, because $13>12$.
The error in this first approach is that we counted some numbers twice - for example, $6$ is divisible by both $2$ and $3$. To get a better guess, we could subtract the number if integers divisible by two of $2,3,$ and $4$. There are $2$ integers from $1$ to $12$ divisible by both $2$ and $3$, $3$ divisible by $2$ and $4$, and one divisible by $3$ and $4$, so now we might guess that there are $13 - 2 - 3 - 1 = 7$ integers with the desired property.
But, that's still not right: $12$ is divisible by $2,3,$ and $4$, so, even though we counted it three times at first, we have now overcorrected - we subtracted one for it being divisible by $2$ and $3$, one for it being divisible by $3$ and $4$, and one for it being divisible by $2$ and $4$. So, to actually count $12$ in our answer, we need to add one to get a final (correct) answer of $7+1=8$.
In general, you will use inclusion-exclusion whenever you have some big set $X$ (in our case, the integers from $1$ to $12$), and some collection $A_1,A_2,\dots A_n$ of subsets of $X$ (in our case, $A_1$ was the integers divisible by $2$, $A_2$ was the ones divisible by $3$, and $A_3$ was the one divisible by $4$), and you want to find the size of the union of all of the $A_i.$ To do this, you first add up the sizes of the individual subsets, then subtract the sum of the sizes of their pairwise intersections, then add back in the sum of the sizes of the intersections of $3$ of the $A_i$, and so on, always adding intersections of odd numbers of subsets and subtracting the even intersections.
Symbolically speaking, we have $$\left|\bigcup_{i=1}^n A_i \right| = \sum_{i=1}^n |A_i| - \sum_{i,j=1}^{n} \left|A_i\cap A_j \right| + \sum_{i,j,k=1}^{n} \left|A_i\cap A_j\cap A_k \right| - \cdots \pm \left|\bigcap_{i=1}^{n} A_i\right|,$$ where the last sign depends on the parity of $n$, and the inner sums range only over distinct $i,j,k$.
