《Mathematics for Computer》Notes for Recitation 14

6.042/18.062] Mathematics for Computer Science April 1, 2005 Srini devadas and Eric Lehman Notes for Recitation 14 Counting rules Rule 1(Generalized Product Rule). Let s be a set of length-k sequences. If there are: mi possible first entries, n2 possible second entries for each first entry m3 possible third entries for each combination of first and second entries, etc n1·n2·n3··k Ak-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 A ear ear ear 4 ear 5 person C ear Rule 2 (Division Rule). If f: A-B is k-to-l, then a=k. B

� � � 6.042/18.062J Mathematics for Computer Science April 1, 2005 Srini Devadas and Eric Lehman Notes for Recitation 14 Counting Rules 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 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 � Rule 2 (Division Rule). If f : A → B is k­to­1, then |A| = k B· | |

Recitation 14 The generalized product rule Problem 1. Solve the following counting problems using the generalized product rule (a) Next week, I'm going to get really fit! On day 1, I'll exercise for 5 minutes each subsequent day, I'll exercise 0, 1, 2, or 3 minutes more than the previot For example, the number of minutes that I exercise on the seven days of next might be 5, 6, 9,9, 9, 11, 12. How many such sequences are possible? Solution. The number of minutes on the first day can be selected in 1 way. The number of minutes on each subsequent day can be selected in 4 ways. Therefore the number of exercise sequences is 1. 4 by the extended product rule (b) An r-permutation of a set is a sequence of r distinct elements of that set. For example, here are all the 2-permutations of a, b, c, d] (b,a)(b,c)(b,d) (c, a)(c, b)(c, d) (d,a)(d,b)(d,c) How many r-permutations of an n-element set are there? express your answer uS- factorial notatio Solution. There are n ways to choose the first element, n-1 ways to choose the second, n-2 ways to choose the third,. . and there are n -r+ l ways to choose the r-th element Thus, there are n·(n-1)·(n-2)…(n-r+1)= r-permutations of an n-element set (c) How many n x n matrices are there with distinct entries drawn from (1,.,p). where p≥n2? Solution. There are p ways to choose the first entry, p-1 ways to choose the second for each way of choosing the first, p-2 ways of choosing the third, and so forth. In all there are p(p-1)(p-2)…(p-n2+1) such matrices. Alternatively this is the number of n2-permutations of a p element set, which is p! /(p-n2)

