Número euleriano

Modelo:Non confundir En combinatoria, o número euleriano $A(n,k)$ é o número de permutacións dos números 1 a $n$ no que exactamente $k$ elementos son maiores que o elemento anterior (permutacións con $k$ "ascendentes").

Leonhard Euler investigounos e tamén os seus polinomios asociados no seu libro de 1755 Institutiones calculi differentialis.

Os polinomios actualmente coñecidos como polinomios eulerianos no traballo de Euler de 1755, Institutiones calculi differentialis, parte 2, p. 485/6. Os coeficientes destes polinomios coñécense como números eulerianos.

Outras notacións para $A(n,k)$ son $E(n,k)$ e $⟨\genfrac{}{}{0ex}{}{n}{k}⟩$.

Definición

Os polinomios eulerianos $A_n(t)$ están definidos pola función xeradora exponencial

$\sum _{n=0}^{\mathrm{\infty }}{A}_n(t)\frac{x^n}{n!}=\frac{t-1}{t-e^{(t-1)x}}.$

Os números eulerianos $A(n,k)$ pódense definir como os coeficientes dos polinomios eulerianos:

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

Unha fórmula explícita para $A(n,k)$ é

Un gráfico dos números eulerianos co segundo argumento fixado en 5.

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

Propiedades básicas

• Para un $n$ fixo hai unha única permutación que ten 0 ascendentes: $(n,n-1,n-2,\dots ,1)$. De feito, como $(\genfrac{}{}{0ex}{}{n}{0})=1$ para todos os $n$, $A(n,0)=1$. Isto inclúe formalmente o conxunto baleiro de números, $n=0$. E $A_0(t)=A_1(t)=1$.
• Para $k=1$, a fórmula explícita implica que $A(n,1)=2^n-(n+1)$, unha sucesión en $n$ que consiste nos números $0,0,1,4,11,26,57,\dots$.
• Invertir completamente unha permutación con $k$ ascendentes crea outra permutación na que hai $n-k-1$ ascendentes. Polo tanto $A(n,k)=A(n,n-k-1)$. Así que tamén hai unha única permutación que ten $n-1$ ascendentes, esta é a permutación ascendente $(1,2,\dots ,n)$. Así, tamén $A(n,n-1)$ é igual a $1$.
• Para $k\ge n>0$, os valores son formalmente cero, o que significa que moitas sumas sobre $k$ pódense escribir cun índice superior só ata $n-1$. Tamén significa que os polinomios $A_n(t)$ son realmente de grao $n-1$ para $n>0$.

A tabulación dos números nunha matriz triangular chámase triángulo de Euler. Comparte algunhas características comúns co triángulo de Pascal. Valores de $A(n,k)$ Modelo:OEIS para $0\le n\le 9$ son:

Modelo:Diagonal split header	0	1	2	3	4	5	6	7	8
0	1
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

Cálculo

Para valores maiores de $n$, $A(n,k)$ tamén se pode calcular usando a fórmula recursiva

$A(n,k)=(n-k)A(n-1,k-1)+(k+1)A(n-1,k).$

Esta fórmula pode ser motivada a partir da definición combinatoria e, polo tanto, serve como punto de partida natural para a teoría.

Aplicando a recorrencia a un exemplo, podemos atopar

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

Así mesmo, os polinomios eulerianos pódense calcular pola recorrencia

$A_0(t)=1,$

$A_n(t)=A_{n^{\prime }-1}(t)\cdot t(1-t)+A_{n-1}(t)\cdot (1+(n-1)t),\text{ for }n>1.$

A segunda fórmula pódese transformar nunha forma con sumatorio,

$A_n(t)=\sum _{k=0}^{n-1}(\genfrac{}{}{0ex}{}{n}{k})A_k(t)\cdot (t-1{)}^{n-1-k},\text{ for }n>1.$

Identidades

Os números eulerianos dividen as permutacións de $n$ elementos, polo que a súa suma é igual ao factorial $n!$ . Así temos

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

con $A(0,0)=0!$. Para evitar conflitos coa convención de suma baleira, é conveniente simplemente indicar os teoremas só para $n>0$.

Moito máis xeralmente, para unha función fixada $f:ℝ\to ℂ$ integrábel no intervalo $(0,n)$

$\sum _{k=0}^{n-1}A(n,k)f(k)=n!\underset{0}{\overset{1}{\int }}\cdots \underset{0}{\overset{1}{\int }}f\left(\lfloor x_1+\cdots +x_n\rfloor \right)\mathrm{d}{x}_1\cdots \mathrm{d}{x}_n$

A identidade de Worpitzky expresa $x^n$ como a combinación linear de números eulerianos con coeficientes binomiais:

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

Dela, despréndese que

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

Fórmulas que implican sumas alternadas

A suma alternada dos números eulerianos para un valor fixo de $n$ está relacionado co número de Bernoulli $B_{n+1}$ do seguinte xeito

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

Fórmulas que implican polinomios

A propiedade de simetría implica:

$A_n(t)=t^{n-1}{A}_n(t^{-1})$

Os números eulerianos están implicados na función xeradora da secuencia das potencias n-ésimas:

$\sum _{i=1}^{\mathrm{\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)$

Unha expresión explícita para os polinomios eulerianos é

$$A_n(t)=\sum _{k=0}^n\left\{\genfrac{}{}{0ex}{}{n}{k}\right\}k!(t-1{)}^{n-k}$$

onde $\left\{\genfrac{}{}{0ex}{}{n}{k}\right\}$ son os números de Stirling do segundo tipo.

Véxase tamén

Bibliografía

• Modelo:Cita revista
• Modelo:Cita revista
• Modelo:Cita revista
• Modelo:Cita arXiv

Outros artigos

• Número de Bernoulli.

Ligazóns externas

• Eulerian Polynomials at OEIS Wiki.
• Modelo:MathWorld
• Modelo:MathWorld
• Modelo:MathWorld
• Modelo:MathWorld
• Euler-matrix (generalized rowindexes, divergent summation)