Section 8.5
Section Summary
The Principle of Inclusion-Exclusion Examples
Principle of Inclusion-Exclusion
In Section 2.2, we developed the following formula for the number of elements in the union of two finite sets:
We will generalize this formula to finite sets of any size.
Two Finite Sets
Example: In a discrete mathematics class every student is a major in computer science or mathematics or both. The number of students havingcomputerscienceasa major(possiblyalongwithmathematics) is 25; the number of students having mathematics as a major (possibly along with computer science) is 13; and the number of students majoring in both computer science and mathematics is 8. How many students are in the class?
Solution: |A∪B| = |A| + |B| −|A∩B| = 25+13−8=30
Three Finite Sets
Three Finite Sets Continued
Example: A total of 1232 students have taken a course in Spanish, 879 have taken a course in French, and 114 have taken a course in Russian. Further, 103 have taken courses in both Spanish and French, 23 have taken courses in both Spanish and Russian, and 14 have taken courses in both French and Russian. If 2092 students have taken a course in at least one of Spanish French and Russian, how many students have taken a course in all 3 languages.
Three Finite Sets Continued
Example: A total of 1232 students have taken a course in Spanish, 879 have taken a course in French, and 114 have taken a course in Russian. Further, 103 have taken courses in both Spanish and French, 23 have taken courses in both Spanish and Russian, and 14 have taken courses in both French and Russian. If 2092 students have taken a course in at least one of Spanish French and Russian, how many students have taken a course in all 3 languages.
Solution: Let S be the set of students who have taken a course in Spanish, F the set of students who have taken a course in French, and R the set of students who have taken a course in Russian. Then, we have
|S| = 1232, |F| = 879, |R| = 114, |S∩F| = 103, |S∩R| = 23, |F∩R| = 14, and |S∪F∪R| = 23.
Using the equation
|S∪F∪R| = |S|+ |F|+ |R| − |S∩F| − |S∩R| − |F∩R| + |S∩F∩R|,
we obtain 2092 = 1232 + 879 + 114 −103 −23 −14 + |S∩F∩R|. Solving for |S∩F∩R| yields 7.
Illustration of Three Finite Set
Example
The Principle of Inclusion-Exclusion
Theorem 1. The Principle of Inclusion-Exclusion: Let A1, A2, …, An be finite sets. Then:
The Principle of Inclusion-Exclusion
(continued)
Proof: An element in the union is counted exactly onceintheright-handsideoftheequation. Consider an element a that is a member of r of the sets A1,…., An where1≤ r≤ n.
It is counted C(r,1) times by Σ|A | i
It is counted C(r,2) times by Σ|A ⋂A | ij
In general, it is counted C(r,m) times by the summation of m of the sets Ai.
The Principle of Inclusion-Exclusion
(cont)
Thus the element is counted exactly
C(r,1) − C(r,2) + C(r,3) − ⋯ + (−1) C(r,r)
By Corollary 2 of Section 6.4, we have
C(r,0) − C(r,1) + C(r,2) − ⋯ + (−1)r C(r,r) = 0.
r+1
times by the right hand side of the equation.
Hence,
1 = C(r,0) = C(r,1) − C(r,2) + ⋯ + (−1)
C(r,r).
r+1
Section 8.6
Section Summary
Counting Onto-Functions Derangements
The Number of Onto Functions
Example: How many onto functions are there from a set with six elements to a set with three elements?
Solution: Suppose that the elements in the codomain are b1, b2, and b3. Let P1, P2, and P3 be the properties that b1, b2, and b3 are not in the range of the function, respectively. The function is onto if none of the properties P1, P2, and P3 hold.
By the inclusion-exclusion principle the number of onto functions from a set with six elements to a set with three elements is
N−[N(P)+N(P )+N(P )] + 123
[N(PP )+N(PP )+N(P P )]−N(PP P )
121323123 6
Here the total number of functions from a set with six elements to one with three elements is N = 3 . The number of functions that do not have in the range is N(P ) = 26. Similarly, N(P ) = N(3 ) = 26 .
NotethatN(PP )=N(PP )=N(P P )=1andN(PP P )=0. 121323123
Hence, the number of onto functions from a set with six elements to a set with three elements is: 36 −3∙26 +3 =729−192 +3 =540
121
The Number of Onto Functions
(continued)
Theorem 1: Let m and n be positive integers with m ≥ n. Then there are
onto functions from a set with m elements to a set with n elements.
Proof follows from the principle of inclusion-exclusion (see Exercise 27).
Derangements
Definition: A derangement is a permutation of objects that leaves no object in the original position.
Example: The permutation of 21453 is a derangement of 12345 because no number is left in its original position. But 21543 is not a derangement of 12345, because 4 is in its original position.
Derangements (continued)
Theorem 2: The number of derangements of a set with n elements is
Proof follows from the principle of inclusion-exclusion (see text).
Derangements (continued)
The Hatcheck Problem: A new employee checks the hats of n people at restaurant, forgetting to put claim check numbers on the hats. When customers return for their hats, the checker gives them back hats chosen at random from the remaining hats. What is the probability that no one receives the correct hat.
Solution: The answer is the number of ways the hats can be arranged so that there is no hat in its original position divided by n!, the number of permutations of n hats.
Remark: It can be shown that the probability of a derangement approaches 1/e as n grows without bound.