Starting with the base cases:
D(0) = 1
D(1) = 0
A derangement is a permutation where no element appears in its original position.
For n=0 (empty set), there is 1 way to arrange it.
For n=1 (one element), there is no way to move it from its original position.
Let's calculate D(2):
D(2) = (2-1) × [D(1) + D(0)]
D(2) = 1 × [0 + 1]
D(2) = 1 × 1 = 1
For n=2 (two elements, say [1,2]), there is exactly 1 derangement: [2,1].
Each element is placed in a position different from its original position.
Now, let's calculate D(3):
D(3) = (3-1) × [D(2) + D(1)]
D(3) = 2 × [1 + 0]
D(3) = 2 × 1 = 2
For n=3 (three elements, say [1,2,3]), there are 2 derangements:
[2,3,1] and [3,1,2]
In each derangement, no element is in its original position.
Finally, let's calculate D(4):
D(4) = (4-1) × [D(3) + D(2)]
D(4) = 3 × [2 + 1]
D(4) = 3 × 3 = 9
For n=4 (four elements), there are 9 different derangements where no element appears in its original position.
The number of derangements grows rapidly as n increases.
Summary of Derangement Values:
D(0)=1
D(1)=0
D(2)=1
D(3)=2
D(4)=9
The derangement numbers follow the recurrence relation:
D(n) = (n-1) × [D(n-1) + D(n-2)]
This pattern continues for higher values of n, with the number of derangements growing rapidly.