Chapter 5 The Principle of Inclusion and Exclusion

Chapter 5: The Principle of Inclusion and Exclusion
(References: Principles and Techniques in Combinatorics by Chuan-Chong and Khee-Meng )
The Principle
Theorem 4.1. (Addition Principle (AP) If A and B are finite sets such that A B = , then
|A B| = |A| + |B|
Theorem 4.2. If A and B are finite sets such that A B 6= , then
|A B| = |A| + |B| |A B|
Theorem 4.3. If A, B, and C are finite sets, then
|A B C| = (|A| + |B| + |C|) (|A B| + |A C| + |B C|) + |A B C|

Proof. Using the previous theorem.
Theorem 4.4. (Principle of Inclusion and Exclusion (PIE) If any q finite sets A1 , A2 , . . . Aq , q 2,
|A1 A2 Aq | =
q
X
i=1
|Ai |
X
i<j
|Ai Aj | +
|Ai Aj Ak | + (1)q+1 |A1 A2 Aq |
i<j<k
Example 4.1. Let {1, 2, . . . , 500}. Find the number of integers in S which are divisible by 2,3, or 5.
Solution: Recall that

1. For each n N, the number of integers in S which are divisible by n is given by b 500
n c
2. For a, b, c N, c is divisible by both a and b if and only if c is divisible by the LCM of a and b.
For Each k N, let Bk = {x S|x is divisible by k}. Thus, we need to find |B2 B3 B5 |. Then, to apply
(PIE), we need solve first |B2 |, |B3 |, |B5 |, |B2 B3 |, |B2 B5 |, |B3 B5 |, and |B2 B3 B5 |. The final answer
is 366.
Example 4.2. Let {1, 2, . . . , 500}. Find the number of integers in S such which are divisible by
1. none of 2, 3, 5?
2. exactly one of 2,3,5?
3. exactly two of 2,3,5?
4. all of 2,3,5?
Definition 4.1. For integer m with 0 m q, let E(m) denote the number of elements of S that posses exactly
m of the q properties; and 1 m q, let (Pi1 , Pi2 , . . . , Pim ) denote the number of elements of S that possess
the properties of Pi1 , Pi2 , . . . , Pim and let
X
(m) =
((Pi1 , Pi2 , . . . , Pim ))
where the summation is taken over all m-combinations {i1 , i2 , . . . , im } of {1, 2, . . . , q}

Example 4.3. Let S = {1, 2, . . . , 10}. Find the element of A such that
1. A = {x S|x possesses P } where the property P may be taken to be less than 6

2. A = {x S|x possesses P } where the property P being divisible by 3.
1
D
MATH 141 - INTRODUCTORY COMBINATORICS / A.B.A. Dalam, MS Math
Generalize Principle of Inclusion and Exclusion

Theorem 4.5. (GPIE) Let S be an n-element set and let {P1 , P2 , . . . , Pq } be a set q properties for elements
of S. Then m = 0, 1, 2, . . . , q,

m+1
m+2
q
qm
E(m) = (m)
(m + 1) +
(m + 2) + (1)
(q)
m
m
m

Pq
k
km
=
(k)
k=m (1)
m
Assignment 2: SET 3 Show solutions and Proof properly.

1. A group of 102 students took examinations in Chinese, English and Mathematics. Among them, 92 passed
Chinese, 75 English, and 63 Mathematics; at most 65 passed Chinese and English, at most 54 Chinese and
Mathematics, and at most 48 English and Mathematics. Find the largest possible number of the students
that could have passed all the three subjects.
2. Find the number of integers in the set {1, 2, . . . , 103 } which are not divisible by 5 nor by 7 but divisible by
3.
3. Find the number of integers in the set {1, 2, . . . , 120} which are divisible by exactly m of the integers: 2,3,5,7,
where
(a) m = 0
(b) m = 2
(c) m = 3
4. Find the number of prime integers in the set {1, 2, . . . , 120}.
5. Each of n boys attends a school gathering with both of his parents. In how many ways can the 3n people
be divided into groups of three such that each group contains a boy, a male parent and female parent, and
no boy is with both of his parents in his group?
6. Find the number of positive divisors of at least one of the numbers: 1040 and 2030 .
7. Find the number of non-negative integer solutions to the equation
x1 + x2 + x3 = 15
where x1 5, x2 6 and x3 7.
8. Find the number of integer solutions to the equation
x1 + x2 + x3 = 40
where 6 x1 15, 5 x2 20 and 10 x3 25.
9. Find the number of ways of arranging n couples {Hi , Wi } in a row such that Hi is not adjacent to Wi for
each i = 1, 2, . . . , n.
10. Prove the Principle of Inclusion and Exclusion Theorem (PIE Theorem) using Mathematical Induction on
q.
11. Let A, B, and C be finite sets. Prove that |Ac B| = |B| |A B|.
12. Let A, B, and C be finite sets. Prove that |Ac B c C| = |C| |A C| |B C| + |A B C|.

2
D
MATH 141 - INTRODUCTORY COMBINATORICS / A.B.A. Dalam, MS Math

Chapter 5 The Principle of Inclusion and Exclusion

Uploaded by

Copyright:

Available Formats

Chapter 5 The Principle of Inclusion and Exclusion

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Chapter 5 The Principle of Inclusion and Exclusion

Uploaded by

Copyright:

Available Formats

What is the Principle of Inclusion and Exclusion (PIE) theorem and how is it used?

What are the steps to solve problem 1 given in the assignment questions?

Chapter 5: The Principle of Inclusion and Exclusion

(References: Principles and Techniques in Combinatorics by Chuan-Chong and Khee-Meng )

Theorem 4.2. If A and B are finite sets such that A B 6= , then

Theorem 4.3. If A, B, and C are finite sets, then

|A B C| = (|A| + |B| + |C|) (|A B| + |A C| + |B C|) + |A B C|

|Ai Aj Ak | + (1)q+1 |A1 A2 Aq |

Solution: Recall that

where the summation is taken over all m-combinations {i1 , i2 , . . . , im } of {1, 2, . . . , q}

1. A = {x S|x possesses P } where the property P may be taken to be less than 6

Generalize Principle of Inclusion and Exclusion

Assignment 2: SET 3 Show solutions and Proof properly.

Chapter 5: The Principle of Inclusion and Exclusion

You might also like