Some refresher of motivation(s) and simple applications of the inclusion-exclusion principle. Remember that: (1) We owe a lot to the Indians who taught us how to count. — Albert Einstein. (2) Everything that can be counted is countable, but everything that is countable does not count. — Albert Einstein.

We will derive and apply an important counting formula called the inclusion-exclusion principle. Recall that the addition principle gives a simple formula for counting the number of objects in a union of sets, *provided that the sets do not overlap *(that is, provided that the sets determine a *partition). *The inclusion-exclusion principle gives a formula for the most general of circumstances in which the sets are free to overlap without restriction. The formula is necessarily complicated, but, as a result is more widely applicable.

**1. The Inclusion-Exclusion Principle:**

We know of several examples in which it is easier to make an indirect count of the number of objects in a set rather than to count the objects directly. Below are two more examples:

**Example: **

Count the permutations of in which 1 is not in the first position (that is, ).

We could make a direct count by observing that the permutations with 1 not in the first position can be divided into parts according to which of the integers k from is in the first position. A permutation with k in the first position consists of k followed by a permutation of the element set . Hence, there are permutations of with k in the first position. By the addition principle, there are permutations of with 1 not in the first position.

Alternatively, we could make an indirect count by observing that the number of permutations of with 1 in the first position is the same set as the number of permutations of . Since the total number of permutations of is n!, the number of permutations of in which 1 is not in the first position is .

**Example:**

Count the number of integers between 1 and 600, inclusive, which are not divisible by 6.

We can do this indirectly as follows: The number of integers between 1 and 600 which are divisible by 6 is 600/6 which is equal to 100 since every sixth integer is divisible by 6. Hence, of the integers between 1 and 600 are not divisible by 6.

**Some further notes:**

The rule used to obtain an indirect count in these examples is the following: If A is a subset of a set S, then the number of objects in A equals the number of objects in S minus the number not in A. Recall that

is the complement of A in S: that is, the set consisting of those objects in S which are not in A. The rule can then be written as

, or equivalently, . This formula is the simplest instance of the inclusion-exclusion principle.

We shall formulate the inclusion-exclusion principle in a manner in which it is convenient to apply. As a first generalization of the preceding rule, let S be a finite set of objects, and let and be two “properties” that each object in S may or may not possess. We wish to count the number of objects in S that have neither property nor property . We can do this by first including all objects of S in our count, then excluding all objects that have property and excluding all objects which have property , and then, noting that we have excluded objects having both properties and twice, readmitting all such objects once. We can write this symbolically as follows: Let be the subset of objects of S that have property , and let be the subset of objects of S that have property . Then, consists of those objects of S not having property and let consists of those objects of S not having property . The objects of the set are those having neither property nor property . We then have .

Since the left side of the preceding equation counts the number of objects of S that have neither property nor property , we can establish the validity of this equation by showing that an object with neither of the two properties and makes a net contribution of 1 to the right side, and every other object makes a net contribution of zero. If x is an object with neither of the properties and , it counted among the objects of S, not counted among the objects of or of , and not counted among the objects of . Hence, its net contribution to the right side of the equation is .

If x has only the property , it contributes to the right side, while it has only the property , it contributes to the right side. Finally, if x has both properties and , it contributes to the right side of the equation. Thus, the right side of the equation also counts the number of objects of S with neither property nor property .

More generally, let , , , , be m properties referring to the objects in S, and let

, and

be the subset of objects of S that have property S (and possibly other properties). Then, is the subset of objects that have both properties and (and, possibly others), is the subset of objects which have properties , , and so on. The subset of objects having none of the properties is . The inclusion exclusion principle shows how to count the number of objects in this set by counting objects according to the properties they **do **have. Thus, in this sense, it “inverts” the counting process.

**Theorem 1.1:**

The number of objects of S that have none of the properties , , , is given by:

,

*where the first sum is over all 1-combinations * *of *, *the second sum is over all 2-combinations * *of *, *the third sum is over all 3-combinations * *of *, *and so on.*

**Reference: **

Introductory Combinatorics (Fourth Edition), Richard A. Brualdi:

For example, available at Amazon India:

Also, for example, available at Flipkart:

To be continued further,

Nalin Pithwa.