The Principal of Inclusion and Exclusion with Examples

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₁, A₂, …, 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_is, 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_ks since it is in none of the A_is.

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_ks. So the net count is 1−1 = 0.

Finally, take an element x in exactly m of the A_is. This is counted once in N, m times in S₁, C(m, 2) times in S₂ (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₁ + y₁ + z₁ + w₁ = 16, where x₁ = x + 1, y₁ = y + 1, z₁ = z + 1, w₁ = 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₁| = C(13, 3), |A₂| = C(12, 3), |A₃| = C(11, 3), |A₄| = C(10, 3), |A₁⋂A₂| = C(6, 3), |A₂⋂A₃| = 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₁ be the set of numbers divisible by 5, and A₂ the set of numbers divisible by 7. Now, N = 1000, |A₁| = 200, |A₂| = 143 and |A₁⋂A₂| = 29. So, by inclusion-exclusion theorem, the answer is 1000 – 200 – 143 + 29 = 686.

<< Previous Topic Counting and Combinatorics

Next Topic >> Pigeonhole

;