Recitation 14 2 The Generalized Product Rule Problem 1. Solve the following counting problems using the generalized product rule. (a) Next week, I’m going to get really fit! On day 1, I’ll exercise for 5 minutes. On each subsequent day, I’ll exercise 0, 1, 2, or 3 minutes more than the previous day. For example, the number of minutes that I exercise on the seven days of next week might be 5, 6, 9, 9, 9, 11, 12. How many such sequences are possible? Solution. The number of minutes on the first day can be selected in 1 way. The number of minutes on each subsequent day can be selected in 4 ways. Therefore, the number of exercise sequences is 1 · 46 by the extended product rule. (b) An r­permutation of a set is a sequence of r distinct elements of that set. For example, here are all the 2­permutations of {a, b, c, d}: (a, b) (a, c) (a, d) (b, a) (b, c) (b, d) (c, a) (c, b) (c, d) (d, a) (d, b) (d, c) How many r­permutations of an n­element set are there? Express your answer us￾ing factorial notation. Solution. There are n ways to choose the first element, n − 1 ways to choose the second, n − 2 ways to choose the third, . . . , and there are n − r + 1 ways to choose the r­th element. Thus, there are: n! n · (n − 1) · ( n − r + 1) = (n − r)! n − 2)· · ·( r­permutations of an n­element set. (c) How many n × n matrices are there with distinct entries drawn from {1, . . . , p}, where p ≥ n2? Solution. There are p ways to choose the first entry, p −1 ways to choose the second for each way of choosing the first, p − 2 ways of choosing the third, and so forth. In all there are p! p(p − 1)(p − 2)· · ·(p − n 2 + 1) = (p − n2)! such matrices. Alternatively, this is the number of n2­permutations of a p element set, which is p!/(p − n2)!

Recitation 14 The Tao of booKKeeper Problem 2. In this problem, we seek enlightenment through contemplation of the word BOOKKEEPER (a) In how many ways can you arrange the letters in the word POKE? Solution. There are 4! arrangments corresponding to the 4! permutations of the set IP,O,K,EH (b) In how many ways can you arrange the letters in the word Bo, k? Observe that we have subscripted the Os to make them distinct symbols Solution. There are 4! arrangments corresponding to the 4! permutations of the set {B,O1,O2,K} (c) Suppose we map arrangements of the letters in BO1 O2K to arrangements of the letters in BOOK by erasing the subscripts. Indicate with arrows how the arrange ments on the left are mapped to the arrangements on the right O2 BO,K KO2BO1 O1BO2K BOOK KO,BO. OBOK KOBO BO1O2K BO2O,K (d) What kind of mapping is this, young grasshopper? Solution 2-to-1 (e) In light of the Division Rule, how many arrangements are there of BOOK? Solution. 4 /2 (f)Very good, young master! How many arrangements are there of the letters in KE1E2PE3R? by erasing subscripts. List all the different arrangements of KEiErPE3R that are (g) Suppose we map each arrangement of K E1E2 PEsR to an arrangement of KEEP mapped to REPEEK in this way. Solution. RElPE2E3K, reyPE3E2k, re2PElE3k, rerPE3Elk, RE3 PElE2K RE3PE2EIK (h) What kind of mapping is this? Solution 3 -to-1

Recitation 14 3 The Tao of BOOKKEEPPER Problem 2. In this problem, we seek enlightenment through contemplation of the word BOOKKEEP ER. (a) In how many ways can you arrange the letters in the word P OKE? Solution. There are 4! arrangments corresponding to the 4! permutations of the set {P, O, K, E}. (b) In how many ways can you arrange the letters in the word BO1O2K? Observe that we have subscripted the O’s to make them distinct symbols. Solution. There are 4! arrangments corresponding to the 4! permutations of the set {B, O1, O2, K}. (c) Suppose we map arrangements of the letters in BO1O2K to arrangements of the letters in BOOK by erasing the subscripts. Indicate with arrows how the arrange￾ments on the left are mapped to the arrangements on the right. O2BO1K KO2BO1 BOOK O1BO2K OBOK KO1BO2 KOBO BO1O2K . . . BO2O1K . . . (d) What kind of mapping is this, young grasshopper? Solution. 2­to­1 (e) In light of the Division Rule, how many arrangements are there of BOOK? Solution. 4!/2 (f) Very good, young master! How many arrangements are there of the letters in KE1E2P E3R? Solution. 6! (g) Suppose we map each arrangement of KE1E2P E3R to an arrangement of KEEP ER by erasing subscripts. List all the different arrangements of KE1E2P E3R that are mapped to REP EEK in this way. Solution. RE1P E2E3K, RE1P E3E2K, RE2P E1E3K, RE2P E3E1K, RE3P E1E2K, RE3P E2E1K (h) What kind of mapping is this? Solution. 3!­to­1

Recitation 14 (i) So how many arrangements are there of the letters in KEEPER? Solution. 6! /3! G) Now you are ready to face the bookKeeper! How many arrangements of B0102KiK2ElE2PE3R are there? Solution 10! (k) How many arrangements of BOOKiK2E1E2PE3R are there? Solution. 10!/ 2 ( How many arrangements of BOOKKElE2PE3R are there? Solution. 10! /(2!. 2! (m) How many arrangements of BOOKKEEPER are there? Solution.10!/(2!.2!.3) (n) How many arrangements of VOODOO DOLL are there? Solution.10/(2!.2.5) (o)(IMPORTANT) How many n-bit sequences contain k zeros and (n-k)ones? Solution n! /(k!(n-k)!) This quantity is denoted(r)and read"n choose k". You will see it almost every day in 6.042 from now until the end of the term Remember well what you have learned: subscripts on, subscripts of This is the Tao of Bookkeeper

� � Recitation 14 4 (i) So how many arrangements are there of the letters in KEEP ER? Solution. 6!/3! (j) Now you are ready to face the BOOKKEEPER! How many arrangements of BO1O2K1K2E1E2P E3R are there? Solution. 10! (k) How many arrangements of BOOK1K2E1E2P E3R are there? Solution. 10!/2! (l) How many arrangements of BOOKKE1E2P E3R are there? Solution. 10!/(2! · 2!) (m) How many arrangements of BOOKKEEP ER are there? Solution. 10!/(2! 2! · · 3!) (n) How many arrangements of V OODOODOLL are there? Solution. 10!/(2! 2! · · 5!) (o) (IMPORTANT) How many n­bit sequences contain k zeros and (n − k) ones? Solution. n!/(k! · (n − k)!) This quantity is denoted n k and read “n choose k”. You will see it almost every day in 6.042 from now until the end of the term. Remember well what you have learned: subscripts on, subscripts off. This is the Tao of Bookkeeper

Recitation 14 5 Problem 3. Solve the following counting problems. Define an appropriate mapping(bi jective or k-to-1) between a set whose size you know and the set in question (a)(IMPORTANT) In how many ways can k elements be chosen from an n-element Solution. There is a bijection from n-bit sequences k ones. The sequence (b1, .. bn)maps to the subset that contains i if and if bi= 1. Therefore, the number of such subsets is(r) (b)How many different ways are there to select a dozen donuts if four varieties are available? Solution. There is a bijection from selections of a dozen donuts to 15-bit sequences with exactly 3 ones. In particular, suppose that the varieties are glazed, chocolate, on creme. Then a selection of g gla Boston creme maps to the sequence: (g0s)1(c06)1(06)1(b0s) Therefore, the number of selections is equal to the number of 15-bit sequences with exactly 3 ones, which is 15! 3!12! 3 (c) How many paths are there from(0, 0) to(10, 20) consisting of right-steps(which increment the first coordinate)and up-steps(which increment the second coord nate)? Solution. There is a bijection from 30-bit sequences with 10 zeros and 20 ones. The sequence(b1,., b30) maps to a path where the i-th step is right if bi =0 and up if bi= 1. Therefore, the number of paths is equal to Go) (d) An independent living group is hosting eight pre-frosh, affectionately known at Pi,..., Ps by the permanent residents. Each pre-frosh must must be assigned a task 2 must wash pots 2 must clean the kitchen 1 must clean the bathrooms 1 must clean the common area, and 2 must serve dinner. In how many ways can Pl,..., P8 put to productive use Solution. There is a bijection from sequences containing two P's, two Ks,a B, a C, and two D's. In particular, the sequence(t1,., ts)corresponds to assigning Pi to washing pots if ti= P, to cleaning the kitchen if ti= K, to cleaning the bathrooms if ti= B, etc. Therefore, the number of possible assignments is 2!2!1!1!2!

� � � � Recitation 14 5 Problem 3. Solve the following counting problems. Define an appropriate mapping (bi￾jective or k­to­1) between a set whose size you know and the set in question. (a) (IMPORTANT) In how many ways can k elements be chosen from an n­element set {x1, x2, . . . , xn}? Solution. There is a bijection from n­bit sequences with k ones. The sequence (b1, . . . , bn) maps to the subset that contains xi if and only if bi = 1. Therefore, the n number of such subsets is . k (b) How many different ways are there to select a dozen donuts if four varieties are available? Solution. There is a bijection from selections of a dozen donuts to 15­bit sequences with exactly 3 ones. In particular, suppose that the varieties are glazed, chocolate, lemon, and Boston creme. Then a selection of g glazed, c chocolate, l lemon, and b Boston creme maps to the sequence: (g 0� s) 1 (c 0� s) 1 (l 0� s) 1 (b 0� s) Therefore, the number of selections is equal to the number of 15­bit sequences with exactly 3 ones, which is: � � 15! 15 = 3! 12! 3 (c) How many paths are there from (0, 0) to (10, 20) consisting of right­steps (which increment the first coordinate) and up­steps (which increment the second coordi￾nate)? Solution. There is a bijection from 30­bit sequences with 10 zeros and 20 ones. The sequence (b1, . . . , b30) maps to a path where the i­th step is right if bi = 0 and up if bi = 1. Therefore, the number of paths is equal to 30 . 10 (d) An independent living group is hosting eight pre­frosh, affectionately known at P1, . . . , P8 by the permanent residents. Each pre­frosh must must be assigned a task: 2 must wash pots, 2 must clean the kitchen, 1 must clean the bathrooms, 1 must clean the common area, and 2 must serve dinner. In how many ways can P1, . . . , P8 be put to productive use? Solution. There is a bijection from sequences containing two P’s, two K’s, a B, a C, and two D’s. In particular, the sequence (t1, . . . , t8) corresponds to assigning Pi to washing pots if ti = P, to cleaning the kitchen if ti = K, to cleaning the bathrooms if ti = B, etc. Therefore, the number of possible assignments is: 8! 2! 2! 1! 1! 2!

Recitation 14 (e) In how many ways can Mr and Mrs. Grumperson distribute 13 indistinguishable pieces of coal to their two--no, threel--children for Christmas? Solution. There is a bijection from 15-bit strings with two ones. In particular, the bit string 0@1010 maps to the assignment of a coals to the first child, b coals to the second, and c coals to the third. Therefore, there are(2)assignments (f) How many solutions over the natural numbers are there to the equation x1+x2+..+x10≤100 Solution. There is a bijection from 110-bit sequences with 10 ones to solutions to this equation. In particular, ai is the number of zeros before the i-th one but after the (i-1)-st one(or the beginning of the sequence). Therefore, there are(10) solutions (g(Quiz 2, Fall03)Suppose that two identical 52-card decks of are mixed together n how many ways can the cards in this double-size deck be arranged? Solution. The number of sequences of the 104 cards containing 2 of each card is 104!/(2

� � � � Recitation 14 6 (e) In how many ways can Mr. and Mrs. Grumperson distribute 13 indistinguishable pieces of coal to their two— no, three!— children for Christmas? Solution. There is a bijection from 15­bit strings with two ones. In particular, the bit string 0a10b 10c maps to the assignment of a coals to the first child, b coals to the second, and c coals to the third. Therefore, there are 15 assignments. 2 (f) How many solutions over the natural numbers are there to the equation: x1 + x2 + . . . + x10 ≤ 100 Solution. There is a bijection from 110­bit sequences with 10 ones to solutions to this equation. In particular, xi is the number of zeros before the i­th one but after the (i − 1)­st one (or the beginning of the sequence). Therefore, there are 110 solutions. 10 (g) (Quiz 2, Fall ’03) Suppose that two identical 52­card decks of are mixed together. In how many ways can the cards in this double­size deck be arranged? Solution. The number of sequences of the 104 cards containing 2 of each card is 104!/(2!)52