##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
(D(n) recursive formula)
Let D(n) be the number of derangements of n items. D(0) = 1, D(1) = 0, D(2) = 1.
Recursive formula: D(n) = (n-1) × (D(n-1) + D(n-2)).
Example: D(3) = 2 × (D(2) + D(1)) = 2 × (1 + 0) = 2. Matches our count from before.
D(4) = 3 × (D(3) + D(2)) = 3 × (2 + 1) = 9. You can verify this by listing all derangements of 4 items.
