Let theta=(a_(1),a_(2),a_(3),...,a_(n)) be a given arrangement of n distinct objects a_(1),a_(2),a_(3),…,a_(n). A derangement of theta is an a

17 views

closed
Let theta=(a_(1),a_(2),a_(3),...,a_(n)) be a given arrangement of n distinct objects a_(1),a_(2),a_(3),…,a_(n). A derangement of theta is an arrangment of these n objects in which none of the objects occupies its original position. Let D_(n) be the number of derangements of the permutations theta.
The relation between D_(n) and D_(n-1) is given by
A. D_(n)-nD_(n-1)=(-1)^(n)
B. D_(n)-(n-1)D_(n-1)=(-1)^(n-1)
C. D_(n)-nD_(n-1)=(-1)^(n-1)
D. D_(n)-D_(n-1)=(-1)^(n-1)

by (90.7k points)
selected

(a) D_(n)-nD_(n-1)=(-1)(D_(n-1)-(n-1)D_(n-2))
By implied induction on n, we obtain
D_(n)-nD_(n-1)=(-1)^(n-2)(D_(2)-2D_(1)), Where D_(1)=0 and D_(2)=1
=(-1)^(n)