# Nombre eulérien

En mathématiques, et plus précisément en 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 » ($0\leqslant k\leqslant n-1$)$^,$$^,$. Les nombres eulériens sont les coefficients des polynômes eulériens :
    ${\begin{aligned}&A_{n}=\sum _{k=0}^{n}{A(n,k)X^{k}}\\&A_{0}=A_{1}=1,A_{2}=1+X,A_{3}=1+4X+X^{2},\dotsc \end{aligned}}$
Ces polynômes apparaissent au numérateur d'expressions liées à la série génératrice de la suite 1$^n$, 2$^n$, 3$^n$, …{\textstyle 1^{n}, \ 2^{n}, \ 3^{n}, \ \dots }.
Ces nombres forment la suite A008292 de l'OEIS.
Les nombres A(n, k) sont aussi notés E(n, k) et $\left\langle {n \atop k}\right\rangle$.

## Historique

En 1755, dans son livre Institutiones calculi differentialis, Leonhard Euler a étudié les polynômes α$_1$(x) = 1,α$_2$(x) = x + 1, α$_3$(x) = x$^2$ + 4x + 1, etc. (voir le facsimilé ci-contre). Ce sont les polynômes eulériens A$_n$(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 k}\right\rangle$ 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 $\sigma$ de $\{1,2,..,n\}$ est l'un des $n-1$ couples $(\sigma (i),\sigma (i+1))$ tel que $\sigma (i)<\sigma (i+1)$ (resp. $\sigma (i)>\sigma (i+1)$).
Par exemple, la permutation ${\begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}}$ 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 $\sigma$ par $\sigma ^{-}(i)=n+1-i$, 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 ;
* $A(n,k)=A(n,n-k-1)$ (propriété de symétrie).

### Suites montantes

