Skip to content
Textbook Guides

Solution Manual for Discrete Mathematics for Computer Scientists, 1st Edition

Solution Manual for Discrete Mathematics for Computer Scientists, 1st Edition helps you navigate your textbook with ease, offering answers to every question.

Preview 16 of 145 pages

See the first 16 pages exactly as they appear in the document.

  1. Page 1
    Read page 1 as text

    Bogart-81046 book April 27, 2005 17:12 1 COUNTING 1.1 BASIC COUNTING Pages 7 to 8 Problem 1 Solution The value of i ranges from 2 to n . When i = k , the variable j ranges from 2 to k . Thus, there are at most k − 1 comparisons (because we stop if j = 2). Thus, the total number of comparisons is 1 + 2 + · · · + n − 1 = n ( n − 1 ) 2 . The algorithm will make this number of comparisons if the original ordering is the reverse of the sorted ordering. Problem 2 Solution Number the five teams 1–5. Team 1 must play all four others. Team 2 will be in one of these games but must play in three more games with Teams 3, 4, and 5. Team 3 is in two of the games already mentioned and must still play Teams 4 and 5 for two more games. Team 4 must play Team 5, in addition to playing in three of the games already mentioned. Thus, there are 4 + 3 + 2 + 1 = 10 games. Alternatively, there are five teams, each of which must play in four games, giving us 20 pairings of two teams each. However, each game involves two of these pairings, so there are 20 / 2 = 10 games. S1

  2. Page 2
  3. Page 3
    Read page 3 as text

    Bogart-81046 book April 27, 2005 17:12 Problem 3 Solution The set of possible draws is a union of 52 sets (one for each possible first card), each of size 51. So, by the product principle, there are 52 · 51 ways to draw the two cards. Problem 4 Solution The answer is the same as in Problem 3, except we can draw the cards in either order. Therefore, the number of ways is 52 · 51 / 2 = 1326. Problem 5 Solution 52 · 51 · 50, by two applications of the product principle. Problem 6 Solution 10 · 9 = 90. Problem 7 Solution ( 10 2 ) = 10 · 9 / 2 = 45. Problem 8 Solution 10 · ( 9 2 ) , or 8 ( 10 2 ) . Problem 9 Solution This formula counts the number of ways to choose a president and an executive advisory board (not including the president) from a club of n people. The left side chooses the president first, then the committee. The right side chooses the committee first, then the president. Problem 10 Solution m · n . Problem 11 Solution By the product rule, there are 10 · 9 = 90 ways to choose two-scoop cones with two different flavors. However, according to your mother’s rule, the order of scoops doesn’t matter. Because each two-scoop cone can be ordered in two different ways (e.g., chocolate over vanilla and vanilla over chocolate), we have 90 / 2 = 45 ways of choosing two-scoop cones with different flavors. There are an additional ten cones with the same flavor for both scoops, giving 55 possible cones. S2 Chapter 1: Counting

  4. Page 4
    Read page 4 as text

    Bogart-81046 book April 27, 2005 17:12 Problem 12 Solution Because order does matter, we have 10 · 9 = 90 ways to choose ice cream cones with two distinct flavors, plus ten more with the same flavor for both scoops, giving 100 choices. Problem 13 Solution 1 + 2 + 4 + · · · + 2 19 = 2 20 − 1 = 1,048,575. Your justification may be neither principle, only the sum principle (the set of all pennies is the union of the set of pennies on Day 1 with those on Day 2, and so on), or both principles (the set of pennies you receive on Day i is the union of two sets of pennies, each of the size that you received on Day i − 1). As long as your explanation makes sense, any of these answers is fine. Problem 14 Solution 5 · 3 · 3 · 3 = 135. Problem 15 Solution Yes; in Line 4, j could start at i + 1 rather than i . 1.2 COUNTING LISTS, PERMUTATIONS, AND SUBSETS Pages 17 to 19 Problem 1 Solution For each piece of fruit, we have n choices of who to give it to. So, by version 2 of the product principle, the number of ways to pass out the fruit is n k . Problem 2 Solution f 1 ( 1 ) = a f 1 ( 2 ) = a f 1 ( 3 ) = a f 2 ( 1 ) = a f 2 ( 2 ) = a f 2 ( 3 ) = b f 3 ( 1 ) = a f 3 ( 2 ) = b f 3 ( 3 ) = a f 4 ( 1 ) = a f 4 ( 2 ) = b f 4 ( 3 ) = b f 5 ( 1 ) = b f 5 ( 2 ) = a f 5 ( 3 ) = a f 6 ( 1 ) = b f 6 ( 2 ) = a f 6 ( 3 ) = b f 7 ( 1 ) = b f 7 ( 2 ) = b f 7 ( 3 ) = a f 8 ( 1 ) = b f 8 ( 2 ) = b f 8 ( 3 ) = b None are one-to-one; all but f 1 and f 8 are onto. 1.2: Counting Lists, Permutations, and Subsets S3

  5. Page 5
    Read page 5 as text

    Bogart-81046 book April 27, 2005 17:12 Problem 3 Solution f 1 ( 1 ) = a f 1 ( 2 ) = a f 2 ( 1 ) = a f 2 ( 2 ) = b f 3 ( 1 ) = a f 3 ( 2 ) = c f 4 ( 1 ) = b f 4 ( 2 ) = a f 5 ( 1 ) = b f 5 ( 2 ) = b f 6 ( 1 ) = b f 6 ( 2 ) = c f 7 ( 1 ) = c f 7 ( 2 ) = a f 8 ( 1 ) = c f 8 ( 2 ) = b f 9 ( 1 ) = c f 9 ( 2 ) = c None of the functions are onto; all except f 1 , f 5 , and f 9 are one-to-one. Problem 4 Solution If we list S as x 1 , x 2 , . . . , x s , then there is a bijection between functions from S to T and lists f ( x 1 ), f ( x 2 ), . . . , f ( x s ) . For each i , there are t choices for f ( x i ) . So, by the product principle, there are t s functions from S to T . Problem 5 Solution We are asking for the number of k -element permutations of n children, which is n k , or zero, if k > n . Problem 6 Solution What matters is what subset of the n children get fruit, so the answer is ( n k ) . If k > n , the answer is zero. Problem 7 Solution First, note that “a five-digit base 10 number” means a string of five digits, where the first digit is not 0 and each digit is in the set { 0 , 1 , . . . , 9 } . By the product rule, the number of these is 9 · 10 4 , or 90,000. If no two consecutive digits can be equal, then there are nine choices for the first digit, nine for the second (any digit other than the first), nine for the third (any digit other than the second), and so on. By the product principle, the total number is 9 5 . By the sum principle, the total number of five-digit numbers equals the number that have no two consecutive digits equal plus the number that have at least one pair of consecutive digits equal. Thus, letting x denote the number of the latter, we have 9 · 10 4 = 9 5 + x ; so, x = 9 · 10 4 − 9 5 = 30,951. S4 Chapter 1: Counting

  6. Page 6
    Read page 6 as text

    Bogart-81046 book April 27, 2005 17:12 Problem 8 Solution In both cases, there are two ways to decide whether the leftmost spot is for a student or for an administrator. This decision determines which four places are for students and which are for administrators. Thus, there are 4! ways to assign the students to their places and 4! ways to assign the administrators to their places. In both cases, the product principle leads us to conclude that there are 2 · 4! · 4! lists. Problem 9 Solution 123 124 125 132 134 135 142 143 145 152 153 154 213 214 215 231 234 235 241 243 245 251 253 254 312 314 315 321 324 325 341 342 345 351 352 354 412 413 415 421 423 425 431 432 435 451 452 453 512 513 514 521 523 524 531 532 534 541 542 543 Six permutations correspond to any given three-element set. We have 60 permutations, so there are 10 three-element sets. Problem 10 Solution ( 20 3 ) = 20 · 19 · 18 / 6 = 1140. Problem 11 Solution ( 10 4 )( 20 4 ) . Problem 12 Solution 2 ( 10 4 )( 20 4 ) 4!4! = 2 · 10 4 20 4 . Problem 13 Solution When both scoops have the same flavor, we have 10 possibilities, because there are only 10 flavors. When the scoops have different flavors, we have 45 possibilities, according to your mother’s rule, as solved before. So, for ice cream, we have 10 + 45 = 55 possibilities. For topping, we have 3 possibilities. For whipped cream, nuts, and cherry, because we may either have any, all, or none, we have 2 possibilities for each of them (for example, either have cherry or don’t have cherry). By the product rule, we have 2 · 2 · 2 = 8 possibilities. Thus, we have 55 · 3 · 8 = 1320 possible sundaes. 1.2: Counting Lists, Permutations, and Subsets S5

  7. Page 7
    Read page 7 as text

    Bogart-81046 book April 27, 2005 17:12 Problem 14 Solution Although this problem is similar to Problem 13, we may have three different flavors (there are 10 · 9 · 8 / 6 = 2880 ways to choose three flavors), two scoops of one flavor and one of a second (there are 10 · 9 = 90 ways to do this), or three scoops of the same flavor (there are 10 ways to choose these). Thus, we have 220 · 3 · 8 = 5280 different sundaes. Problem 15 Solution Suppose we list the people in the club in some way and keep that list for the remainder of the problem. Take the first person from the list and pair that person with any of the 2 n − 1 remaining people. Now take the next unpaired person from the list and pair that person with any of the remaining 2 n − 3 unpaired people. Continuing in this way, once k pairs have been selected, take the next unpaired person from the list and pair that person with any of the remaining 2 n − 2 k − 1 unpaired people. Every pairing can arise in this way, and no pairing can arise twice in this process. Thus, the number of outcomes is ∏ n − 1 i = 0 2 n − 2 i − 1. For another solution, choose people in pairs. There are ( 2 n 2 ) ways to choose one pair, ( 2 n − 2 2 ) ways to choose a second pair, and once k pairs have been chosen, there are ( 2 n − 2 k 2 ) ways to choose the next pair. The number of lists of pairs we get in this way is ∏ n − 1 i = 0 ( 2 n − 2 i 2 ) = ( 2 n ) ! 2 i . Both ways of pairing people gets listed n ! times because we see all possible lists of pairs of length n . Therefore, the number of actual pairings is ( 2 n ) ! ( 2 n ) n ! = 2 n ! 2 n · 2 n − 2 · 2 n − 4 · · · · · 2 = n − 1 ∏ i = 0 ( 2 n − 2 i − 1 ) . For the second question, multiply the answer to the first question by 2 n to give ( 2 n ) ! / n !. Problem 16 Solution ( 12 5 ) . ( 5 2 )( 4 2 )( 3 1 ) = 180. ( 5 2 )( 4 2 )( 1 1 ) + ( 5 2 )( 5 2 )( 2 1 ) —that is, either the versatile player is playing center or not; if not, that player is available to play forward. Problem 17 Solution If f is one-to-one, it has n distinct values. Therefore, all elements of the range must be values of f , so it must be onto. Thus, a one-to-one function from an n -element set to an n -element set is onto. If we now suppose that f is onto, then f has n distinct values because it maps onto a set of size n . But in this case, we may conclude that because there are only n values of x , all the values of f ( x ) are different. Therefore, f must be one-to-one. S6 Chapter 1: Counting

  8. Page 8
    Read page 8 as text

    Bogart-81046 book April 27, 2005 17:12 Problem 18 Solution a. If f is a bijection, we may define g ( y ) to be the unique x such that f ( x ) = y . This defines a function because different values of y are related to different values of x . But then f ( g ( y )) is the result of applying f to the unique x with f ( x ) = y , so f ( g ( y )) = y . Also, g ( f ( x )) is the unique x that is related to f ( x ) , so g ( f ( x )) = x . This shows that if f is a bijection, then f has an inverse function. On the other hand, if f has an inverse function g and if f ( x ) = f ( x ′ ) , then g ( f ( x )) = g ( f ( x ′ )) , which gives us x = x ′ . Therefore, if f has an inverse function, then f is one-to-one. Further, if f has an inverse function g , then because y = f ( g ( y )) and g ( y ) is in the domain of f , there is an x in the domain of f (namely, g ( y ) ) such that f ( x ) = y ; so, f is onto. b. Suppose g and h both satisfy the definition of being inverses to f . Suppose y is in the range of f and g ( y ) = x . Then, f ( g ( y )) = f ( x ) and h ( f ( g ( y ))) = h ( f ( x )) = x . Because f ( g ( y )) = y , we have h ( y ) = x as well. Thus, for any y in the range of f , h ( y ) = g ( y ) , which means that g and h are equal. Thus, f has only one inverse function. 1.3 BINOMIAL COEFFICIENTS Pages 26 to 28 Problem 1 Solution 220, 220. ( n k ) equals ( n n − k ) . Problem 2 Solution 1 8 28 56 70 56 28 8 1 Problem 3 Solution a. ( x + 1 ) 5 = x 5 + 5 x 4 + 10 x 3 + 10 x 2 + 5 x + 1. b. ( x + y ) 5 = x 5 + 5 x 4 y + 10 x 3 y 2 + 10 x 2 y 3 + 5 x y 4 + y 5 . c. ( x + 2 ) 5 = x 5 + 10 x 4 + 40 x 3 + 80 x 2 + 80 x + 32. d. ( x − 1 ) 5 = x 5 − 5 x 4 + 10 x 3 − 10 x 2 + 5 x − 1. Problem 4 Solution ( x + y ) 4 = x 4 + ( 4 1 ) x 3 y 1 + ( 4 2 ) x 2 y 2 + ( 4 3 ) x 1 y 3 + y 4 . To expand the product, we create all possible products of x ’s and y ’s by selecting y from some of the factors and x from the remaining ones. Then we add all these products. There is 1 = ( 4 0 ) way to choose a y from none of our four x + y factors. Thus, the coefficient of x 4 is 1. There 1.3: Binomial Coefficients S7

  9. Page 9
    Read page 9 as text

    Bogart-81046 book April 27, 2005 17:12 are ( 4 1 ) ways to choose a y from one of the four factors. Because we choose x from the remaining factors, this choice gives us the term ( 4 1 ) x 3 y . There are ( 4 2 ) ways to choose y from two of our four factors, so the coefficient of x 2 y 2 is ( 4 2 ) . There are ( 4 3 ) ways to choose y from three of our factors, so the coefficient of x y 3 is ( 4 3 ) . There is 1 = ( 4 4 ) way to choose y from all the factors, so the coefficient of y 4 is 1. Problem 5 Solution 10! /( 3!3!4! ) = 4200. This is the number of ways to label three of the chairs with the label green, three of the chairs with the label blue, and four of the chairs with the label red. Problem 6 Solution The multinomial coefficient ( n n 1 , n 2 ,..., n k ) is the coefficient of x n 1 1 x n 2 2 · · · x n k k in ( x 1 + x 2 + · · · + x k ) n . The proof is just like the proofs of the binomial theorem and the trinomial theorem. Problem 7 Solution If N is a set and K is a subset of N , let N − K stand for the set of all elements of N that are not in K . If f ( K ) = N − K , then f is a bijection that maps the k -element subsets of N onto the ( n − k ) -element subsets of N . Problem 8 Solution ( m + n n ) or ( m + n m ) , because of the following: • From any line segment on our path, we have two choices: horizontal and vertical. Clearly, we need n vertical line segments and m horizontal line segments to reach ( m , n ) in exactly m + n steps. • By deciding on our choice of n vertical lines, we have also decided the choice of m horizontal lines, because we must choose a horizontal line for each step that is not a vertical line. We could also start by choosing m horizontal lines, which automatically decides the choice of n vertical lines. Thus, the number of ways to choose the path is the number of ways to choose the n places for vertical lines from m + n places or the m places for horizontal lines from m + n places. Problem 9 Solution ∑ n i = 0 ( n i ) x i y n − i = y n + ( n 1 ) x y n − 1 + ( n 2 ) x 2 y n − 2 + · · · + x n . S8 Chapter 1: Counting

  10. Page 10
    Read page 10 as text

    Bogart-81046 book April 27, 2005 17:12 Problem 10 Solution Once we choose four disjoint subsets from a 12-element set, we may label them in 4! ways. That is, choosing the sets does not tell us which set to label with which label. Therefore, the number of choices of the four sets is the number of labelings divided by 4!, namely, 12! 4! ( 3! ) 4 . The number of ways to choose three disjoint subsets of size four from a 12-element set is 12! 3! ( 4! ) 3 . Problem 11 Solution For the first case, the president may be chosen from 20 persons, and after that, the vice president may chosen from 19 persons, the secretary from 18 persons, and the treasurer from 17 persons. The nominations committee may be chosen from the remaining 16 persons without order mattering. So, there are 20 · 19 · 18 · 17 · ( 16 3 ) ways to choose the committee. For the second case, the nominating committee may be chosen from the 20 persons without order mattering. So, there are 20 · 19 · 18 · 17 · ( 20 3 ) ways to choose the committee. Problem 12 Solution ( n − 1 k − 1 ) + ( n − 1 k ) = ( n − 1 ) ! ( k − 1 ) ! ( n − k ) ! + ( n − 1 ) ! k ! ( n − k − 1 ) ! = ( n − 1 ) ! k ( k ) ! ( n − k ) ! + ( n − 1 ) ! ( n − k ) k ! ( n − k ) ! = ( n − 1 ) ! ( k + n − k ) k ! ( n − k ) ! = n ! k ! ( n − k ) ! = ( n k ) . Problem 13 Solution Proof 1: n ! k ! ( n − k ) ! = n ! ( n − k ) ! k ! . Proof 2: The number of ways to choose the k elements that are in a k -element subset is the same as the number of ways to choose the elements that are not in the subset, and there are n − k such elements. 1.3: Binomial Coefficients S9

  11. Page 11
    Read page 11 as text

    Bogart-81046 book April 27, 2005 17:12 Problem 14 Solution Proof 1: ( n k ) ( k j ) = n ! k ! ( n − k ) ! k ! j ! ( k − j ) ! = n ! ( n − k ) ! j ! ( k − j ) ! = n ! j ! ( n − j ) ! ( n − j ) ! ( k − j ) ! ( n − k ) ! = ( n j ) ( n − j k − j ) . Proof 2: The number of ways to choose k items from n items and then choose j items from the chosen k items is ( n k )( k j ) . We can also carry out this process in the following way: First choose j items from n items, and then choose k − j more items from the remaining n − j items. The number of ways to do this is ( n j )( n − j k − j ) . Problem 15 Solution Proof 1: ( n k ) ( n − k j ) = n ! ( n − k ) ! k ! ( n − k ) ! j ! ( n − k − j ! ) = n ! k ! j ! ( n − k − j ) ! . Similarly, ( n k )( n − k j ) equals the same expression. Proof 2: There are two ways of choosing two disjoint sets, one with k elements and one with j elements. We can pick the k -element set first, then choose j elements from what is left, or we can pick the j -element set first, then choose k elements from what is left. Problem 16 Solution n k 3 4 5 6 6 20 15 6 1 7 35 21 7 8 56 28 9 84 Problem 17 Solution The formula is simply the expansion of ( 1 − 1 ) n . S10 Chapter 1: Counting

  12. Page 12
    Read page 12 as text

    Bogart-81046 book April 27, 2005 17:12 Problem 18 Solution ( 1 + x ) n = ∑ n i = 0 ( n i ) x i . Taking the derivative of both sides, we get n ( 1 + x ) n − 1 = n ∑ i = 1 i ( n i ) x i − 1 . Thus, if we let x = 1, we have n 2 n − 1 = ∑ n i = 1 i ( n i ) . Problem 19 Solution False. ( 4 2 ) is 6, but ( 2 0 ) + ( 2 1 ) + ( 2 2 ) is 4. The correct statement is ( n k ) = ( n − 2 k − 2 ) + 2 ( n − 2 k − 1 ) + ( n − 2 k ) . The proof consists of applying the Pascal relationship to both ( n − 1 k − 1 ) and ( n − 1 k ) and adding the results. 1.4 EQUIVALENCE RELATIONS AND COUNTING Pages 38 to 41 Problem 1 Solution ( n − 1 ) ! ways. Problem 2 Solution If we rotate a scarf through 180 degrees, we do not change the scarf, but we do get the reversed row of circles. Thus, two arrangements of n circles are equivalent if one is the reverse of the other. The equivalence classes have two members, so the number of ways to embroider the circles on the scarf is n ! / 2. Problem 3 Solution There are ( 5 2 ) = 10 ways to choose the two places out of five in which the golden apples are placed. For equivalence class counting, there are 5! ways to line up the apples. Two ways are equivalent if we interchange the golden apples or mix up the red apples in any way. Thus, there are 2 · 3! arrangements per equivalence class. Therefore, there are 5! /( 2 · 3! ) equivalence classes. This means that there are 5! /( 2 · 3! ) ways to line up the apples. Note that the second answer is simply the usual formula for the first answer. 1.4: Equivalence Relations and Counting S11

  13. Page 13
    Read page 13 as text

    Bogart-81046 book April 27, 2005 17:12 Problem 4 Solution Passing out the apples corresponds to choosing a k -element multiset from the n chil- dren. Choosing a k -element multiset from the children tells us how many apples to give each child. Thus, there are ( n + k − 1 k ) ways to pass out the apples. Problem 5 Solution Number the places around the table consecutively from 1 to 2 n . A seating gives a list of the 2 n people. Once we decide the gender of the person in Seat 1, we have n ! ways to seat that gender and n ! ways to seat the other gender. By the product principle, we have 2 · n ! · n ! lists of people corresponding to seating arrangements. But there are 2 n lists that correspond to the same circular arrangement. Therefore, the number of ways to seat the people is 2 n ! n ! / 2 n = n ! ( n − 1 ) !. Another way is to seat one gender in ( n − 1 ) ! ways and then seat the other gender in the n places between members of the first group in n ! ways. Then, by the product principle, we have ( n − 1 ) ! n ! seating arrangements. Problem 6 Solution Give one apple to each child. Then pass out k − n apples to the children in ( n + k − n − 1 k − n ) = ( k − 1 k − n ) ways. Problem 7 Solution Select k books in ( n k ) ways, and place one on the far left of each shelf in n ! ways. Then shelve the remaining k − n books in n k − n ways. This gives ( k n ) n ! n k − n = k ! ( k − 1 ) ! ( k − n ) ! ( n − 1 ) ! ways to shelve all the books. Problem 8 Solution a. ( k + n − 1 k ) , or the number of ways to choose the places where the red checkers go. This is also the way to put k identical books and n − 1 identical blocks of wood in a line, because it is the number of ways to choose where the books (or the blocks of wood) go. b. The number of red checkers between black checker number i − 1 and black checker number i (or before black checker number 1) is the multiplicity of i (or 1). The number of red checkers after the last black checker is the multiplicity of black checker n . S12 Chapter 1: Counting

  14. Page 14
    Read page 14 as text

    Bogart-81046 book April 27, 2005 17:12 c. Parts a and b count the same thing, so the number of k -element multisets chosen from an n -element set is ( n + k − 1 k ) . Problem 9 Solution If you think of the value of x i as the multiplicity of i in a multiset, then the number of solutions is the number of multisets, ( n + k − 1 k ) . Problem 10 Solution If you think of x i as the multiplicity of i in a multiset, then you are counting the number of k -element multisets chosen from { 1 , 2 , . . . , n } in which every element has multiplicity at least 1. This is the same as the number of k − n element multisets of { 1 , 2 , . . . , n } , which is ( k − 1 k − n ) . To see why this is the answer, think of giving k identical apples to n children. Give each child one apple and then distribute the remaining k − n apples however you want. Problem 11 Solution Imagine this circular arrangement as a linear arrangement. If both the n red checkers and the n + 1 black checkers were distinguishable, there would be ( n + n + 1 ) ! = ( 2 n + 1 ) ! possible linear arrangements. When we think of the red checkers (and the black ones) as indistinguishable, we have n ! ( n + 1 ) ! lists per equivalence class, because these lists would be equivalent if we mixed n red checkers among themselves and n + 1 black checkers among themselves. Each linear arrangement of n red and n + 1 black checkers corresponds to 2 n + 1 other arrangements, which become identical when we put them into a circle. (This would not be the case if we had n red and n black checkers; think about alternating red and black.) So, the number of arrangements is ( 2 n + 1 ) ! ( 2 n + 1 ) n ! ( n + 1 ) ! = ( 2 n ) ! n ! ( n + 1 ) ! = 1 n + 1 ( 2 n n ) . Problem 12 Solution a. For S ( n , n ) , each element must be in a part by itself. There is one such partition, so S ( n , n ) = 1. For S ( n , 1 ) , every element must be in the same part, so S ( n , 1 ) = 1. b. An element a may be in a part by itself or not. The number of partitions in which a is in a part by itself is S ( n − 1 , k − 1 ) , because then we have to choose remaining k − 1 parts from remaining n − 1 elements. Otherwise a is in a part with other elements. Because a can be in any of the k parts and the other n − 1 elements may be partitioned into k parts in S ( n − 1 , k ) ways, we have 1.4: Equivalence Relations and Counting S13

  15. Page 15
    Read page 15 as text

    Bogart-81046 book April 27, 2005 17:12 k S ( n − 1 , k ) partitions of this type. By the sum principle, we get S ( n , k ) = S ( n − 1 , k − 1 ) + k S ( n − 1 , k ) . c. n k 1 2 3 4 5 6 1 1 2 1 1 3 1 3 1 4 1 7 6 1 5 1 15 25 10 1 6 1 31 90 65 15 1 Problem 13 Solution There are six lists of four letters: you can make a list by choosing two of the four places for the red beads in ( 4 2 ) = 6 ways. The equivalence classes are { RRBB , RBBR , BBRR , BRRB } and { RBRB , BRBR } . Because the sizes of the equivalence classes are not the same, you cannot apply Theorem 1.5. Problem 14 Solution a. “Greater than” is transitive. “Is a brother of” is not transitive (Paul can be a brother to Bob and Bob to Paul, but Paul is not a brother to Paul). “Is a sibling of” is not transitive but is symmetric. “Is a sibling of or is” is transitive, symmetric, and reflexive. b. x is in the same equivalence class as x , so it is reflexive. If x is in the same equivalence class as y , then y is in the same equivalence class as x . Therefore, it is symmetric. If x is in the same equivalence class as y and y is in the same equivalence class as z , then x is in the same equivalence class as z . Therefore, it is transitive. c. If S x and S y have a common element, such as a , then we have that a is related to both x and y . We also have that y is related to a by symmetry. For any element b in S y , we have b is related to y . Then b is related to a by transitivity and related to x again by transitivity. Thus, we have b ∈ S x , which shows that S y ⊆ S x . Similarly, we have S x ⊆ S y . Therefore, we have S x = S y . Thus, if S x and S y have a common element, they are identical. If S x and S y have no common element, they are disjoint. Therefore, we can use the relationship to divide S into disjoint sets: the sets S x . Note that by reflexivity, any element x is in the set S x . Thus, a reflexive symmetric transitive relation is an equivalence relation. d. Part b says that an equivalence relation, as defined in the text, is reflexive, symmetric, and transitive. Part c says that a reflexive, symmetric, and transitive relation is an equivalence relation, as was defined in the text. S14 Chapter 1: Counting

  16. Page 16
    Read page 16 as text

    Bogart-81046 book April 27, 2005 17:12 Problem 15 Solution The original version computes the entire Pascal triangle up to the element in row n and column k each time it is called. Your new version should store that information globally so that it only has to do one addition each time it computes a new value in Pascal’s triangle. Problem 16 Solution a. This problem asks you to count functions from the candy to the people, so the answer is n k . b. This asks for one-to-one functions from the candy to the people, so the answer is n k . Note how the notation for counting one-to-one functions is similar to the notation for counting functions. c. A distribution is equivalent to a k -element multiset of the n -element set of people. Thus, there are ( n + k − 1 k ) distributions. d. This asks for k -element subsets of the n people, so the answer is ( n k ) . e. This is the number of k -element permutations of the n objects, so the answer is n k . f. Because you are counting functions, the answer is n k . g. By definition, ( n k ) . h. By the theorem for counting multisets, ( n + k − 1 k ) . i. This is asking for the number of lists of k distinct people chosen out of n . Such a list is a k -element permutation of the n elements, so the answer is n k . j. This is asking for the number of k -element multisets of an n -element set, and this number is ( n + k − 1 k ) . k. Because it matters who gets which type, this is the same as asking how many one-to-one functions there are from a k -element set to an n -element set. Thus, the answer is n k . 1.4: Equivalence Relations and Counting S15

129 more pages in the full document

Unlock it once and it stays in your library, ready to chat with or turn into flashcards.

Unlock the full document

More Mathematics study materials

See all

Study this document with CramX

Once it is in your library, every tool can work from it.