Nombre eulérien
![Page d’aide sur l’homonymie](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Logo_disambig.svg/20px-Logo_disambig.svg.png)
Pour les articles homonymes, voir Nombres d'Euler.
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 » ()[1],[2],[3]. Les nombres eulériens sont les coefficients des polynômes eulériens :
- .
Ces polynômes apparaissent au numérateur d'expressions liées à la fonction génératrice de la suite .
Ces nombres forment la suite A008292 de l'OEIS.
Les nombres A(n, k) sont aussi notés E(n, k) et
Historique
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/43/EulerianPolynomialsByEuler1755.png/220px-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). Ce sont les polynômes eulériens An(x).
Par analogie avec la notation des coefficients binomiaux et avec celle des nombres de Stirling et la notation 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 de est l'un des couples tel que (resp. ).
Par exemple, la permutation 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 par , 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.
- (propriété de symétrie)
Suites montantes
Une suite montante de est une liste croissante d'entiers consécutifs maximale extraite de la liste . Par exemple, la permutation possède trois suites montantes : .
Si une permutation possède k suites montantes, la permutation réciproque possède descentes. En effet, chaque passage d'une suite montante de à la suivante provoque une descente pour . Regarder par exemple . On en déduit que :
- Le nombre A(n, k) est aussi le nombre de permutations présentant 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 A(1,0) = 1 2 0 A(2,0) = 1 1 A(2,1) = 1 3 0 A(3,0) = 1 1 A(3,1) = 4 2 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].
Par exemple
Les valeurs de A(n, k) pour (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
Formule explicite
Une formule explicite pour A(n, k) est
- [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 Bn+1
Voici d'autres formules de sommation :
où Bn est le nombre de Bernoulli de rang n.
Identités
- L’identité de Worpitzky[2],[4],[3],[5] exprime comme combinaison linéaire de nombres eulériens avec des coefficients binomiaux :
- .
- On en déduit la fonction génératrice de la suite des puissances n-ièmes :
- .
- On en déduit :
- en intervertissant les deux signes de sommations pour .
- Plus généralement, on a[4] :
- 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 est une suite de variables aléatoires i.i.d. uniformes sur [0, 1] et si
- ,
- alors
- .
Nombres eulériens de seconde espèce
Le nombre des permutations du multiensemble 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 .
Le nombre eulérien de seconde espèce, noté 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:
À partir de cette définition, on montre facilement que les nombres vérifient la récurrence :
avec les conditions initiales :
- .
On leur fait correspondre les polynômes eulériens de seconde espèce, notés ici Pn :
- ;
des relations de récurrence précédentes, on déduit que les Pn vérifient la relation :
On peut la réécrire :
- ;
ainsi la fonction rationnelle
satisfait :
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 ( 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 Pn(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
- ↑ (en) Ronald Graham, Donald Knuth et Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science, Addison Wesley, , p. 267–272
- ↑ a et b Ronald Graham, Donald Knuth et Oren Patashnik (trad. Alain Denise), Mathématiques concrètes, Thomson, , p. 283-286
- ↑ a b c et d Louis Comtet, Analyse combinatoire, tome second, PUF, , p. 82-85
- ↑ a b c et d Donald Knuth, The Art of Computer Programming, vol. 3, (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, , p. 203-232 (lire en ligne)
- ↑ voir (en) Stephen Tanny, « A probabilistic interpretation of the Eulerian numbers », Duke Math. J., vol. 40, , p. 717-722 ou bien (en) Richard P. Stanley, « Eulerian partitions of a unit hypercube », Higher Combinatorics, Dordrecht, M. Aigner, ed., Reidel, .
- ↑ Ronald Graham, Donald Knuth et Oren Patashnik, Mathématiques concrètes, Thomson, , 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, (lire en ligne), chap. VII
- (en) Ronald Graham, Donald Knuth et Oren Patashnik, Concrete Mathematics : A Foundation for Computer Science, Addison-Wesley, , 2e é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 » (no 138), , 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