For n Z+, dn denotes the number of derangements of {1, 2, 3, . . ., n],

For n ˆˆ Z+, dn denotes the number of derangements of {1, 2, 3, . . ., n], as discussed in Section 8.3.
(a) If n > 2, show that dn satisfies the recurrence relation
dn = (n - l)(dn-1 + dn-2), d2 = l, d1 = 0.
(b) How can we define d0 so that the result in part (a) is valid for n ‰¥ 2?
(c) Rewrite the result in part (a) as dn - ndn-1 = - [dn-1= (n-l )dn-2] .
How can dn - ndn-1 be expressed in terms of dn-2, dn-3?
(d) Show that dn - ndn-1 = (-1)n.
(e) Let f(x) = ˆ‘ˆžn=0(dnxn)/n!. After multiplying both sides of the equation in part (d) by xn/n! and summing for n ‰¥ 2, verify that f(x) = (e-x) / (1 - x ). Hence

Transcribed Image Text:

2 3!