Nombre eulérien

 Ne pas confondre avec e, la base du logarithme naturel, aussi appelée occasionnellement nombre d'Euler, ni avec les nombres d'Euler.

En mathématiques, et plus précisément en analyse combinatoire, le nombre eulérien A(n, m), est le nombre de permutations des entiers de 1 à n pour lesquelles exactement m éléments sont plus grands que l'élément précédent (permutations avec m « montées » ). Ce sont les coefficients des polynômes eulériens :

$A_{n}(x) = \sum_{m=0}^{n} A(n,m)\ x^{n-m}.$

Ces polynômes apparaissent au numérateur d'expressions liées à la fonction génératrice de la suite $\scriptstyle 1^n,\ 2^n,\ 3^n,\ \dots$.

D'autres notations pour A(n, m) sont E(n, m) et $\left \langle {n\atop m} \right \rangle .$

Historique

En 1755, dans son livre Institutiones calculi differentialis, Leonhard Euler a étudié les polynômes α₁(x) = 1,α₂(x) = x + 1, α₃(x) = x² + 4x + 1, etc. (voir le facsimilé ci-contre). Ces polynômes sont une forme décalée de nos polynômes eulériens A_n(x).

Par analogie avec la notation des coefficients binomiaux $\left ( {n\atop k} \right )$ et avec celle des nombres de Stirling $\left [ {n\atop k} \right ]$ et $\left \{ {n\atop k} \right \} ,$ la notation $\left \langle {n\atop m} \right \rangle$ fut proposée par Donald Knuth en 1968 dans The Art of Computer Programming.

Propriétés élémentaires

Pour un n donné  > 0, l'indice m de A(n, m) peut aller de 0 à n − 1. Pour n fixé, il y a une seule permutation sans montée, la permutation descendante (n, n − 1, n − 2, ..., 1). Il y a également une seule permutation avec n − 1 montées, la permutation identique (ou montante) (1, 2, 3, ..., n). Ainsi, A(n, 0) = A(n, n − 1) = 1 pour tout n.

Renverser une permutation ayant m montées crée une autre permutation ayant n − m − 1 montées ; ainsi

A(n, m) = A(n, n − m − 1).

Les valeurs de A(n, m) peuvent être calculées « à la main » pour de petites valeurs de n et m. Par exemple

n	m	Permutations	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

Pour des valeurs plus grandes de n, A(n, m) peut être calculé à l'aide de la relation de récurrence

A(n,m) = (n − m)A(n − 1,m − 1) + (m + 1)A(n − 1,m).

Par exemple

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

