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

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

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

^[3]^,^[4].

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

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!

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

Formule explicite

Une formule explicite pour $A$ ( $n, k$ ) est

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

\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 fonction 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}}}$ .
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é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 k}\right\rangle \!\!\right\rangle$ vérifient 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)

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

↑ (en) Ronald Graham, Donald Knuth et Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science, Addison Wesley, 1994, p. 267–272
↑ ^{a et b} Ronald Graham, Donald Knuth et Oren Patashnik (trad. Alain Denise), Mathématiques concrètes, Thomson, 1998, p. 283-286
↑ ^{a b c et d} Louis Comtet, Analyse combinatoire, tome second, PUF, 1970, p. 82-85
↑ ^{a b c et d} 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 (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

[1] (en) Ronald Graham, Donald Knuth et Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science, Addison Wesley, 1994, p. 267–272

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

[:0-3] {a b c et d} Louis Comtet, Analyse combinatoire, tome second, PUF, 1970, p. 82-85

[Knuth-4] {a b c et d} 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]