Números de Stirling y conteo refinado

Motivación: contar particiones de conjuntos

Los coeficientes binomiales $\binom{n}{k}$ cuentan subconjuntos de tamaño $k$. Pero ¿qué pasa cuando queremos contar particiones de un conjunto en subconjuntos? Es decir, dividir $\{1, 2, \ldots, n\}$ en $k$ grupos no vacíos no ordenados.

Ejemplo: las particiones de $\{1, 2, 3\}$ en 2 grupos son: $\{\{1\}, \{2,3\}\}$, $\{\{2\}, \{1,3\}\}$, $\{\{3\}, \{1,2\}\}$. Hay 3 de ellas. El número que cuenta estas particiones es el número de Stirling de segunda clase $S(3,2) = 3$.

Un problema relacionado: ¿de cuántas maneras podemos escribir la permutación $\sigma \in S_n$ como producto de ciclos disjuntos con exactamente $k$ ciclos? Esto lo cuenta el número de Stirling de primera clase $c(n,k)$ (también denotado $\left[\begin{smallmatrix}n\\k\end{smallmatrix}\right]$).

Ambos tipos de números de Stirling aparecen naturalmente en problemas de olimpiadas avanzadas, especialmente cuando se combinan con el principio de inclusión-exclusión o con funciones generatrices.

Los números de Stirling son los "primos" de la combinatoria refinada: así como los números primos generan los enteros por multiplicación, los números de Stirling generan las potencias por suma, a través de las fórmulas de conversión entre bases de polinomios.

Números de Stirling de segunda clase $S(n,k)$

El número de Stirling de segunda clase $S(n,k)$ (también escrito $\left\{\begin{smallmatrix}n\\k\end{smallmatrix}\right\}$) es el número de particiones del conjunto $\{1, 2, \ldots, n\}$ en exactamente $k$ partes no vacías no ordenadas.

Recurrencia: $S(n,k) = k \cdot S(n-1,k) + S(n-1,k-1)$ para $n \geq 1$, $k \geq 1$.

Demostración: para contar las particiones de $\{1,\ldots,n\}$ en $k$ partes, miramos el elemento $n$. Caso 1: $n$ forma un bloque solitario $\{n\}$. Entonces los $n-1$ elementos restantes se parten en $k-1$ bloques: $S(n-1,k-1)$ maneras. Caso 2: $n$ se agrega a un bloque existente (no es solitario). Entonces primero partimos $\{1,\ldots,n-1\}$ en $k$ bloques ($S(n-1,k)$ maneras) y luego agregamos $n$ a uno de los $k$ bloques existentes ($k$ opciones). En total: $S(n,k) = S(n-1,k-1) + k \cdot S(n-1,k)$.

Casos base: $S(n,1) = 1$ (todos en un bloque), $S(n,n) = 1$ (todos separados), $S(n,0) = 0$ para $n \geq 1$, $S(0,0) = 1$ por convención.

Tabla de valores:

$S(1,1) = 1$. $S(2,1) = 1$, $S(2,2) = 1$. $S(3,1) = 1$, $S(3,2) = 3$, $S(3,3) = 1$. $S(4,1) = 1$, $S(4,2) = 7$, $S(4,3) = 6$, $S(4,4) = 1$. $S(5,2) = 15$, $S(5,3) = 25$, $S(5,4) = 10$.

Fórmula explícita por inclusión-exclusión: $S(n,k) = \frac{1}{k!} \sum_{j=0}^{k} (-1)^{k-j} \binom{k}{j} j^n$. Demostración: de $k^n$ funciones sobreyectivas de $\{1,\ldots,n\}$ a $\{1,\ldots,k\}$ (donde los bloques están etiquetados) en $k!$ particiones — esperar, el conteo es: hay $k!S(n,k)$ funciones sobreyectivas de $\{1,\ldots,n\}$ a $\{1,\ldots,k\}$. Por inclusión-exclusión, el número de tales funciones es $\sum_{j=0}^{k}(-1)^{k-j}\binom{k}{j}j^n$, de donde se obtiene la fórmula.

Números de Stirling de primera clase $c(n,k)$

El número de Stirling de primera clase $c(n,k)$ (signado) es el coeficiente de $x^k$ en el factorial descendente $x^{\underline{n}} = x(x-1)(x-2)\cdots(x-n+1) = \sum_{k=0}^{n} (-1)^{n-k} c(n,k) x^k$. El número de Stirling de primera clase sin signo $\left[\begin{smallmatrix}n\\k\end{smallmatrix}\right] = |c(n,k)|$ cuenta el número de permutaciones de $n$ elementos con exactamente $k$ ciclos.

Recurrencia: $\left[\begin{smallmatrix}n\\k\end{smallmatrix}\right] = (n-1)\left[\begin{smallmatrix}n-1\\k\end{smallmatrix}\right] + \left[\begin{smallmatrix}n-1\\k-1\end{smallmatrix}\right]$.

Demostración: para contar permutaciones de $\{1,\ldots,n\}$ con $k$ ciclos, miramos el elemento $n$. Caso 1: $n$ forma un ciclo solitario $(n)$. Las permutaciones de $\{1,\ldots,n-1\}$ con $k-1$ ciclos: $\left[\begin{smallmatrix}n-1\\k-1\end{smallmatrix}\right]$ maneras. Caso 2: $n$ se inserta dentro de un ciclo existente. Una permutación de $\{1,\ldots,n-1\}$ con $k$ ciclos tiene $n-1$ posiciones donde insertar $n$ (inmediatamente después de cualquiera de los $n-1$ elementos): $\left[\begin{smallmatrix}n-1\\k\end{smallmatrix}\right] \cdot (n-1)$ maneras. Total: $\left[\begin{smallmatrix}n\\k\end{smallmatrix}\right] = \left[\begin{smallmatrix}n-1\\k-1\end{smallmatrix}\right] + (n-1)\left[\begin{smallmatrix}n-1\\k\end{smallmatrix}\right]$.

