número euleriano

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

Leonhard Euler los investigó, junto con los polinomios asociados , en su libro de 1755, Institutiones calculi differentialis . ^{[ 1 ] [ 2 ]}

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

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

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

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

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

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

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

• Para fijo${\textstyle n}$Existe una única permutación que tiene 0 ascensos:${\textstyle (n,n-1,n-2,\ldots ,1)}$De hecho, como${\displaystyle {\tbinom {n}{0}}=1}$a pesar de${\displaystyle n}$,${\textstyle A(n,0)=1}$. Esto incluye formalmente la colección vacía de números,${\textstyle n=0}$. Y entonces${\textstyle A_{0}(t)=A_{1}(t)=1}$.
• Para${\textstyle k=1}$La fórmula explícita implica${\estilo de texto A(n,1)=2^{n}-(n+1)}$, una secuencia en${\displaystyle n}$que se lee${\estilo de texto 0,0,1,4,11,26,57,\puntos }$.
• Invertir completamente una permutación con${\textstyle k}$Los ascensos crean otra permutación en la que hay${\textstyle nk-1}$ascensos. Por lo tanto${\textstyle A(n,k)=A(n,nk-1)}$. Por lo tanto, también hay una única permutación que tiene${\textstyle n-1}$ascensos, es decir, la permutación ascendente${\textstyle (1,2,\ldots ,n)}$. Así también${\textstyle A(n,n-1)}$igual${\displaystyle 1}$.
• Dado que una permutación de los números${\displaystyle 1}$a${\displaystyle n}$que tiene${\displaystyle k}$Los ascensos deben tener${\displaystyle n-1-k}$descensos, la simetría${\textstyle A(n,k)=A(n,nk-1)}$muestra que${\textstyle A(n,k)}$también cuenta el número de permutaciones con${\displaystyle k}$descensos .
• Para${\textstyle k\geq n>0}$, los valores son formalmente cero, lo que significa que muchas sumas sobre${\textstyle k}$se puede escribir con un índice superior solo hasta${\textstyle n-1}$También significa que los polinomios${\displaystyle A_{n}(t)}$son realmente de grado${\textstyle n-1}$para${\textstyle n>0}$.

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

Para valores mayores de${\textstyle n}$,${\textstyle A(n,k)}$También se puede calcular utilizando la fórmula recursiva ^{[ 4 ].}

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

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

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

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.}$

Asimismo, los polinomios eulerianos pueden calcularse 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.}$

Para cualquier partición de un conjunto finito en subconjuntos disjuntos , la suma de las cardinalidades de las partes es igual a la cardinalidad del conjunto completo. Dado que hay${\displaystyle n!}$(el factorial de${\displaystyle n}$) permutaciones de tamaño${\displaystyle n}$y los números eulerianos dan las cardinalidades de los subconjuntos de estas permutaciones con un número fijo de descensos, se deduce que $${\displaystyle \sum _{k=0}^{n}A(n,k)=n!\,.}$$ (El sumando${\displaystyle k=n}$es 0 para${\displaystyle n>0}$pero se incluye para dar la suma correcta${\displaystyle A(0,0)=0!}$cuando${\displaystyle n=0}$.) De forma mucho más general, para una función fija${\displaystyle f\colon \mathbb {R} \rightarrow \mathbb {C} }$integrable en el intervalo${\displaystyle [0,n]}$, se cumple la siguiente identidad: ^{[ 5 ]}

${\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)dx_{1}\cdots dx_{n}.}$

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

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

De esto se deduce que

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

Esta identidad recibe su nombre de Julius Worpitzky, quien la descubrió en la década de 1880; ^{[ 6 ]} originalmente había sido descubierta algo antes por Li Shanlan en su obra de 1867, Duò Jī Bǐ Lèi . ^{[ 7 ] [ 8 ]}

Los números eulerianos aparecen como coeficientes del polilogaritmo para entradas enteras negativas:$${\displaystyle \operatorname {Li} _{-n}(z)={1 \over (1-z)^{n+1}}\sum _{k=0}^{n-1}A(n,k)z^{n-k}\qquad (n=1,2,3,\ldots ).}$$

Los números eulerianos tienen dos importantes interpretaciones geométricas que involucran politopos convexos .

En primer lugar, la identidad

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

implica que los números eulerianos forman el${\displaystyle h^{\ast }}$-vector del estándar${\displaystyle n}$hipercubo de dimensión , que es la envoltura convexa de todos${\displaystyle 0,1}$-vectores en${\displaystyle \mathbb {R} ^{n}}$.

En segundo lugar, la identidad $${\displaystyle A_{n}(t)=\sum _{k=0}^{n}\left\{{n \atop k}\right\}k!(t-1)^{n-k}}$$ significa que los números eulerianos también forman el${\displaystyle h}$-vector del politopo simple que es dual al${\displaystyle n}$permutoedro de dimensión , que es la envoltura convexa de todas las permutaciones del vector${\displaystyle (1,2,\ldots ,n)}$en${\displaystyle \mathbb {R} ^{n}}$.

