Permutaciones sin puntos fijos: Dₙ = n!(1 - 1/1! + 1/2! - ... + (-1)ⁿ/n!).
Un desarreglo es una permutación de un conjunto donde ningún elemento aparece en su posición original. Por ejemplo, los desarreglos de ${1, 2, 3}$ son $(2, 3, 1)$ y $(3, 1, 2)$ — exactamente 2 de las 6 permutaciones totales.
Los desarreglos se cuentan usando el principio de inclusión-exclusión. El número de desarreglos de $n$ elementos, que escribimos como $D_n$ o $!n$ (subfactorial), tiene una forma cerrada muy bonita y se acerca a $n!/e$ cuando $n$ es grande.
Algunas aplicaciones clásicas son:
Conteo de Desarreglos: $$D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} = n! \left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + \frac{(-1)^n}{n!}\right)$$
Forma Cerrada: $$D_n = \left\lfloor \frac{n!}{e} + \frac{1}{2} \right\rfloor$$
(el entero más cercano a $n!/e$)
Relaciones de Recurrencia: $$D_n = (n-1)(D_{n-1} + D_{n-2})$$ $$D_n = nD_{n-1} + (-1)^n$$
Valores Iniciales: $$D_0 = 1, \quad D_1 = 0, \quad D_2 = 1, \quad D_3 = 2, \quad D_4 = 9, \quad D_5 = 44$$
Probabilidad: $$P(\text{desarreglo}) = \frac{D_n}{n!} = \sum_{k=0}^{n} \frac{(-1)^k}{k!} \approx \frac{1}{e} \approx 0.368$$
Asintótica: $$D_n \sim \frac{n!}{e}$$
Demostración usando Inclusión-Exclusión:
Sea $A_i$ el conjunto de permutaciones donde el elemento $i$ está en la posición $i$ (un "punto fijo").
Lo que quieres es contar las permutaciones que no tienen puntos fijos: $|\overline{A_1} \cap \overline{A_2} \cap \cdots \cap \overline{A_n}|$.
Por inclusión-exclusión: $$D_n = n! - |A_1 \cup A_2 \cup \cdots \cup A_n|$$
$$= n! - \sum_i |A_i| + \sum_{i<j} |A_i \cap A_j| - \cdots + (-1)^n |A_1 \cap \cdots \cap A_n|$$
Ahora, nota que $|A_i| = (n-1)!$ (fijas la posición $i$ y permutas el resto).
$|A_i \cap A_j| = (n-2)!$ (fijas las posiciones $i$ y $j$).
En general, $|A_{i_1} \cap \cdots \cap A_{i_k}| = (n-k)!$.
Hay $\binom{n}{k}$ formas de elegir $k$ índices, así que:
$$D_n = \sum_{k=0}^{n} (-1)^k \binom{n}{k} (n-k)! = \sum_{k=0}^{n} (-1)^k \frac{n!}{k!}$$
$$= n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$$ $\square$
Demostración de la recurrencia $D_n = (n-1)(D_{n-1} + D_{n-2})$:
Considera el elemento 1. En un desarreglo, el 1 tiene que ir a alguna posición $k \neq 1$.
Tienes $n - 1$ opciones para elegir esa $k$.
Caso 1: El elemento $k$ va a la posición 1.
Entonces los elementos 1 y $k$ intercambian lugares. Los $n - 2$ elementos restantes deben formar un desarreglo entre ellos.
El número de estos desarreglos es $D_{n-2}$.
Caso 2: El elemento $k$ NO va a la posición 1.
Considera un problema modificado: los elementos ${2, 3, \ldots, n}$ deben ponerse en las posiciones ${1, 2, \ldots, k-1, k+1, \ldots, n}$ de tal forma que:
Esto es equivalente a hacer un desarreglo de $n - 1$ elementos (puedes pensar que la posición 1 es la "posición prohibida" para el elemento $k$).
El número de estos desarreglos es $D_{n-1}$.
En total: $D_n = (n-1)(D_{n-2} + D_{n-1})$ $\square$