Les valeurs de A(n, m) pour 0 ≤ n ≤ 9 (c'est la suite A008292 de l’OEIS) sont :

n \ m	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

Ce tableau triangulaire s'appelle le triangle d'Euler, et possède certaines des caractéristiques du triangle de Pascal. La somme de la n-ème ligne est le nombre de toutes les permutations, soit la factorielle n!.

Formule explicite

Une formule explicite pour A(n, m) est

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

Calculs de sommes

D'après leur définition combinatoire, la somme des nombres eulériens pour une valeur donnée de n est le nombre total de permutations des entiers de 1 à n, et donc

$\sum_{m=0}^{n-1}A(n,m)=n!.$

La somme alternée des nombres eulériens pour une valeur donnée de n est liée au nombre de Bernoulli B_n+1

$\sum_{m=0}^{n-1}(-1)^{m}A(n,m)=\frac{2^{n+1}(2^{n+1}-1)B_{n+1}}{n+1}.$

Voici d'autres formules de sommation  :

$\sum_{m=0}^{n-1}(-1)^m\frac{A(n,m)}{\binom{n-1}{m}}=0,$

$\sum_{m=0}^{n-1}(-1)^m\frac{A(n,m)}{\binom{n}{m}}=(n+1)B_{n},$

où B_n est le n-ème nombre de Bernoulli.

Identités

• Les nombres eulériens apparaissent dans la fonction génératrice de la suite des puissances n-èmes

$\sum_{k=1}^{\infty}k^n x^k = \frac{\sum_{m=0}^{n}A(n,m)x^{m+1}}{(1-x)^{n+1}}.$

• L’identité de Worpitzky exprime xⁿ comme combinaison linéaire de nombres eulériens avec des coefficients binomiaux :

$x^n=\sum_{m=0}^{n-1}A(n,m)\binom{x+m}{n}.$

• Une autre identité remarquable est obtenue par la transformation :

$e^k=\sum_{n=0}^\infty \frac{k^n}{n!}$

$(x^k)(e^k)=\sum_{n=0}^\infty \frac{(x^k)(k^n)}{n!}$

$\sum_{k=1}^\infty(x^k)(e^k)=\sum_{k=1}^\infty\sum_{n=0}^\infty \frac{(x^k)(k^n)}{n!}$

Pour $0\le x<{1}/{e}$, les termes de droite sont positifs ; on peut donc interchanger les sommations. Les termes de gauche forment une série géométrique convergente. Utilisant l'identité précédente, on obtient :

$\sum_{k=1}^\infty(xe)^k=\sum_{k=1}^\infty\sum_{n=0}^\infty \frac{(x^k)(k^n)}{n!}$

$\frac{ex}{1-ex}=\sum_{n=0}^\infty\sum_{k=1}^\infty \frac{(x^k)(k^n)}{n!}=\sum_{n=0}^\infty\frac{\sum_{m=0}^{n}A(n,m)x^{m+1}}{n!(1-x)^{n+1}}$

En définitive, pour $0\le x<{1}/{e}$, on a

$\frac{e}{1-ex}=\sum_{n=0}^\infty\frac{\sum_{m=0}^{n}A(n,m)x^{m}}{n!(1-x)^{n+1}}.$

La somme du numérateur de droite est la somme des polynômes d'Euler.

• Une identité remarquable^[1] probabiliste permet de démontrer simplement un théorème central limite pour le nombre de montées d'une permutation tirée au hasard. Si $\scriptstyle\ (U_1,U_2,\dots,U_n)\$ est une suite de variables aléatoires i.i.d. uniformes sur [0,1] et si

$S_n=\sum_{k=1}^nU_k,\quad X_n=\left\lfloor S_n\right\rfloor,$

alors

$\mathbb P\left(k\le S_n<k+1\right)=\mathbb P\left(X_n=k\right)\ =\frac{A(n,k)}{n!}.$

Nombres eulériens de seconde espèce

Le nombre des permutations du multiensemble $\{1,1,2,2,\cdots,n,n \}$ telles que pour chaque k, tous les nombres entre les deux occurrences de k sont plus grands que k, est le produit des entiers impairs jusqu'à 2n-1 (appelé parfois la double factorielle de (2n-1), et noté (2n-1)!!) ; on a$(2n-1)!!=\prod_{{k=1}}^n(2k-1)=\frac{{(2n)!}}{{2^nn!}}$.

Le nombre eulérien de seconde espèce, noté $\left \langle \!\! \left \langle {n\atop m} \right \rangle \!\! \right \rangle,$ compte le nombre de toutes ces permutations ayant exactement m montées. Par exemple, pour n=3, il y a 3!! = 15 permutations de ce type, une sans montées, 8 avec une montée, et 6 avec deux montées:

$332211,\;$

$221133,\; 221331,\;223311,\;233211,\;113322, \;133221, \; 331122,\; 331221,$

$112233,\; 122133,\;112332,\; 123321,\;133122, \;122331.$

À partir de cette définition, on montre facilement que les nombres $\left \langle \!\! \left \langle {n\atop m} \right \rangle \!\! \right \rangle$ vérifient la récurrence  :

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

avec les conditions initiales :

$\left \langle \!\!\left \langle {0\atop m} \right \rangle \!\! \right \rangle =0\$ pour m > 0 et $\left \langle \!\!\left \langle {0\atop 0} \right \rangle \!\! \right \rangle =1$.

On leur fait correspondre les polynômes eulériens de seconde espèce, notés ici P_n :

$P_n(x):=\sum_{n=0}^n \left \langle \!\! \left \langle {n\atop m} \right \rangle \!\! \right \rangle x^m$ ;

des relations de récurrence précédentes, on déduit que les P_n(x) vérifient la relation :

$P_{n+1}(x)=(2nx+1)P_n(x)-x(x-1)P_n^\prime(x)$, avec P₀(x) = 1.

On peut la réécrire :

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

ainsi la fonction rationnelle

u_n(x): = (x − 1) ^{− 2n}P_n(x)

satisfait :

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

d'où l'on tire les polynômes sous la forme P_n(x)=(1-x)²ⁿu_n(x); puis les nombres eulériens de seconde espèce qui sont leurs coefficients.

Voici quelques valeurs de ces nombres (la suite A008517 de l’OEIS) :

n \ m	0	1	2	3	4	5	6	7	8
0	1
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 somme de la n-ème ligne est P_n(1) = (2n-1)!!.

À voir

Notes

1. ↑ voir (en) S. Tanny, « A probabilistic interpretation of the Eulerian numbers », dans Duke Math. J., vol. 40, 1973, p. 717-722  ou bien (en) R.P. Stanley, « Eulerian partitions of a unit hypercube », dans Higher Combinatorics, Dordrecht, M. Aigner, ed., Reidel, 1977 .

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Eulerian number » (voir la liste des auteurs)
• (la) Leonhard Euler, Institutiones calculi differentialis cum eius usu in analysi finitorum ac doctrina serierum (Fondement du Calcul différentiel, avec des applications à l'Analyse finie et aux séries), vol. II, Academia imperialis scientiarum Petropolitana, 1755 [lire en ligne], chap. VII 
• (en) Ronald Graham, Donald Knuth et Oren Patashnik (en), Concrete Mathematics (en) : A Foundation for Computer Science, 1994 (deuxième édition), Addison-Wesley, p. 267–272

Liens externes

• (en) Eulerian Polynomials sur le wiki de l'OEIS
• (en) Eulerian Numbers sur MathPages
• (en) Eric W. Weisstein, « Eulerian Number », MathWorld
• (en) Eric W. Weisstein, « Euler's Number Triangle », MathWorld
• (en) Eric W. Weisstein, « Worpitzky's Identity », MathWorld
• (en) Eric W. Weisstein, « Second-Order Eulerian Triangle », MathWorld
• (en) Triangle d'Euler sur la page de Gottfried Helms, de l'université de Cassel