El grupo hiperoctaédrico de orden${\displaystyle n}$es el grupo de todas las permutaciones con signo de los números${\displaystyle 1}$a${\displaystyle n}$, es decir, biyecciones${\displaystyle \pi }$del conjunto${\displaystyle \{-n,-n+1,\ldots ,-1,1,2,\ldots ,n\}}$a sí mismo con la propiedad que${\displaystyle \pi (-i)=-\pi (i)}$a pesar de${\displaystyle i}$. Al igual que el grupo simétrico de orden${\displaystyle n}$(es decir, el grupo de todas las permutaciones de los números${\displaystyle 1}$a${\displaystyle n}$) es el grupo Coxeter de tipo${\displaystyle A_{n-1}}$, el grupo hiperoctaédrico de orden${\displaystyle n}$es el grupo Coxeter de tipo${\displaystyle B_{n}}$.

Dado un elemento${\displaystyle \pi }$del grupo hiperoctaédrico de orden${\displaystyle n}$un descenso de tipo B de${\displaystyle \pi }$es un índice${\displaystyle i\in \{0,1,\ldots ,n-1\}}$para qué${\displaystyle \pi (i)>\pi (i-1)}$, con la convención de que${\displaystyle \pi (0)=0}$El número euleriano de tipo B${\displaystyle B(n,k)}$es el número de elementos del grupo hiperoctaédrico de orden${\displaystyle n}$con exactamente${\displaystyle k}$descensos. ^{[ 10 ]} Se dan mediante la siguiente fórmula: ^{[ 11 ]}

${\displaystyle B(n,k)=\sum _{i=1}^{k}(-1)^{k-i}{\binom {n}{k-i}}(2i-1)^{n-1}.}$

La tabla de${\displaystyle B(n,k)}$(secuencia A060187 en el OEIS ) es

Los polinomios correspondientes${\displaystyle M_{n}(x)=\sum _{k=0}^{n}B(n,k)x^{k}}$Se denominan polinomios eulerianos de punto medio debido a su uso en la interpolación y la teoría de splines; véase Schoenberg. ^{[ 12 ]}

Los números y polinomios eulerianos de tipo B satisfacen muchas identidades similares y tienen muchas propiedades similares a las de los números y polinomios eulerianos de tipo A, es decir, los habituales. Por ejemplo, para cualquier${\displaystyle n\geq 1}$,

${\displaystyle \sum _{i=0}^{\infty }(2i+1)^{n}x^{i}={\frac {M_{n}(x)}{(1-x)^{n+1}}}.}$

Y los números eulerianos de tipo B dan el vector h del politopo simple dual al permutoedro de tipo B.

De hecho, se pueden definir números eulerianos para cualquier grupo de Coxeter finito con propiedades análogas. ^{[ 13 ]}

Las permutaciones del multiconjunto${\textstyle \{1,1,2,2,\ldots ,n,n\}}$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 doble factorial .${\textstyle (2n-1)!!}$Estas se denominan permutaciones de Stirling .

El número euleriano de segundo orden, denotado${\textstyle \left\langle \!\left\langle {n \atop m}\right\rangle \!\right\rangle }$, cuenta el número de todas las permutaciones de Stirling que tienen exactamente m ascensos. Por ejemplo, para n = 3 hay 15 de esas 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 deduce 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].}$

Correspondientemente, 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${\displaystyle P_{0}(x)=1}$Esta última recurrencia puede escribirse de forma algo más compacta mediante un factor integrante :

${\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${\textstyle P_{n}(x)=(1-x)^{2n}u_{n}(x)}$y los números eulerianos de segundo orden como sus coeficientes.

Los polinomios eulerianos de segundo orden satisfacen una identidad análoga a la identidad

${\displaystyle \sum _{i=1}^{\infty }i^{n}x^{i}={\frac {xA_{n}(x)}{(1-x)^{n+1}}}}$

satisfechos por los polinomios eulerianos usuales. Específicamente, como demostraron Gessel y Stanley, ^{[ 14 ]} satisfacen la identidad

${\displaystyle \sum _{m=0}^{\infty }\left\{{n+m \atop m}\right\}x^{m}={\frac {xP_{n}(x)}{(1-x)^{2n+1}}}}$

donde de nuevo el${\displaystyle \left\{{n \atop k}\right\}}$denotamos los números de Stirling de segunda especie . (Esta apariencia de los números de Stirling explica la terminología " permutaciones de Stirling ").

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

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

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

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

• 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 . 
• Comtet, Louis (1974). Combinatoria avanzada: El arte de las expansiones finitas e infinitas (PDF) . Dordrecht: Springer Netherlands. ISBN 978-94-010-2198-2.
• Gould, HW (1978). "Evaluación de sumas de potencias convolucionadas usando números de Stirling y Eulerianos" . Fib. Quart . 16 (6): 488– 497. doi : 10.1080/00150517.1978.12430271 .
• Desarmenien, Jacques; Foata, Dominique (1992). "Los números eulerianos con signo" . Discrete Math . 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" . Aecuaciones Mathematicae . 46 ( 1– 2): 119– 142. doi : 10.1007/bf01834003 . S2CID 121868847 . 
• Koutras, MV (1994). "Números eulerianos asociados con secuencias de polinomios" . Fib. Quart . 32 (1): 44– 57. doi : 10.1080/00150517.1994.12429255 .
• Graham, Ronald ; Knuth, Donald ; Patashnik, Oren (1994). Matemáticas concretas : Fundamentos 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" . Discrete Math . 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". 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.{{cite book}}: Falta o está vacío |title=( ayuda )

• Polinomios eulerianos en la wiki de OEIS .
• "Números eulerianos" . MathPages.com .
• Weisstein, Eric W. "Número euleriano" . MathWorld .
• 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)