Table of Contents

**INCLUSION And EXCLUSION**

Let us begin with a problem we have made inclusion and exclusion alternately: In a sports club with 54 members, 34 play tennis, 22 play golf, and 10 play both. There are 11 members who play handball, of whom 6 play tennis also, 4 play golf also, and 2 play both tennis and golf. How many play none of the three sports?

To answer this, let S represent the set of all members of the club. Let T represent the set of tennis playing members, G represent the set of golf playing members, and H represent the set of handball playing members. Let us represent the number of elements in A by |A|. Consider the number |S| – |T| – |G| – |H|. Is this the answer to the problem? No, because those who are in T as well as G have been subtracted twice. To compensate for this double subtraction, we may now consider the number |S| – |T| – |G| – |H| + |T⋂H| + |G⋂H| + |H⋂T|. Is this the answer? No, because those playing all the three games have been subtracted thrice and then added thrice. But those members have to be totally excluded also. Hence, we now consider the number |S| – |T| – |G| – |H| + |T⋂H| + |G⋂H| + |H⋂T| – |T⋂G⋂H|. This is the correct answer. This reduces to 54 – 34 – 22 – 11 + 10 + 6 +4 – 2 = 5.

To solve this problem we have made inclusions and exclusions alternately to arrive at the correct answer. This is a simple case of the **principle of inclusion and exclusion**. It is also known as the **sieve principle** because we subject the objects to sieves of a progressively finer mesh to arrive at a certain grading.

Let us state and prove this principle now.

**Theorem: The Inclusion-Exclusion Formula**

Let A_{1}, A_{2}, …, A_{n} be n sets in a universal set ξ (or U) consisting of N elements. Let S_{k} denote the sum of the sizes of all the sets formed by intersecting k of the A_{i}’s at a time. Then the number of elements in none of the sets is given by

\[\left| A_{1}^{c}\cap A_{2}^{c}\cap ….\cap A_{n}^{c} \right|=N-{{S}_{1}}+{{S}_{2}}-{{S}_{3}}+…+{{\left( -1 \right)}^{k}}{{S}_{k}}+…+{{\left( -1 \right)}^{n}}{{S}_{n}}\]

**Proof:**

The proof is on the same lines as the counting argument given in the ‘sports club’ example at the beginning of this section. If an element is in none of the A_{i}s, then it should be counted only once, as part of ‘N’ in the RHS of the formula above. It is not counted in any of the S_{k}s since it is in none of the A_{i}s.

Next, an element in exactly one A_{i}, say A_{r}, is counted once in N, and once in S1, and in none of the other S_{k}s. So the net count is 1−1 = 0.

Finally, take an element x in exactly m of the A_{i}s. This is counted once in N, m times in S_{1}, C(m, 2) times in S_{2} (since x is in C(m, 2) intersections A_{i}∩A_{j}),…, C(m, k) times in S_{k} for k ≤m. x is not counted in any S_{k} for k > m. So the net count of x in the RHS of the formula is 1− C(m,1) + C(m,2) − … + (−1)^{k} C(m, k) + … + (−1)^{m} C(m, m) = 0

So the only elements that have a net count of 1 in the RHS are those in \underset{i=1}{\overset{n}{\mathop{\cap }}}\,A_{i}^{c}.The rest have a net count of 0. Hence the formula.

**Corollary:** Given the situation of Theorem

\[\left| {{A}_{1}}\cup {{A}_{2}}\cup …\cup {{A}_{n}} \right|={{S}_{1}}-{{S}_{2}}+…+{{\left( -1 \right)}^{k-1}}{{S}_{k}}+…+{{\left( -1 \right)}^{n-1}}{{S}_{n}}\]

Example 01 |

**How many ways are there to distribute r distinct objects into five (distinct) boxes with i) at least one empty box? ii) no empty box (r ≥ 5)?**

**Solution:**

