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