Nombre eulérien

En mathématiques, et plus précisément en 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 » ( $0\leqslant k\leqslant n-1$ )^[1]^,^[2]^,^[3]. Les nombres eulériens sont les coefficients des polynômes eulériens :

{\begin{aligned}&A_{n}=\sum _{k=0}^{n-1}{A(n,k)X^{k}}\;;\\&A_{0}=A_{1}=1,\ A_{2}=1+X,\ A_{3}=1+4X+X^{2},\dotsc ,\ A_{n}=\sum _{k=0}^{n-1}{A(n,k)X^{k}}.\end{aligned}}

Ces polynômes apparaissent au numérateur d'expressions liées à la série 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 $\left\langle {n \atop k}\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). Ce sont les 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$ 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 $\sigma$ de $\{1,2,..,n\}$ est l'un des $n-1$ couples $(\sigma (i),\sigma (i+1))$ tel que $\sigma (i)<\sigma (i+1)$ (resp. $\sigma (i)>\sigma (i+1)$ ).

Par exemple, la permutation ${\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 $\sigma$ par $\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 ;
$A(n,k)=A(n,n-k-1)$ (propriété de symétrie).

Suites montantes

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

Si une permutation possède $k$ suites montantes, la permutation réciproque possède $k-1$ descentes. En effet, chaque passage d'une suite montante de $\sigma$ à la suivante provoque une descente pour $\sigma ^{-1}$ . Regarder par exemple ${\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 $k+1$ suites montantes.

Détermination du triangle d'Euler

Pour un $n$ strictement positif donné, le nombre de descentes $k$ d'une permutation est compris entre 0 et $n$ − 1. Pour $n$ fixé, il y a une et une seule permutation sans descente, à savoir l'identité, et une et une seule permutation avec $n$ − 1 montées, à savoir le renversement rencontré ci-dessus, défini par $w_{0}(i)=n+1-i$ pour tout $i$ . 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$ .

n	k	Permutations	A(n, k)
1	0	${\begin{pmatrix}1\\1\end{pmatrix}}$	A(1,0) = 1
2	0	${\begin{pmatrix}1&2\\2&1\end{pmatrix}}$	A(2,0) = 1
2	1	${\begin{pmatrix}1&2\\1&2\end{pmatrix}}$	A(2,1) = 1
3	0	${\begin{pmatrix}1&2&3\\3&2&1\end{pmatrix}}$	A(3,0) = 1
	1	${\begin{pmatrix}1&2&3\\1&3&2\end{pmatrix}}$ ${\begin{pmatrix}1&2&3\\2&1&3\end{pmatrix}}$ ${\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}}$ ${\begin{pmatrix}1&2&3\\3&1&2\end{pmatrix}}$	A(3,1) = 4
	2	${\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^[3]^,^[4] :

A(n,k)=(n-k)A(n-1,k-1)+(k+1)A(n-1,k)

.

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, k$ ) pour $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 $A(n,1)=2^{n}-n-1$ pour tout $n$ (suite A000295 de l'OEIS).

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

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

et

A(n,k)=A(n,n-1-k)

.

On en déduit que le polynôme eulérien $A_{n}=\sum _{k=0}^{n-1}{A(n,k)X^{k}}$ est un polynôme réciproque : $A_{n}\left({\frac {1}{X}}\right)={\frac {1}{X^{n-1}}}A_{n}(X)$ .

Formule explicite

Une formule explicite pour $A$ ( $n, k$ ) est^[3] :

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

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

\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 :

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

\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 $x^{n}$ comme combinaison linéaire de nombres eulériens avec des coefficients binomiaux :
$x^{n}=\sum _{k=0}^{n-1}A(n,k){\binom {x+k}{n}}$ .
On en déduit la série génératrice de la suite des puissances $n$ -ièmes :
$\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}}}$ , ce que l'on peut aussi écrire :

$\sum _{i=1}^{\infty }{\frac {i^{n}}{x^{i}}}={\frac {xA_{n}(x)}{(x-1)^{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 }\mathrm {e} ^{k}x^{k-1}={\frac {\mathrm {e} }{1-\mathrm {e} x}}$ en intervertissant les deux signes de sommations pour $|x|<{\frac {1}{\mathrm {e} }}$ .
Plus généralement, on a^[4] :
$\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 $(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 $m$ , tous les nombres entre les deux occurrences de $m$ sont plus grands que $m$ , 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 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ée, 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 k}\right\rangle \!\!\right\rangle$ satisfont à la récurrence :

\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 :

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

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 :

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)

est caractérisée par la relation de récurrence

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 ligne de rang $n$ est $P n (1) = (2 n - 1)!!$ .

Articles connexes

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

↑ Graham, Knuth et Patashnik (1994).
1 2 Ronald Graham, Donald Knuth et Oren Patashnik (trad. Alain Denise), Mathématiques concrètes, Thomson, 1998, p. 283-286
1 2 3 4 Louis Comtet, Analyse combinatoire, t. 2, Presses universitaires de France, coll. « Collection SUP : le mathématicien » (n^o 5), 1970 (ISSN 1244-636X), p. 82-85.
1 2 3 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.
↑ (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)
↑ 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.
↑ 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 p. (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

Portail des mathématiques

[GrahamKnuthPatashnik1994-1] Graham, Knuth et Patashnik (1994).

[:1-2] 1 2 Ronald Graham, Donald Knuth et Oren Patashnik (trad. Alain Denise), Mathématiques concrètes, Thomson, 1998, p. 283-286

[:0-3] 1 2 3 4 Louis Comtet, Analyse combinatoire, t. 2, Presses universitaires de France, coll. « Collection SUP : le mathématicien » (n^o 5), 1970 (ISSN 1244-636X), p. 82-85.

[Knuth-4] 1 2 3 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

[1]

[2]

[3]

[4]

[5]

[6]

[7]