S(m,n) cuenta las particiones de un conjunto.
La conexión entre contar suprayecciones y los números de Stirling de segunda especie es un puente fundamental en la combinatoria, ya que une problemas de "cajas etiquetadas" con problemas de "cajas sin etiquetas". Una suprayección de un conjunto de tamaño $m$ a uno de tamaño $n$ representa distribuir $m$ objetos distintos en $n$ cajas distintas de modo que ninguna caja se quede vacía. En cambio, el número de Stirling de segunda especie, que escribimos como $S(m,n)$ o $\left{ \begin{matrix} m \ n \end{matrix} \right}$, cuenta de cuántas formas puedes partir un conjunto de $m$ elementos en $n$ subconjuntos no vacíos que no se pueden distinguir entre sí.
Esta relación es crucial porque calcular suprayecciones directamente suele requerir el Principio de Inclusión-Exclusión (PIE), lo que te da una fórmula con una sumatoria. Al reconocer el vínculo estructural entre las suprayecciones y las particiones de conjuntos, puedes obtener una identidad muy potente: el número de suprayecciones es exactamente $n!$ veces el número de Stirling correspondiente. La idea es que la única diferencia entre una suprayección (codominio etiquetado) y una partición de un conjunto (grupos sin etiquetas) es cómo asignas las etiquetas a los grupos.
En las olimpiadas de matemáticas, esta conexión te permite cambiar de perspectiva. Si un problema te pide el número de formas de distribuir pelotas distintas en cajas idénticas (números de Stirling), puedes calcular el número de suprayecciones en cajas distintas usando PIE y luego dividir entre $n!$. Al revés, si ya conoces los números de Stirling (por ejemplo, por su relación de recurrencia), puedes encontrar fácilmente el número de suprayecciones sin tener que volver a armar la sumatoria del PIE.
Imagina que $Surj(m,n)$ es el número de funciones suprayectivas de un conjunto de $m$ elementos a uno de $n$ elementos. Sea $S(m,n)$ el número de Stirling de segunda especie.
La Identidad Fundamental: $$Surj(m,n) = n! \cdot S(m,n)$$
Fórmula Explícita para los Números de Stirling (vía PIE): Usando la fórmula de PIE para suprayecciones, obtienes la fórmula explícita para los números de Stirling: $$S(m,n) = \frac{1}{n!} \sum_{k=0}^n (-1)^k \binom{n}{k} (n-k)^m$$
Notación Alternativa: $$n! \left{ \begin{matrix} m \ n \end{matrix} \right} = \sum_{j=0}^n (-1)^{n-j} \binom{n}{j} j^m$$ (Nota: Esta es equivalente a la fórmula de arriba, solo cambiaron los índices).
Teorema: El número de suprayecciones de un conjunto $A$ con $|A|=m$ a un conjunto $B$ con $|B|=n$ es $n! \cdot S(m,n)$.
Demostración: La idea es usar un argumento combinatorio basado en cómo se estructuran las funciones y las particiones.
Define las Preimágenes: Toma una función suprayectiva $f: A \to B$. Para cada elemento $y \in B$, la preimagen de $y$ es el conjunto $f^{-1}(y) = {x \in A \mid f(x) = y}$.
Establece la Estructura de la Partición: Como $f$ es una función, cada $x \in A$ va a parar a exactamente un $y \in B$. Por lo tanto, los conjuntos ${f^{-1}(y) \mid y \in B}$ son ajenos entre sí y su unión es $A$. Como $f$ es suprayectiva, para cada $y \in B$, el conjunto $f^{-1}(y)$ no está vacío. Así que la colección de preimágenes forma una partición de $A$ en exactamente $n$ subconjuntos no vacíos.
Construye el Mapeo: Puedes construir cualquier suprayección $f: A \to B$ en dos pasos independientes:
Conclusión: Por el Principio Multiplicativo, el número total de estas suprayecciones es el producto de las formas en que puedes hacer estos pasos: $$Surj(m,n) = S(m,n) \times n!$$
$\square$