《Mathematics for Computer》Problem Set 7 Solutions

6.042/18.] Mathematics for Computer Science March 29, 2005 Srini devadas and Eric Lehman Problem set 7 Solutions Due: Monday, April 4 at 9 PM Problem 1. Every function has some subset of these properties injective surjective lective Determine the properties of the functions below, and briefly explain your reasoning (a) The function f: R-R defined by f(r)=er Solution. This function is injective, since ef takes on each nonnegative real value for exactly one r. However, the function is not surjective, because e never takes on negative values. Therefore the function is not bijective either (b)The function f: R-R+t defined by f(a)=er Solution. The function et takes on every nonnegative value for exactly one so it is injective, surjective, and bijective (c) The function f: R- R defined by f(ar)=(+1)a(a-1 Solution. This function is surjective, since it is continuous, it tends to +oo for large itive z, and tends to -oo for large negative r. Thus, the function takes on each real value for at least one However, this function is not injective, since it takes on the value 0 at a =-l, =0, and a= 1. Therefore, the function is not bijective either (d) Let S be the set of all 20-bit sequences. Let T be the set of all 10-bit sequences. Let f: S-T map each 20-bit sequence to its first 10 bits. For exampl ∫(11101010101010010)=11101010 Solution. This function is surjective since the sequence b1b2... b10 is mapped to by b1b2 .b1000.0, for example. However, the function is not injective, because this sequence is also mapped to by b1b2.boll.1. Consequently, the function is not bijective either. Problem 2. There are 20 books arranged in a row on a shelf

6.042/18.062J Mathematics for Computer Science March 29, 2005 Srini Devadas and Eric Lehman Problem Set 7 Solutions Due: Monday, April 4 at 9 PM Problem 1. Every function has some subset of these properties: injective surjective bijective Determine the properties of the functions below, and briefly explain your reasoning. x (a) The function f : R R → defined by f(x) = e . Solution. This function is injective, since ex takes on each nonnegative real value for exactly one x. However, the function is not surjective, because ex never takes on negative values. Therefore, the function is not bijective either. x (b) The function f : R R+ → defined by f(x) = e . Solution. The function ex takes on every nonnegative value for exactly one x, so it is injective, surjective, and bijective. (c) The function f : R → R defined by f(x) = (x + 1)x(x − 1). Solution. This function is surjective, since it is continuous, it tends to +∞ for large positive x, and tends to −∞ for large negative x. Thus, the function takes on each real value for at least one x. However, this function is not injective, since it takes on the value 0 at x = −1, x = 0, and x = 1. Therefore, the function is not bijective either. (d) Let S be the set of all 20­bit sequences. Let T be the set of all 10­bit sequences. Let f : S T → map each 20­bit sequence to its first 10 bits. For example: f(11110110101101010010) = 1111011010 Solution. This function is surjective since the sequence b1b2 . . . b10 is mapped to by b1b2 . . . b1000 . . . 0, for example. However, the function is not injective, because this sequence is also mapped to by b1b2 . . . b1011 . . . 1. Consequently, the function is not bijective either. Problem 2. There are 20 books arranged in a row on a shelf

Problem set 7 (a) Describe a bijection between ways of choosing 6 of these books so that no two elected and 15-bit Solution. There is a bijection from 15-bit sequences with exactly six 1's to valid book selections: given such a sequence, map each zero to a non-chosen book, each of the chosen book. For example, here is a configuration of books and the correspondin.? first five 1s to a chosen book followed by a non-chosen book, and the last 1 to ng Inary sequence Selected books are darkened. Notice that the first fives ones are mapped to a chosen book and an non-chosen book in order to ensure that the binary sequence maps to a alid selection of books (b) How many ways are there to select 6 books so that no two adjacent books are selected? Solution. By the Bijection Rule, this is equal to the number of 15-bit sequences with exactly 6 ones, which is equal to 15 6!9! by the bookkeeper Rule Problem 3. Answer the following questions and provide brief justifications. Not every problem can be solved with a cute formula; you may have to fall back on case analysis, explicit enumeration or ad hoc methods. You may leave factorials and binomial coefficients in your answers (a) In how many different ways can the letters in the name of the popular 1980s band BANAN A be arranged? Solution. There are 5 As, 2 Ns, 1 B, 1 R, and 1 m. therefore the number of arrangements Is 5!2!1!1!! by the bookkeeper rule (b) How many different paths are there from point(0, 0, 0)to point( 12, 24, 36)if ev- ery step increments one coordinate and leaves the other two unchanged? Solution. There is a bijection between the set of all such paths and the set of strings containing 12X,s, 24Y's, and 36Z's. In particular, we obtain a path by working

2 Problem Set 7 (a) Describe a bijection between ways of choosing 6 of these books so that no two adjacent books are selected and 15­bit sequences with exactly 6 ones. Solution. There is a bijection from 15­bit sequences with exactly six 1’s to valid book selections: given such a sequence, map each zero to a non­chosen book, each of the first five 1’s to a chosen book followed by a non­chosen book, and the last 1 to a chosen book. For example, here is a configuration of books and the corresponding binary sequence: 1 ���� 0 ���� 0 ���� 0 1 � �� � � �� � � �� � � �� � ���� � �� � 0 ���� 0 1 ���� 0 ���� 0 ���� 0 1 1 ���� 0 ���� 1 Selected books are darkened. Notice that the first fives ones are mapped to a chosen book and an non­chosen book in order to ensure that the binary sequence maps to a valid selection of books. (b) How many ways are there to select 6 books so that no two adjacent books are selected? Solution. By the Bijection Rule, this is equal to the number of 15­bit sequences with exactly 6 ones, which is equal to � � 15! 15 = 6! 9! 6 by the Bookkeeper Rule. Problem 3. Answer the following questions and provide brief justifications. Not every problem can be solved with a cute formula; you may have to fall back on case analysis, explicit enumeration, or ad hoc methods. You may leave factorials and binomial coefficients in your answers. (a) In how many different ways can the letters in the name of the popular 1980’s band BANANARAMA be arranged? Solution. There are 5 A’s, 2 N’s, 1 B, 1 R, and 1 M. Therefore, the number of arrangements is 10! 5! 2! 1! 1! 1! by the Bookkeeper Rule. (b) How many different paths are there from point (0, 0, 0) to point (12, 24, 36) if ev￾ery step increments one coordinate and leaves the other two unchanged? Solution. There is a bijection between the set of all such paths and the set of strings containing 12 X’s, 24 Y’s, and 36 Z’s. In particular, we obtain a path by working

Problem Set 7 through a string from left to right. An X corresponds to a step that increments the first coordinate, a y increments the second coordinate and a Z increments the third The number of such strings is Therefore, this is also the number of paths 361 12!24!3 (c) In how many different ways can 2n students be paired up? Solution. Pair up students by the following procedure. Line up the students and pair the first and second, the third and fourth, the fifth and sixth, etc. The students can be lined up in(2n)! ways. However, this overcounts by a factor of 2n, because we would get the same pairing if the first and second students were swapped, the third and fourth were swapped, etc. Furthermore, we are still overcounting by a factor of n!, because we would get the same pairing even if pairs of students were permuted g. the first and second were swapped with the ninth and tenth. Therefore, number of pairings is: (d) How many different solutions over the natural numbers are there to the follow- ing equation? +x8=100 A solution is a specification of the value of each variable r. Two solutions are dif- ferent if different values are specified for some variable x Solution. There is a bijection between sequences containing 100 zeros and 7 ones Specifically, the 7 ones divide the zeros into 8 segments. Let a, be the number of zeros in the i-th segment. Therefore, the number of solutions is (e) In how many different ways can one choose n out of 2n objects, given that n of the 2n objects are identical and the other n are all unique? Solution. We can select n objects as follows. First, take a subset of the unique objects. Then take however many identical elements are needed to bring the total m. The first step can be done in 2n ways, and the second can be done in only 1 w Therefore there are 2n ways to choose n objects (f) How many undirected graphs are there with vertices U1, U2,..., Un if self-loops ar permitted? Solution. There are (2)+n potential edges, each of which may or may not appear in a given graph. Therefore, the number of graphs 2(2)+n

� � � � Problem Set 7 3 through a string from left to right. An X corresponds to a step that increments the first coordinate, a Y increments the second coordinate, and a Z increments the third. The number of such strings is: 72! 12! 24! 36! Therefore, this is also the number of paths. (c) In how many different ways can 2n students be paired up? Solution. Pair up students by the following procedure. Line up the students and pair the first and second, the third and fourth, the fifth and sixth, etc. The students can be lined up in (2n)! ways. However, this overcounts by a factor of 2n, because we would get the same pairing if the first and second students were swapped, the third and fourth were swapped, etc. Furthermore, we are still overcounting by a factor of n!, because we would get the same pairing even if pairs of students were permuted, e.g. the first and second were swapped with the ninth and tenth. Therefore, the number of pairings is: (2n)! 2n · n! (d) How many different solutions over the natural numbers are there to the follow￾ing equation? x1 + x2 + x3 + . . . + x8 = 100 A solution is a specification of the value of each variable xi. Two solutions are dif￾ferent if different values are specified for some variable xi. Solution. There is a bijection between sequences containing 100 zeros and 7 ones. Specifically, the 7 ones divide the zeros into 8 segments. Let xi be the number of zeros in the i­th segment. Therefore, the number of solutions is: 100 + 7 7 (e) In how many different ways can one choose n out of 2n objects, given that n of the 2n objects are identical and the other n are all unique? Solution. We can select n objects as follows. First, take a subset of the unique objects. Then take however many identical elements are needed to bring the total to n. The first step can be done in 2n ways, and the second can be done in only 1 way. Therefore, there are 2n ways to choose n objects. (f) How many undirected graphs are there with vertices v1, v2, . . . , vn if self­loops are permitted? n Solution. There are + n potential edges, each of which may or may not appear 2 in a given graph. Therefore, the number of graphs is: 2( n 2)+n

Problem set 7 (g In how many different ways can 10 indistinguishable balls be placed in four dis tinguishable boxes, such that every box gets 1, 2, 3, or 4 balls? Solution. First, we might as well put 1 ball in every box. Now the problem is to put the remaining 6 balls into 4 boxes so that no box gets more than 3 balls. Now we turn to case analysis. For example, we could put 3 balls in two boxes and o balls in the other two boxes. There are 2l2=6 ways to do this. All cases are listed below distribution of balls of ways 3,3,0,0 6 3.2.1.0 1!=24 2,2,2,0 2,2,1,1 22=6 Thus, there are 6+24+4+4+6= 44 ways in all (h) There are 15 sidewalk squares in a row. Suppose that a ball can be thrown so that it bounces on o, 1, 2, or 3 distinct sidewalk squares. Assume that the ball alw from left to right. How many different throws are possible? As an example, a two-bounce throw is illustrated below Solution 15 15 15 0 Gi) In how many different ways can the numbers shown on a red die, a green die, and a blue die total up to 15? Assume that these are ordinary 6-sided dice Solution. We fall back on explicit enumeration. Let R, G, and b be the values shown on the three dice R=1,B+G=14→0ways R=2,B+G=13→0wav R=3,B+G=12→1way R=4,B+G=11 R=5,B+G=10→3ways R=6,B+G=9 4 way Gj) The working days in the next year can be numbered 1, 2, 3, ., 300. I'd like to avoid as many as possible

