Nombre eulérien
# 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 » ($0\leqslant k\leqslant n-1$$)^,^,.$ Les nombres eulériens sont les coefficients des polynômes eulériens :

    $A_{n}(X)=\sum _{k=0}^{n}A(n,k)\ X^{k}\quad (A_{0}(X)=A_{1}(X)=1,A_{2}(X)=1+X,A_{3}(X)=1+4X+X^{2},\dots )$.

Ces polynômes apparaissent au numérateur d'expressions liées à la fonction 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

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 fonction 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)!!.

