Números de Stirling de segunda especie

Los números de Stirling de segunda especie responden a una pregunta fundamental de conteo en matemáticas discretas: dados n objetos distintos, ¿de cuántas formas puede particionarlos en exactamente k grupos no vacíos sin etiqueta? La respuesta se escribe S(n,k) o a veces {n choose k} con llaves. Estos números aparecen siempre que agrupa personas en equipos sin nombrar los equipos, reparte un conjunto de claves en cubos sin etiqueta, cuenta funciones sobreyectivas salvo un factor factorial, construye números de Bell como suma sobre k, o califica ejercicios que piden particiones de conjuntos en lugar de permutaciones. Esta capacidad acepta enteros no negativos n (número de ítems) y k (número de subconjuntos no vacíos) y devuelve el S(n,k) exacto como cadena decimal calculada con programación dinámica BigInt, de modo que valores muy por encima de los límites de enteros seguros ordinarios permanecen correctos dígito a dígito. Las entradas con k negativo o con k mayor que n se rechazan con un error de validación claro en lugar de un cero silencioso o una respuesta errónea.

Cómo se definen los números de Stirling de segunda especie

Un número de Stirling de segunda especie S(n,k) cuenta las particiones de un conjunto de n elementos en exactamente k subconjuntos no vacíos sin etiqueta. El orden dentro de un subconjunto no importa, y los subconjuntos mismos no están ordenados: la partición {{1,2},{3}} es la misma que {{3},{1,2}}. La recurrencia estándar es S(n,k) = k · S(n−1,k) + S(n−1,k−1).

Intuitivamente, al añadir el elemento más reciente n, o forma un singleton propio (entonces los n−1 elementos restantes forman k−1 subconjuntos, contados por S(n−1,k−1)), o se une a uno de los k subconjuntos existentes en una partición de los primeros n−1 elementos en k bloques (k opciones, por S(n−1,k)). Los casos base que cierran la tabla son S(0,0) = 1, S(n,0) = 0 para n > 0, S(0,k) = 0 para k > 0, S(n,1) = 1 y S(n,n) = 1.

Comprobaciones clásicas de libro incluyen S(3,2) = 3, S(4,2) = 7, S(5,2) = 15 y S(5,3) = 25. El número de Bell B_n, el total de particiones de un n-conjunto con cualquier número de bloques, es la suma de S(n,k) sobre k de cero a n. Objetos relacionados pero distintos incluyen los números de Stirling de primera especie (que siguen permutaciones por recuento de ciclos) y los coeficientes binomiales (que eligen elementos sin particionar el resto).

Esta implementación no usa nunca aproximación de coma flotante, muestreo Monte Carlo ni tablas externas: rellena una fila de programación dinámica con aritmética BigInt exacta para que cada dígito sea correcto. El camino es totalmente determinista —sin semillas aleatorias, relojes, red ni deriva de modelo—, de modo que el mismo n y k siempre producen la misma cadena.

Dónde aparecen los recuentos de Stirling de segunda especie en el trabajo real

Los cursos de combinatoria y los concursos de programación preguntan constantemente de cuántas formas dividir n personas etiquetadas en k equipos sin etiqueta, cuántas relaciones de equivalencia en n elementos tienen exactamente k clases, o de cuántas formas repartir n regalos distintos en k cajas idénticas no vacías —todo lo cual equivale a S(n,k).

Los diseñadores de algoritmos usan tablas de Stirling de segunda especie al analizar estructuras de datos de partición de conjuntos, bocetos de clustering con un número fijo de clústeres, o al contar las formas en que un proceso recursivo puede agrupar resultados intermedios. Los cursos de probabilidad y estadística conectan S(n,k) con el número de formas de asignar n resultados distintos a k cubos no vacíos sin etiqueta y con la forma cerrada del número de sobreyecciones de un n-conjunto sobre un k-conjunto, que es k!

· S(n,k). Educadores y preparación de entrevistas a menudo muestran un triángulo breve de valores pequeños de S(n,k); calcular una sola entrada en una llamada mantiene las demos interactivas alineadas con libros y claves de respuesta sin mantener a mano tablas grandes. Si más adelante necesita números de Stirling de primera especie, solo números de Bell, recuentos de sobreyección con el factor k! ya aplicado, o un listado explícito de particiones en lugar del recuento, trátelos como intenciones de búsqueda separadas en lugar de sobrecargar esta página.