Problem
COM-B2-M02-P015 Recurrence for Derangements
#15
★★★★☆ Level 4 of 5
Prove the recurrence \(D_n=(n-1)(D_{n-1}+D_{n-2})\) for \(n\ge2\).
Look where element \(1\) goes, and what happens to the element that lands in position \(1\).
In a derangement, element \(1\) goes to position \(j\ne1\), giving \(n-1\) choices. Consider element \(j\). If \(j\) goes to position \(1\), the remaining \(n-2\) elements form a derangement: \(D_{n-2}\) ways. If \(j\) does not go to position \(1\), after merging the roles of positions \(1\) and \(j\), the problem reduces to a derangement of \(n-1\) elements: \(D_{n-1}\) ways. Hence \(D_n=(n-1)(D_{n-1}+D_{n-2})\).
This is not inclusion-exclusion, but it is important for derangements.