Nombre eulérien

En mathématiques, et plus précisément en analyse combinatoire, le nombre eulérien A(n, k), est le nombre de permutations des entiers de 1 à n pour lesquelles exactement k éléments sont plus grands que l'élément précédent (permutations avec k « montées » (${\displaystyle 0\leqslant k\leqslant n-1}$)^[1],[2],[3]. Les nombres eulériens sont les coefficients des polynômes eulériens :

${\displaystyle A_{n}(X)=\sum _{k=0}^{n}A(n,k)\ X^{k}\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 ${\textstyle 1^{n},\ 2^{n},\ 3^{n},\ \dots }$.

Ces nombres forment la suite A008292 de l'OEIS.

Les nombres A(n, k) sont aussi notés E(n, k) et ${\displaystyle \left\langle {n \atop k}\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 les polynômes eulériens A_n(x).

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

Propriétés

Montées et descentes

Une montée (resp. une descente) d'une permutation ${\displaystyle \sigma }$ de ${\displaystyle \{1,2,..,n\}}$ est l'un des ${\displaystyle n-1}$ couples ${\displaystyle (\sigma (i),\sigma (i+1))}$ tel que ${\displaystyle \sigma (i)<\sigma (i+1)}$ (resp. ${\displaystyle \sigma (i)>\sigma (i+1)}$).

Par exemple, la permutation ${\displaystyle {\begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}}}$ possède une montée (2, 5), et trois descentes (5, 4), (4,3) et (3,1).

Si on définit la permutation renversée de ${\displaystyle \sigma }$ par ${\displaystyle \sigma ^{-}(i)=n+1-i}$, on remarque que le renversement d'une permutation transforme les montées en descentes, et réciproquement. Le renversement étant bijectif, on en déduit que :

• Le nombre A(n, k) est aussi le nombre de permutations présentant k descentes.
• ${\displaystyle A(n,k)=A(n,n-k-1)}$ (propriété de symétrie)

Suites montantes

Une suite montante de ${\displaystyle \sigma }$ est une liste croissante d'entiers consécutifs maximale extraite de la liste ${\displaystyle (\sigma (1),\sigma (2),\cdots ,\sigma (n))}$. Par exemple, la permutation ${\displaystyle {\begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}}}$ possède trois suites montantes : ${\displaystyle (1),(2,3),(4),(5)}$.

Si une permutation possède k suites montantes, la permutation réciproque possède ${\displaystyle k-1}$ descentes. En effet, chaque passage d'une suite montante de ${\displaystyle \sigma }$ à la suivante provoque une descente pour ${\displaystyle \sigma ^{-1}}$. Regarder par exemple ${\displaystyle {\begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}}^{-1}={\begin{pmatrix}1&2&3&4&5\\5&1&4&3&2\end{pmatrix}}}$. On en déduit que :

• Le nombre A(n, k) est aussi le nombre de permutations présentant ${\displaystyle k+1}$ suites montantes.

Détermination du triangle d'Euler

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

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

n	k	Permutations	A(n, k)
1	0	${\displaystyle {\begin{pmatrix}1\\1\end{pmatrix}}}$	A(1,0) = 1
2	0	${\displaystyle {\begin{pmatrix}1&2\\2&1\end{pmatrix}}}$	A(2,0) = 1
	1	${\displaystyle {\begin{pmatrix}1&2\\1&2\end{pmatrix}}}$	A(2,1) = 1
3	0	${\displaystyle {\begin{pmatrix}1&2&3\\3&2&1\end{pmatrix}}}$	A(3,0) = 1
	1	${\displaystyle {\begin{pmatrix}1&2&3\\1&3&2\end{pmatrix}}}$${\displaystyle {\begin{pmatrix}1&2&3\\2&1&3\end{pmatrix}}}$${\displaystyle {\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}}}$ ${\displaystyle {\begin{pmatrix}1&2&3\\3&1&2\end{pmatrix}}}$	A(3,1) = 4
	2	${\displaystyle {\begin{pmatrix}1&2&3\\1&2&3\end{pmatrix}}}$	A(3,2) = 1

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

${\displaystyle A(n,k)=(n-k)A(n-1,k-1)+(k+1)A(n-1,k).}$^[3],[4].

Par exemple