- - - @ � @ � 4 Problem Set 7 (g) In how many different ways can 10 indistinguishable balls be placed in four dis￾tinguishable boxes, such that every box gets 1, 2, 3, or 4 balls? Solution. First, we might as well put 1 ball in every box. Now the problem is to put the remaining 6 balls into 4 boxes so that no box gets more than 3 balls. Now we turn to case analysis. For example, we could put 3 balls in two boxes and 0 balls in the other two boxes. There are 4! = 6 ways to do this. All cases are listed below: 2! 2! distribution of balls # of ways 4! 3, 3, 0, 0 2! 2! = 6 4! 3, 2, 1, 0 = 24 1! 1! 1! 1! 4! 3, 1, 1, 1 3! 1! = 4 4! 2, 2, 2, 0 3! 1! = 4 4! 2, 2, 1, 1 2! 2! = 6 Thus, there are 6 + 24 + 4 + 4 + 6 = 44 ways in all. (h) There are 15 sidewalk squares in a row. Suppose that a ball can be thrown so that it bounces on 0, 1, 2, or 3 distinct sidewalk squares. Assume that the ball always moves from left to right. How many different throws are possible? As an example, a two­bounce throw is illustrated below.  




@R�




R�@





















Solution. � � � � � � � � 15 15 15 15 + + + 0 1 2 3 (i) In how many different ways can the numbers shown on a red die, a green die, and a blue die total up to 15? Assume that these are ordinary 6­sided dice. Solution. We fall back on explicit enumeration. Let R, G, and B be the values shown on the three dice. R = 1, B + G = 14 → 0 ways R = 2, B + G = 13 → 0 ways R = 3, B + G = 12 → 1 way R = 4, B + G = 11 → 2 ways R = 5, B + G = 10 → 3 ways R = 6, B + G = 9 → 4 ways (j) The working days in the next year can be numbered 1, 2, 3, . . . , 300. I’d like to avoid as many as possible

