D_n = (n-1)(D_{n-1} + D_{n-2}).
Un desarreglo de un conjunto de $n$ elementos es una permutación $\sigma$ tal que ningún elemento aparece en su posición original; es decir, $\sigma(i) \neq i$ para todo $i \in {1, 2, \dots, n}$. El número de estos desarreglos lo escribimos como $D_n$ (o a veces $!n$, el subfactorial). Aunque la fórmula explícita para $D_n$ que obtienes con el Principio de Inclusión-Exclusión es poderosa, puede ser estorbosa para hacer cálculos o manipulaciones algebraicas. La Recurrencia de Desarreglos te da un método recursivo para calcular $D_n$ basándote en los valores de $D_{n-1}$ y $D_{n-2}$.
Esta recurrencia es muy importante en las olimpiadas de matemáticas (como el AIME o la USAMO) porque te permite calcular rápido los valores para $n$ pequeñas sin tener que sumar factoriales. Además, la lógica combinatoria que usas para obtener la recurrencia —dividir el problema según el comportamiento de un elemento específico— es una técnica fundamental en la combinatoria enumerativa. Te enseña la estrategia de distinguir entre "intercambiar" elementos y formar ciclos más largos.
Intuitivamente, la recurrencia surge al considerar a dónde va el primer elemento. Si el elemento 1 se mueve a la posición $k$, tienes que preguntarte