The Inclusion-Exclusion Principle again !! RMO basics

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 \{ i_{1}i_{2}\ldots i_{n}\} of \{ 1,2, \ldots ,n\} in which 1 is not in the first position (that is, i_{1} \neq 1).

We could make a direct count by observing that the permutations with 1 not in the first position can be divided into (n-1) parts according to which of the (n-1) integers k from \{ 2,3,\ldots, n\} is in the first position. A permutation with k in the first position consists of k followed by a permutation of the (n-1)- element set \{ 1, \ldots, k-1, k+1, \ldots, n\}. Hence, there are (n-1)! permutations of \{ 1,2,3 \ldots, n\} with k in the first position. By the addition principle, there are (n-1)!(n-1) permutations of \{ 1,2, \ldots, n\} with 1 not in the first position.

Alternatively, we could make an indirect count by observing that the number of permutations of \{1, 2, \ldots, n \} with 1 in the first position is the same set as the number (n-1)! of permutations of \{ 2,3,\ldots,n\}. Since the total number of permutations of \{ 1,2,\ldots, n\} is n!, the number of permutations of \{ 1,2,\ldots,n\} in which 1 is not in the first position is n!-(n-1)!=(n-1)!(n-1).

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, 600-100=500 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

A^{'}=S-A= \{ x: x \in S, x \notin A\}

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

|A| = |S| - |A^{'}|, or equivalently, |A^{'}|=|S|-|A|. 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 P_{1} and P_{2} 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 P_{1} nor property P_{2}. We can do this by first including all objects of S in our count, then excluding all objects that have property P_{1} and excluding all objects which have property P_{2}, and then, noting that we have excluded objects having both properties P_{1} and P_{2} twice, readmitting all such objects once. We can write this symbolically as follows: Let A_{1} be the subset of objects of S that have property P_{1}, and let A_{2} be the subset of objects of S that have property P_{2}. Then, A_{1}^{'} consists of those objects of S not having property P_{1} and let A_{2}^{'} consists of those objects of S not having property P_{2}. The objects of the set A_{1}^{'}\bigcap A_{2}^{'} are those having neither property P_{1} nor property P_{2}. We then have |A_{1}^{'} \bigcap A_{2}^{'}|=|S|-|A_{1}|-|A_{2}|+|A_{1}\bigcap A_{2}|.

Since the left side of the preceding equation counts the number of objects of S that have neither property P_{1} nor property P_{2}, we can establish the validity of this equation by showing that an object with neither of the two properties P_{1} and P_{2} 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 P_{1} and P_{2}, it counted among the objects of S, not counted among the objects of A_{1} or of A_{2}, and not counted among the objects of A_{1}\bigcap A_{2}. Hence, its net contribution to the right side of the equation is 1-0-0+0=1.

If x has only the property P_{1}, it contributes 1-1-0+0=0 to the right side, while it has only the property P_{2}, it contributes 1-0-1+0=0 to the right side. Finally, if x has both properties P_{1} and P_{2}, it contributes 1-1-1+1=0 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 P_{1} nor property P_{2}.

More generally, let P_{1}, P_{2}, P_{3}, \ldots, P_{m} be m properties referring to the objects in S, and let

A_{i}=\{ x: x \in S, \hspace{0.1 in} x \hspace{0.1 in} has \hspace{0.1 in} property \hspace{0.1 in} P_{i}\}, and \{ i= 1,2,\ldots,m\}

be the subset of objects of S that have property S (and possibly other properties). Then, A_{i}\bigcap A_{j} is the subset of objects that have both properties P_{1} and P_{2} (and, possibly others), A_{i}\bigcap A_{j}\bigcap A_{k} is the subset of objects which have properties P_{i}, P_{j}, P_{k} and so on. The subset of objects having none of the properties is A_{1}^{'}\bigcap A_{2}^{'} \bigcap \ldots \bigcap A_{m}^{'}. 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 P_{1}, P_{2}, \ldots, P_{m} is given by:

|A_{1}^{'}\bigcap A_{2}^{'} \bigcap A_{3}^{'}\bigcap \ldots A_{m}^{'}| = |S|-\sum|A_{i}|+\sum|A_{i}\bigcap A_{j}|-\sum|A_{i} \bigcap A_{j} \bigcap A_{k}|+ \ldots + (-1)^{m}|A_{1}\bigcap A_{2}\bigcap A_{3}\ldots \bigcap A_{m}|,

where the first sum is over all 1-combinations \{ i\} of \{ 1,2,3, \ldots, m \}, the second sum is over all 2-combinations \{ i,j\} of \{ 1,2,\ldots, m\}the third sum is over all 3-combinations \{i,j,k\} of \{ 1,2,\ldots, m\}and so on.

Reference: 

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

For example, available at Amazon India:

http://www.amazon.in/Introductory-Combinatorics-4e-Brualdi/dp/8131718824/ref=sr_1_1?s=books&ie=UTF8&qid=1500279459&sr=1-1&keywords=introductory+combinatorics.

Also, for example, available at Flipkart:

https://www.flipkart.com/introductory-combinatorics-4th/p/itme3fz6nykgzdyw?pid=9788131718827&srno=s_1_1&otracker=search&lid=LSTBOK978813171882786XN5F&qH=75550818a6d8f118T

To be continued further,

Nalin Pithwa.

 

 

 

 

 

 

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s