Inclusion Exclusion Principle : further RMO Basics

Note: continued from previous blog article of same topic; same reference text (by the way, this is a beautiful introductory classic in Combinatorics, but a “thick, huge” text !!! :-))

https://madhavamathcompetition.com/2017/07/13/the-inclusion-exclusion-principle-again/

Theorem 1.1: (or 6.1.1 of text):

The number of objects of S that have none of the properties P_{1}, P_{2}, P_{3}, \ldots, P_{m} is given by:

|\overline{A_{1}}\bigcap \overline{A_{2}}\bigcap\ldots\bigcap \overline{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 \ldots \bigcap A_{m}|

Some remarks on the theorem 1.1 before we present the proof:

If m=0, the statement of the theorem becomes:

|A_{1}^{'}\bigcap A_{2}^{'}\bigcap A_{3}^{'}|=|S|-(|A_{1}|+|A_{2}|+|A_{3}|)+(|A_{1}\bigcap A_{2}|+|A_{1}\bigcap A_{3}|+|A_{2}\bigcap A_{3}|) - |A_{1}\bigcap A_{2} \bigcap A_{3}|

Note that there are 1+3+3+1=8 terms on the RHS. If m=4, then the statement of the theorem becomes:

|A_{1}^{'}\bigcap A_{2}^{'} \bigcap A_{3}^{'} \bigcap A_{4}^{'}|= |S|-(|A_{1}|+|A_{2}|+|A_{3}|+|A_{4}|) +(|A_{1}\bigcap A_{2}|+|A_{1}\bigcap A_{3}|+|A_{1}\bigcap A_{4}|+|A_{2}\bigcap A_{3}|+|A_{2}\bigcap A_{4}|+|A_{3}\bigcap A_{4}|) - (|A_{1}\bigcap A_{2} \bigcap A_{3}|+|A_{1}\bigcap A_{3} \bigcap A_{4}|+|A_{2}\bigcap A_{3}\bigcap A_{4}|)+|A_{1}\bigcap A_{2} \bigcap A_{3} \bigcap A_{4}|

In this case, there are 1+4+6+4+1=16 terms on the right side. In the general case, the number of terms on the right side of the equation/theorem statement is:

{m \choose 0}+{m \choose 1} + {m \choose 2} + {m \choose 3}+ \ldots + {m \choose m}=2^{m}.

Proof of theorem 1.1:

The LHS of the theorem statement (equation) counts the number of objects of S with none of the stated properties. We can establish the validity of the equation by showing that an object with none of the properties P_{1}, P_{2}, \ldots, P_{m} makes a net contribution of 1 to the right side, and an object with at least one of the properties makes a net contribution of 0. First, consider an object x with none of the properties. Its contribution to the right side of the equation is :

1-0+0-0+\ldots + (-1)^{m}0=1,

since it is in S, but in none of the other sets. Now, consider an object y  with exactly n \geq 1 of the properties. The contribution of y to |S| is 1= {n \choose 0}. Its contribution to \sum|A_{i}| is n = {n \choose 1} since it has exactly n of the properties and so is a member of exactly n of the sets A_{1}, A_{2}, \ldots , A_{m}. The contribution of y to \sum|A_{i}\bigcap A_{j}| is n \choose 2 since we may select a pair of the properties y has in n \choose 2 ways, and so y is a member of exactly n \choose 2 of the sets A_{i}\bigcap A_{j}. The contribution of y to the RHS of Equation I is

{n \choose 0} - {n \choose 1} + {n \choose 2} - {n \choose 3} + \ldots +(-1)^{m}{n \choose m}, which equals {n \choose 0} - {n \choose 1} + {n \choose 2} - {n \choose 3} + \ldots +(-1)^{n}{n \choose n}, since n \leq m and {n \choose k}=0, if k>n. Since this last expression equals 0 according to the identity 5.4, the net contribution of y to the RHS of Equation I is 0, if y has at least one of the properties. QED.

PS: By the way, identity 5.4 is as follows:

{n \choose 0}-{n \choose 1}+{n \choose 2}- \ldots + (-1)^{n}{n \choose n}=0, when n \geq 1.

Corollary 6.2:

The number of objects of S which have at least one of the properties P_{1}, P_{2}, \ldots, P_{m} is given by

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

…call this relation as 6.2

where the summations are as specified in theorem 6.1.1(that is, theorem 1 of the previous blog mentioned above)

Proof of the above corollary:

The set A_{1} \bigcup A_{2} \bigcup \ldots A_{m} consists of all those objects in S which possess at least one of the properties. Also,

|A_{1} \bigcup A_{2} \bigcup A_{3} \ldots A_{m}|=|S|-|\overline{A_{1}\bigcup A_{2}\bigcup \ldots \bigcup A_{m}}|.

Since, as is readily verified, \overline{|A_{1}\bigcup A_{2} \bigcup \ldots A_{m}|}=\overline{A_{1}}\bigcap \overline{A_{2}}\bigcap \ldots \bigcap \overline{A_{m}}, we have

|A_{1}\bigcup A_{2}\bigcup \ldots \bigcup A_{m}|=|S|-|\overline{A_{1}}\bigcap \overline{A_{2}}\bigcap \overline{A_{3}}\bigcap\ldots \bigcap \overline{A_{m}}|.

Combining this equation with 6.1, we obtain equation or relation 6.2. QED.

Example:

Find the number of integers between 1 and 1000, inclusive, that are not divisible by 5, 6 and 8.

Solution:

Method 1: use some properties of number theory.

Method 2: use some properties of number theory and figure out how to apply the theory given above ! I agree it seems a very simple illustration of this generalized inclusion-exclusion principle, but we learn here to apply this technique with “clarity”…

To solve this problem, we introduce some notation. For a real number r, recall that \lfloor{r}\rfloor stands for the largest integer that does not exceed r. Also, we shall abbreviate the LCM of two integers, a and b or three integers a, b and c by lcm{(a,b)} and lcm{(a,b,c)} respectively. Let P_{1} be the property that an integer is divisible by 5, P_{2} the property that an integer is divisible by 6, and P_{3} the property that an integer is divisible by 8. Let S be the set consisting of the first thousand positive integers. For i=1,2,3, let A_{i} be the set consisting of those integers in S with property P_{i}. We wish to find the number of integers in \overline{A_{1}} \bigcap \overline{A_{2}} \bigcap \overline{A_{3}}.

We first see that |A_{1}|=\lfloor\frac{1000}{5}\rfloor=200; |A_{2}|=\lfloor \frac{1000}{6}\rfloor=166; |A_{3}|=\lfloor\frac{1000}{8}\rfloor=125

Integers in the set A_{1}\bigcap A_{2} are divisible by both 5 and 8. But, an integer is divisible by both 5 and 6 iff it is divisible by lcm{5,6}, which is, 30. Also, lcm{5,8}=40 and lcm{6,8}=24. Hence, we get

|A_{1}\bigcap A_{2}|=\lfloor \frac{1000}{30} \rfloor=33; |A_{1}\bigcap A_{3}|=\lfloor \frac{1000}{40} \rfloor=25; and |A_{2}\bigcap A_{3}|=\lfloor \frac{1000}{24} \rfloor=41

Because lcm{5,6,8}=120, we conclude that |A_{1}\bigcap A_{2} \bigcap A_{3}|=\lfloor \frac{1000}{120} \rfloor=8.

Thus, by the inclusion-exclusion principle, the number of integers between 1 and 1000 that are not divisible by 5, 6 and 8 equals:

|\overline{A_{1}}\bigcap \overline{A_{2}}\bigcap \overline{A_{3}}|=1000-(200+166+125)+(33+25+41)-8=600.

Example: 

How many permutations of the letters M,A,T,H,I,S,F,U, N are there such that none of the words MATH, IS, and FUN occur as consecutive letters ?(Thus, for instance, the permutation MATHISFUN is not allowed nor are the permutations INUMATHSF and ISMATHFUN.)

Solution:

We apply the generalized inclusion-exclusion principle (theorem 1).

Step 1: Identify the set S as the set of all permutations of the 9 letters given.

Step 2: Let P_{1} be the property that a permutation in S contains the word MATH as consecutive letters; let P_{2} be the property that a permutation in S contains the word IS and let P_{3} be the property that a permutation contains the word FUN. For i=1,2,3, let A_{i} be the set of those permutations in S satisfying property P_{i}.

Step 3: To find the number of permutations in \overline{A_{1}}\bigcap \overline{A_{2}}\bigcap \overline{A_{3}}.

Solution:

We have |S|=9!=362880. The permutations in A_{1} can be thought of as permutations of the six symbols: MATH, I, S, F, U and N.

Hence, |A_{1}|=6!=720.

Similarly, the permutations in A_{2} are permutations of the eight symbols: M,A,T,H,IS,F,U,N. So, |A_{2}|=8!=40320; and the permutations in A_{3} are permutations of the seven symbols : M,A,T,H,I,S,FUN so |A_{3}|=7!=5040.

The permutations in A_{1}\bigcap A_{2} are permutations of the five symbols: MATH, IS, F,U,N; the permutations in A_{1}\bigcap A_{3} are permutations of the four symbols: MATH, I, S, FUN; the permutations in A_{2}\bigcap A_{3} are permutations of the six symbols : M,A,T,H,IS,FUN.

Hence, we get the following:

|A_{1}\bigcap A_{2}|=120; |A_{1} \bigcap A_{3}|=4!=24; and |A_{2}\bigcap A_{3}|=6!=720.

Finally, A_{1}\bigcap A_{2} \bigcap A_{3} consists of the permutations of the three symbols MATH, IS, F, U, N; therefore, |A_{1}\bigcap A_{2} \bigcap A_{3}|=3!=6

Substituting into the equation of the theorem 1.1, we get:

|\overline{A_{1}}\bigcap \overline{A_{2}} \bigcap \overline{A_{3}}|=362880-700-40320-5040+120+24+720-6=317658.

(I hope you liked it!):-)

Remarks:

Later on, we consider applications of the inclusion-exclusion principle to some general problems. The following special case of the inclusion-exclusion principle will be useful:

Assume that the size of the set A_{i_{1}}\bigcap A_{i_{2}}\bigcap A_{i_{3}} \bigcap \ldots \bigcap A_{i_{k}} that occurs in the inclusion-exclusion principle depends only on k and not on which k sets are used in the intersection. Thus, there are constants \alpha_{0}, \alpha_{1}, \alpha_{2}, \ldots, \alpha_{n} such that

\alpha_{0}=|S|

\alpha_{1}=|A_{1}|=|A_{2}|=\ldots = |A_{m}|

\alpha_{2}=|A_{1}\bigcap A_{2}|=\ldots = |A_{m-1}\bigcap A_{m}|

\alpha_{3}=|A_{1}\bigcap A_{2} \bigcap A_{3}|=\ldots = |A_{m-2}\bigcap A_{m-1}\bigcap A_{m}|

\vdots

\alpha_{m} = |A_{1}\bigcap A_{2}\bigcap A_{3}\bigcap \ldots \bigcap A_{m}|

In this case, the inclusion-exclusion principle simplifies to 

Slatex |\overline{A_{1}}\bigcap \overline{A_{2}}\bigcap \ldots \bigcap \overline{A_{m}}|=\alpha_{0}-{m \choose 1}\alpha_{1}+{m \choose 2}\alpha_{2}-{m \choose 3}\alpha_{3}+\ldots+(-1)^{k}{m \choose k}\alpha_{k}+\ldots + (-1)^{m}\alpha_{m}$….call this equation III (or equation 6.3 as the book calls it).

This is because the kth summation that occurs in the inclusion-exclusion principle contains {m \choose k} summands, each equal to \alpha_{k}.

Example:

How many integers between 0 and 99999 (inclusive) have among their digits each of 2,5, and 8?

Solution:

Let S be the set of integers between 0 and 99999. Each integer in S has 5 digits including possible leading zeros. (Thus, we think of the integers in S as the 5-permutations of the multiset in which each digit 0,1,2,3,4,5,6,7,8,9 has repetition number 5 or greater).

Let P_{1} be the property that an integer does not contain the digit 2; let P_{2} be the property that an integer does not contain the digit 5, and let P_{3} be the property that an integer does not contain the digit 8. For i=1,2,3, let A_{i} be the set consisting of those integers in S with property P_{i}.

We wish to count the number of integers in \overline{A_{1}}\bigcap \overline{A_{2}\overline{A_{3}}}.

Using the notation in the preceding example, we have:

\alpha_{0}=10^{5}

\alpha_{1}=9^{5}

\alpha_{2}=8^{6}

\alpha_{3}=7^{5}.

For instance, the number of integers between 0 and 99999 that do not contain the digit 2 and that do not contain the digit 5, the size of |A_{1}\bigcap A_{2}|, equals the number of 5-permutations of the multiset

\{ 5.0, 5.1, 5.3,5.4,5.6, 5.7, 5.8,5.9\},

and this equals 8^{5}. By the corollary, we get the answer as : 10^{5}-3 \times 9^{5}+ 3 \times 8^{5}-7^{5}.

Did you like this? I hope to continue it further by also putting up some exercise problems from Brualdi’s Combinatorics book. 

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