Números de Stirling

Teoría

Los Números de Stirling son un conjunto de dos sucesiones de números que aparecen seguido en combinatoria, sobre todo en problemas que tienen que ver con agrupar elementos o descomponer permutaciones. Los Números de Stirling de Segunda Especie, que escribimos como $\left{ \begin{smallmatrix} n \ k \end{smallmatrix} \right}$ o $S(n,k)$, cuentan de cuántas formas puedes partir un conjunto de $n$ elementos distintos en $k$ subconjuntos no vacíos que no puedes distinguir entre sí. Esto es fundamental en problemas de "pelotas y cajas" donde las pelotas son distintas pero las cajas son idénticas. Por ejemplo, $\left{ \begin{smallmatrix} 4 \ 2 \end{smallmatrix} \right}$ representa la cantidad de formas de dividir cuatro objetos únicos en dos montones.

Los Números de Stirling de Primera Especie, que escribimos como $\left[ \begin{smallmatrix} n \ k \end{smallmatrix} \right]$ o $c(n,k)$, cuentan el número de permutaciones de $n$ elementos distintos que tienen exactamente $k$ ciclos disjuntos. Mientras que los de Segunda Especie tratan con particiones de conjuntos, los de Primera Especie tienen que ver con descomposiciones en ciclos. Estos números son clave para analizar algoritmos y en combinatoria algebraica porque te dan los coeficientes para pasar de potencias estándar de variables ($x^n$) a factoriales crecientes o decrecientes.

La intuición detrás de ambos tipos se basa mucho en la construcción recursiva. Para encontrar el valor para $n$ elementos, considera específicamente al $n$-ésimo elemento. Para los de Segunda Especie, el $n$-ésimo elemento o forma un subconjunto nuevo él solo, o lo unes a un subconjunto que ya existe. Para los de Primera Especie, el $n$-ésimo elemento o forma un ciclo de longitud 1 o lo metes en un ciclo ya existente. Este enfoque "constructivo" permite que descompongas problemas de conteo complejos en relaciones de recurrencia más simples, una técnica vital para combinatoria de nivel USAMO e IMO.

Fórmulas Clave

Notación:

• $\left{ \begin{smallmatrix} n \ k \end{smallmatrix} \right}$: Números de Stirling de Segunda Especie (particiones de $n$ elementos en $k$ subconjuntos).
• $\left[ \begin{smallmatrix} n \ k \end{smallmatrix} \right]$: Números de Stirling de Primera Especie sin signo (permutaciones de $n$ elementos con $k$ ciclos).
• $(x)_n = x(x-1)\dots(x-n+1)$: El factorial decreciente.
• $x^{\overline{n}} = x(x+1)\dots(x+n-1)$: El factorial creciente.

Relaciones de Recurrencia: $$ \left{ \begin{smallmatrix} n \ k \end{smallmatrix} \right} = k \left{ \begin{smallmatrix} n-1 \ k \end{smallmatrix} \right} + \left{ \begin{smallmatrix} n-1 \ k-1 \end{smallmatrix} \right} $$ $$ \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] $$

Fórmula Explícita (Segunda Especie): $$ \left{ \begin{smallmatrix} n \ k \end{smallmatrix} \right} = \frac{1}{k!} \sum_{j=0}^k (-1)^{k-j} \binom{k}{j} j^n $$

Identidades Polinomiales: Los números de Stirling funcionan como coeficientes de cambio de base entre bases polinomiales. $$ x^n = \sum_{k=0}^n \left{ \begin{smallmatrix} n \ k \end{smallmatrix} \right} (x)k $$ $$ x^{\overline{n}} = \sum{k=0}^n \left[ \begin{smallmatrix} n \ k \end{smallmatrix} \right] x^k $$

Valores Especiales:

• $\left{ \begin{smallmatrix} n \ 1 \end{smallmatrix} \right} = 1$, $\left{ \begin{smallmatrix} n \ n \end{smallmatrix} \right} = 1$
• $\left{ \begin{smallmatrix} n \ 2 \end{smallmatrix} \right} = 2^{n-1} - 1$
• $\left[ \begin{smallmatrix} n \ 1 \end{smallmatrix} \right] = (n-1)!$, $\left[ \begin{smallmatrix} n \ n \end{smallmatrix} \right] = 1$
• Suma de los de Segunda Especie (Número de Bell): $B_n = \sum_{k=0}^n \left{ \begin{smallmatrix} n \ k \end{smallmatrix} \right}$

Demostración

Teorema: Los Números de Stirling de Segunda Especie cumplen la relación de recurrencia: $$ \left{ \begin{smallmatrix} n \ k \end{smallmatrix} \right} = k \left{ \begin{smallmatrix} n-1 \ k \end{smallmatrix} \right} + \left{ \begin{smallmatrix} n-1 \ k-1 \end{smallmatrix} \right} $$ para $1 \le k < n$.

Demostración: Usa un argumento combinatorio (conteo constructivo). Sea $S = {1, 2, \dots, n}$. Lo que quieres es contar de cuántas formas puedes partir $S$ en $k$ subconjuntos no vacíos e indistinguibles. Enfócate en el elemento específico $n$. En cualquier partición, el elemento $n$ tiene que estar en exactamente uno de los subconjuntos. Hay dos casos que no pueden pasar al mismo tiempo:

Caso 1: El elemento $n$ está solo en un subconjunto. Si ${n}$ es uno de los subconjuntos de la partición, entonces tienes que repartir los $n-1$ elementos que quedan en los $k-1$ subconjuntos no vacíos restantes. Por definición, la cantidad de formas de partir el conjunto ${1, \dots, n-1}$ en $k-1$ subconjuntos no vacíos es $\left{ \begin{smallmatrix} n-1 \ k-1 \end{smallmatrix} \right}$.

Caso 2: El elemento $n$ comparte subconjunto con otros elementos. Si $n$ no está solo, puedes pensar en este proceso como si primero partieras los otros $n-1$ elementos en $k$ subconjuntos no vacíos, y luego metieras a $n$ en uno de esos subconjuntos que ya existen.

1. La cantidad de formas de partir ${1, \dots, n-1}$ en $k$ subconjuntos no vacíos es $\left{ \begin{smallmatrix} n-1 \ k \end{smallmatrix} \right}$.
2. Una vez que formas estos $k$ subconjuntos, tienes que elegir uno de ellos para que contenga a $n$. Como hay $k$ subconjuntos distintos disponibles (se vuelven distintos después de que les pones elementos de ${1, \dots, n-1}$), tienes $k$ opciones para poner a $n$. Así que el número de formas para este caso es $k \times \left{ \begin{smallmatrix} n-1 \ k \end{smallmatrix} \right}$.

Conclusión: Como estos dos casos cubren todas las posibilidades y no se traslapan, el número total de particiones es la suma de los conteos de ambos casos: $$ \left{ \begin{smallmatrix} n \ k \end{smallmatrix} \right} = \left{ \begin{smallmatrix} n-1 \ k-1 \end{smallmatrix} \right} + k \left{ \begin{smallmatrix} n-1 \ k \end{smallmatrix} \right} $$ $\square$