Voir la source de Nombre eulérien

{{Homon|Liste des sujets nommés d'après Leonhard Euler#Nombres{{!}}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 [[permutation]]s 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''' :
:<math>A_{n}(x) = \sum_{m=0}^{n} A(n,m)\ x^{n-m}.</math>
Ces polynômes apparaissent au numérateur d'expressions liées à la [[fonction génératrice]] de la suite <math>\scriptstyle 1^n,\ 2^n,\ 3^n,\ \dots</math>.

D'autres notations pour ''A''(''n'', ''m'') sont ''E''(''n'', ''m'') et <math>\left \langle {n\atop m} \right \rangle .</math>

== Historique ==
[[Image:EulerianPolynomialsByEuler1755.png|vignette|Euler, ''Institutiones calculi differentialis'', {{2e|partie}}, 1755]]
En 1755, dans son livre ''Institutiones calculi differentialis'', [[Leonhard Euler]] a étudié les polynômes ''α''<sub>1</sub>(''x'')&nbsp;=&nbsp;1,''α''<sub>2</sub>(''x'')&nbsp;=&nbsp;''x''&nbsp;+&nbsp;1, ''α''<sub>3</sub>(''x'')&nbsp;=&nbsp;''x''<sup>2</sup>&nbsp;+&nbsp;4''x''&nbsp;+&nbsp;1, etc. (voir le facsimilé ci-contre). Ces polynômes sont une forme décalée de nos polynômes eulériens ''A''<sub>''n''</sub>(''x'').

Par analogie avec la notation des [[coefficient binomial|coefficients binomiaux]] <math>\left ( {n\atop k} \right )</math> et avec celle des [[nombre de Stirling|nombres de Stirling]] <math>\left [ {n\atop k} \right ]</math> et <math>\left \{ {n\atop k} \right \} ,</math> la notation <math>\left \langle {n\atop m} \right \rangle</math> fut proposée par [[Donald Knuth]] en 1968 dans ''[[The Art of Computer Programming]]''.

== Propriétés élémentaires ==
Pour un ''n'' donné &nbsp;&gt;&nbsp;0, l'indice ''m'' de ''A''(''n'', ''m'') peut aller de 0 à ''n''&nbsp;−&nbsp;1. Pour ''n'' fixé, il y a une seule permutation sans montée, la permutation descendante (''n'', ''n''&nbsp;−&nbsp;1, ''n''&nbsp;−&nbsp;2, ..., 1). Il y a également une seule permutation avec ''n''&nbsp;−&nbsp;1 montées, la permutation identique (ou montante) (1, 2, 3, ..., ''n''). Ainsi, ''A''(''n'', 0) = ''A''(''n'', ''n''&nbsp;−&nbsp;1) = 1 pour tout ''n''.

Renverser une permutation ayant ''m'' montées crée une autre permutation ayant ''n''&nbsp;−&nbsp;''m''&nbsp;−&nbsp;1 montées ; ainsi
:''A''(''n'', ''m'') = ''A''(''n'', ''n''&nbsp;−&nbsp;''m''&nbsp;−&nbsp;1).

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

:{| class="wikitable"
|-
! ''n''
! ''m''
! Permutations
! ''A''(''n'', ''m'')
|-
| 1
| 0
| (1)
| ''A''(1,0) = 1
|-
|rowspan="2" | 2
| 0
| (2, 1)
| ''A''(2,0) = 1
|-
| 1
| (1, '''2''')
| ''A''(2,1) = 1
|-
|rowspan="3" | 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]]
:<math>A(n,m)=(n-m)A(n-1,m-1) + (m+1)A(n-1,m).</math>

Par exemple
:<math>A(4,1)=(4-1)A(3,0) + (1+1)A(3,1)=3 \times 1 + 2 \times 4 = 11.</math>
Les valeurs de ''A''(''n'', ''m'') pour 0 ≤ ''n'' ≤ 9 (c'est la {{OEIS|id=A008292}}) sont :
:{| class="wikitable"
|-
! n&nbsp;\&nbsp;m
! width="50" | 0
! width="50" | 1
! width="50" | 2
! width="50" | 3
! width="50" | 4
! width="50" | 5
! width="50" | 6
! width="50" | 7
! width="50" | 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''<nowiki>!</nowiki>.

=== Formule explicite ===
Une [[solution de forme fermée|formule explicite]] pour ''A''(''n'', ''m'') est

:<math>A(n,m)=\sum_{k=0}^{m}(-1)^k \binom{n+1}{k} (m+1-k)^n.</math>

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

:<math>\sum_{m=0}^{n-1}A(n,m)=n!.</math>

La [[série alternée|somme alternée]] des nombres eulériens pour une valeur donnée de ''n'' est liée au [[nombre de Bernoulli]] ''B''<sub>''n''+1</sub>
:<math>\sum_{m=0}^{n-1}(-1)^{m}A(n,m)=\frac{2^{n+1}(2^{n+1}-1)B_{n+1}}{n+1}.</math>
Voici d'autres formules de sommation :

:<math>\sum_{m=0}^{n-1}(-1)^m\frac{A(n,m)}{\binom{n-1}{m}}=0,</math>

:<math>\sum_{m=0}^{n-1}(-1)^m\frac{A(n,m)}{\binom{n}{m}}=(n+1)B_{n},</math>

où ''B''<sub>''n''</sub> est le ''n''-ème [[nombre de Bernoulli]].

== Identités ==
* Les nombres eulériens apparaissent dans la [[fonction génératrice]] de la suite des puissances ''n''-èmes
:<math>\sum_{k=1}^{\infty}k^n x^k = \frac{\sum_{m=0}^{n}A(n,m)x^{m+1}}{(1-x)^{n+1}}.</math>

* L’'''identité de Worpitzky''' exprime ''x''<sup>''n''</sup> comme [[combinaison linéaire]] de nombres eulériens avec des [[coefficient binomial|coefficients binomiaux]] :
:<math>x^n=\sum_{m=0}^{n-1}A(n,m)\binom{x+m}{n}.</math>

* Une autre identité remarquable est obtenue par la transformation :
:<math>e^k=\sum_{n=0}^\infty \frac{k^n}{n!}</math>
:<math>(x^k)(e^k)=\sum_{n=0}^\infty \frac{(x^k)(k^n)}{n!}</math>
:<math>\sum_{k=1}^\infty(x^k)(e^k)=\sum_{k=1}^\infty\sum_{n=0}^\infty \frac{(x^k)(k^n)}{n!}</math>

:Pour <math>0\le x<{1}/{e}</math>, les termes de gauche forment une série géométrique convergente, et les termes de droite sont positifs ; on peut donc interchanger les sommations. Utilisant l'identité précédente, on obtient :
:<math>\sum_{k=1}^\infty(xe)^k=\sum_{k=1}^\infty\sum_{n=0}^\infty \frac{(x^k)(k^n)}{n!}</math>
:<math>\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}}</math>

:En définitive, pour <math>0\le x<{1}/{e}</math>, on a
:<math>\frac{e}{1-ex}=\sum_{n=0}^\infty\frac{\sum_{m=0}^{n}A(n,m)x^{m}}{n!(1-x)^{n+1}}.</math>

:La somme du numérateur de droite est la somme des polynômes d'Euler.

* Une identité remarquable<ref>voir {{article|langue=en|prénom1=S.|nom1=Tanny|lien auteur1=|titre=A probabilistic interpretation of the Eulerian numbers|périodique=Duke Math. J.|lien périodique=|volume=40|numéro=|jour=|mois=|année=1973|pages=717-722|issn=|url texte=|consulté le=}} ou bien {{article|langue=en|prénom1=R.P.|nom1=Stanley|lien auteur1=:en:Richard P. Stanley|titre=Eulerian partitions of a unit hypercube|périodique=Higher Combinatorics|lien périodique=|éditeur=M. Aigner, ed., Reidel|lieu=Dordrecht|volume=|numéro=|jour=|mois=|année=1977|pages=|issn=|url texte=|consulté le=}}.</ref> 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 <math>\scriptstyle\ (U_1,U_2,\dots,U_n)\ </math> est une suite de variables aléatoires [[Indépendance (probabilités)|i.i.d.]] [[Loi uniforme continue#Nombres de descentes d'une permutation aléatoire, et nombres eulériens|uniformes]] sur ''[0,1]'' et si
:<math>S_n=\sum_{k=1}^nU_k,\quad X_n=\left\lfloor S_n\right\rfloor,</math>
:alors
:<math>\mathbb P\left(k\le S_n<k+1\right)=\mathbb P\left(X_n=k\right)\ =\frac{A(n,k)}{n!}.</math>

== Nombres eulériens de seconde espèce ==
Le nombre des permutations du [[multiensemble]] <math> \{1,1,2,2,\cdots,n,n \} </math> 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'à 2''n''-1 (appelé parfois la ''double factorielle'' de (2''n''-1), et noté (2''n''-1)!!) ; on a <math>(2n-1)!!=\prod_{{k=1}}^n(2k-1)=\frac{{(2n)!}}{{2^nn!}}</math>.

Le '''nombre eulérien de seconde espèce''', noté <math> \left \langle \!\! \left \langle {n\atop m} \right \rangle \!\! \right \rangle,</math> 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:
:<math>332211,\;</math>
:<math> 221133,\; 221331,\;223311,\;233211,\;113322,  \;133221, \; 331122,\; 331221, </math>
:<math>112233,\; 122133,\;112332,\; 123321,\;133122,  \;122331.</math>

À partir de cette définition, on montre facilement que les nombres <math> \left \langle \!\! \left \langle {n\atop m} \right \rangle \!\! \right \rangle</math> vérifient la récurrence :
: <math> \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,</math>
avec les conditions initiales :
: <math> \left \langle \!\!\left \langle {0\atop m} \right \rangle \!\! \right \rangle =0\ </math> pour ''m'' > 0 et <math> \left \langle \!\!\left \langle {0\atop 0} \right \rangle \!\! \right \rangle =1 </math>.
On leur fait correspondre les polynômes eulériens de seconde espèce, notés ici <math>P_n</math> :
:<math>P_n(x):=\sum_{n=0}^n  \left \langle \!\! \left \langle {n\atop m} \right \rangle \!\! \right \rangle x^m</math> ;
des relations de récurrence précédentes, on déduit que les P<sub>n</sub>(x) vérifient la relation :
:<math>P_{n+1}(x)=(2nx+1)P_n(x)-x(x-1)P_n^\prime(x)</math>, avec <math>P_0(x)=1.</math>
On peut la réécrire :
:<math>(x-1)^{-2n-2}P_{n+1}(x)=\left(x(1-x)^{-2n-1}P_n(x)\right)^\prime</math> ;
ainsi la fonction rationnelle
:<math>u_n(x):=(x-1)^{-2n}P_{n}(x)</math>
satisfait :
:<math>u_{n+1}=\left(\frac{x}{1-x}u_n\right)^\prime\quad, u_0=1,</math>
d'où l'on tire les polynômes sous la forme P<sub>n</sub>(x)=(1-x)<sup>2n</sup>u<sub>n</sub>(x); puis les nombres eulériens de seconde espèce qui sont leurs coefficients.

Voici quelques valeurs de ces nombres (la {{OEIS|id=A008517}}) :
:{| class="wikitable"
|-
! n&nbsp;\&nbsp;m
! width="50" | 0
! width="50" | 1
! width="50" | 2
! width="50" | 3
! width="50" | 4
! width="50" | 5
! width="50" | 6
! width="50" | 7
! width="50" | 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 P<sub>n</sub>(1) = (2n-1)!!.

== Articles connexes ==
* [[Ensemble triangulaire]]
* [[Leonhard Euler]]
* [[Nombre de Stirling]]
* [[Triangle de Pascal]]

== Notes et références ==
=== Notes ===
{{Références}}
=== Références ===
{{Traduction/Référence|en|Eulerian number|403815568}}
* {{la}} {{Ouvrage|auteur=[[Leonhard Euler]]|url=http://www.math.dartmouth.edu/~euler/docs/originals/E212sec2ch7.pdf|titre={{lang|la|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)|éditeur=[[Académie des sciences de Russie|Academia imperialis scientiarum Petropolitana]]|année=1755|volume=II|numéro chapitre=VII}}
* {{en}} [[Ronald Graham]], [[Donald Knuth]] et [[Oren Patashnik]], ''[[Concrete Mathematics]] : A Foundation for Computer Science'', 1994 (deuxième édition), Addison-Wesley, p.&nbsp;267–272
== Liens externes ==
* {{en}} [http://oeis.org/wiki/Eulerian_polynomials Eulerian Polynomials] sur le [[wiki]] de l'[[OEIS]]
* {{en}} [http://www.mathpages.com/home/kmath012/kmath012.htm Eulerian Numbers] sur ''MathPages''
* {{MathWorld|titre=Eulerian Number|nom_url=EulerianNumber}}
* {{MathWorld|titre=Euler's Number Triangle|nom_url=EulersNumberTriangle}}
* {{MathWorld|titre=Worpitzky's Identity|nom_url=WorpitzkysIdentity}}
* {{MathWorld|titre=Second-Order Eulerian Triangle|nom_url=Second-OrderEulerianTriangle}}
* {{en}} [http://go.helms-net.de/math/binomial_new/01_12_Eulermatrix.pdf Triangle d'Euler] sur la page de Gottfried Helms, de l'[[université de Cassel]]
{{Portail|mathématiques}}

[[Catégorie:Triangle de nombres|Euler]]
[[Catégorie:Leonhard Euler]]
[[Catégorie:Combinatoire]]