《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