Derangements y el número de Euler

El problema de los sobres y su historia

Un secretario escribe $n$ cartas y $n$ sobres, coloca cada carta en un sobre aleatoriamente, y envía todo. ¿Cuál es la probabilidad de que ninguna carta llegue a su destinatario correcto?

Este problema fue planteado y resuelto por Nicolaus Bernoulli en 1713 y popularizado por Pierre de Montmort en su "Essay d'Analyse sur les Jeux de Hazard" (1713). La solución conecta el álgebra discreta (el PIE) con el análisis (el número $e$), un enlace notable para la época.

Una permutación $\sigma$ de $\{1, 2, \ldots, n\}$ es un derangement (o desarreglo) si $\sigma(i) \neq i$ para todo $i$, es decir, ningún elemento está en su posición original. El número de derangements de $n$ elementos se denota $D_n$ o $!n$ (subfactorial de $n$).

Los primeros valores son: $D_0 = 1$ (la permutación vacía es un derangement por vacuidad), $D_1 = 0$, $D_2 = 1$ (solo $\{2,1\}$), $D_3 = 2$ ($\{2,3,1\}$ y $\{3,1,2\}$), $D_4 = 9$, $D_5 = 44$, $D_6 = 265$.

Los derangements tienen aplicaciones directas en olimpiadas: problemas sobre "repartir $n$ objetos entre $n$ personas de modo que nadie reciba el suyo", ciclos completos en permutaciones, y coloraciones con restricciones de adjacencia.

Fórmula explícita por PIE

Calculamos $D_n$ usando el PIE. Sea $U = S_n$ el conjunto de todas las $n!$ permutaciones. Para cada $i \in \{1, \ldots, n\}$, sea $A_i$ el conjunto de permutaciones con $\sigma(i) = i$ (punto fijo en $i$). Queremos $|\overline{A_1} \cap \cdots \cap \overline{A_n}|$.

La intersección $A_{i_1} \cap \cdots \cap A_{i_k}$ consiste en las permutaciones que fijan $i_1, \ldots, i_k$; hay $(n-k)!$ de ellas (los $n-k$ elementos restantes se permutan libremente). Por simetría, $|A_S| = (n - |S|)!$ para todo $S$ de tamaño $|S|$.

Aplicando el PIE: $D_n = \sum_{k=0}^{n} (-1)^k \binom{n}{k}(n-k)! = \sum_{k=0}^{n} (-1)^k \frac{n!}{k!}$.

Esta es la fórmula exacta del subfactorial:

Verificación para $n = 4$: $D_4 = 24 - 24 + 12 - 4 + 1 = 9$. ✓

La fórmula también se escribe como $D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$. La suma $\sum_{k=0}^{n} \frac{(-1)^k}{k!}$ converge a $e^{-1} = 1/e$ cuando $n \to \infty$ (es el inicio de la serie de Taylor de $e^{-1}$). Por tanto $D_n / n! \to 1/e \approx 0.3679$: cerca del $36.8\%$ de las permutaciones son derangements para $n$ grande.

Recurrencia y cálculo eficiente

Para calcular $D_n$ sin sumar todos los términos, usamos la recurrencia de los derangements:

Demostración: Fijemos una permutación $\sigma$ con $\sigma(1) = j \neq 1$ (hay $n-1$ opciones para $j$). Dos casos:

Caso 1: $\sigma(j) = 1$ (es decir, $1$ y $j$ se intercambian). Entonces $\sigma$ restringida a $\{2, \ldots, n\} \setminus \{j\}$ debe ser un derangement de $n-2$ elementos: hay $D_{n-2}$ opciones.

Caso 2: $\sigma(j) \neq 1$. Definamos $\tau$ igual a $\sigma$ excepto que $\tau(j) = 1$ (en lugar de $\sigma(j) \neq 1$). Entonces $\tau$ es un derangement de $\{2, \ldots, n\}$ en el sentido de que $\tau(i) \neq i$ para $i \geq 2$, y también $\tau(j) = 1 \neq j$. En realidad, $\tau$ es un derangement de $n-1$ elementos (identificando la restricción a $\{2, \ldots, n\}$ con un derangement de $\{1, \ldots, n-1\}$ vía la biyección $i \mapsto i-1$). Hay $D_{n-1}$ opciones.

Sumando sobre los $n-1$ posibles valores de $j$: $D_n = (n-1)(D_{n-2} + D_{n-1})$.

Corolario — recurrencia lineal: De $D_n = (n-1)D_{n-1} + (n-1)D_{n-2}$ y $D_{n-1} = (n-1)D_{n-1} - D_{n-1}$... Más directamente, restando: $D_n - n D_{n-1} = -(D_{n-1} - (n-1)D_{n-2}) = -(-1)^{n-1} \cdot 1 = (-1)^n$. Esto da la recurrencia lineal $D_n = n D_{n-1} + (-1)^n$, que es más fácil de usar para calcular términos sucesivos.

Tabla: $D_0=1, D_1=0, D_2=1, D_3=2, D_4=9, D_5=44, D_6=265, D_7=1854, D_8=14833$.

Aproximación entera: Para $n \geq 1$, $D_n$ es el entero más cercano a $n!/e$, ya que $|D_n - n!/e| < 1/(n+1) < 1$. En la práctica: $D_n = \text{round}(n!/e)$.

El número de Euler (primera especie)

Los números de Euler de primera especie $\langle\begin{smallmatrix}n\\k\end{smallmatrix}\rangle$ (distintos de los números de Euler del análisis) cuentan las permutaciones de $\{1,\ldots,n\}$ con exactamente $k$ ascensos, donde un ascenso en la posición $i$ significa $\sigma(i) < \sigma(i+1)$.

