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)!