《Mathematics for Computer》Counting Il

6.042/18.] Mathematics for Computer Science March 31. 2005 Srini devadas and Eric Lehman Lecture notes Counting Il We realize everyone has been working pretty hard this term, and were considering Warding some prizes for truly exceptional coursework. Here are some possible categories Best Administrative Critique We asserted that the quiz was closed-book. On the cover page, one strong candidate for this award wrote, There is no book. Best Collaboration Statement Inspired by the student who wrote"I worked alone"on 1 Olfactory Fixation Award A surprisingly competitive category this term, this goes to the student who comes up with the greatest number of odor-related mathematical ex- amples We also considered some less flattering categories such as Proof Most Likely Readable from the Surface of the Moon, Solution Most Closely Resembling a Football Play Diagram with Good Yardage Potential, etc. But then we realized that you all might think up sim- ilar"awards"for the course staff and decided to turn the whole matter into a counting problem. In how many ways can, say, three different prizes be awarded to n people? Remember our basic strategy for counting 1. Learn to count sequences 2. Translate everything else into a sequence-counting problem via bijections We'll flesh out this strategy considerably today but the rough outline above is good r now So we first need to find a bijection that translates the problem about awards into a problem about sequences. Let P be the set of n people in 6.042. Then there is a bijection from ways of awarding the three prizes to the set Px PxP. In particular, the assignment person r wins prize #1, y wins prize #2, and z wins prize #3 maps to the sequence(a, y, 2). All that remains is to count these sequences. By the Product Rule, we have P×P×P=|P|·|P|·|P Thus, there are nways to award the prizes to a class of n people ' Actually, these notes were written last fall, but the problem sets are no easier this term

6.042/18.062J Mathematics for Computer Science March 31, 2005 Srini Devadas and Eric Lehman Lecture Notes Counting II We realize everyone has been working pretty hard this term1, and we’re considering awarding some prizes for truly exceptional coursework. Here are some possible categories: Best Administrative Critique We asserted that the quiz was closed­book. On the cover page, one strong candidate for this award wrote, “There is no book.” Best Collaboration Statement Inspired by the student who wrote “I worked alone” on quiz 1. Olfactory Fixation Award A surprisingly competitive category this term, this goes to the student who comes up with the greatest number of odor­related mathematical ex￾amples. We also considered some less flattering categories such as Proof Most Likely Readable from the Surface of the Moon, Solution Most Closely Resembling a Football Play Diagram with Good Yardage Potential, etc. But then we realized that you all might think up sim￾ilar “awards” for the course staff and decided to turn the whole matter into a counting problem. In how many ways can, say, three different prizes be awarded to n people? Remember our basic strategy for counting: 1. Learn to count sequences. 2. Translate everything else into a sequence­counting problem via bijections. We’ll flesh out this strategy considerably today, but the rough outline above is good enough for now. So we first need to find a bijection that translates the problem about awards into a problem about sequences. Let P be the set of n people in 6.042. Then there is a bijection from ways of awarding the three prizes to the set P ×P ×P. In particular, the assignment: “person x wins prize #1, y wins prize #2, and z wins prize #3” maps to the sequence (x, y, z). All that remains is to count these sequences. By the Product Rule, we have: | | | P × P × P = P P P 3 | · | | · | | = n Thus, there are n3 ways to award the prizes to a class of n people. 1Actually, these notes were written last fall, but the problem sets are no easier this term. :­)

