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 » (). 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 . Les nombres A(n, k) sont aussi notés E(n, k) et 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. 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) 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. Pour un n donné > 0, l'indice k de A(n, k) peut aller de 0 à k − 1.