Casos base: $\left[\begin{smallmatrix}n\\n\end{smallmatrix}\right] = 1$ (cada elemento es su propio ciclo: la identidad), $\left[\begin{smallmatrix}n\\1\end{smallmatrix}\right] = (n-1)!$ (permutaciones con un solo ciclo = permutaciones cíclicas), $\left[\begin{smallmatrix}n\\0\end{smallmatrix}\right] = 0$ para $n \geq 1$.

Suma de filas: $\sum_{k=1}^{n} \left[\begin{smallmatrix}n\\k\end{smallmatrix}\right] = n!$ (el total de permutaciones de $n$ elementos).

Relación entre primera y segunda clase: Los números de Stirling de ambas clases son inversos en el sentido matricial: $\sum_{j=k}^{n} \left[\begin{smallmatrix}n\\j\end{smallmatrix}\right] S(j,k) = \delta_{nk} \cdot n!$. Esto refleja la dualidad entre las bases $\{x^n\}$ y $\{x^{\underline{n}}\}$ en el espacio de polinomios.

Números de Bell y el teorema de suma

El número de Bell $B_n$ es el número total de particiones del conjunto $\{1, 2, \ldots, n\}$ (sin restricción en el número de partes). Por definición, $B_n = \sum_{k=1}^{n} S(n,k)$.

Los primeros valores son: $B_0 = 1$, $B_1 = 1$, $B_2 = 2$, $B_3 = 5$, $B_4 = 15$, $B_5 = 52$.

Triángulo de Bell: Los números de Bell se calculan con el triángulo de Bell (análogo al de Pascal). Empezamos la fila $n$ con $B_n$. Cada siguiente elemento es la suma del elemento anterior en la misma fila y el elemento arriba de ese. El último elemento de la fila $n$ es $B_{n+1}$.

Recurrencia: $B_{n+1} = \sum_{k=0}^{n} \binom{n}{k} B_k$. Demostración: en una partición de $\{1,\ldots,n+1\}$, el elemento $n+1$ pertenece a un bloque. Si ese bloque tiene $k+1$ elementos (incluyendo $n+1$), hay $\binom{n}{k}$ formas de elegir los otros $k$ elementos del bloque, y luego $B_{n-k}$ maneras de particionar los $n-k$ elementos restantes.

Fórmula de Dobin (Función generatriz exponencial): $\sum_{n=0}^{\infty} B_n \frac{x^n}{n!} = e^{e^x - 1}$. Esta es la función generatriz exponencial de los números de Bell. En problemas olímpicos avanzados, se usa para establecer congruencias de Bell: $B_{p+1} \equiv B_1 + B_0 = 2 \pmod p$ y más generalmente $B_{n+p} \equiv B_n + B_{n+1} \pmod p$ para primo $p$ (congruencia de Touchard).

Aplicación de distribución: El número de maneras de distribuir $n$ objetos indistinguibles en $k$ cajas distinguibles tal que ninguna caja quede vacía es $S(n,k) \cdot k!$, el número de funciones sobreyectivas. El número total de distribuciones (con cajas vacías permitidas) es $k^n$.

Conexión con potencias: la fórmula de cambio de base

Una de las aplicaciones más importantes de los números de Stirling es la conversión entre potencias ordinarias y factoriales descendentes. Estas dos bases de polinomios son análogas a diferentes sistemas de coordenadas en el espacio de polinomios.

Potencia a factorial descendente: $x^n = \sum_{k=0}^{n} S(n,k) x^{\underline{k}}$, donde $x^{\underline{k}} = x(x-1)\cdots(x-k+1)$.

Factorial descendente a potencia: $x^{\underline{n}} = \sum_{k=0}^{n} (-1)^{n-k} c(n,k) x^k$, donde $c(n,k) = \left[\begin{smallmatrix}n\\k\end{smallmatrix}\right]$ (con signo).

Importancia: La fórmula $x^n = \sum_{k} S(n,k) x^{\underline{k}}$ permite calcular sumas $\sum_{j=0}^{m} j^n$ usando la fórmula de suma para factoriales descendentes: $\sum_{j=0}^{m} j^{\underline{k}} = \frac{(m+1)^{\underline{k+1}}}{k+1}$ (análogo de la integral de $x^k$). Esto da la fórmula de Bernoulli para sumas de potencias en términos de números de Bernoulli.

Ejemplo: $\sum_{j=1}^{m} j^2 = \sum_{j=1}^{m} \bigl(S(2,1) j^{\underline{1}} + S(2,2) j^{\underline{2}}\bigr) = 1 \cdot \sum j + 1 \cdot \sum j(j-1) = \frac{m(m+1)}{2} + \frac{m(m+1)(m-1)}{3} = \frac{m(m+1)(2m+1)}{6}$.

En olimpiadas: Los números de Stirling aparecen cuando se pregunta "¿de cuántas maneras se puede hacer X?" y la respuesta involucra partir un conjunto en grupos. Reconocer que la estructura es una partición de conjunto (no un subconjunto) es la clave para activar la herramienta de Stirling de segunda clase.