Nombre eulérien

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

Ces nombres forment la suite A008292 de l'OEIS.

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

Historique

Euler, *Institutiones calculi differentialis*, 2^e partie, 1755

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
2	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\leq x<{1}/{e}

, les termes de gauche forment une série géométrique convergente, et les termes de droite sont positifs ; on peut donc interchanger les sommations. 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\leq 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}^{n}U_{k},\quad X_{n}=\left\lfloor S_{n}\right\rfloor ,

alors

\mathbb {P} \left(k\leq 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^{n}n!}}$ .

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_{0}(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)!!.

Articles connexes

Notes et références

Notes

↑ voir (en) S. Tanny, « A probabilistic interpretation of the Eulerian numbers », Duke Math. J., vol. 40,‎ 1973, p. 717-722 ou bien (en) R.P. Stanley, « Eulerian partitions of a unit hypercube », 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, Concrete Mathematics : 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 », sur MathWorld
(en) Eric W. Weisstein, « Euler's Number Triangle », sur MathWorld
(en) Eric W. Weisstein, « Worpitzky's Identity », sur MathWorld
(en) Eric W. Weisstein, « Second-Order Eulerian Triangle », sur MathWorld
(en) Triangle d'Euler sur la page de Gottfried Helms, de l'université de Cassel

Portail des mathématiques

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

[1]