Let U be all possible distributions of r distinct objects into five boxes. Let A_{i} denote the set of possible distributions with the ith box being empty.

i) Then the required number of distributions with at least one empty box is \left| {{A}_{1}}\cup {{A}_{2}}\cup ...\cup {{A}_{5}} \right|. We have N = 5^{r}. Also, \left| {{A}_{i}} \right|={{\left( 5-1 \right)}^{r}}, the number of distributions in which the objects are put into one of the remaining four boxes. Similarly, \left| {{A}_{i}}-{{A}_{j}} \right|={{\left( 5-2 \right)}^{r}}, and so forth. Thus, by the corollary above, we have

\[\left| {{A}_{1}}\cup {{A}_{2}}\cup …\cup {{A}_{5}} \right|={{S}_{1}}-{{S}_{2}}+{{S}_{3}}-{{S}_{4}}+{{S}_{5}}\]

\[=C\left( 5,1 \right){{4}^{r}}-C\left( 5,2 \right){{3}^{r}}+C\left( 5,3 \right){{2}^{r}}-C\left( 5,4 \right){{1}^{r}}+0\]

\[ii) \left| A_{1}^{c}\cap A_{2}^{c}\cap …\cap A_{5}^{c} \right|={{5}^{r}}-C\left( 5,1 \right){{4}^{r}}+C\left( 5,2 \right){{3}^{r}}-C\left( 5,3 \right){{2}^{r}}+C\left( 5,4 \right){{1}^{r}}\]

Example 02 |

**How many solutions are there to the equation x + y + z + w = 20, where x, y, z, w are positive integers such that x ≤ 6, y ≤ 7, z ≤ 8, w ≤ 9?**

**Solution:**

To use inclusion-exclusion, we let the objects be the solutions (in positive integers) of the given equation. A solution is in A1 if x > 6, in A2 if y > 7, in A3 if z > 8 and in A4 if w > 9. Then what we need is \left| A_{1}^{c}\cap A_{2}^{c}\cap A_{3}^{c}\cap A_{4}^{c} \right|.

Now, to find the local number of positive solutions to the given equation, we rewrite it as x_{1} + y_{1} + z_{1} + w_{1} = 16, where x_{1} = x + 1, y_{1} = y + 1, z_{1} = z + 1, w_{1} = w + 1. Any non-negative solution of this equation will be a positive solution of the given equation. So, the number of positive solutions is<br>N = C(16 + 4 – 1, 3) = C(19, 3)

Similarly, |A_{1}| = C(13, 3), |A_{2}| = C(12, 3), |A_{3}| = C(11, 3), |A_{4}| = C(10, 3), |A_{1}⋂A_{2}| = C(6, 3), |A_{2}⋂A_{3}| = C(5, 3), and so on.

Note that for a solution to be in 3 or more Ai’s, the sum of the respective variables would exceed 20, which is not possible

By inclusion-exclusion, we obtain

\[\left| A_{1}^{c}\cap A_{2}^{c}\cap A_{3}^{c}\cap A_{4}^{c} \right|=C\left( 19,3 \right)-C\left( 13,3 \right)-C\left( 12,3 \right)-C\left( 11,3 \right)-C\left( 10,3 \right)\]

\[+C\left( 6,3 \right)+C\left( 5,3 \right)+C\left( 4,3 \right)+C\left( 4,3 \right)+C\left( 3,3 \right)=217\]

Example 03 |

**How many numbers from 0 to 999 are not divisible by either 5 or 7?**

**Solution:**

Let the objects be the integers 0, 1, …, 999. Let A_{1} be the set of numbers divisible by 5, and A_{2} the set of numbers divisible by 7. Now, N = 1000, |A_{1}| = 200, |A_{2}| = 143 and |A_{1}⋂A_{2}| = 29. So, by inclusion-exclusion theorem, the answer is 1000 – 200 – 143 + 29 = 686.

<< Previous TopicCounting and Combinatorics |
Next Topic >>Pigeonhole |