Número euleriano

Sucesión polinómica

En combinatoria , el número de Euler es el número de permutaciones de los números del 1 al 1 en las que exactamente dos elementos son mayores que el elemento anterior (permutaciones con "ascensos"). ${\textstyle A(n,k)}$ ${\textstyle n}$ ${\textstyle k}$ ${\textstyle k}$

Leonhard Euler los investigó y asoció polinomios en su libro de 1755 Institutiones calculi Differentialis .

Los polinomios que actualmente se conocen como polinomios eulerianos en la obra de Euler de 1755, Institutiones calculi differentiali, parte 2, pág. 485/6. Los coeficientes de estos polinomios se conocen como números eulerianos.

Otras notaciones para son y . ${\textstyle A(n,k)}$ ${\textstyle E(n,k)}$ ${\displaystyle \textstyle \left\langle {n \atop k}\right\rangle }$

Definición

Los polinomios eulerianos se definen mediante la función generadora exponencial ${\displaystyle A_{n}(t)}$

${\displaystyle \sum _{n=0}^{\infty }A_{n}(t)\,{\frac {x^{n}}{n!}}={\frac {t-1}{t-e^{(t-1)\,x}}}.}$

Los números eulerianos pueden definirse como los coeficientes de los polinomios eulerianos: ${\displaystyle A(n,k)}$

${\displaystyle A_{n}(t)=\sum _{k=0}^{n}A(n,k)\,t^{k}.}$

Una fórmula explícita para es ^[1] ${\textstyle A(n,k)}$

Un gráfico de los números eulerianos con el segundo argumento fijado en 5.

${\displaystyle A(n,k)=\sum _{i=0}^{k}(-1)^{i}{\binom {n+1}{i}}(k+1-i)^{n}.}$

Propiedades básicas

• Para fijo hay una única permutación que tiene 0 ascensos: . En efecto, como para todos los , . Esto incluye formalmente la colección vacía de números, . Y por lo tanto . ${\textstyle n}$ ${\textstyle (n,n-1,n-2,\ldots ,1)}$ ${\displaystyle {\tbinom {n}{0}}=1}$ ${\displaystyle n}$ ${\textstyle A(n,0)=1}$ ${\textstyle n=0}$ ${\textstyle A_{0}(t)=A_{1}(t)=1}$
• Porque la fórmula explícita implica , una secuencia que se lee . ${\textstyle k=1}$ ${\textstyle A(n,1)=2^{n}-(n+1)}$ ${\displaystyle n}$ ${\textstyle 0,0,1,4,11,26,57,\dots }$
• Al invertir por completo una permutación con ascensos se crea otra permutación en la que hay ascensos. Por lo tanto , . Por lo tanto, también hay una única permutación que tiene ascensos, a saber, la permutación ascendente . Por lo tanto, también es igual a . ${\textstyle k}$ ${\textstyle n-k-1}$ ${\textstyle A(n,k)=A(n,n-k-1)}$ ${\textstyle n-1}$ ${\textstyle (1,2,\ldots ,n)}$ ${\textstyle A(n,n-1)}$ ${\displaystyle 1}$
• Un límite superior generoso es . Entre los límites que acabamos de analizar, el valor excede . ${\textstyle A(n,k)\leq (k+1)^{n}\cdot (n+2)^{k}}$ ${\displaystyle 1}$
• Para , los valores son formalmente cero, lo que significa que muchas sumas sobre pueden escribirse con un índice superior solo hasta . También significa que los polinomios son realmente de grado para . ${\textstyle k\geq n>0}$ ${\textstyle k}$ ${\textstyle n-1}$ ${\displaystyle A_{n}(t)}$ ${\textstyle n-1}$ ${\textstyle n>0}$

La tabulación de los números en una matriz triangular se denomina triángulo de Euler o triángulo de Euler . Comparte algunas características comunes con el triángulo de Pascal . Los valores de (secuencia A008292 en la OEIS ) para son: ${\textstyle A(n,k)}$ ${\textstyle 0\leq n\leq 9}$

Cálculo

Para valores mayores de , también se puede calcular utilizando la fórmula recursiva ${\textstyle n}$ ${\textstyle A(n,k)}$

${\displaystyle A(n,k)=(n-k)\,A(n-1,k-1)+(k+1)\,A(n-1,k).}$

Esta fórmula puede motivarse a partir de la definición combinatoria y, por tanto, sirve como punto de partida natural para la teoría.

Para valores pequeños de y , los valores de se pueden calcular manualmente. Por ejemplo ${\textstyle n}$ ${\textstyle k}$ ${\textstyle A(n,k)}$

Aplicando la recurrencia a un ejemplo, podemos encontrar

${\displaystyle A(4,1)=(4-1)\,A(3,0)+(1+1)\,A(3,1)=3\cdot 1+2\cdot 4=11.}$

