ting ll Let P42 be the set of all permutations in which 42 appears; define PGo and Po4 similarly. Thus, for example, the permutation above is contained in both P6o and Po4. In these terms, were looking for the size of the set P42 U PoU P60 First, we must determine the sizes of the individual sets, such as Pgo. We can use a trick: group the 6 and 0 together as a single symbol. Then there is a natural bijection between permutations of (0, 1, 2,...9) containing 6 and 0 consecutively and permutations of {60.1,2,3,4,5,7,8,9} For example, the following two sequences correspond (7,2,5,6,0,4,3,8,1,9)分(7,2,5,60,4,3,8,1,9) There are 9! permutations of the set containing 60, so Pool=9! by the Bijection Rule Similarly, Po4= P421=9! as well Next, we must determine the sizes of the two-way intersections, such as P42 n Pso Using the grouping trick again, there is a bijection with permutations of the set {42,60,1,3,5,7,8,9} Thus, P42 n P6ol=8!. Similarly, P6o n Poal =8! by a bijection with the set {604,1,2,3,5,7,8,9} And Pan Po =8! as well by a similar argument. Finally, note that P6o n Po4n P42=7! by a bijection with the set {6042,1,3,5,7,8,9} Plugging all this into the formula gives PUPo4UF|=9!+9+9!-8!-8!-8!+7! 3.3 Union of n Sets The size of a union of n sets is given by the following rule Rule 3 (Inclusion-Exclusion) S1US2U…∪S the sum of the sizes of the individual sets minus the sizes of all two-way intersections plus the sizes of all three-way intersections minus the sizes of all four-way intersection plus the sizes of all five-way intersections, etc There are various ways to write the Inclusion-Exclusion formula in mathematical sym bols, but none are particularly clear, so weve just used words. The formulas for unions of two and three sets are special cases of this general rule10 Counting II Let P42 be the set of all permutations in which 42 appears; define P60 and P04 similarly. Thus, for example, the permutation above is contained in both P60 and P04. In these terms, we’re looking for the size of the set P42 ∪ P04 ∪ P60. First, we must determine the sizes of the individual sets, such as P60. We can use a trick: group the 6 and 0 together as a single symbol. Then there is a natural bijection between permutations of {0, 1, 2, . . . 9} containing 6 and 0 consecutively and permutations of: {60, 1, 2, 3, 4, 5, 7, 8, 9} For example, the following two sequences correspond: (7, 2, 5, 6, 0, 4, 3, 8, 1, 9) ⇔ (7, 2, 5, 60, 4, 3, 8, 1, 9) There are 9! permutations of the set containing 60, so |P60| = 9! by the Bijection Rule. Similarly, |P04| = = 9! |P42| as well. Next, we must determine the sizes of the two­way intersections, such as P42 ∩ P60. Using the grouping trick again, there is a bijection with permutations of the set: {42, 60, 1, 3, 5, 7, 8, 9} Thus, | | P42 ∩ P60 = 8!. Similarly, | | P60 ∩ P04 = 8! by a bijection with the set: {604, 1, 2, 3, 5, 7, 8, 9} And | | P42 ∩ P04 = 8! as well by a similar argument. Finally, note that |P60 ∩ P04 ∩ P42| = 7! by a bijection with the set: {6042, 1, 3, 5, 7, 8, 9} Plugging all this into the formula gives: |P42 ∪ P04 ∪ P60| = 9! + 9! + 9! − 8! − 8! − 8! + 7! 3.3 Union of n Sets The size of a union of n sets is given by the following rule. Rule 3 (Inclusion­Exclusion). |S1 ∪ S2 ∪ · · · ∪ Sn| = the sum of the sizes of the individual sets minus the sizes of all two­way intersections plus the sizes of all three­way intersections minus the sizes of all four­way intersections plus the sizes of all five­way intersections, etc. There are various ways to write the Inclusion­Exclusion formula in mathematical sym￾bols, but none are particularly clear, so we’ve just used words. The formulas for unions of two and three sets are special cases of this general rule