Problem Set 7 On even-numbered days, I'll say I'm sick On days that are a multiple of 3 I'll say i was stuck in traffic On days that are a multiple of 5, ill refuse to come out from under the blankets In total, how many work days will I avoid in the coming year? Solution. Let D2 be the set of even-numbered days, D3 be the days that are a mul tiple of 3, and D; be days that are a multiple of 5. The set of days I can avoid is D2 U D3 U Ds. By the Inclusion-Exclusion Rule, the size of this set D2 U D3U D D2 D3+IDs I D2∩D3-|D2nDs-|D3nDs +|D2∩D3∩D5 300300300300300300 52.32.53·52.3·5 Problem 4. Use the pigeonhole principle to solve the following problems (a) Prove that among any n=+ l points within an n x n square there must exist two points whose distance is at most Solution. Partition the n x n into m- unit squares. Each of the n2+ 1 points lies in one of these n2 unit squares. (If a point lies on the boundary between squares, assign it to a square arbitrarily. Therefore, by the pigeonhole principle, there exist two points in the same unit square And the distance between those two points can be at most v2 (b) Jellybeans of 6 different flavors are stored in 5 jars. There are 11 jellybeans of each flavor. Prove that some jar contains at least three jellybeans of one flavor and also at least three jellybeans of some other flavor Solution. We use the pigeonhole principle twice. Since there are 11 beans of a given flavor and there are only 5 jars, some jar must get at least 111/5=3 beans of that flavor. Since there are 6 flavors and only 5 jars, some jar must get two pairs of same- flavored beans (c) Prove that among every set of 30 integers, there exist two whose difference or sum is a multiple of 51 Solution. Regard the 30 integers as pigeons. Regard the 26 sets 01, ( 1, 501, ( 2, 49) [25, 26) as pigeonholes. Map integer n to the set containing n rem 51. By the pigeonhole principle, some two pigeons(integers a and b)are mapped to the same pigeonhole. Thus, either a rem 51= b rem 51 and so the difference of a and b is a multiple of 51

