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 »)[1]. Les nombres eulériens sont les coefficients des polynômes eulériens :

A_{n}(X)=\sum _{m=0}^{n}A(n,m)\ X^{m}\quad (A_{0}(X)=A_{1}(X)=1,A_{2}(X)=1+X,A_{3}(X)=1+4X+X^{2},\dots )

.

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). Ce sont 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 k}\right\rangle$ fut proposée par Donald Knuth en 1968 dans The Art of Computer Programming[2].

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

[3]^,[2]

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 (cf. 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 des termes de la ligne d'indice $n$ est le nombre des permutations de $n$ objets, 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}.

[3]

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

L’identité de Worpitzky[2]^,[3]^,[4] exprime $k^{n}$ comme combinaison linéaire de nombres eulériens avec des coefficients binomiaux :
$k^{n}=\sum _{m=0}^{n-1}A(n,m){\binom {k+m}{n}}$ .
On en déduit la fonction génératrice de la suite des puissances $n$ -ièmes :
$\sum _{k=1}^{\infty }k^{n}x^{k}={\frac {\sum _{m=0}^{n-1}A(n,m)x^{m+1}}{(1-x)^{n+1}}}={\frac {xA_{n}(x)}{(1-x)^{n+1}}}$ .
On en déduit :
$\sum _{n=0}^{\infty }{\frac {A_{n}(x)}{n!(1-x)^{n+1}}}=\sum _{n=0}^{\infty }\sum _{k=1}^{\infty }{\frac {k^{n}}{n!}}x^{k-1}=\sum _{k=1}^{\infty }e^{k}x^{k-1}={\frac {e}{1-ex}}$ en intervertissant les deux signes de sommations pour $|x|<{\frac {1}{e}}$ .
Plus généralement, on a[2] :
$\sum _{n=0}^{\infty }A_{n}(x)\,{\frac {t^{n}}{n!}}={\frac {x-1}{x-\mathrm {e} ^{(x-1)\,t}}}$
Une identité remarquable[5] 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 $(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\leqslant 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'à $2 n - 1$ (appelé parfois la double factorielle de $(2 n - 1)$ , et noté $(2 n - 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 ,$ dénombre celles de 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\ \mathrm {pour} \ m>0\ \ \mathrm {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$ vérifient la relation :

P_{n+1}(x)=(2nx+1)P_{n}(x)-x(x-1)P_{n}^{\prime }(x),\ \mathrm {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) 2 n u n (x)$ ; puis les nombres eulériens de seconde espèce qui sont leurs coefficients.

Voici quelques valeurs de ces nombres ( 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) = (2 n - 1)!!$ .

Articles connexes

Notes et références

Notes

(en) R. L. Graham, D. E. Knuth et O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, Addison Wesley, 1994, p. 267
Donald Knuth, The Art of Computer Programming, vol. 3, 1973 (ISBN 0-201-03803-X), p. 34-45. Dans cet ouvrage, la valeur de k est décalée d'une unité car D. Knuth compte le nombre de suites croissantes constituées d'images consécutives de la permutation, séparées par k-1 descentes.
Louis Comtet, Analyse combinatoire, tome second, PUF, 1970, p. 83-85
(de) Worpitzki, « Studien über die Bernoullischen und Eulerschen Zahlen », Journal für die reine und angewandte Mathematik, vol. 94,‎ 1883, p. 203-232 (lire en ligne)
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

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[1] (en) R. L. Graham, D. E. Knuth et O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, Addison Wesley, 1994, p. 267

[Knuth-2] Donald Knuth, The Art of Computer Programming, vol. 3, 1973 (ISBN 0-201-03803-X), p. 34-45. Dans cet ouvrage, la valeur de k est décalée d'une unité car D. Knuth compte le nombre de suites croissantes constituées d'images consécutives de la permutation, séparées par k-1 descentes.

[:0-3] Louis Comtet, Analyse combinatoire, tome second, PUF, 1970, p. 83-85

[4] (de) Worpitzki, « Studien über die Bernoullischen und Eulerschen Zahlen », Journal für die reine und angewandte Mathematik, vol. 94,‎ 1883, p. 203-232 (lire en ligne)

[5] 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.