ing ll 1 The generalized Product Rule What if the three prizes must be awarded to different students? As before, we could map the assignment person a wins prize #1, y wins prize #2, and z wins prize #3 to the triple (a, 3, a)EPx PX P. But this function is no longer a bijection. For exampl no valid assignment maps to the triple(Dave, Dave, Becky) because Dave is not allowed to receive two awards. However, there is a bijection from prize assignments to the set S=i(a, y,z)EPXPXPIa, y, and z are different people) This reduces the original problem to a problem of counting sequences. Unfortunately, the Product Rule is of no help in counting sequences of this type because the entries depend on one another; in particular, they must all be different. However, a slightly sharper tool does the trick Rule 1(Generalized Product Rule). Let s be a set of length-k sequences. If there are . n1 possible first entries, n2 possible second entries for each first entry, n3 possible third entries for each combination of first and second entries, etc. tHh Sl=m1:m2·m3…mk In the awards example, S consists of sequences(a, y, z). There are n ways to choose r, the recipient of prize #1. For each of these, there are n-1 ways to choose y, the recipient of prize #2, since everyone except for person r is eligible. For each combination of a and y, there are n-2 ways to choose z, the recipient of prize #3, because everyone except for and y is eligible. Thus, according to the generalized Product Rule, there are Sl=n·(mn-1)·(n-2) ways to award the 3 prizes to different people 1.1 Defective dollars A dollar is defective some digit appears more than once in the 8-digit serial number. If you check your wallet, youll be sad to discover that defective dollars are all-too-common

2 Counting II 1 The Generalized Product Rule What if the three prizes must be awarded to different students? As before, we could map the assignment “person x wins prize #1, y wins prize #2, and z wins prize #3” to the triple (x, y, z) ∈ P × P × P. But this function is no longer a bijection. For example, no valid assignment maps to the triple (Dave, Dave, Becky) because Dave is not allowed to receive two awards. However, there is a bijection from prize assignments to the set: S = {(x, y, z) ∈ P × P × P x| , y, and z are different people} This reduces the original problem to a problem of counting sequences. Unfortunately, the Product Rule is of no help in counting sequences of this type because the entries depend on one another; in particular, they must all be different. However, a slightly sharper tool does the trick. Rule 1 (Generalized Product Rule). Let S be a set of length­k sequences. If there are: • n1 possible first entries, • n2 possible second entries for each first entry, • n3 possible third entries for each combination of first and second entries, etc. then: | | S = n1 · n2 · n3 · · · nk In the awards example, S consists of sequences (x, y, z). There are n ways to choose x, the recipient of prize #1. For each of these, there are n − 1 ways to choose y, the recipient of prize #2, since everyone except for person x is eligible. For each combination of x and y, there are n − 2 ways to choose z, the recipient of prize #3, because everyone except for x and y is eligible. Thus, according to the Generalized Product Rule, there are | | S = n · (n − 1) · (n − 2) ways to award the 3 prizes to different people. 1.1 Defective Dollars A dollar is defective some digit appears more than once in the 8­digit serial number. If you check your wallet, you’ll be sad to discover that defective dollars are all­too­common

Counting l In fact, how common are nondefective dollars? Assuming that the digit portions of serial numbers all occur equally often, we could answer this question by computing fraction dollars that are nondefective of serial #'s with all digits different total# of serial#’s Let's first consider the denominator. Here there are no restrictions; there areare 10 possi ble first digits, 10 possible second digits, 10 third digits, and so on. Thus, the total number of 8-digit serial numbers is 10 by the Generalized Product Rule. (Alternatively, you could conclude this using the ordinary Product Rule; however, the Generalized Product Rule is strictly more powerful. So you might as well forget the orignial Product Rule now and free up some brain space for 6.002. Next, let's turn to the numerator. now we re not permitted to use any digit twice. S there are still 10 possible first digits, but only 9 possible second digits, 8 possible third digits, and so forth. Thus there are 10! 10.9.8·76·5·4·3 serial numbers with all digits different. Plugging these results into the equation above, we find 1,814,400 fraction dollars that are nondefective 100,000,000 1.8144% 1.2 A Chess Problem In how many different ways can we place a pawn(), a knight(k), and a bishop(b)on a chessboard so that no two pieces share a row or a column? a valid configuration is shown below on the the left, and an invalid configuration is shown on the right k

