Problem 1(a)(b)(c)Problem 2(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)(m)(n)(o)Problem 3(a)(b)(c)(d)(e)(f)(g)� � �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 nk| | · n2 · n3 · · ·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 3ear 2 PPPPPP ear 3 q person B �ear 4 qperson C PPPPPPear 5 � -ear 6 � Rule 2 (Division Rule). If f : A → B is k-to-1, then |A = k B|.| · |2 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. 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)!.3 Recitation 14 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� � 4 Recitation 14 (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 OODOOD OLL 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 nkand 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.� � � � 5 Recitation 14 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 nnumber 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 =
View Full Document
Unlocking...