**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 is given by:

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

If , the statement of the theorem becomes:

Note that there are terms on the RHS. If , then the statement of the theorem becomes:

In this case, there are terms on the right side. In the general case, the number of terms on the right side of the equation/theorem statement is:

.

**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 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 :

,

since it is in S, but in none of the other sets. Now, consider an object y with exactly of the properties. The contribution of y to is . Its contribution to is since it has exactly n of the properties and so is a member of exactly n of the sets . The contribution of y to is since we may select a pair of the properties y has in ways, and so y is a member of exactly of the sets . The contribution of y to the RHS of **Equation I** is

, which equals , since and , if . 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:

, when .

**Corollary 6.2:**

The number of objects of S which have at least one of the properties is given by

…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 consists of all those objects in S which possess at least one of the properties. Also,

.

Since, as is readily verified, , we have

.

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 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 and respectively. Let be the property that an integer is divisible by 5, the property that an integer is divisible by 6, and the property that an integer is divisible by 8. Let S be the set consisting of the first thousand positive integers. For , let be the set consisting of those integers in S with property . We wish to find the number of integers in .

We first see that ; ;

Integers in the set 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

; ; and

Because lcm{5,6,8}=120, we conclude that .

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

.

**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 be the property that a permutation in S contains the word MATH as consecutive letters; let be the property that a permutation in S contains the word IS and let be the property that a permutation contains the word FUN. For , let be the set of those permutations in S satisfying property .

Step 3: To find the number of permutations in .

*Solution:*

We have . The permutations in can be thought of as permutations of the six symbols: MATH, I, S, F, U and N.

Hence, .

Similarly, the permutations in are permutations of the eight symbols: M,A,T,H,IS,F,U,N. So, ; and the permutations in are permutations of the seven symbols : M,A,T,H,I,S,FUN so .

The permutations in are permutations of the five symbols: MATH, IS, F,U,N; the permutations in are permutations of the four symbols: MATH, I, S, FUN; the permutations in are permutations of the six symbols : M,A,T,H,IS,FUN.

Hence, we get the following:

; ; and .

Finally, consists of the permutations of the three symbols MATH, IS, F, U, N; therefore,

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

.

*(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** 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 such that

**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 summands, each equal to .

**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 be the property that an integer does not contain the digit 2; let be the property that an integer does not contain the digit 5, and let be the property that an integer does not contain the digit 8. For , let be the set consisting of those integers in S with property .

We wish to count the number of integers in .

Using the notation in the preceding example, we have:

.

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 , equals the number of 5-permutations of the multiset

,

and this equals . By the corollary, we get the answer as : .

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

*Nalin Pithwa.*