En matemáticas , los números de Stirling surgen en una variedad de problemas analíticos y combinatorios . Uno de los primeros resultados que llevaron al descubrimiento de los números de Stirling se debió a Masanobu Saka en 1782. [1] James Stirling en su libro ( Methodus Differentials ), los había encontrado en un entorno puramente algebraico en 1730. [2] A pesar de Stirling's Descubrimiento anterior, Saka ha recibido el crédito de asociar un significado combinatorio a estos números, que ahora llevan el nombre de James Stirling. [2] Dos conjuntos diferentes de números llevan este nombre: los números de Stirling del primer tipo y elNúmeros de Stirling del segundo tipo . Además, los números de Lah a veces se denominan números de Stirling del tercer tipo. Cada tipo se detalla en su respectivo artículo, este sirve como descripción de las relaciones entre ellos.
Una propiedad común de los tres tipos es que describen coeficientes que relacionan tres secuencias diferentes de polinomios que surgen con frecuencia en la combinatoria. Además, los tres pueden definirse como el número de particiones de n elementos en k subconjuntos no vacíos, con diferentes formas de contar los ordenamientos dentro de cada subconjunto.
Notación
Se utilizan varias notaciones diferentes para los números de Stirling. La notación común para los números Stirling ordinarios (con signo) del primer tipo es:
Para los números de Stirling sin signo del primer tipo , que cuentan el número de permutaciones de n elementos con k ciclos disjuntos , es:
Y para los números de Stirling del segundo tipo , que cuentan el número de formas de dividir un conjunto de n elementos en k subconjuntos no vacíos: [3]
Por ejemplo, la suma es el número de todas las permutaciones, mientras que la suma es el n º número de Bell .
Abramowitz y Stegun usan una S mayúscula y una S negra , respectivamente, para el primer y segundo tipo de número de Stirling. La notación de corchetes y llaves, en analogía con los coeficientes binomiales , fue introducida en 1935 por Jovan Karamata y promovida más tarde por Donald Knuth . (La notación entre corchetes entra en conflicto con una notación común para los coeficientes gaussianos . [4] ) La motivación matemática para este tipo de notación, así como las fórmulas numéricas de Stirling adicionales, se pueden encontrar en la página de números de Stirling y funciones generadoras exponenciales .
Expansiones de factoriales descendentes y ascendentes
Los números de Stirling expresan coeficientes en expansiones de factoriales ascendentes y descendentes (también conocido como el símbolo de Pochhammer) como polinomios.
Es decir, el factorial descendente , definido como, es un polinomio en x de grado n cuya expansión es
con números de Stirling (con signo) del primer tipo como coeficientes.
Tenga en cuenta que ( x ) 0 = 1 porque es un producto vacío . Los combinatorios a veces también usan la notación para el factorial descendente, y para el factorial ascendente. [5] (De manera confusa, el símbolo de martillo perforador que muchos usan para factoriales descendentes se usa en funciones especiales para factoriales ascendentes ).
De manera similar, el factorial ascendente , definido como, es un polinomio en x de grado n cuya expansión es
con números de Stirling sin signo del primer tipo como coeficientes. Una de estas expansiones puede derivarse de la otra observando que.
Los números de Stirling del segundo tipo expresan las relaciones inversas:
y
Como cambio de coeficientes de base
Considerando el conjunto de polinomios en la variable (indeterminada) x como un espacio vectorial, cada una de las tres secuencias
es una base . Es decir, cada polinomio en x se puede escribir como una suma para algunos coeficientes únicos (de manera similar para las otras dos bases). Las relaciones anteriores expresan entonces el cambio de base entre ellas, como se resume en el siguiente diagrama conmutativo :
Los coeficientes de los dos cambios inferiores se describen mediante los números Lah a continuación. Dado que los coeficientes en cualquier base son únicos, se pueden definir los números de Stirling de esta manera, como los coeficientes que expresan polinomios de una base en términos de otra, es decir, los números únicos que relacionan con factoriales descendentes y ascendentes como arriba.
Los factoriales descendentes definen, hasta escalar, los mismos polinomios que los coeficientes binomiales :. Los cambios entre la base estándar y la base se describen así mediante fórmulas similares:
- y .
Como matrices inversas
Los números de Stirling del primer y segundo tipo pueden considerarse inversos entre sí:
y
dónde es el delta de Kronecker . Estas dos relaciones pueden entenderse como relaciones de matriz inversa. Es decir, sea s la matriz triangular inferior de los números de Stirling del primer tipo, cuyos elementos de la matrizLa inversa de esta matriz es S , la matriz triangular inferior de los números de Stirling del segundo tipo, cuyas entradas son Simbólicamente, esto está escrito
Aunque s y S son infinitos, por lo que el cálculo de una entrada de producto implica una suma infinita, el trabajo multiplicaciones de matrices debido a que estas matrices son más bajos triangular, de modo que sólo un número finito de términos de la suma son distintos de cero.
Ejemplo
Expresar un polinomio en base a factoriales descendentes es útil para calcular sumas del polinomio evaluado en números enteros consecutivos. De hecho, la suma de un factorial descendente se expresa simplemente como otro factorial descendente (para k ≠ −1)
Esto es análogo a la integral , aunque la suma debe estar sobre enteros i estrictamente menores que n .
Por ejemplo, la suma de las cuartas potencias de los números enteros hasta n (esta vez con n incluido) es:
Aquí, los números de Stirling se pueden calcular a partir de su definición como el número de particiones de 4 elementos en k subconjuntos no vacíos sin etiquetar.
En contraste, la suma en la base estándar viene dada por la fórmula de Faulhaber , que en general es más compleja.
Números de lah
Los números de Lah a veces se denominan números de Stirling del tercer tipo. [6] Por convención, y Si o .
Estos números son coeficientes que expresan factoriales descendentes en términos de factoriales ascendentes y viceversa:
- y
Como arriba, esto significa que expresan el cambio de base entre las bases. y , completando el diagrama. En particular, una fórmula es la inversa de la otra, así:
Del mismo modo, componiendo, por ejemplo, el cambio de base de a con el cambio de base de a da el cambio de base directamente desde a :
En términos de matrices, si denota la matriz con entradas y denota la matriz con entradas , entonces uno es el inverso del otro: . De manera similar, al componer la matriz de números de Stirling sin signo del primer tipo con la matriz de números de Stirling del segundo tipo se obtienen los números de Lah:.
Los números se puede definir como el número de particiones de n elementos en k subconjuntos no vacíos sin etiquetar, cada uno de los cuales está desordenado, ordenado cíclicamente u ordenado linealmente, respectivamente. En particular, esto implica las siguientes desigualdades:
Fórmulas simétricas
Abramowitz y Stegun dan las siguientes fórmulas simétricas que relacionan los números de Stirling del primer y segundo tipo. [7]
y
Números de Stirling con valores integrales negativos
Los números de Stirling se pueden extender a valores integrales negativos, pero no todos los autores lo hacen de la misma manera. [8] [9] [10] Independientemente del enfoque adoptado, vale la pena señalar que los números de Stirling de primer y segundo tipo están conectados por las relaciones:
cuando n y k son números enteros no negativos. Entonces tenemos la siguiente tabla para:
k norte | −1 | −2 | −3 | −4 | −5 |
---|---|---|---|---|---|
−1 | 1 | 1 | 1 | 1 | 1 |
−2 | 0 | 1 | 3 | 7 | 15 |
−3 | 0 | 0 | 1 | 6 | 25 |
−4 | 0 | 0 | 0 | 1 | 10 |
−5 | 0 | 0 | 0 | 0 | 1 |
Donald Knuth [10] definió los números de Stirling más generales extendiendo una relación de recurrencia a todos los números enteros. En este enfoque, y son cero si n es negativo y k no es negativo, o si n es no negativo y k es negativo, por lo que tenemos, para cualquier número entero n y k ,
- .
Por otro lado, para los enteros positivos n y k , David Branson [9] definió, , , y (pero no o ). En este enfoque, se tiene la siguiente extensión de la relación de recurrencia de los números de Stirling del primer tipo:
- ,
Por ejemplo, . Esto conduce a la siguiente tabla de valores de.
k norte | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
−1 | 1 | 1 | 1 | 1 | 1 |
−2 | |||||
−3 | |||||
−4 | |||||
−5 |
En este caso dónde es un número de Bell , por lo que uno puede definir los números de Bell negativos por. Por ejemplo, esto produce.
Ver también
- Polinomios de campana
- Número catalán
- Ciclos y puntos fijos
- Lah número
- Símbolo de martillo
- Secuencia polinomial
- Transformación de Stirling
- Polinomios de Touchard
- Permutación de Stirling
Citas
- ^ Mansour y Schork 2015 , p. 4.
- ↑ a b Mansour y Schork , 2015 , p. 5.
- ^ Ronald L. Graham, Donald E. Knuth, Oren Patashnik (1988) Matemáticas concretas , Addison-Wesley, Reading MA. ISBN 0-201-14236-8 , pág. 244.
- ^ Donald Knuth
- ^ Aigner, Martin (2007). "Sección 1.2 - Subconjuntos y coeficientes binomiales". Un curso de enumeración . Saltador. págs. 561 . ISBN 978-3-540-39032-9.
- ^ Sándor, Jozsef; Crstici, Borislav (2004). Manual de teoría de números II . Editores académicos de Kluwer . pag. 464. ISBN 9781402025464.
- ^ Goldberg, K .; Newman, M; Haynsworth, E. (1972), "Números Stirling del primer tipo, números Stirling del segundo tipo", en Abramowitz, Milton; Stegun, Irene A. (eds.), Manual de funciones matemáticas con fórmulas, gráficos y tablas matemáticas, décima impresión , Nueva York: Dover, págs. 824–825
- ^ Loeb, Daniel E. (1992) [Recibido el 3 de noviembre de 1989]. "Una generalización de los números de Stirling". Matemáticas discretas . 103 (3): 259–269. doi : 10.1016 / 0012-365X (92) 90318-A .
- ^ a b Branson, David (agosto de 1994). "Una extensión de los números de Stirling" (PDF) . El Fibonacci Quarterly . Consultado el 6 de diciembre de 2017 .
- ^ a b D.E. Knuth, 1992.
Referencias
- Rosen, Kenneth H., ed. (2018), Manual de matemáticas discretas y combinatorias , CRC Press, ISBN 978-1-5848-8780-5
- Mansour, Toufik; Schork, Mathias (2015), relaciones de conmutación, ordenamiento normal y números de Stirling , CRC Press, ISBN 978-1-4665-7989-7
Otras lecturas
- Adamchik, Victor (1997). "Sobre números de Stirling y sumas de Euler" (PDF) . Revista de Matemática Computacional y Aplicada . 79 : 119-130. doi : 10.1016 / s0377-0427 (96) 00167-7 .
- Benjamin, Arthur T .; Preston, Gregory O .; Quinn, Jennifer J. (2002). "Un encuentro de Stirling con números armónicos" (PDF) . Revista de Matemáticas . 75 (2): 95–103. CiteSeerX 10.1.1.383.722 . doi : 10.2307 / 3219141 . JSTOR 3219141 .
- Boyadzhiev, Khristo N. (2012). "Encuentros cercanos con los números de Stirling del segundo tipo" (PDF) . Revista de Matemáticas . 85 (4): 252–266. arXiv : 1806.09468 . doi : 10.4169 / math.mag.85.4.252 .
- Comtet, Louis (1970). "Valeur de s ( n , k ) " . Analizar Combinatoire, Tome Second (en francés): 51.
- Comtet, Louis (1974). Combinatoria avanzada: el arte de las expansiones finitas e infinitas . Dordrecht-Holland / Boston-USA: Reidel Publishing Company.
- Hsien-Kuei Hwang (1995). "Expansiones asintóticas para los números de Stirling del primer tipo" . Revista de Teoría Combinatoria, serie A . 71 (2): 343–351. doi : 10.1016 / 0097-3165 (95) 90010-1 .
- Knuth, DE (1992), "Two notes on notation", Amer. Matemáticas. Mensual , 99 (5): 403–422, arXiv : math / 9205211 , doi : 10.2307 / 2325085 , JSTOR 2325085
- Miksa, Francis L. (enero de 1956). "Números de Stirling del primer tipo: 27 hojas reproducidas de un manuscrito mecanografiado depositado en el Archivo UMT". Tablas matemáticas y otras ayudas a la computación: revisiones y descripciones de tablas y libros . 10 (53): 37–38. JSTOR 2002617 .
- Miksa, Francis L. (1972) [1964]. "Análisis combinatorio, tabla 24.4, números de Stirling del segundo tipo" . En Abramowitz, Milton; Stegun, Irene A. (eds.). Manual de funciones matemáticas (con fórmulas, gráficos y tablas matemáticas) . 55. Departamento de Comercio de EE. UU., Oficina Nacional de Estándares, Matemáticas Aplicadas. pag. 835.
- Mitrinović, Dragoslav S. (1959). "Sur les nombres de Stirling de estreno espèce et les polynômes de Stirling" (PDF) . Publications de la Faculté d'Electrotechnique de l'Université de Belgrade, Série Mathématiques et Physique (en francés) (23): 1–20. ISSN 0522-8441 .
- O'Connor, John J .; Robertson, Edmund F. (septiembre de 1998). "James Stirling (1692-1770)" .
- Sixdeniers, JM; Penson, KA; Solomon, AI (2001). "Números extendidos de Bell y Stirling de la exponenciación hipergeométrica" (PDF) . Diario de secuencias de enteros . 4 : 01.1.4.
- Spivey, Michael Z. (2007). "Sumas combinatorias y diferencias finitas". Matemáticas discretas . 307 (24). págs. 3130–3146. doi : 10.1016 / j.disc.2007.03.052 .
- Sloane, N. J. A. (ed.). "Secuencia A008275 (números Stirling de primer tipo)" . La enciclopedia en línea de secuencias de enteros . Fundación OEIS.
- Sloane, N. J. A. (ed.). "Secuencia A008277 (números Stirling de segundo tipo)" . La enciclopedia en línea de secuencias de enteros . Fundación OEIS.