Counting II 3 In fact, how common are nondefective dollars? Assuming that the digit portions of serial numbers all occur equally often, we could answer this question by computing: # of serial #’s with all digits different fraction dollars that are nondefective = total # of serial #’s Let’s first consider the denominator. Here there are no restrictions; there are are 10 possi￾ble first digits, 10 possible second digits, 10 third digits, and so on. Thus, the total number of 8­digit serial numbers is 108 by the Generalized Product Rule. (Alternatively, you could conclude this using the ordinary Product Rule; however, the Generalized Product Rule is strictly more powerful. So you might as well forget the orignial Product Rule now and free up some brain space for 6.002.) Next, let’s turn to the numerator. Now we’re not permitted to use any digit twice. So there are still 10 possible first digits, but only 9 possible second digits, 8 possible third digits, and so forth. Thus there are 10! 10 · 9 8 7 6 5 4 3 = · · · · · · 2 = 1, 814, 400 serial numbers with all digits different. Plugging these results into the equation above, we find: 1, 814, 400 fraction dollars that are nondefective = 100, 000, 000 = 1.8144% 1.2 A Chess Problem In how many different ways can we place a pawn (p), a knight (k), and a bishop (b) on a chessboard so that no two pieces share a row or a column? A valid configuration is shown below on the the left, and an invalid configuration is shown on the right. k b p p b k valid invalid

ing ll First, we map this problem about chess pieces to a question about sequences. There is a bijection from configurations to sequences here rp, Tk, and ro are distinct rows and Cp, Ck, and cb are distinct columns. In particular, Tp is the pawn s row, cp is the pawn s column, Tk is the knight's row, etc. Now we can count the number of such sequences using the Generalized Product rule Tp is one of 8 rows p is one of 8 columns .Tk is one of 7 rows(any one but rp) Ck is one of 7 columns(any one but cp) .rb is one of 6 rows(any one but rp or rk Cb is one of 6 columns(any one but cp or Ck) Thus, the total number of configurations is (8.76) 1.3 Permutation A permutation of a set S is a sequence that contains every element of S exactly once. For example, here are all the permutations of the set a, b, cl (a, b, c)(a, c, b)(b, a, c) (b, c,a)(c,a, b)(c, b,a How many permutations of an n-element set are there? Well, there are n choices for the first element. For each of these, there are n-1 remaining choices for the second element For every combination of the first two elements, there are n-2 ways to choose the third element, and so forth Thus, there are a total of n·(n-1)·(n-2)…3·2.1=n! permutations of an n-element set. In particular, this formula says that there are 3!=6 permuations of the 3-element set a, b, c, which is the number we found above Permutations will come up again in this course approximately 1.6 bazillion times. In fact, permutations are the reason why factorial comes up so often and why we taught you Stirlings approximation m!

4 Counting II First, we map this problem about chess pieces to a question about sequences. There is a bijection from configurations to sequences (rp, cp, rk, ck, rb, cb) where rp, rk, and rb are distinct rows and cp, ck, and cb are distinct columns. In particular, rp is the pawn’s row, cp is the pawn’s column, rk is the knight’s row, etc. Now we can count the number of such sequences using the Generalized Product Rule: • rp is one of 8 rows cp • is one of 8 columns • rk is one of 7 rows (any one but rp) • ck is one of 7 columns (any one but cp) • rb is one of 6 rows (any one but rp or rk) • cb is one of 6 columns (any one but cp or ck) Thus, the total number of configurations is (8 7 · 6)2 · . 1.3 Permutations A permutation of a set S is a sequence that contains every element of S exactly once. For example, here are all the permutations of the set {a, b, c}: (a, b, c) (a, c, b) (b, a, c) (b, c, a) (c, a, b) (c, b, a) How many permutations of an n­element set are there? Well, there are n choices for the first element. For each of these, there are n − 1 remaining choices for the second element. For every combination of the first two elements, there are n − 2 ways to choose the third element, and so forth. Thus, there are a total of n · (n − 1) · (n − 2) 3 2 1 = · · · · · n! permutations of an n­element set. In particular, this formula says that there are 3! = 6 permuations of the 3­element set {a, b, c}, which is the number we found above. Permutations will come up again in this course approximately 1.6 bazillion times. In fact, permutations are the reason why factorial comes up so often and why we taught you Stirling’s approximation: n n n! ∼ √ 2πn � � e