Problem Set 7 5 • On even­numbered days, I’ll say I’m sick. • On days that are a multiple of 3, I’ll say I was stuck in traffic. • On days that are a multiple of 5, I’ll refuse to come out from under the blankets. In total, how many work days will I avoid in the coming year? Solution. Let D2 be the set of even­numbered days, D3 be the days that are a mul￾tiple of 3, and D5 be days that are a multiple of 5. The set of days I can avoid is D2 ∪ D3 ∪ D5. By the Inclusion­Exclusion Rule, the size of this set is: |D2 ∪ D3 ∪ D5| | | | | | = D2| + D3 + D5 − | | − | | − | | D2 ∩ D3 D2 ∩ D5 D3 ∩ D5 + |D2 ∩ D3 ∩ D5| 300 300 300 300 300 300 300 = 2 + 3 + 5 − 2 3 − 2 5 − 3 5 + · · · 2 3 5 · · = 220 Problem 4. Use the pigeonhole principle to solve the following problems. (a) Prove that among any n2 + 1 points within an n × n square there must exist two points whose distance is at most √2. Solution. Partition the n × n into n2 unit squares. Each of the n2 + 1 points lies in one of these n2 unit squares. (If a point lies on the boundary between squares, assign it to a square arbitrarily.) Therefore, by the pigeonhole principle, there exist two points in the same unit square. And the distance between those two points can be at most √2. (b) Jellybeans of 6 different flavors are stored in 5 jars. There are 11 jellybeans of each flavor. Prove that some jar contains at least three jellybeans of one flavor and also at least three jellybeans of some other flavor. Solution. We use the pigeonhole principle twice. Since there are 11 beans of a given flavor and there are only 5 jars, some jar must get at least �11/5�= 3 beans of that flavor. Since there are 6 flavors and only 5 jars, some jar must get two pairs of same­ flavored beans. (c) Prove that among every set of 30 integers, there exist two whose difference or sum is a multiple of 51. Solution. Regard the 30 integers as pigeons. Regard the 26 sets {0}, {1, 50}, {2, 49}, . . ., {25, 26} as pigeonholes. Map integer n to the set containing n rem 51. By the pigeonhole principle, some two pigeons (integers a and b) are mapped to the same pigeonhole. Thus, either: • a rem 51 = b rem 51 and so the difference of a and b is a multiple of 51

