《離散數(shù)學(xué)》ch(10)

1、整理課件7.5 Inclusion-Exclusion (容斥容斥)Introduction Example 0 (page 499) A discrete mathematics class contains 30 women and 50 sophomores (二年級(jí)學(xué)二年級(jí)學(xué)生生). How many students in the class are either women or sophomore?Solution: This question can not be answered unless more information is provided. need to kno

2、w the number of women sophomores.整理課件2. The Principle of Inclusion-Exclusion (容斥原理容斥原理)Example 1 (page 500) A discrete mathematics class contains 25 students majoring in computer science, 13 students majoring in mathematics, and eight joint mathematics and computer science majors. How many students

3、are in this class, if every student is majoring in mathematics, computer science, or both mathematics and computer science?整理課件Solution: A- the set of students in the class majoring in computer science B- the set of students in the class majoring in mathematics |AB| = |A|+|B|-|AB| = 25 + 13 -8 = 30整

4、理課件(2) Example 2 (Page 501)How many positive integers not exceeding 1000 are divisible by 7 or 11?Solution: A - the set of positive integers not exceeding 1000 that are divisible by 7 B - the set of positive integers not exceeding 1000 that are divisible by 11 Then, AB - the set of integers not exce

5、eding 1000 that are divisible by either 7 or 11 AB - the set of integers not exceeding 1000 that are divisible by both 7 and 11. 整理課件Further, we have: |A| = 1000/7 = 142 |B| = 1000/11 = 90 |AB| = 1000/(711) = 12Therefore, |AB| = |A| + |B| - |AB| = 142 + 90 12 =220 整理課件(3) Example 3 (page 501)Suppose

6、 that there are 1807 freshmen (大大學(xué)一年級(jí)學(xué)生學(xué)一年級(jí)學(xué)生) at your school. Of these, 453 are taking a course in computer science, 567 are taking a course in mathematics, and 299 are taking courses in both computer science and mathematics. How many are not taking a course either in computer science or mathematic

7、s?整理課件Solution: A - the set of all freshmen taking a course in computer science B - the set of all freshmen taking a course in mathematics It follows that |A|=453, |B|=567, and |AB|=299.Therefore, |AB| = |A| + |B| - |AB| = 721Consequently, there are 1807-721=1086 freshmen who are not taking a course

8、 in computer science or mathematics.整理課件(4) Example 4 (page 502)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 Ru

9、ssian, and 14 have taken courses in both French and Russian. If 2092 students have taken at least one of Spanish, French, and Russian, how many students have taken a course in all three languages?整理課件Solution:S - the set of students who have taken a course in SpanishF - the set of students who have

10、taken a course in FrenchR - the set of students who have taken a course in RussianFurther, we have: |S|=1232, |F|=879, |R|=114, |SF|=103, |SR|=23, |FR|=14,and |SFR|=2096整理課件Inserting these questions into the equation |SFR| = |S| + |F| + |R| - |SF| - |SR| - |FR| + |SFR|Therefore, we have: |SFR|=7整理課件

11、(5) The Principle of Inclusion-Exclusion (容斥原理容斥原理, page 503) Let A1, A2, , An be finite sets. Then |A1A2An| = 1in |Ai| - 1ijn |AiAj| + 1ijkn |AiAjAk| - . + (-1)n+1|A1A2An| Proof: Please see page 503. 整理課件(6) Example 5 (page 504) Given a formula for the number of elements in the union of four sets.Solutio