Counting l 2 The division rule We can count the number of people in a room by counting ears and dividing by two Or we could count the number of fingers and divide by 10. Or we could count the number of fingers and toes and divide by 20. (Someone is probably short a finger or has an extra ear, but let's not worry about that right now. These observations lead to an important counting rule a k-to-1 function maps exactly k elements of the domain to every element of the range For example, the function mapping each ear to its owner is 2-to-1 t person A B ear 6 Similarly, the function mapping each finger to its owner is 10-to-1. And the function maping each each finger or toe to its owner is 20-to-1. Now just as a bijection implies two sets are the same size, a k-to-1 function implies that the domain is k times larger than the domain. Rule 2(Division Rule). If f: A-B is k-to-1, then [Al=k. BI Suppose A is the set of ears in the room and B is the set of people. Since we know there is a 2-to-1 mapping from ears to people, the Division Rule says that [A =2. B or, equivalently, B= Al /2. Thus, the number of people is half the number of ears Now this might seem like a stupid way to count people. But, surprisingly, many count- ing problems are made much easier by initially counting every item multiple times and then correcting the answer using the Division Rule. Let's look at some examples 2.1 Another chess problem In how many different ways can you place two identical rooks on a chessboard so that they do not share a row or column? A valid configuration is shown below on the left, and

� � � Counting II 5 2 The Division Rule We can count the number of people in a room by counting ears and dividing by two. Or we could count the number of fingers and divide by 10. Or we could count the number of fingers and toes and divide by 20. (Someone is probably short a finger or has an extra ear, but let’s not worry about that right now.) These observations lead to an important counting rule. A k­to­1 function maps exactly k elements of the domain to every element of the range. For example, the function mapping each ear to its owner is 2­to­1: ear 1 - person A 3 ear 2  PPPPPP  ear 3  q person B �  ear 4 q person C ear 5 PPP � - PPP ear 6 � Similarly, the function mapping each finger to its owner is 10­to­1. And the function maping each each finger or toe to its owner is 20­to­1. Now just as a bijection implies two sets are the same size, a k­to­1 function implies that the domain is k times larger than the domain: Rule 2 (Division Rule). If f : A → B is k­to­1, then |A| = k B· | |. Suppose A is the set of ears in the room and B is the set of people. Since we know there is a 2­to­1 mapping from ears to people, the Division Rule says that |A| = 2 · |B| or, equivalently, |B| = | | A /2. Thus, the number of people is half the number of ears. Now this might seem like a stupid way to count people. But, surprisingly, many count￾ing problems are made much easier by initially counting every item multiple times and then correcting the answer using the Division Rule. Let’s look at some examples. 2.1 Another Chess Problem In how many different ways can you place two identical rooks on a chessboard so that they do not share a row or column? A valid configuration is shown below on the left, and

ing ll an invalid configuration is shown on the right valid invalid Let a be the set of all sequences where ri and r2 are distinct rows and ci and c2 are distinct columns. let b be the set of all valid rook configurations. There is a natural function f from set A to set B; in particular, f maps the sequence(r1, C1, r2, C2)to a configuration with one rook in row r1, column Ci and the other rook in row r2, column c2 But now theres a snag. Consider the sequences (1,1,8,8) d(8,8,1,1) The first sequence maps to a configuration with a rook in the lower-left corner and a rook in the upper-right corner. The second sequence maps to a configuration with a rook in the upper-right corner and a rook in the lower-left corner. The problem is that those are two different ways of describing the same configuration In fact, this arrangement is shown on the left side in the diagram above More generally, the function f map exactly two sequences to every board configuration that is f is a 2-to-l function. Thus, by the quotient rule, A=2. B Rearranging terms 8·7)2 On the second line, weve computed the size of A using the General Product rule just as in the earlier chess problem 2.2 Knights of the Round Table In how many ways can King Arthur seat n different knights at his round table? Two lent if xample, the following two arrangements are equivalent:

6 Counting II an invalid configuration is shown on the right. r r r r valid invalid Let A be the set of all sequences (r1, c1, r2, c2) where r1 and r2 are distinct rows and c1 and c2 are distinct columns. Let B be the set of all valid rook configurations. There is a natural function f from set A to set B; in particular, f maps the sequence (r1, c1, r2, c2) to a configuration with one rook in row r1, column c1 and the other rook in row r2, column c2. But now there’s a snag. Consider the sequences: (1, 1, 8, 8) and (8, 8, 1, 1) The first sequence maps to a configuration with a rook in the lower­left corner and a rook in the upper­right corner. The second sequence maps to a configuration with a rook in the upper­right corner and a rook in the lower­left corner. The problem is that those are two different ways of describing the same configuration! In fact, this arrangement is shown on the left side in the diagram above. More generally, the function f map exactly two sequences to every board configuration; that is f is a 2­to­1 function. Thus, by the quotient rule, |A| | = 2 · |B . Rearranging terms gives: |B = |A| | 2 (8 · 7)2 = 2 On the second line, we’ve computed the size of A using the General Product Rule just as in the earlier chess problem. 2.2 Knights of the Round Table In how many ways can King Arthur seat n different knights at his round table? Two seatings are considered equivalent if one can be obtained from the other by rotation. For example, the following two arrangements are equivalent:

Counting l kl k 2 Let A be all the permutations of the knights, and let b be the set of all possible seating arrangements at the round table. We can map each permutator in set A seating arrangement in set B by seating the first knight in the permutation anywhere, putting the second knight to his left, the third knight to the left of the second, and so forth all the way around the table. For example (k2,k4,k1,k3)→k3 This mapping is actually an n-to-1 function from A to B, since all n cyclic shifts of the original sequence map to the same seating arrangement. In the example, n=4 different sequences map to the same seating arranement (k2,k4,k1,k3) (k4,k1,k3,k2) (k1,k3,k2,k4) (ka,k2,k4,k1) Therefore, by the division rule, the number of circular seating arrangements is 1B=14 Note that A=n! since there are n! permutations of n knights 3 Inclusion-Exclusion How big is a union of sets? For example, suppose there are 60 Math majors, 200 EECS majors, and 40 Physics majors. How many students are there in these three departments?

Counting II 7 ✧✦ ★✥ k1 k2 k3 k4 ✧✦ ★✥ k3 k4 k1 k2 Let A be all the permutations of the knights, and let B be the set of all possible seating arrangements at the round table. We can map each permutaton in set A to a circular seating arrangement in set B by seating the first knight in the permutation anywhere, putting the second knight to his left, the third knight to the left of the second, and so forth all the way around the table. For example: (k2, k4, k1, k3) ⇒ ✧✦ ★✥ k2 k4 k1 k3 This mapping is actually an n-to-1 function from A to B, since all n cyclic shifts of the original sequence map to the same seating arrangement. In the example, n = 4 different sequences map to the same seating arranement: (k2, k4, k1, k3) (k4, k1, k3, k2) (k1, k3, k2, k4) (k3, k2, k4, k1) ⇒ ✧✦ ★✥ k2 k4 k1 k3 Therefore, by the division rule, the number of circular seating arrangements is: |B| = |A| n = n! n = (n − 1)! Note that |A| = n! since there are n! permutations of n knights. 3 Inclusion-Exclusion How big is a union of sets? For example, suppose there are 60 Math majors, 200 EECS majors, and 40 Physics majors. How many students are there in these three departments?

