Cuenta particiones de conjuntos.
Los Números de Stirling de Segunda Especie, que escribes como $\left{ \begin{matrix} n \ k \end{matrix} \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í. En el contexto de las "Doce Formas" (Twelvefold Way) de la combinatoria, esto equivale a repartir $n$ objetos distintos (bolas numeradas) en $k$ recipientes idénticos (cajas sin etiquetas) de modo que ninguna caja quede vacía. Si las cajas fueran distintas, solo tendrías que multiplicar el resultado por $k!$.
Estos números son fundamentales en el conteo avanzado porque conectan las estructuras discretas con el álgebra de polinomios. Aparecen seguido en problemas de funciones suprayectivas, donde el número de funciones suprayectivas de un conjunto de tamaño $n$ a uno de tamaño $k$ es $k! \left{ \begin{matrix} n \ k \end{matrix} \right}$. Además, te dan los coeficientes necesarios para escribir potencias normales $x^n$ como una combinación lineal de factoriales descendentes, lo que une la combinatoria con el cálculo de diferencias finitas.
La intuición para calcular estos números suele venir de un enfoque recursivo parecido al del Triángulo de Pascal. Para partir un conjunto ${1, 2, \dots, n}$ en $k$ subconjuntos, fíjate en el último elemento, el $n$. O bien el $n$ forma un conjunto solito, o se mete en uno de los subconjuntos que ya habías armado con los $n-1$ elementos anteriores. Esta división lógica es la base de la relación de recurrencia fundamental que usas para calcular valores de $n$ y $k$ pequeños.
1. Relación de Recurrencia Fundamental Para $n \ge k \ge 1$: $$ \left{ \begin{matrix} n \ k \end{matrix} \right} = \left{ \begin{matrix} n-1 \ k-1 \end{matrix} \right} + k \left{ \begin{matrix} n-1 \ k \end{matrix} \right} $$
2. Fórmula Explícita (por Inclusión-Exclusión) $$ \left{ \begin{matrix} n \ k \end{matrix} \right} = \frac{1}{k!} \sum_{j=0}^{k} (-1)^{k-j} \binom{k}{j} j^n $$
3. Conexión con Potencias y Factoriales Descendentes Si tomas $(x)k = x(x-1)\dots(x-k+1)$ como el factorial descendente, entonces: $$ x^n = \sum{k=0}^{n} \left{ \begin{matrix} n \ k \end{matrix} \right} (x)_k $$
4. Condiciones de Frontera y Valores Especiales $$ \left{ \begin{matrix} n \ n \end{matrix} \right} = 1, \quad \left{ \begin{matrix} n \ 1 \end{matrix} \right} = 1, \quad \left{ \begin{matrix} n \ 0 \end{matrix} \right} = 0 \text{ (para } n \ge 1) $$ $$ \left{ \begin{matrix} n \ n-1 \end{matrix} \right} = \binom{n}{2}, \quad \left{ \begin{matrix} n \ 2 \end{matrix} \right} = 2^{n-1} - 1 $$
5. Relación con los Números de Bell El número de Bell $B_n$ cuenta el total de formas de partir un conjunto de tamaño $n$: $$ B_n = \sum_{k=0}^{n} \left{ \begin{matrix} n \ k \end{matrix} \right} $$
Teorema: Los Números de Stirling de Segunda Especie cumplen la relación de recurrencia $\left{ \begin{matrix} n \ k \end{matrix} \right} = \left{ \begin{matrix} n-1 \ k-1 \end{matrix} \right} + k \left{ \begin{matrix} n-1 \ k \end{matrix} \right}$.
Demostración: Imagina que $S = {1, 2, \dots, n}$ es un conjunto de $n$ elementos distintos. La idea es contar de cuántas formas puedes partir $S$ en $k$ subconjuntos no vacíos que no puedes distinguir entre sí. A este número lo escribes como $\left{ \begin{matrix} n \ k \end{matrix} \right}$.
Fíjate en el elemento específico $n \in S$. En cualquier partición de $S$, el elemento $n$ tiene que estar en exactamente un subconjunto. Puedes separar esto en dos casos que cubren todas las posibilidades y no se enciman, dependiendo de cómo sea el subconjunto donde está $n$.
Caso 1: El elemento $n$ está solo en su subconjunto. Si ${n}$ es uno de los subconjuntos de la partición, entonces tienes que repartir los $n-1$ elementos que sobran (el conjunto ${1, 2, \dots, n-1}$) en los $k-1$ subconjuntos no vacíos que quedan. Por definición, el número de formas de partir $n-1$ elementos en $k-1$ subconjuntos es: $$ \left{ \begin{matrix} n-1 \ k-1 \end{matrix} \right} $$
Caso 2: El elemento $n$ está en un subconjunto con otros elementos. Si ${n}$ no está solo, entonces $n$ comparte su subconjunto con algunos elementos de ${1, 2, \dots, n-1}$. Para armar una partición así, primero partes los $n-1$ elementos ${1, 2, \dots, n-1}$ en $k$ subconjuntos no vacíos. El número de formas de hacer esto es $\left{ \begin{matrix} n-1 \ k \end{matrix} \right}$. Ya que tienes esos $k$ subconjuntos armados, tienes que meter el elemento $n$ en uno de ellos. Como los $k$ subconjuntos ya tienen elementos, ahora sí los puedes distinguir por lo que tienen adentro. Por lo tanto, tienes $k$ opciones para elegir dónde poner el elemento $n$. El número de formas para este caso es: $$ k \times \left{ \begin{matrix} n-1 \ k \end{matrix} \right} $$
Conclusión: Como estos dos casos cubren todas las opciones y no se traslapan, el total de particiones es la suma de lo que obtuviste en el Caso 1 y el Caso 2: $$ \left{ \begin{matrix} n \ k \end{matrix} \right} = \left{ \begin{matrix} n-1 \ k-1 \end{matrix} \right} + k \left{ \begin{matrix} n-1 \ k \end{matrix} \right} $$ $\square$