${\displaystyle 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, k) pour ${\displaystyle 0\leqslant n\leqslant 9}$ (cf. la suite A008292 de l'OEIS) sont :

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

On a par exemple ${\displaystyle A(n,1)=2^{n}-n-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!. De plus, nous avons une relation de symétrie, soit pour n > 0, nous avons

${\displaystyle \sum _{k=0}^{n-1}A(n,k)=n!}$

${\displaystyle A(n,k)=A(n,n-1-k)}$

Formule explicite

Une formule explicite pour A(n, k) est

${\displaystyle A(n,k)=\sum _{i=0}^{k}(-1)^{i}{\binom {n+1}{i}}(k+1-i)^{n}.}$^[3]

Calculs de sommes

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

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

Voici d'autres formules de sommation :

${\displaystyle \sum _{k=0}^{n-1}(-1)^{k}{\frac {A(n,k)}{\binom {n-1}{k}}}=0,}$

${\displaystyle \sum _{k=0}^{n-1}(-1)^{k}{\frac {A(n,k)}{\binom {n}{k}}}=(n+1)B_{n},}$

où B_n est le nombre de Bernoulli de rang n.

Identités

• L’identité de Worpitzky^{[2],[4],[3],[5]} exprime ${\displaystyle x^{n}}$ comme combinaison linéaire de nombres eulériens avec des coefficients binomiaux :

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

• On en déduit la fonction génératrice de la suite des puissances n-ièmes :

  ${\displaystyle \sum _{i=1}^{\infty }i^{n}x^{i}={\frac {\sum _{k=0}^{n-1}A(n,k)x^{k+1}}{(1-x)^{n+1}}}={\frac {xA_{n}(x)}{(1-x)^{n+1}}}}$.

• On en déduit :

  ${\displaystyle \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 }\mathrm {e} ^{k}x^{k-1}={\frac {\mathrm {e} }{1-\mathrm {e} x}}}$ en intervertissant les deux signes de sommations pour ${\displaystyle |x|<{\frac {1}{\mathrm {e} }}}$.

• Plus généralement, on a^[4] :

  ${\displaystyle \sum _{n=0}^{\infty }A_{n}(x)\,{\frac {t^{n}}{n!}}={\frac {x-1}{x-\mathrm {e} ^{(x-1)\,t}}}}$

• Une identité remarquable^[6] 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 ${\displaystyle (U_{1},U_{2},\dots ,U_{n})}$ est une suite de variables aléatoires i.i.d. uniformes sur [0, 1] et si

${\displaystyle S_{n}=\sum _{k=1}^{n}U_{k},\quad X_{n}=\left\lfloor S_{n}\right\rfloor }$,

alors

${\displaystyle \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 ${\displaystyle \{1,1,2,2,\cdots ,n,n\}}$ telles que pour chaque m, tous les nombres entre les deux occurrences de m sont plus grands que m, est le produit des entiers impairs jusqu'à 2n − 1 (appelé parfois la double factorielle de (2n − 1), et noté (2n − 1)!!) ; on a ${\displaystyle (2n-1)!!=\prod _{k=1}^{n}(2k-1)={\frac {(2n)!}{2^{n}n!}}}$.

Le nombre eulérien de seconde espèce, noté ${\displaystyle \left\langle \!\!\left\langle {n \atop k}\right\rangle \!\!\right\rangle ,}$ dénombre celles de ces permutations ayant exactement k montées^[7]. 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:

${\displaystyle 332211,\;}$

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

${\displaystyle 112233,\;122133,\;112332,\;123321,\;133122,\;122331.}$

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

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

avec les conditions initiales :

${\displaystyle \left\langle \!\!\left\langle {0 \atop k}\right\rangle \!\!\right\rangle =0\ \mathrm {pour} \ k>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 :

${\displaystyle P_{n}(x):=\sum _{k=0}^{n}\left\langle \!\!\left\langle {n \atop k}\right\rangle \!\!\right\rangle x^{k}}$ ;

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

${\displaystyle 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 :

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

ainsi la fonction rationnelle

${\displaystyle u_{n}(x):=(x-1)^{-2n}P_{n}(x)}$

satisfait :

${\displaystyle 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 ( 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 ligne de rang n est P_n(1) = (2n − 1)!!.

Articles connexes

• Ensemble triangulaire
• Nombre de Stirling
• Triangle de Pascal
• Leonhard Euler
• Liste de sujets portant le nom de Leonhard Euler

Notes et références

Notes

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

Références

1. (en) Ronald Graham, Donald Knuth et Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science, Addison Wesley, 1994, p. 267–272
2. Ronald Graham, Donald Knuth et Oren Patashnik (trad. Alain Denise), Mathématiques concrètes, Thomson, 1998, p. 283-286
3. Louis Comtet, Analyse combinatoire, tome second, PUF, 1970, p. 82-85
4. 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.
5. (de) Julius Worpitzky, « Studien über die Bernoullischen und Eulerschen Zahlen », Journal für die reine und angewandte Mathematik, vol. 94,‎ 1883, p. 203-232 (lire en ligne)
6. voir (en) Stephen Tanny, « A probabilistic interpretation of the Eulerian numbers », Duke Math. J., vol. 40,‎ 1973, p. 717-722 ou bien (en) Richard P. Stanley, « Eulerian partitions of a unit hypercube », Higher Combinatorics, Dordrecht, M. Aigner, ed., Reidel,‎ 1977.
7. Ronald Graham, Donald Knuth et Oren Patashnik, Mathématiques concrètes, Thomson, 1998, p. 286-287

Bibliographie

• (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, Addison-Wesley, 1994, 2^e éd., p. 267–272.
• Dominique Foata et Marcel-Paul Schützenberger, Théorie géométrique des polynômes eulériens, Springer-Verlag, coll. « Lecture Notes in Mathematics » (n^o 138), 1970, v+94 (ISBN 978-3-540-04927-2, arXiv math/0508232). — Version révisée de 2005.

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