ing ll Let M be the set of Math majors, E be the set of EECS majors, and p be the set of Physics majors. In these terms, we re asking for MUEUPl The Sum rule says that the size of union of disjoint sets is the sum of their sizes IMUEUP=M+E+P(if M, E, and P are disjoint However, the sets M, E, and P might not be disjoint. For example, there might be a student majoring in both Math and Physics. Such a student would be counted twice on the right sides of this equation, once as an element of M and once as an element of P. Norse, there might be a triple-major counting three times on the right side! Our last counting rule determines the size of a union of sets that are not necessarily disjoint. Before we state the rule, let's build some intuition by considering some easier special cases: unions of just two or three sets 3.1 Union of two sets For two sets, Si and S2, the size of the union is given by the following equation S1US2=|S1+|S2-|S1∩S2 Intuitively, each element of S1 is accounted for in the first term, and each element of S2 accounted for in the second term. elements in both S1 and s2 are counted twice- once in the first term and once in the second This double-counting is corrected by the final term We can prove equation(1)rigorously by applying the Sum Rule to some disjoint sub sets of S1U S2. As a first step, we observe that given any two sets, S, T, we can decompo S into the disjoint sets consisting of those elements in S but not T, and those elements in S and also in T. That is, S is the union of the disjoint sets S-Tand SnT. So by the Sum Rule we have S=|S-m+|S∩T and so IS-T=IS-ISnTI Now we decompose S1 U S2 into three disjoint sets S1∪S2=(S1-S2)∪(S2-S1)∪(S1∩S2) Now we have S1US2=(S1-S2)∪(S2-S1)U(S1∩S2 by(3) S1-S2+|S2-S1+|S1∩S2 (Sum Rule (1S1-|S1∩S2|)+(S2|-|S1nS2)+|51∩S2 by(2) S1+|S2|-|S1∩S2 (algebra)

8 Counting II Let M be the set of Math majors, E be the set of EECS majors, and P be the set of Physics majors. In these terms, we’re asking for | | M ∪ E ∪ P . The Sum Rule says that the size of union of disjoint sets is the sum of their sizes: | | | | | | | M ∪ E ∪ P = M| + E + P (if M, E, and P are disjoint) However, the sets M, E, and P might not be disjoint. For example, there might be a student majoring in both Math and Physics. Such a student would be counted twice on the right sides of this equation, once as an element of M and once as an element of P. Worse, there might be a triple­major counting three times on the right side! Our last counting rule determines the size of a union of sets that are not necessarily disjoint. Before we state the rule, let’s build some intuition by considering some easier special cases: unions of just two or three sets. 3.1 Union of Two Sets For two sets, S1 and S2, the size of the union is given by the following equation: | | | | | − | | S1 ∪ S2 = S1| + S2 S1 ∩ S2 (1) Intuitively, each element of S1 is accounted for in the first term, and each element of S2 is accounted for in the second term. Elements in both S1 and S2 are counted twice— once in the first term and once in the second. This double­counting is corrected by the final term. We can prove equation (1) rigorously by applying the Sum Rule to some disjoint sub￾sets of S1 ∪S2. As a first step, we observe that given any two sets, S, T, we can decompose S into the disjoint sets consisting of those elements in S but not T, and those elements in S and also in T. That is, S is the union of the disjoint sets S − T and S ∩ T. So by the Sum Rule we have |S| = |S − T| + |S ∩ T| , |S − T| = |S| − |S ∩ T| . and so (2) Now we decompose S1 ∪ S2 into three disjoint sets: S1 ∪ S2 = (S1 − S2) ∪ (S2 − S1) ∪ (S1 ∩ S2). (3) Now we have | | | S1 ∪ S2 = (S1 − S2) ∪ (S2 − S1) ∪ (S1 ∩ S2)| (by (3)) = | | | | | | S1 − S2 + S2 − S1 + S1 ∩ S2 (Sum Rule) = (|S1| − | | | | − | | | | S1 ∩ S2 ) + ( S2 S1 ∩ S2 ) + S1 ∩ S2 (by (2)) = | | | − | | S1| + S2 S1 ∩ S2 (algebra)

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)

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 rule

10 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