Problem set 7 a rem 51+ b rem 51 is either 0 or 51 and so the sum of a and b is a multiple of Problem 5. a balanced parentheses string is a sequence of left and right parentheses such that the total number of left and right parentheses is equal, and the number of left parentheses is greater than or equal to the number of right paren theses in For Balanced √ ot balanced (0)((0 more left than right o(o)o)o( fewer left than right in prefix O) Let Cn be the number of balanced parentheses strings with 2n parentheses. The values Co, C1, C2,...are the Catalan numbers, which come up in dozens of different counting problems. Here are the first few Catalan numbers 10 421324291430 (a) Verify the first four entries by listing all balanced parentheses strings with at most 6 parentheses (Dont forget the empty string! Solution. Here are all the balanced parentheses strings with at most 6 parentheses empty (0)0 (0) (()) 000 Therefore Co=1, C1= 1, C2= 2, and C3= 5 as claimed in the table (b)A path from(0, 0)to(n, n) consisting of unit steps upward or rightward is safe if it does not cross the diagonal boundary of the Flaming Chasm of Hideous Death

6 Problem Set 7 • a rem 51 + b rem 51 is either 0 or 51 and so the sum of a and b is a multiple of 51. Problem 5. A balanced parentheses string is a sequence of left and right parentheses such that • the total number of left and right parentheses is equal, and • the number of left parentheses is greater than or equal to the number of right paren￾theses in every prefix. For example: Balanced Not Balanced (()) ((() more left than right ()(()) ())()( fewer left than right in prefix ()) Let Cn be the number of balanced parentheses strings with 2n parentheses. The values C0, C1, C2, . . . are the Catalan numbers, which come up in dozens of different counting problems. Here are the first few Catalan numbers: n 0 1 2 3 4 5 6 7 8 9 10 11 12 Cn 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 (a) Verify the first four entries by listing all balanced parentheses strings with at most 6 parentheses. (Don’t forget the empty string!) Solution. Here are all the balanced parentheses strings with at most 6 parentheses: empty () ()() (()) ()(()) (())() (()()) ((())) ()()() Therefore, C0 = 1, C1 = 1, C2 = 2, and C3 = 5 as claimed in the table. (b) A path from (0, 0) to (n, n) consisting of unit steps upward or rightward is safe if it does not cross the diagonal boundary of the Flaming Chasm of Hideous Death

Problem Set 7 flaming g flaming 8 Chasm of Chasm of Hideous Hideous Death Death A Safe Path An unsafe path Show that there are exactly Cn safe paths by describing a bijection with balanced parentheses strings (c) Many computational geometry algorithms begin by partitioning polygons into triangles with the same vertices. For example, here are all the possible triangulations of a pentagon Show that there are Cn different ways to triangulate a convex (n+2) -gon by describ ing a bijection from triangulations to balanced parentheses strings. (This problem is challenging, ask your TA for help if you're stuck Solution. Note that every nonempty balanced parentheses string has the form(a)B since the first symbol must be( and there must be a matching ). Thus, every bal- anced parentheses string can be decomposed into two smaller strings a and B. We'll exploit this fact to recursively map a balanced parentheses string to a triangulation Suppose we have a not-yet-triangulated(n+ 2)-gon and a balanced parentheses string(a)B. We must map the parentheses string to a triangulation. Select two consecutive vertices a and y and denote the remaining vertices vor Un-1. It must be that a contains j pairs of parentheses and B contains the remaining (n-1)-j pairs for some j between 0 and n-1. Draw a triangle with the vertices ,y, and v

Problem Set 7 7 � � � �� �� � � � � � � Flami Chasm of ng � � Hideous �� Death �� � �� �� � � � � �� � � Fl C ami has ng m of � � Hideous �� Death �� A Safe Path An Unsafe Path Show that there are exactly Cn safe paths by describing a bijection with balanced parentheses strings. (c) Many computational geometry algorithms begin by partitioning polygons into triangles with the same vertices. For example, here are all the possible triangulations of a pentagon: B B Q     QQQ  QQQQ  B B QQQQ  QQQQ  QQ  B   B   QQ c B C Cc C B C # C # C c B C c C B C # C # C cc B C c C B C ## C ## C c B C cc C B C # C # C cB C c C B C# C# Show that there are Cn different ways to triangulate a convex (n+2)­gon by describ￾ing a bijection from triangulations to balanced parentheses strings. (This problem is challenging; ask your TA for help if you’re stuck!) Solution. Note that every nonempty balanced parentheses string has the form (α)β since the first symbol must be ( and there must be a matching ). Thus, every bal￾anced parentheses string can be decomposed into two smaller strings α and β. We’ll exploit this fact to recursively map a balanced parentheses string to a triangulation. Suppose we have a not­yet­triangulated (n + 2)­gon and a balanced parentheses string (α)β. We must map the parentheses string to a triangulation. Select two consecutive vertices x and y and denote the remaining vertices v0, . . . , vn−1. It must be that α contains j pairs of parentheses and β contains the remaining (n − 1) − j pairs for some j between 0 and n − 1. Draw a triangle with the vertices x, y, and vj .

Problem set 7 This triangle partitions the polygon into a(+2)-gon and a(n-j+1)-gon. Trian gulate these polygons recursively using the balanced parentheses strings a and B (Let a and u; play the role of r and y in triangulation one side, and let uj and y play the role of r and y on the other. Problem 6. A derangement is a permutation(a1, 32,..., En)of the set (1, 2,..., n) such that 3 appears in the third position. The objective of this problem is to count derangement o it i for all i. For example, (2, 3, 4, 5, 1)is a derangement, but(2, 1, 3, 5, 4)is not because (a)Let's first work on counting permutations of (1, 2, ...,n) that are not derange- ments. Let Si be the set of all permutations(a1, 12,..., n)of the set (1, 2, ..., n] such that ai = i. Use the inclusion-exclusion formula to express the number of non-derangements in terms of sizes of intersections of the sets S1,..., S, Solution ∑ls!|-∑|s:∩S+∑ls:∩S;ns-…±lS∩S2n…∩Sn , k In each summation, the subscripts are distinct elements of (1, .., n) (b) What is S:? Solution. There is a bijection between permutations of (1, 2, .., n) with i in the i-th position and unrestricted permutations of (1, 2,.,n-i. Therefore, Si =(n-1)! (c) What is S;,l where i j? Solution. The set Sin,, consists of all permutations with i in the i-th position and j in the j-th position. Thus, there is a bijection with permutations of (1, 2, ...,n) Li, jJ, and so Sins,=(n-2) (d) What is|S1∩S2∩..∩ Sil where il,t2,…, ik are all distinct? Solution. By the same argument, (n-k)!

� � � | | � 8 Problem Set 7 x y v0 v1 v2 v3 v4 v5 v6 v7 This triangle partitions the polygon into a (j + 2)­gon and a (n − j + 1)­gon. Trian￾gulate these polygons recursively using the balanced parentheses strings α and β. (Let x and vj play the role of x and y in triangulation one side, and let vj and y play the role of x and y on the other.) Problem 6. A derangement is a permutation (x1, x2, . . . , xn) of the set {1, 2, . . . , n} such that xi =� i for all i. For example, (2, 3, 4, 5, 1) is a derangement, but (2, 1, 3, 5, 4) is not because 3 appears in the third position. The objective of this problem is to count derangements. (a) Let’s first work on counting permutations of {1, 2, . . . , n} that are not derange￾ments. Let Si be the set of all permutations (x1, x2, . . . , xn) of the set {1, 2, . . . , n} such that xi = i. Use the inclusion­exclusion formula to express the number of non­derangements in terms of sizes of intersections of the sets S1, . . . , Sn. Solution. |Si| − |Si ∩ Sj + |Si ∩ Sj ∩ Sk| | − . . . ± S1 ∩ S2 ∩ . . . ∩ Sn| i i,j | i,j,k In each summation, the subscripts are distinct elements of {1, . . . , n}. (b) What is |Si|? Solution. There is a bijection between permutations of {1, 2, . . . , n} with i in the i­th position and unrestricted permutations of {1, 2, . . . , n} −i. Therefore, | | Si = (n−1)!. (c) What is Si ∩ Sj where i = j? Solution. The set Si ∩ Sj consists of all permutations with i in the i­th position and j in the j­th position. Thus, there is a bijection with permutations of {1, 2, . . . , n} − {i, j}, and so | | Si ∩ Sj = (n − 2)!. (d) What is |Si1 ∩ Si2 ∩ . . . ∩ Sik | where i1, i2, . . . , ik are all distinct? Solution. By the same argument, (n − k)!

Problem Set 7 e) How many terms in the expression in part(a) have the form Si∩S2∩∴∩S1k| Solution. There is one such term for each k-element subset of the n-element set n). Therefore, there are(n)such terms (f)Combine your answers to the preceding parts to get a(messy) expression for the number of non-derangements Solution ∑lS!|-∑ls:∩S|+∑|s:∩s;nS|-…±lS1∩S2n.…∩Sl (n-2)!+ 3 m! 1!-2!+3 nI (g)Now give an expression for the number of derangements Solution (h) As n goes to infinity, this expression approaches a constant fraction of all permu- tations. what is that constant? Recall that 1+x+-+-,+ Solution. 1/

� � � � � � � � � � � � � Problem Set 7 9 (e) How many terms in the expression in part (a) have the form Si1 ∩ Si2 ∩ . . . ∩ Sik | |? Solution. There is one such term for each k­element subset of the n­element set n {1, 2, . . . , n}. Therefore, there are such terms. k (f) Combine your answers to the preceding parts to get a (messy) expression for the number of non­derangements. Solution. |Si| − |Si ∩ Sj + |Si ∩ Sj ∩ Sk| | − . . . ± S1 ∩ S2 ∩ . . . ∩ Sn| i i,j | i,j,k n n n n = 1 · (n − 1)! − � 2 · (n − 2)! + � 3 · (n − 3)! − . . . ± n · 0! 1 1 1 1 = n! 1! − 2! + 3! − . . . ± n! (g) Now give an expression for the number of derangements. Solution. � � 1 1 1 1 n! 1 − + 3! − . . . ± 1! − 2! n! (h) As n goes to infinity, this expression approaches a constant fraction of all permu￾tations. What is that constant? Recall that: 2 3 x x x e = 1 + x + + + . . . 2! 3! Solution. 1/e