Nombre eulérien

Nombre eulérien
Page d'aide sur l'homonymie Ne pas confondre avec e, la base du logarithme naturel, aussi appelée occasionnellement nombre d'Euler, ni avec les 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 .

Sommaire

Historique

EulerianPolynomialsByEuler1755.png

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

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

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

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

où Bn est le n-ème nombre de Bernoulli.

Identités

\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

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

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

un(x): = (x − 1) − 2nPn(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

Notes

  1. ↑ voir (en) S. Tanny, « A probabilistic interpretation of the Eulerian numbers », dans Duke Math. J., vol. 40, 1973, p. 717-722  ou bien (en) R.P. Stanley, « Eulerian partitions of a unit hypercube », dans Higher Combinatorics, Dordrecht, M. Aigner, ed., Reidel, 1977 .

Références

Liens externes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Nombre eulérien de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Nombre Premier — 7 est un nombre premier car il admet exactement deux diviseurs positifs …   Wikipédia en Français

  • Eulérien — Leonhard Euler « Euler » redirige ici. Pour les autres significations, voir Euler (homonymie). Leonhard Euler …   Wikipédia en Français

  • Nombre premier — 7 est un nombre premier car il admet exactement deux diviseurs positifs. Un nombre premier est un entier naturel qui admet exactement deux diviseurs distincts entiers et positifs (qui sont alors 1 et lui même). Cette définition exclut 1, qui n a… …   Wikipédia en Français

  • Chemin eulérien — Graphe eulérien En théorie des graphes, on dit d un graphe non orienté qu il est « eulérien » en référence à Euler (la plupart des mathématiciens écrivent « Eulérien » à cause de l usage anglo saxon) s il a la propriété… …   Wikipédia en Français

  • Graphe Eulérien — En théorie des graphes, on dit d un graphe non orienté qu il est « eulérien » en référence à Euler (la plupart des mathématiciens écrivent « Eulérien » à cause de l usage anglo saxon) s il a la propriété suivante : On… …   Wikipédia en Français

  • Graphe eulerien — Graphe eulérien En théorie des graphes, on dit d un graphe non orienté qu il est « eulérien » en référence à Euler (la plupart des mathématiciens écrivent « Eulérien » à cause de l usage anglo saxon) s il a la propriété… …   Wikipédia en Français

  • Graphe eulérien — En théorie des graphes, on dit d un graphe non orienté qu il est « eulérien » en référence à Euler (la plupart des mathématiciens écrivent « Eulérien » à cause de l usage anglo saxon) s il a la propriété suivante : On… …   Wikipédia en Français

  • Produit eulerien — Produit eulérien Leonhard Euler En mathématiques, et plus précisément en théorie analytique des nombres, un produit eulérien est un développement en produit infini, indexé par les nombres premiers. Il permet de mesurer la répartition des nombres… …   Wikipédia en Français

  • Produit eulérien — En mathématiques, et plus précisément en théorie analytique des nombres, un produit eulérien est un développement en produit infini, indexé par les nombres premiers[1]. Il permet de mesurer la répartition des nombres premiers et est intimement… …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”