En combinatoria , el número euleriano A ( n , m ) es el número de permutaciones de los números 1 an en el que exactamente m elementos son mayores que el elemento anterior (permutaciones con m "ascensos"). Son los coeficientes de los polinomios eulerianos :
Los polinomios eulerianos están definidos por la función generadora exponencial
Los polinomios eulerianos se pueden calcular mediante la recurrencia
Una forma equivalente de escribir esta definición es establecer los polinomios eulerianos inductivamente por
Otras notaciones para A ( n , m ) son E ( n , m ) y.
Historia
En 1755 Leonhard Euler investigó en su libro Institutiones calculi differentialis polinomios α 1 ( x ) = 1 , α 2 ( x ) = x + 1 , α 3 ( x ) = x 2 + 4 x + 1 , etc. (ver el facsímil ). Estos polinomios son una forma desplazada de lo que ahora se llama polinomios eulerianos A n ( x ).
Propiedades básicas
Para un valor dado de n > 0, el índice m en A ( n , m ) puede tomar valores de 0 a n - 1. Para n fijo hay una única permutación que tiene 0 ascensos: ( n , n - 1, n - 2, ..., 1). También hay una única permutación que tiene n - 1 ascensos; esta es la permutación ascendente (1, 2, 3, ..., n ). Por lo tanto, A ( n , 0) y A ( n , n - 1) son 1 para todos los valores de n .
Invertir una permutación con m ascensos crea otra permutación en la que hay n - m - 1 ascensos. Por lo tanto A ( n , m ) = A ( n , n - m - 1).
Los valores de A ( n , m ) puede calcularse "a mano" para valores pequeños de n y m . Por ejemplo
norte metro Permutaciones A ( n , m ) 1 0 (1) A (1,0) = 1 2 0 (2, 1) A (2,0) = 1 1 (1, 2 ) A (2,1) = 1 3 0 (3, 2, 1) A (3,0) = 1 1 (1, 3 , 2) (2, 1, 3 ) (2, 3 , 1) (3, 1, 2 ) A (3,1) = 4 2 (1, 2 , 3 ) A (3,2) = 1
Para valores más grandes de n , A ( n , m ) se puede calcular usando la fórmula recursiva
Por ejemplo
Los valores de A ( n , m ) (secuencia A008292 en la OEIS ) para 0 ≤ n ≤ 9 son:
- metronorte
0 1 2 3 4 5 6 7 8 1 1 2 1 1 3 1 4 1 4 1 11 11 1 5 1 26 66 26 1 6 1 57 302 302 57 1 7 1 120 1191 2416 1191 120 1 8 1 247 4293 15619 15619 4293 247 1 9 1 502 14608 88234 156190 88234 14608 502 1
La matriz triangular anterior se llama triángulo de Euler o triángulo de Euler , y comparte algunas características comunes con el triángulo de Pascal . La suma de la fila n es el factorial n !.
Fórmula explícita
Una fórmula explícita para A ( n , m ) es [1]
Se puede ver en esta fórmula, así como en la interpretación combinatoria, que por , así que eso es un polinomio de grado por .
Propiedades de suma
De la definición combinatoria se desprende claramente que la suma de los números eulerianos para un valor fijo de n es el número total de permutaciones de los números 1 an , por lo que
La suma alterna de los números eulerianos para un valor fijo de n está relacionada con el número de Bernoulli B n +1
Otras propiedades de suma de los números eulerianos son:
donde B n es el n- ésimo número de Bernoulli.
Identidades
Los números eulerianos están involucrados en la función generadora de la secuencia de n- ésimas potencias:
por . Esto supone que 0 0 = 0 y A (0,0) = 1 (ya que hay una permutación de ningún elemento y no tiene ascensos).
La identidad de Worpitzky [2] expresa x n como la combinación lineal de números eulerianos con coeficientes binomiales :
De la identidad de Worpitzky se desprende que
Otra identidad interesante es
El numerador del lado derecho es el polinomio euleriano.
Para una función fija que es integrable en tenemos la fórmula integral [3]
Números eulerianos de segundo orden
Las permutaciones de la multiset {1, 1, 2, 2, ···, n , n } que tienen la propiedad de que para cada k , todos los números que aparecen entre las dos apariciones de k en la permutación son mayores que k se cuentan por el número factorial doble (2 n −1) !!. El número euleriano de segundo orden, denotado, cuenta el número de todas esas permutaciones que tienen exactamente m ascensos. Por ejemplo, para n = 3 hay 15 de tales permutaciones, 1 sin ascensos, 8 con un solo ascenso y 6 con dos ascensos:
- 332211,
- 221133, 221331, 223311, 233211, 113322, 133221, 331122, 331221,
- 112233, 122133, 112332, 123321, 133122, 122331.
Los números eulerianos de segundo orden satisfacen la relación de recurrencia, que se sigue directamente de la definición anterior:
con condición inicial para n = 0, expresada en notación de corchetes Iverson :
En consecuencia, el polinomio euleriano de segundo orden, aquí denotado P n (no existe una notación estándar para ellos) son
y las relaciones de recurrencia anteriores se traducen en una relación de recurrencia para la secuencia P n ( x ):
con condición inicial
La última recurrencia se puede escribir de una forma más compacta por medio de un factor integrador:
para que la función racional
satisface una recurrencia autónoma simple:
de donde se obtienen los polinomios eulerianos de segundo orden como P n ( x ) = (1− x ) 2 n u n ( x ), y los números eulerianos de segundo orden como sus coeficientes.
A continuación se muestran algunos valores de los números eulerianos de segundo orden:
- metronorte
0 1 2 3 4 5 6 7 8 1 1 2 1 2 3 1 8 6 4 1 22 58 24 5 1 52 328 444 120 6 1 114 1452 4400 3708 720 7 1 240 5610 32120 58140 33984 5040 8 1 494 19950 195800 644020 785304 341136 40320 9 1 1004 67260 1062500 5765500 12440064 11026296 3733920 362880
La suma de la n -ésima fila, que también es el valor P n (1), es (2 n - 1) !!.
La indexación de los números eulerianos de segundo orden tiene tres variantes : (secuencia A008517 en la OEIS ) siguiendo a Riordan y Comtet, (secuencia A201637 en la OEIS ) siguiendo a Graham, Knuth y Patashnik y (secuencia A340556 en la OEIS ), ampliando la definición de Gessel y Stanley.
Referencias
- Eulerus, Leonardus [Leonhard Euler] (1755). Institutiones calculi differentialis cum eius usu in analysi finitorum ac doctrina serierum [Fundamentos del cálculo diferencial, con aplicaciones al análisis finito y series] . Academia imperialis scientiarum Petropolitana; Berolini: Officina Michaelis.
- Carlitz, L. (1959). "Números eulerianos y polinomios". Matemáticas. Mag . 32 (5): 247–260. doi : 10.2307 / 3029225 . JSTOR 3029225 .
- Gould, HW (1978). "Evaluación de sumas de potencias convolucionadas utilizando números de Stirling y Eulerianos" . Mentira. Quart . 16 (6): 488–497.
- Desarmenien, Jacques; Foata, Dominique (1992). "Los números eulerianos firmados". Matemáticas discretas . 99 (1-3): 49-58. doi : 10.1016 / 0012-365X (92) 90364-L .
- Lesieur, Leonce; Nicolas, Jean-Louis (1992). "Sobre los números eulerianos M = max (A (n, k))". Europ. J. Combinat . 13 (5): 379–399. doi : 10.1016 / S0195-6698 (05) 80018-6 .
- Butzer, PL; Hauss, M. (1993). "Números eulerianos con parámetros de orden fraccionario" . Aequationes Mathematicae . 46 (1-2): 119-142. doi : 10.1007 / bf01834003 . S2CID 121868847 .
- Koutras, MV (1994). "Números eulerianos asociados a secuencias de polinomios" . Mentira. Quart . 32 (1): 44.
- Graham; Knuth; Patashnik (1994). Matemáticas concretas : una base para la informática (2ª ed.). Addison-Wesley. págs. 267-272.
- Hsu, Leetsch C .; Jau-Shyong Shiue, Peter (1999). "Sobre ciertos problemas de suma y generalizaciones de polinomios y números eulerianos". Matemáticas discretas . 204 (1–3): 237–247. doi : 10.1016 / S0012-365X (98) 00379-3 .
- Boyadzhiev, Khristo N. (2007). "Funciones de Apostol-Bernoulli, polinomios derivados y polinomios eulerianos". arXiv : 0710.1124 [ matemáticas.CA ].
- Petersen, T. Kyle (2015). Números eulerianos . Birkhäuser Textos avanzados Basler Lehrbücher. Birkhäuser. págs. 3-18. doi : 10.1007 / 978-1-4939-3091-3_1 . ISBN 978-1-4939-3090-6.
Citas
- ↑ (L. Comtet 1974, p. 243)
- ^ Worpitzky, J. (1883). "Studien über die Bernoullischen und Eulerschen Zahlen" . Journal für die reine und angewandte Mathematik . 94 : 203–232.
- ^ Ejercicio 6.65 en Matemáticas concretas de Graham, Knuth y Patashnik.
enlaces externos
- Polinomios eulerianos en OEIS Wiki.
- "Números eulerianos" . MathPages.com .
- Weisstein, Eric W. "Número euleriano" . MathWorld .
- Weisstein, Eric W. "Triángulo numérico de Euler" . MathWorld .
- Weisstein, Eric W. "Identidad de Worpitzky" . MathWorld .
- Weisstein, Eric W. "Triángulo euleriano de segundo orden" . MathWorld .
- Matriz de Euler (rowindexes generalizados, suma divergente)