En matemáticas , particularmente en combinatoria , un número de Stirling del 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 .
Los números de Stirling del segundo tipo son uno de los dos tipos de números de Stirling , el otro tipo se llama números de Stirling del primer tipo (o números de ciclo de Stirling). Se pueden formar matrices triangulares mutuamente inversas (finitas o infinitas) a partir de los números de Stirling de cada tipo de acuerdo con los parámetros n , k .
Definición
Los números de Stirling del segundo tipo, escritos o o con otras notaciones, cuente el número de formas de particionar un conjunto de objetos etiquetados en subconjuntos no vacíos sin etiquetar. De manera equivalente, cuentan el número de relaciones de equivalencia diferentes con precisión clases de equivalencia 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,
- y para
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 . Se pueden calcular utilizando la siguiente fórmula explícita: [2]
Los números de Stirling del segundo tipo también pueden caracterizarse como los números que surgen cuando uno expresa potencias de una x indeterminada en términos de factoriales descendentes [3]
(En particular, ( x ) 0 = 1 porque es un producto vacío .) En general, uno tiene
Notación
Se han utilizado varias notaciones para los números de Stirling del segundo tipo. La notación de corséFue utilizado 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 The Art of Computer Programming (1968). [6] [7] Según la tercera edición de The Art of Computer Programming , 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, de 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 las particiones de un conjunto de n elementos 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 número n 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 a través de
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 la OEIS ):
k norte | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | ||||||||||
1 | 0 | 1 | |||||||||
2 | 0 | 1 | 1 | ||||||||
3 | 0 | 1 | 3 | 1 | |||||||
4 | 0 | 1 | 7 | 6 | 1 | ||||||
5 | 0 | 1 | 15 | 25 | 10 | 1 | |||||
6 | 0 | 1 | 31 | 90 | sesenta y cinco | 15 | 1 | ||||
7 | 0 | 1 | 63 | 301 | 350 | 140 | 21 | 1 | |||
8 | 0 | 1 | 127 | 966 | 1701 | 1050 | 266 | 28 | 1 | ||
9 | 0 | 1 | 255 | 3025 | 7770 | 6951 | 2646 | 462 | 36 | 1 | |
10 | 0 | 1 | 511 | 9330 | 34105 | 42525 | 22827 | 5880 | 750 | 45 | 1 |
Al igual que con los coeficientes binomiales , esta tabla podría extenderse hasta k > n , pero todas esas entradas serían 0.
Propiedades
Relación de recurrencia
Los números de Stirling del segundo tipo obedecen a la relación de recurrencia
para k > 0 con condiciones iniciales
para n > 0.
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 de arriba y a la izquierda de 25, 6 es el número de arriba de 25 y 3 es la columna que contiene el 6.
Para probar esta recurrencia, observe que una partición del objetos en k subconjuntos no vacíos o bien contiene el-ésimo objeto como 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 el disponiblesubconjuntos. En el otro caso el-th objeto pertenece a un subconjunto que contiene otros objetos. El número de formas viene dado por
ya que particionamos todos los objetos que no sean -th en k subconjuntos, y luego nos quedan k opciones para insertar objetos. La suma de estos dos valores da el resultado deseado.
Algunas recurrencias más son las siguientes:
Límites inferior y superior
Si y , luego
dónde
y
Máximo
Para fijo , tiene un solo máximo, que se alcanza como máximo para dos valores consecutivos de k . Es decir, hay un entero tal que
Cuándo es largo
y el valor máximo del número de Stirling de segundo tipo es
Paridad
La paridad de un número de Stirling del segundo tipo es igual a la paridad de un coeficiente binomial relacionado :
- dónde
Esta relación se especifica mapeando las coordenadas n y k en el triángulo de Sierpiński .
Más directamente, supongamos que dos conjuntos contienen posiciones de unos en representaciones binarias de los resultados de las respectivas expresiones:
Se puede imitar una operación AND bit a bit al cruzar estos dos conjuntos:
para obtener la paridad de un número de Stirling del segundo tipo en el tiempo O (1) . En pseudocódigo :
dónde es el soporte de Iverson .
Identidades simples
Algunas identidades simples incluyen
Esto se debe a que dividir n elementos en n - 1 conjuntos necesariamente significa dividirlo en un conjunto de tamaño 2 y n - 2 conjuntos de tamaño 1. Por lo tanto, solo necesitamos elegir esos dos elementos;
y
Para ver esto, primero nota que hay 2 n ordenados pares 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, dado que 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 da identidades en el espíritu del ejemplo anterior.
Estos ejemplos se pueden resumir por la recurrencia
Fórmula explícita
Los números de Stirling del segundo tipo vienen dados por la fórmula explícita:
Esto se puede derivar usando inclusión-exclusión para contar el número de sobreyecciones de n a ky usando el hecho de que el número de tales sobreyecciones es.
Además, esta fórmula es un caso especial de la k- ésima diferencia directa del monomio evaluado en x = 0:
Debido a que los polinomios de Bernoulli pueden escribirse en términos de estas diferencias hacia adelante, se obtiene inmediatamente una relación en los números de Bernoulli :
Funciones generadoras
Para un entero fijo n , la función generadora ordinaria para los números de Stirling del segundo tipo es dado por
dónde son polinomios de Touchard . Si, en cambio, se suman los números de Stirling contra el factorial descendente, se pueden mostrar las siguientes identidades, entre otras:
y
Para un entero fijo k , los números de Stirling del segundo tipo tener una función generadora ordinaria racional
y tienen una función generadora exponencial dada por
Una función generadora bivariada mixta para los números de Stirling del segundo tipo es
Aproximación asintótica
Por valor fijo de el valor asintótico de los números de Stirling del segundo tipo como es dado por
Por otro lado, si (donde o denota la notación o pequeña ) entonces
- [12]
También existe una aproximación uniformemente válida: para todo k tal que 1 < k < n , uno tiene
dónde , y es la rama principal de la función W de Lambert . [13] El error relativo está limitado por aproximadamente.
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 n é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 n º 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 distribuida uniformemente de un conjunto finito de tamaño m . Entonces el n- ésimo momento de X es
Nota: El límite superior de la suma es m , no n .
En otras palabras, el n- é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 permutación aleatoria , 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 líneas.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
Números de Stirling asociados del segundo tipo
Un número de Stirling asociado a r del 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. [14] Se denota por y obedece a la relación de recurrencia
Los 2 números asociados (secuencia A008299 en el OEIS ) aparecen en otros lugares como "números de Ward" y como las magnitudes de los coeficientes de los polinomios de Mahler .
Números de Stirling reducidos del segundo tipo
Denote los n objetos a dividir por los enteros 1, 2, ..., n . Defina los números de Stirling reducidos del segundo tipo, denotados, para ser el número de formas de dividir los enteros 1, 2, ..., n en k subconjuntos no vacíos de modo que todos los elementos de cada subconjunto tengan una distancia por pares 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"). [15] Observe (tanto por definición como por fórmula de reducción) que, los conocidos números de Stirling del segundo tipo.
Ver también
- Número de campana : el número de particiones de un conjunto con n miembros
- Números de Stirling del primer tipo
- Polinomios de Stirling
- Doce veces
- Materiales de aprendizaje relacionados con triángulos numéricos relacionados con particiones en Wikiversity
Referencias
- ^ Ronald L. Graham, Donald E. Knuth, Oren Patashnik (1988) Matemáticas concretas , Addison-Wesley, Reading MA. ISBN 0-201-14236-8 , pág. 244.
- ^ "Número de Stirling del segundo tipo" .
- ^ Confusamente, la notación que usan los combinatorios parafactoriales descendentes coincide con la notación usada en funciones especiales parafactoriales ascendentes ; consulte el símbolo de Pochhammer .
- ^ Transformación de series por una variante de los números de Stirling, Imanuel Marx, The American Mathematical Monthly 69 , # 6 (junio-julio de 1962), págs. 530-532, JSTOR 2311194 .
- ↑ Antonio Salmeri, Introduzione alla teoria dei coefficienti fattoriali, Giornale di Matematiche di Battaglini 90 (1962), págs. 44–54.
- ^ a b Knuth, DE (1992), "Two notes on notation", Amer. Matemáticas. Mensualmente , 99 (5): 403–422, arXiv : math / 9205211 , Bibcode : 1992math ...... 5211K , doi : 10.2307 / 2325085 , JSTOR 2325085
- ^ Donald E. Knuth, Algoritmos fundamentales , Lectura, Mass .: Addison-Wesley, 1968.
- ^ p. 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), " Arreglos de Riordan y sumas combinatorias" (PDF) , Matemáticas discretas , 132 (1-3): 267-290, doi : 10.1016 / 0012-365X (92) 00570-H , MR 1297386
- ^ a b Rennie, BC; Dobson, AJ (1969). "Sobre 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.
- ^ NM Temme, Estimaciones asintóticas de números de Stirling, ESTUDIOS EN MATEMÁTICAS APLICADAS 89: 233-243 (1993), Elsevier Science Publishing.
- ^ L. Comtet, Combinatoria avanzada , Reidel, 1974, p. 222.
- ^ A. Mohr y TD Porter, Aplicaciones de polinomios cromáticos que involucran números de Stirling , Revista de matemáticas combinatorias y computación combinatoria 70 (2009), 57-64.
- Boyadzhiev, Khristo (2012). "Encuentros cercanos con los números de Stirling del segundo tipo". Revista de Matemáticas . 85 (4): 252–266. arXiv : 1806.09468 . doi : 10.4169 / math.mag.85.4.252 ..
- "Números de Stirling del segundo tipo, S (n, k)" . PlanetMath ..
- Weisstein, Eric W. "Número de Stirling del segundo tipo" . MathWorld .
- Calculadora para números de Stirling del segundo tipo
- Establecer particiones: números de Stirling
- Jack van der Elsen (2005). Transformaciones en blanco y negro . Maastricht. ISBN 90-423-0263-1.