Nombre eulérien

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir 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[modifier | modifier le code]

Euler, Institutiones calculi differentialis, 2e partie, 1755

En 1755, dans son livre Institutiones calculi differentialis, Leonhard Euler a étudié les polynômes α1(x) = 1,α2(x) = x + 1, α3(x) = x2 + 4x + 1, etc. (voir le facsimilé ci-contre). Ces polynômes sont une forme décalée de nos polynômes eulériens An(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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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 Bn+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},

Bn est le n-ème nombre de Bernoulli.

Identités[modifier | modifier le code]

\sum_{k=1}^{\infty}k^n x^k = \frac{\sum_{m=0}^{n}A(n,m)x^{m+1}}{(1-x)^{n+1}}.
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[modifier | modifier le code]

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 Pn(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 Pn(x)=(1-x)2nun(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 Pn(1) = (2n-1)!!.

À voir[modifier | modifier le code]

Notes[modifier | modifier le code]

  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.

Références[modifier | modifier le code]

Liens externes[modifier | modifier le code]