De la misma manera, los polinomios eulerianos se pueden calcular mediante la recurrencia

${\displaystyle A_{0}(t)=1,}$

${\displaystyle A_{n}(t)=A_{n-1}'(t)\cdot t\,(1-t)+A_{n-1}(t)\cdot (1+(n-1)\,t),{\text{ for }}n>1.}$

La segunda fórmula se puede expresar en forma inductiva,

${\displaystyle A_{n}(t)=\sum _{k=0}^{n-1}{\binom {n}{k}}A_{k}(t)\cdot (t-1)^{n-1-k},{\text{ for }}n>1.}$

Identidades

Para cualquier propiedad que divida un conjunto finito en un número finito de conjuntos más pequeños, la suma de las cardinalidades de los conjuntos más pequeños es igual a la cardinalidad del conjunto más grande. Los números eulerianos dividen las permutaciones de elementos, por lo que su suma es igual al factorial . Es decir ${\displaystyle n}$ ${\displaystyle n!}$

${\displaystyle \sum _{k=0}^{n-1}A(n,k)=n!,{\text{ for }}n>0.}$

así como . Para evitar conflictos con la convención de suma vacía , es conveniente simplemente enunciar los teoremas para solamente. ${\displaystyle A(0,0)=0!}$ ${\displaystyle n>0}$

De manera mucho más general, para una función fija integrable en el intervalo ^[2] ${\displaystyle f\colon \mathbb {R} \rightarrow \mathbb {C} }$ ${\displaystyle (0,n)}$

${\displaystyle \sum _{k=0}^{n-1}A(n,k)\,f(k)=n!\int _{0}^{1}\cdots \int _{0}^{1}f\left(\left\lfloor x_{1}+\cdots +x_{n}\right\rfloor \right){\mathrm {d} }x_{1}\cdots {\mathrm {d} }x_{n}}$

La identidad de Worpitzky ^[3] se expresa como la combinación lineal de números eulerianos con coeficientes binomiales : ${\textstyle x^{n}}$

${\displaystyle \sum _{k=0}^{n-1}A(n,k){\binom {x+k}{n}}=x^{n}.}$

De ello se deduce que

${\displaystyle \sum _{k=1}^{m}k^{n}=\sum _{k=0}^{n-1}A(n,k){\binom {m+k+1}{n+1}}.}$

Fórmulas que implican sumas alternadas

La suma alternada de los números eulerianos para un valor fijo de está relacionada con el número de Bernoulli ${\textstyle n}$ ${\textstyle B_{n+1}}$

${\displaystyle \sum _{k=0}^{n-1}(-1)^{k}A(n,k)=2^{n+1}(2^{n+1}-1){\frac {B_{n+1}}{n+1}},{\text{ for }}n>0.}$

Además,

${\displaystyle \sum _{k=0}^{n-1}(-1)^{k}{\frac {A(n,k)}{\binom {n-1}{k}}}=0,{\text{ for }}n>1}$

y

${\displaystyle \sum _{k=0}^{n-1}(-1)^{k}{\frac {A(n,k)}{\binom {n}{k}}}=(n+1)B_{n},{\text{ for }}n>1}$

Fórmulas que involucran polinomios

La propiedad de simetría implica:

${\displaystyle A_{n}(t)=t^{n-1}A_{n}(t^{-1})}$

Los números eulerianos intervienen en la función generadora de la secuencia de n- ^ésimas potencias:

${\displaystyle \sum _{i=1}^{\infty }i^{n}x^{i}={\frac {1}{(1-x)^{n+1}}}\sum _{k=0}^{n}A(n,k)\,x^{k+1}={\frac {x}{(1-x)^{n+1}}}A_{n}(x)}$

Una expresión explícita para los polinomios eulerianos es ^[4]

${\displaystyle A_{n}(t)=\sum _{k=0}^{n}\left\{{n \atop k}\right\}k!(t-1)^{n-k}}$

¿Dónde están los números de Stirling del segundo tipo ? ${\textstyle \left\{{n \atop k}\right\}}$

Números eulerianos de segundo orden

Las permutaciones del multiconjunto que tienen la propiedad de que para cada k , todos los números que aparecen entre las dos ocurrencias de k en la permutación son mayores que k se cuentan por el número factorial doble . El número euleriano de segundo orden, denotado , cuenta el número de todas las permutaciones de este tipo que tienen exactamente m ascensos. Por ejemplo, para n = 3 hay 15 permutaciones de este tipo, 1 sin ascensos, 8 con un solo ascenso y 6 con dos ascensos: ${\textstyle \{1,1,2,2,\ldots ,n,n\}}$ ${\textstyle (2n-1)!!}$ ${\displaystyle \scriptstyle \left\langle \!\left\langle {n \atop m}\right\rangle \!\right\rangle }$

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 desprende directamente de la definición anterior:

${\displaystyle \left\langle \!\!\left\langle {n \atop k}\right\rangle \!\!\right\rangle =(2n-k-1)\left\langle \!\!\left\langle {n-1 \atop k-1}\right\rangle \!\!\right\rangle +(k+1)\left\langle \!\!\left\langle {n-1 \atop k}\right\rangle \!\!\right\rangle ,}$

con condición inicial para n = 0, expresada en notación de corchetes de Iverson :

${\displaystyle \left\langle \!\!\left\langle {0 \atop k}\right\rangle \!\!\right\rangle =[k=0].}$

En consecuencia, los polinomios eulerianos de segundo orden, aquí denotados P _n (no existe una notación estándar para ellos) son

${\displaystyle P_{n}(x):=\sum _{k=0}^{n}\left\langle \!\!\left\langle {n \atop k}\right\rangle \!\!\right\rangle x^{k}}$

y las relaciones de recurrencia anteriores se traducen en una relación de recurrencia para la secuencia P _n ( x ):

${\displaystyle P_{n+1}(x)=(2nx+1)P_{n}(x)-x(x-1)P_{n}^{\prime }(x)}$

con condición inicial . La última recurrencia puede escribirse de una forma algo más compacta mediante un factor integrador: ${\displaystyle P_{0}(x)=1.}$

${\displaystyle (x-1)^{-2n-2}P_{n+1}(x)=\left(x\,(1-x)^{-2n-1}P_{n}(x)\right)^{\prime }}$

de modo que la función racional

${\displaystyle u_{n}(x):=(x-1)^{-2n}P_{n}(x)}$

satisface una recurrencia autónoma simple:

${\displaystyle u_{n+1}=\left({\frac {x}{1-x}}u_{n}\right)^{\prime },\quad u_{0}=1}$

De donde se obtienen los polinomios eulerianos de segundo orden como , y los números eulerianos de segundo orden como sus coeficientes. ${\textstyle P_{n}(x)=(1-x)^{2n}u_{n}(x)}$

La siguiente tabla muestra los primeros números eulerianos de segundo orden:

La suma de la fila n -ésima, que también es el valor , es . ${\textstyle P_{n}(1)}$ ${\textstyle (2n-1)!!}$

La indexación de los números eulerianos de segundo orden se presenta de tres formas:

• (secuencia A008517 en la OEIS ) siguiendo a Riordan y Comtet,
• (secuencia A201637 en la OEIS ) siguiendo a Graham, Knuth y Patashnik,
• (secuencia A340556 en la OEIS ), ampliando la definición de Gessel y Stanley.

Referencias

• Eulerus, Leonardus [Leonhard Euler] (1755). Institutiones calculi diferencialis cum eius usu in analysi finitorum ac doctrina serierum [Fundamentos del cálculo diferencial, con aplicaciones al análisis finito y a las series] . Academia imperialis scientiarum Petropolitana; Berolini: Officina Michaelis.
• Carlitz, L. (1959). "Números eulerianos y polinomios". Math. 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". Fib. Quart . 16 (6): 488–497.
• Desarmenien, Jacques; Foata, Dominique (1992). "Los números eulerianos con signo". Matemáticas discretas . 99 (1–3): 49–58. doi : 10.1016/0012-365X(92)90364-L .
• Lesieur, Leonce; Nicolás, Jean-Louis (1992). "Sobre los números eulerianos M = max (A (n, k))". Europa. 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". Fib. 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 [math.CA].
• Petersen, T. Kyle (2015). "Números eulerianos". 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

1. (L. Comtet 1974, pág. 243)
2. Ejercicio 6.65 de Matemáticas Concretas de Graham, Knuth y Patashnik.
3. Worpitzky, J. (1883). "Studien über die Bernoullischen und Eulerschen Zahlen". Journal für die reine und angewandte Mathematik . 94 : 203–232.
4. Qi, Feng; Guo, Bai-Ni (1 de agosto de 2017). "Fórmulas explícitas y relaciones de recurrencia para polinomios eulerianos de orden superior". Indagationes Mathematicae . 28 (4): 884–891. doi : 10.1016/j.indag.2017.06.010 . ISSN  0019-3577.

Enlaces externos

• Polinomios eulerianos en OEIS Wiki.
• "Números eulerianos". MathPages.com .
• Weisstein, Eric W. "Número euleriano". MundoMatemático .
• Weisstein, Eric W. "El triángulo numérico de Euler". MathWorld .
• Weisstein, Eric W. "La identidad de Worpitzky". MundoMatemático .
• Weisstein, Eric W. "Triángulo euleriano de segundo orden". MathWorld .
• Matriz de Euler (índices de fila generalizados, suma divergente)