Une suite montante de $\sigma$ est une liste croissante d'entiers consécutifs maximale extraite de la liste $(\sigma (1),\sigma (2),\cdots ,\sigma (n))$. Par exemple, la permutation ${\begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}}$ possède trois suites montantes : $(1),(2,3),(4),(5)$.
Si une permutation possède k suites montantes, la permutation réciproque possède $k-1$ descentes. En effet, chaque passage d'une suite montante de $\sigma$ à la suivante provoque une descente pour $\sigma ^{-1}$. Regarder par exemple ${\begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}}^{-1}={\begin{pmatrix}1&2&3&4&5\\5&1&4&3&2\end{pmatrix}}$. On en déduit que :
* Le nombre A(n, k) est aussi le nombre de permutations présentant $k+1$ 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 ${\begin{pmatrix}1\\1\end{pmatrix}}$ A(1,0) = 1 2 0 ${\begin{pmatrix}1&2\\2&1\end{pmatrix}}$ A(2,0) = 1 1 ${\begin{pmatrix}1&2\\1&2\end{pmatrix}}$ A(2,1) = 1 3 0 ${\begin{pmatrix}1&2&3\\3&2&1\end{pmatrix}}$ A(3,0) = 1 1 ${\begin{pmatrix}1&2&3\\1&3&2\end{pmatrix}}$${\begin{pmatrix}1&2&3\\2&1&3\end{pmatrix}}$${\begin{pmatrix}1&2&3\\2&3&1\end{pmatrix}}$ ${\begin{pmatrix}1&2&3\\3&1&2\end{pmatrix}}$ A(3,1) = 4 2 ${\begin{pmatrix}1&2&3\\1&2&3\end{pmatrix}}$ 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 :
    $A(n,k)=(n-k)A(n-1,k-1)+(k+1)A(n-1,k).$$^,$.
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, k) pour $0\leqslant n\leqslant 9$ (cf. la suite A008292 de l'OEIS) sont :
    n \ k 0 1 2 3 4 5 6 7 8 0 1 1 1 2 11 3 141 4 111111 5 12666261 6 157302302571 7 11201191241611911201 8 12474293156191561942932471 9 1502146088823415619088234146085021
On a par exemple $A(n,1)=2^{n}-n-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
    $\sum _{k=0}^{n-1}A(n,k)=n!$
    $A(n,k)=A(n,n-1-k)$

### Formule explicite

Une formule explicite pour A(n, k) est :
    $A(n,k)=\sum _{i=0}^{k}(-1)^{i}{\binom {n+1}{i}}(k+1-i)^{n}.$

## 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 B$_{n+1}$
    $\sum _{k=0}^{n-1}(-1)^{k}A(n,k)={\frac {2^{n+1}(2^{n+1}-1)B_{n+1}}{n+1}}.$
Voici d'autres formules de sommation :
    $\sum _{k=0}^{n-1}(-1)^{k}{\frac {A(n,k)}{\binom {n-1}{k}}}=0,$
    $\sum _{k=0}^{n-1}(-1)^{k}{\frac {A(n,k)}{\binom {n}{k}}}=(n+1)B_{n},$
où B$_n$ est le nombre de Bernoulli de rang n.

## Identités

* L’identité de Worpitzky$^,$$^,$$^,$ exprime $x^{n}$ comme combinaison linéaire de nombres eulériens avec des coefficients binomiaux :
    $x^{n}=\sum _{k=0}^{n-1}A(n,k){\binom {x+k}{n}}$.
* On en déduit la série génératrice de la suite des puissances n-ièmes :
    $\sum _{i=1}^{\infty }i^{n}x^{i}={\frac {\sum _{k=0}^{n-1}A(n,k)x^{k+1}}{(1-x)^{n+1}}}={\frac {xA_{n}(x)}{(1-x)^{n+1}}}$.
* On en déduit :
    $\sum _{n=0}^{\infty }{\frac {A_{n}(x)}{n!(1-x)^{n+1}}}=\sum _{n=0}^{\infty }\sum _{k=1}^{\infty }{\frac {k^{n}}{n!}}x^{k-1}=\sum _{k=1}^{\infty }\mathrm {e} ^{k}x^{k-1}={\frac {\mathrm {e} }{1-\mathrm {e} x}}$ en intervertissant les deux signes de sommations pour $|x|<{\frac {1}{\mathrm {e} }}$.
* Plus généralement, on a :
    $\sum _{n=0}^{\infty }A_{n}(x)\,{\frac {t^{n}}{n!}}={\frac {x-1}{x-\mathrm {e} ^{(x-1)\,t}}}$
* Une identité remarquable 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 $(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}^{n}U_{k},\quad X_{n}=\left\lfloor S_{n}\right\rfloor$,
    alors
    $\mathbb {P} \left(k\leqslant 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 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 $(2n-1)!!=\prod _{k=1}^{n}(2k-1)={\frac {(2n)!}{2^{n}n!}}$.
Le nombre eulérien de seconde espèce, noté $\left\langle \!\!\left\langle {n \atop k}\right\rangle \!\!\right\rangle ,$ dénombre celles de ces permutations ayant exactement k 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 k}\right\rangle \!\!\right\rangle$ vérifient la récurrence :
    $\left\langle \!\!\left\langle {n \atop k}\right\rangle \!\!\right\rangle =(2n-k-1)\left\langle \!\!\left\langle {{n-1} \atop {k-1}}\right\rangle \!\!\right\rangle +(k+1)\left\langle \!\!\left\langle {{n-1} \atop {k}}\right\rangle \!\!\right\rangle ,$
avec les conditions initiales :
    $\left\langle \!\!\left\langle {0 \atop k}\right\rangle \!\!\right\rangle =0\ \mathrm {pour} \ k>0\ \ \mathrm {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 P$_n$ :
    $P_{n}(x):=\sum _{k=0}^{n}\left\langle \!\!\left\langle {n \atop k}\right\rangle \!\!\right\rangle x^{k}$ ;
des relations de récurrence précédentes, on déduit que les P$_n$ vérifient la relation :
    $P_{n+1}(x)=(2nx+1)P_{n}(x)-x(x-1)P_{n}^{\prime }(x),\ \mathrm {avec} \ P_{0}(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
    $u_{n}(x):=(x-1)^{-2n}P_{n}(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 P$_n$(x) = (1 − x)$^{2n}$u$_n$(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 12 3 186 4 1225824 5 152328444120 6 1114145244003708720 7 124056103212058140339845040 8 14941995019580064402078530434113640320 9 11004672601062500576550012440064110262963733920362880
La somme de la ligne de rang n est P$_n$(1) = (2n − 1)!!.