Counting l 3.2 Union of three sets So how many students are there in the Math, EECS, and Physics departments? In other words, what is MUEUPlif M=60 E|=200 P|=40 The size of a union of three sets is given by a more complicated formula S1US2US3=|S1+|S2+|S3| SinS2-|S1nSa-|S2∩Sa +|S1∩S2∩S3 Remarkably, the expression on the right accounts for each element in thethe union of S1 S2, and S3 exactly once. For example, suppose that r is an element of all three sets. Then a is counted three times(by the Sil, IS2l, and IS3 terms), subtracted off three times (by the S1nS2l, Sin s3l, and S2n S3l terms), and then counted once more (by the S1n S2n S3l term). The net effect is that a is counted just once So we can't answer the original question without knowing the sizes of the various intersections. Let' s suppose that there are 4 Math-EECS double majors 3 Math-Physics double majors 11 EECS-Physics double majors 2 triple majors Then 4∩E=4+2,MnP=3+2,E∩P|=11+2,and|MnE∩P=2. Plugging all this into the formula gives MUEUP=|M+|E+|P|-|M∩E-|MnP-|E∩P+|MnE∩P 60+200+40-6-5-13+2 =278 Sequences with 42, 04, or 60 In how many permutations of the set 0, 1, 2,..., 9) do either 4 and 2, 0 and 4, or 6 and O appear consecutively? For example, none of these pairs appears in: (7,2,9,5,4,1,3,8,0,6) The 06 at the end doesn't count; we need 60 On the other hand, both 04 and 60 appear consecutively in this permutation (7,2,5,6,Q,4,3,8,1,9)Counting II 9 3.2 Union of Three Sets So how many students are there in the Math, EECS, and Physics departments? In other words, what is | | M ∪ E ∪ P if: |M| = 60 |E| = 200 | | P = 40 The size of a union of three sets is given by a more complicated formula: |S1 ∪ S2 ∪ S3| | | | | | = S1| + S2 + S3 − | | − | | − | | S1 ∩ S2 S1 ∩ S3 S2 ∩ S3 + |S1 ∩ S2 ∩ S3| Remarkably, the expression on the right accounts for each element in the the union of S1, S2, and S3 exactly once. For example, suppose that x is an element of all three sets. Then x is counted three times (by the |S1| | | | | , S2 , and S3 terms), subtracted off three times (by the | | | | | | S1 ∩ S2 , S1 ∩ S3 , and S2 ∩ S3 terms), and then counted once more (by the |S1 ∩ S2 ∩ S3| term). The net effect is that x is counted just once. So we can’t answer the original question without knowing the sizes of the various intersections. Let’s suppose that there are: 4 Math ­ EECS double majors 3 Math ­ Physics double majors 11 EECS ­ Physics double majors 2 triple majors Then | | | | | | M ∩ E = 4 + 2, M ∩ P = 3 + 2, E ∩ P = 11 + 2, and | | M ∩ E ∩ P = 2. Plugging all this into the formula gives: | | | | | | | − | | − | | − | | | | M ∪ E ∪ P = M| + E + P M ∩ E M ∩ P E ∩ P + M ∩ E ∩ P = 60 + 200 + 40 − 6 − 5 − 13 + 2 = 278 Sequences with 42, 04, or 60 In how many permutations of the set {0, 1, 2, . . . , 9} do either 4 and 2, 0 and 4, or 6 and 0 appear consecutively? For example, none of these pairs appears in: (7, 2, 9, 5, 4, 1, 3, 8, 0, 6) The 06 at the end doesn’t count; we need 60. On the other hand, both 04 and 60 appear consecutively in this permutation: (7, 2, 5, 6, 0, 4, 3, 8, 1, 9)