En mathématiques, et plus précisément en combinatoire, le nombre eulérien (), est le nombre de permutations des entiers de 1 à pour lesquelles exactement éléments sont plus grands que l'élément précédent (permutations avec « montées » (). Les nombres eulériens sont les coefficients des polynômes eulériens :
Ces polynômes apparaissent au numérateur d'expressions liées à la série génératrice de la suite .
Ces nombres forment la .
Les nombres sont aussi notés et .
Historique vignette|Euler, Institutiones calculi differentialis, , 1755 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.
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 () est aussi le nombre de permutations présentant 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 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 () est aussi le nombre de permutations présentant suites montantes.
Détermination du triangle d'Euler Pour un strictement positif donné, le nombre de descentes d'une permutation est compris entre 0 et − 1. Pour fixé, il y a une et une seule permutation sans descente, à savoir l'identité, et une et une seule permutation avec − 1 montées, à savoir le renversement rencontré ci-dessus, défini par pour tout . Ainsi, A(, 0) = A(, − 1) = 1 pour tout .
Les valeurs de () peuvent être calculées « à la main » pour de petites valeurs de et .
{| class="wikitable" |- ! n ! k ! Permutations ! A(n, k) |- | 1 | 0 | | A(1,0) = 1 |- | rowspan="2" | 2 | 0 | | A(2,0) = 1 |- | 1 | | A(2,1) = 1 |- | rowspan="3" | 3 | 0 | | A(3,0) = 1 |- | 1
| A(3,1) = 4 |- | 2 | | A(3,2) = 1
Pour des valeurs plus grandes de , () peut être calculé à l'aide de la relation de récurrence. : .
Par exemple
Les valeurs de () pour (cf. la ) sont : {| class="wikitable" |- ! n \ k ! 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
On a par exemple pour tout ().
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 est le nombre des permutations de objets, soit la factorielle !. De plus, nous avons une relation de symétrie, soit pour > 0, nous avons
et . On en déduit que le polynôme eulérien est un polynôme réciproque : .
Formule explicite Une formule explicite pour () est :
Calculs de sommes La somme alternée des nombres eulériens pour une valeur donnée de est liée au nombre de Bernoulli Bn+1
Voici d'autres formules de sommation :
où Bn est le nombre de Bernoulli de rang .
Identités L’identité de Worpitzky exprime comme combinaison linéaire de nombres eulériens avec des coefficients binomiaux : . On en déduit la série génératrice de la suite des puissances -ièmes : , ce que l'on peut aussi écrire : . On en déduit : en intervertissant les deux signes de sommations pour . Plus généralement, on a :
Une identité remarquablevoir ou bien . 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 , tous les nombres entre les deux occurrences de sont plus grands que , est le produit des entiers impairs jusqu'à (appelé parfois la double factorielle de , et noté ) ; on a : .
Le nombre eulérien de seconde espèce, noté dénombre celles de ces permutations ayant exactement montées. Par exemple, pour = 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:
À partir de cette définition, on montre facilement que les nombres satisfont à la récurrence :
avec les conditions initiales : . On leur fait correspondre les polynômes eulériens de seconde espèce, notés ici : ; des relations de récurrence précédentes, on déduit que les vérifient la relation :
On peut la réécrire : ; ainsi la fonction rationnelle
est caractérisée par la relation de récurrence
d'où l'on tire les polynômes sous la forme ; puis les nombres eulériens de seconde espèce qui sont leurs coefficients.
Voici quelques valeurs de ces nombres ( ). {| class="wikitable" |- ! n \ 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 ligne de rang est .
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
Références
Bibliographie
. . — Version révisée de 2005.
Liens externes Eulerian Polynomials sur le wiki de l'OEIS Eulerian Numbers sur MathPages
Triangle d'Euler sur la page de Gottfried Helms, de l'université de Cassel
Euler Catégorie:Leonhard Euler Catégorie:Combinatoire