stringtranslate.com

Números de Stirling de segunda especie.

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.

Otra relación de recurrencia está dada por

[ cita necesaria ]

Identidades simples

Algunas identidades simples incluyen

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:

Debido a que los polinomios de Bernoulli pueden escribirse en términos de estas diferencias directas, se obtiene inmediatamente una relación en los números de Bernoulli :

La evaluación del polinomio exponencial incompleto de Bell B n , k ( x 1 , x 2 ,...) en la secuencia de unos es igual a un número de Stirling de segunda especie:

Otra fórmula explícita dada en el Manual de funciones matemáticas del NIST es

Paridad

Paridad de números de Stirling de segunda especie.

La paridad de un número de Stirling de segunda especie es igual a la paridad de un coeficiente binomial relacionado :

dónde

Esta relación se especifica asignando las coordenadas n y k al triángulo de Sierpiński .

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 :

¿Dónde está el soporte de Iverson ?

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

y tener una función generadora exponencial dada por

Una función generadora bivariada mixta para los números de Stirling del segundo tipo es

Límites inferior y superior

Si y , entonces

[12]

Aproximación asintótica

Para el valor fijo del valor asintótico de los números de Stirling de segunda clase dado por

Si (donde o denota la notación o pequeña ) entonces

[13]

También existe una aproximación uniformemente válida: para todo k tal que 1 < k < n , se tiene

donde , y es la solución única para . [14] El error relativo está limitado por aproximadamente .

Máximo para n fijo

Para fijo , tiene un máximo único, que se alcanza como máximo para dos valores consecutivos de k . Es decir, existe un número entero tal que

Mirando la tabla de valores anterior, los primeros valores de son

cuando es grande

y el valor máximo del número de Stirling se puede aproximar con

[12]

Aplicaciones

Momentos de la distribución de Poisson

Si X es una variable aleatoria con una distribución de Poisson con valor esperado λ, entonces su n- ésimo momento es

En particular, el enésimo momento de la distribución de Poisson con valor esperado 1 es precisamente el número de particiones de un conjunto de tamaño n , es decir, es el enésimo número de Bell ( este hecho es la fórmula de Dobiński ).

Momentos de puntos fijos de permutaciones aleatorias.

Sea la variable aleatoria X el número de puntos fijos de una permutación aleatoria uniformemente distribuida de un conjunto finito de tamaño m . Entonces el enésimo momento de X es

Nota: El límite superior de la suma es m , no n .

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.

Ver también

Referencias

  1. ^ Ronald L. Graham, Donald E. Knuth, Oren Patashnik (1988) Matemáticas concretas , Addison – Wesley, Reading MA. ISBN  0-201-14236-8 , pág. 244.
  2. ^ "Números de Stirling de segundo tipo, teorema 3.4.1".
  3. ^ 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 .
  4. ^ 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.
  5. ^ Antonio Salmeri, Introduzione alla teoria dei coeficientei fattoriali, Giornale di Matematiche di Battaglini 90 (1962), págs.
  6. ^ 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
  7. ^ Donald E. Knuth, Algoritmos fundamentales , Reading, Mass.: Addison – Wesley, 1968.
  8. ^ pág. 66, Donald E. Knuth, Algoritmos fundamentales , 3.ª ed., Reading, Mass.: Addison–Wesley, 1997.
  9. ^ 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.
  10. ^ 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
  11. ^ 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
  12. ^ 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.
  13. ^ 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
  14. ^ NM Temme, Estimaciones asintóticas de números de Stirling, ESTUDIOS EN MATEMÁTICAS APLICADAS 89:233-243 (1993), Elsevier Science Publishing.
  15. ^ Broder, A. (1984). Los números de r-Stirling. Matemáticas discretas 49, 241-259
  16. 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.
  17. ^ L. Comtet, Combinatoria avanzada , Reidel, 1974, pág. 222.
  18. ^ 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.