Los primeros valores: $\langle\begin{smallmatrix}1\\0\end{smallmatrix}\rangle = 1$ (la permutación $1$ no tiene ascensos). $\langle\begin{smallmatrix}2\\0\end{smallmatrix}\rangle = 1$ ($21$), $\langle\begin{smallmatrix}2\\1\end{smallmatrix}\rangle = 1$ ($12$). $\langle\begin{smallmatrix}3\\0\end{smallmatrix}\rangle = 1$ ($321$), $\langle\begin{smallmatrix}3\\1\end{smallmatrix}\rangle = 4$ ($132, 213, 231, 312$), $\langle\begin{smallmatrix}3\\2\end{smallmatrix}\rangle = 1$ ($123$).

Recurrencia: $\langle\begin{smallmatrix}n\\k\end{smallmatrix}\rangle = (k+1)\langle\begin{smallmatrix}n-1\\k\end{smallmatrix}\rangle + (n-k)\langle\begin{smallmatrix}n-1\\k-1\end{smallmatrix}\rangle$.

Conexión con potencias: La identidad clave de los números de Euler es $m^n = \sum_{k=0}^{n-1} \langle\begin{smallmatrix}n\\k\end{smallmatrix}\rangle \binom{m+k}{n}$, que expresa potencias en términos de coeficientes binomiales. Esto generaliza la fórmula de sumas de potencias de enteros consecutivos y conecta con las funciones generatrices de Euler.

Relación con derangements: El número de derangements de $n$ elementos puede interpretarse en términos de la distribución de ciclos en permutaciones aleatorias. En una permutación aleatoria de $n$ elementos, el número esperado de puntos fijos es 1 (cada elemento tiene probabilidad $1/n$ de ser un punto fijo, y hay $n$ elementos). La distribución del número de puntos fijos converge a la distribución de Poisson con parámetro 1 cuando $n \to \infty$, lo que implica $D_n/n! \to e^{-1}$.

En olimpiadas: Los números de Euler aparecen en problemas sobre distribuciones de bolas en urnas, estadísticas de orden, y conteo de permutaciones con restricciones de inversiones o ascensos. El conocimiento de la recurrencia y los primeros valores es suficiente para los niveles Iberoamericano y Cono Sur.

Derangements parciales y generalizaciones

Un derangement parcial o **$k$-derangement** de $\{1,\ldots,n\}$ es una permutación con exactamente $n-k$ puntos fijos (o equivalentemente, exactamente $k$ elementos fuera de su posición). El número de tales permutaciones es $\binom{n}{k} D_k$: elegimos cuáles $k$ posiciones están "desplazadas" ($\binom{n}{k}$ opciones) y derangements de esas $k$ posiciones ($D_k$ opciones).

Verificación: $\sum_{k=0}^{n} \binom{n}{k} D_k = n!$ (todas las permutaciones). Esto es la "convolución" del binomio con el subfactorial, y puede verificarse directamente o como caso especial del PIE aplicado al universo $S_n$.

Problemas de "cartas revueltas": Muchos problemas iberoamericanos son variantes del problema de cartas: $n$ personas en círculo, cada una pasa su regalo al vecino, ¿cuántos arreglos hay tal que nadie recibe su propio regalo? Esto es un derangement con restricciones adicionales (la permutación debe evitar no solo los puntos fijos sino también las transposiciones adyacentes), lo que requiere un PIE más cuidadoso.

Menage problem (problema del banquete): $n$ parejas sentadas en una mesa circular con $2n$ sillas, hombres y mujeres alternados, de modo que ningún miembro de una pareja quede adyacente. El número de arreglos es $2 \cdot n! \cdot M_n$ donde $M_n = \sum_{k=0}^{n} (-1)^k \frac{2n}{2n-k} \binom{2n-k}{k} (n-k)!$ son los números ménage. Este es un ejemplo del PIE aplicado a una permutación con restricciones de gráfico (evitar ciertas posiciones relativas), tema central de la próxima lección.

Identidad fundamental: $n! = \sum_{k=0}^{n} \binom{n}{k} D_k = \sum_{k=0}^{n} \binom{n}{k} D_{n-k}$. Esta identidad de convolución es el corazón de muchas aplicaciones de derangements en conteo avanzado.

Problema trabajado: derangements en el aula

Problema: En un examen, $n$ estudiantes entregan sus respuestas. El profesor las mezcla y devuelve una respuesta a cada estudiante al azar. ¿Cuál es la probabilidad de que al menos un estudiante reciba su propia respuesta?

Solución: La probabilidad de que ninguno reciba la suya es $P(\text{derangement}) = D_n / n! = \sum_{k=0}^{n} (-1)^k / k!$.

Por tanto, la probabilidad de que al menos uno reciba la suya es $1 - D_n/n! = 1 - \sum_{k=0}^{n} (-1)^k/k! = \sum_{k=1}^{n} (-1)^{k-1}/k! = 1 - 1/2! + 1/3! - \cdots$.

Para $n \geq 3$, esta probabilidad es aproximadamente $1 - 1/e \approx 0.6321$, independientemente de $n$. Este resultado sorprendente (la probabilidad no depende del número de estudiantes para $n$ grande) es uno de los más famosos de la probabilidad combinatoria.

Verificación: $n=2$: $P(\text{al menos uno}) = 1/2$. $n=3$: $1 - D_3/6 = 1 - 2/6 = 2/3$. $n=4$: $1 - 9/24 = 1 - 3/8 = 5/8$. Estos convergen a $1 - 1/e \approx 0.632$. $\square$