Números que parametrizan formas de particionar un conjunto
Las 15 particiones de un conjunto de 4 elementos ordenadas en un diagrama de Hasse Hay S (4,1), ..., S (4, 4) = 1, 7, 6, 1 particiones que contienen 1, 2, 3, 4 conjuntos.
En matemáticas , particularmente en combinatoria , un número de Stirling de segundo tipo (o número de partición de Stirling ) es el número de formas de dividir un conjunto de n objetos en k subconjuntos no vacíos y se denota por o . [1] Los números de Stirling del segundo tipo ocurren en el campo de las matemáticas llamado combinatoria y el estudio de particiones . Llevan el nombre de James Stirling .
Los números de Stirling de primera y segunda clase pueden entenderse como inversos entre sí cuando se ven como matrices triangulares . Este artículo está dedicado a los detalles de los números de Stirling del segundo tipo. Las identidades que vinculan los dos tipos aparecen en el artículo sobre los números de Stirling .
Definición
Los números de Stirling del segundo tipo, escritos o con otras notaciones, cuentan el número de formas de dividir un conjunto de objetos etiquetados en subconjuntos no vacíos y no etiquetados. De manera equivalente, cuentan el número de relaciones de equivalencia diferentes con clases de equivalencia precisas que se pueden definir en un conjunto de elementos. De hecho, existe una biyección entre el conjunto de particiones y el conjunto de relaciones de equivalencia en un conjunto dado. Obviamente,
para norte ≥ 0, y para norte ≥ 1,
ya que la única forma de dividir un conjunto de n elementos en n partes es poner cada elemento del conjunto en su propia parte, y la única forma de dividir un conjunto no vacío en una parte es poner todos los elementos en la misma parte . A diferencia de los números de Stirling de primera especie , se pueden calcular mediante una fórmula de suma única: [2]
Los números de Stirling del segundo tipo también pueden caracterizarse como los números que surgen cuando se expresan potencias de un x indeterminado en términos de factoriales decrecientes [3]
(En particular, ( x ) 0 = 1 porque es un producto vacío .)
En otras palabras
Notación
Se han utilizado varias notaciones para los números de Stirling de segunda especie. La notación entre llaves fue utilizada por Imanuel Marx y Antonio Salmeri en 1962 para variantes de estos números. [4] [5] Esto llevó a Knuth a usarlo, como se muestra aquí, en el primer volumen de El arte de la programación informática (1968). [6] [7] Según la tercera edición de El arte de la programación informática , esta notación también fue utilizada anteriormente por Jovan Karamata en 1935. [8] [9] La notación S ( n , k ) fue utilizada por Richard Stanley en su libro Enumerative Combinatorics y también, mucho antes, por muchos otros escritores. [6]
Las notaciones utilizadas en esta página para los números de Stirling no son universales y pueden entrar en conflicto con las notaciones de otras fuentes.
Relación con los números de Bell
Dado que el número de Stirling cuenta particiones establecidas de un elemento n establecido en k partes, la suma
sobre todos los valores de k es el número total de particiones de un conjunto con n miembros. Este número se conoce como el enésimo número de Bell .
De manera análoga, los números de Bell ordenados se pueden calcular a partir de los números de Stirling del segundo tipo mediante
[10]
tabla de valores
A continuación se muestra una matriz triangular de valores para los números de Stirling del segundo tipo (secuencia A008277 en OEIS ):
Al igual que con los coeficientes binomiales , esta tabla podría ampliarse a k > n , pero todas las entradas serían 0.
Propiedades
Relación de recurrencia
Los números de Stirling de segunda especie obedecen a la relación de recurrencia.
con condiciones iniciales
Por ejemplo, el número 25 en la columna k = 3 y la fila n = 5 viene dado por 25 = 7 + (3×6), donde 7 es el número arriba y a la izquierda de 25, 6 es el número arriba de 25 y 3 es la columna que contiene el 6.
Para probar esta recurrencia, observe que una partición de los objetos en k subconjuntos no vacíos contiene el -ésimo objeto como un singleton o no. El número de formas en que el singleton es uno de los subconjuntos viene dado por
ya que debemos dividir los n objetos restantes en los subconjuntos disponibles . En el otro caso, el -ésimo objeto pertenece a un subconjunto que contiene otros objetos. El número de formas está dado por
ya que dividimos todos los objetos distintos del -ésimo en k subconjuntos, y luego nos quedan k opciones para insertar el objeto . La suma de estos dos valores da el resultado deseado.
Esto se debe a que dividir n elementos en n − 1 conjuntos significa necesariamente dividirlos en un conjunto de tamaño 2 y n − 2 conjuntos de tamaño 1. Por lo tanto, sólo necesitamos elegir esos dos elementos;
y
Para ver esto, primero observe que hay 2 n pares ordenados de subconjuntos complementarios A y B. En un caso, A está vacío y en otro B está vacío, por lo que quedan 2 n − 2 pares ordenados de subconjuntos. Finalmente, como queremos pares desordenados en lugar de pares ordenados , dividimos este último número por 2, dando el resultado anterior.
Otra expansión explícita de la relación de recurrencia proporciona identidades en el espíritu del ejemplo anterior.
Identidades
La tabla de la sección 6.1 de Matemáticas Concretas proporciona una gran cantidad de formas generalizadas de sumas finitas que involucran los números de Stirling. Se incluyen varias sumas finitas particulares relevantes para este artículo.
Fórmula explícita
Los números de Stirling de segunda especie vienen dados por la fórmula explícita:
Esto se puede derivar usando inclusión-exclusión para contar las sobrejecciones de n a k y usando el hecho de que el número de dichas sobrejecciones es .
Además, esta fórmula es un caso especial de la k -ésima diferencia directa del monomio evaluada en x = 0:
Más directamente, dejemos que dos conjuntos contengan posiciones de unos en representaciones binarias de los resultados de las expresiones respectivas:
Se puede imitar una operación AND bit a bit intersectando estos dos conjuntos:
para obtener la paridad de un número de Stirling de segunda especie en tiempo O (1) . En pseudocódigo :
La paridad de un número de Stirling central de segunda especie es impar si y sólo si es un número fibinario , un número cuya representación binaria no tiene dos unos consecutivos. [11]
Funciones generadoras
Para un entero fijo n , la función generadora ordinaria para los números de Stirling del segundo tipo viene dada por
¿Dónde están los polinomios de Touchard ? Si, en cambio, se suman los números de Stirling con el factorial descendente, se pueden mostrar las siguientes identidades, entre otras:
y
que tiene un caso especial
.
Para un entero fijo k , los números de Stirling del segundo tipo tienen una función generadora ordinaria racional
En otras palabras, el enésimo momento de esta distribución de probabilidad es el número de particiones de un conjunto de tamaño n en no más de m partes. Esto se demuestra en el artículo sobre estadísticas de permutaciones aleatorias , aunque la notación es un poco diferente.
Esquemas de rima
Los números de Stirling del segundo tipo pueden representar el número total de esquemas de rima para un poema de n versos. da el número de posibles esquemas de rima para n líneas usando k sílabas de rima únicas. Como ejemplo, para un poema de 3 líneas, hay 1 esquema de rima que usa solo una rima (aaa), 3 esquemas de rima que usan dos rimas (aab, aba, abb) y 1 esquema de rima que usa tres rimas (abc).
Variantes
r -Números de Stirling del segundo tipo.
El número r -Stirling del segundo tipo cuenta el número de particiones de un conjunto de n objetos en k subconjuntos disjuntos no vacíos, de modo que los primeros r elementos estén en subconjuntos distintos. [15] Estos números satisfacen la relación de recurrencia.
Algunas identidades combinatorias y una conexión entre estos números y gramáticas libres de contexto se pueden encontrar en [16]
Números de Stirling asociados de segunda especie.
Un número de Stirling asociado a r de segundo tipo es el número de formas de dividir un conjunto de n objetos en k subconjuntos, y cada subconjunto contiene al menos r elementos. [17] Se denota y obedece a la relación de recurrencia.
Los números asociados a 2 (secuencia A008299 en la OEIS ) aparecen en otros lugares como "números de Ward" y como las magnitudes de los coeficientes de los polinomios de Mahler .
Números reducidos de Stirling del segundo tipo.
Denota los n objetos a dividir por los números enteros 1, 2, ..., n . Defina los números de Stirling reducidos del segundo tipo, denotados como el número de formas de dividir los números enteros 1, 2, ..., n en k subconjuntos no vacíos de modo que todos los elementos de cada subconjunto tengan una distancia por pares de al menos d . Es decir, para cualquier número entero i y j en un subconjunto dado, se requiere que . Se ha demostrado que estos números satisfacen
(de ahí el nombre "reducido"). [18] Observe (tanto por definición como por la fórmula de reducción), que los familiares números de Stirling de segunda clase.
^ "Números de Stirling de segundo tipo, teorema 3.4.1".
^ De manera confusa, la notación que usan los combinatorialistas para factoriales descendentes coincide con la notación utilizada en funciones especiales para factoriales ascendentes ; ver símbolo de Pochhammer .
^ Transformación de series mediante una variante de los números de Stirling, Imanuel Marx, The American Mathematical Monthly 69 , n.° 6 (junio-julio de 1962), págs. 530-532, JSTOR 2311194.
^ Antonio Salmeri, Introduzione alla teoria dei coeficientei fattoriali, Giornale di Matematiche di Battaglini 90 (1962), págs.
^ ab Knuth, DE (1992), "Dos notas sobre notación", Amer. Matemáticas. Mensual , 99 (5): 403–422, arXiv : math/9205211 , Bibcode : 1992math......5211K, doi : 10.2307/2325085, JSTOR 2325085, S2CID 119584305
^ Donald E. Knuth, Algoritmos fundamentales , Reading, Mass.: Addison – Wesley, 1968.
^ pág. 66, Donald E. Knuth, Algoritmos fundamentales , 3.ª ed., Reading, Mass.: Addison–Wesley, 1997.
^ Jovan Karamata, Théorèmes sur la sommabilité exponentielle et d'autres sommabilités s'y rattachant, Mathematica (Cluj) 9 (1935), págs., 164-178.
^ Sprugnoli, Renzo (1994), "Matrices de Riordan y sumas combinatorias" (PDF) , Matemáticas discretas , 132 (1–3): 267–290, doi : 10.1016/0012-365X(92)00570-H , SEÑOR 1297386
^ Chan, O-Yeat; Manna, Dante (2010), "Congruencias de números de Stirling de segunda especie" (PDF) , Gems in Experimental Mathematics , Contemporary Mathematics, vol. 517, Providence, Rhode Island: Sociedad Matemática Estadounidense, págs. 97–111, doi :10.1090/conm/517/10135, SEÑOR 2731094
^ ab Rennie, antes de Cristo; Dobson, AJ (1969). "Sobre los números de Stirling del segundo tipo". Revista de teoría combinatoria . 7 (2): 116–121. doi : 10.1016/S0021-9800(69)80045-1 . ISSN 0021-9800.
^ LC Hsu , Nota sobre una expansión asintótica de la enésima diferencia de cero, AMS Vol.19 NO.2 1948, págs.273--277
^ NM Temme, Estimaciones asintóticas de números de Stirling, ESTUDIOS EN MATEMÁTICAS APLICADAS 89:233-243 (1993), Elsevier Science Publishing.
^ Broder, A. (1984). Los números de r-Stirling. Matemáticas discretas 49, 241-259
↑ Triana, J. (2022). Números r-Stirling de segunda especie a través de gramáticas libres de contexto. Revista de autómatas, lenguajes y combinatoria 27(4), 323-333.
^ L. Comtet, Combinatoria avanzada , Reidel, 1974, pág. 222.
^ A. Mohr y TD Porter, Aplicaciones de polinomios cromáticos que involucran números de Stirling , Journal of Combinatorial Mathematics and Combinatorial Computing 70 (2009), 57–64.
Boyadzhiev, Khristo (2012). "Encuentros cercanos con los números de Stirling del segundo tipo". Revista Matemáticas . 85 (4): 252–266. arXiv : 1806.09468 . doi : 10.4169/math.mag.85.4.252. S2CID 115176876..
"Números de Stirling del segundo tipo". PlanetMath ..