Nombre eulérien

Modèle:HomonEn mathématiques, et plus précisément en combinatoire, le nombre eulérien Modèle:Mvar(Modèle:Mvar), est le nombre de permutations des entiers de 1 à Modèle:Mvar pour lesquelles exactement Modèle:Mvar éléments sont plus grands que l'élément précédent (permutations avec Modèle:Mvar « montées » ($0⩽k⩽n-1$)Modèle:,Modèle:,. Les nombres eulériens sont les coefficients des polynômes eulériens :

$\begin{array}{cc}& 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,\dots \end{array}$

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,\dots$.

Ces nombres forment la Modèle:OEIS.

Les nombres Modèle:Math sont aussi notés Modèle:Math et $⟨\genfrac{}{}{0ex}{}{n}{k}⟩$.

Historique

Euler, Institutiones calculi differentialis, Modèle:2e, 1755

En 1755, dans son livre Institutiones calculi differentialis, Leonhard Euler a étudié les polynômes α₁(x) = 1,α₂(x) = x + 1, α₃(x) = x² + 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(\genfrac{}{}{0ex}{}{n}{k}\right)$ et avec celle des nombres de Stirling $\left[\genfrac{}{}{0ex}{}{n}{k}\right]$ et $\left\{\genfrac{}{}{0ex}{}{n}{k}\right\},$ la notation $⟨\genfrac{}{}{0ex}{}{n}{k}⟩$ 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 $\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 2& 5& 4& 3& 1\end{array}\right)$ 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 Modèle:Mvar(Modèle:Mvar) est aussi le nombre de permutations présentant Modèle:Mvar 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 $\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 2& 5& 4& 3& 1\end{array}\right)$ possède trois suites montantes : $(1),(2,3),(4),(5)$.

Si une permutation possède Modèle:Mvar 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 ${\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 2& 5& 4& 3& 1\end{array}\right)}^{-1}=\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 5& 1& 4& 3& 2\end{array}\right)$. On en déduit que :

• Le nombre Modèle:Mvar(Modèle:Mvar) est aussi le nombre de permutations présentant $k+1$ suites montantes.

Détermination du triangle d'Euler

Pour un Modèle:Mvar donné  > 0, l'indice Modèle:Mvar de Modèle:Mvar(Modèle:Mvar) peut aller de 0 à Modèle:Mvar − 1. Pour Modèle:Mvar fixé, il y a une seule permutation sans descente, et une seule permutation avec Modèle:Mvar − 1 montées, la permutation identique (ou montante). Ainsi, A(Modèle:Mvar, 0) = A(Modèle:Mvar, Modèle:Mvar − 1) = 1 pour tout Modèle:Mvar.

Les valeurs de Modèle:Mvar(Modèle:Mvar) peuvent être calculées « à la main » pour de petites valeurs de Modèle:Mvar et Modèle:Mvar. Par exemple :

n	k	Permutations	A(n, k)
1	0	$\left(\begin{array}{c}1\\ 1\end{array}\right)$	A(1,0) = 1
2	0	$\left(\begin{array}{cc}1& 2\\ 2& 1\end{array}\right)$	A(2,0) = 1
	1	$\left(\begin{array}{cc}1& 2\\ 1& 2\end{array}\right)$	A(2,1) = 1
3	0	$\left(\begin{array}{ccc}1& 2& 3\\ 3& 2& 1\end{array}\right)$	A(3,0) = 1
	1	$\left(\begin{array}{ccc}1& 2& 3\\ 1& 3& 2\end{array}\right)$$\left(\begin{array}{ccc}1& 2& 3\\ 2& 1& 3\end{array}\right)$$\left(\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\end{array}\right)$ $\left(\begin{array}{ccc}1& 2& 3\\ 3& 1& 2\end{array}\right)$	A(3,1) = 4
	2	$\left(\begin{array}{ccc}1& 2& 3\\ 1& 2& 3\end{array}\right)$	A(3,2) = 1

Pour des valeurs plus grandes de Modèle:Mvar, Modèle:Mvar(Modèle:Mvar) 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).$Modèle:,.

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 Modèle:Mvar(Modèle:Mvar) pour $0⩽n⩽9$ (cf. la Modèle: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

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 Modèle:Mvar est le nombre des permutations de Modèle:Mvar objets, soit la factorielle Modèle:Mvar!. De plus, nous avons une relation de symétrie, soit pour Modèle:Mvar 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 Modèle:Mvar(Modèle:Mvar) est :

$A(n,k)=\sum _{i=0}^k(-1{)}^i(\genfrac{}{}{0ex}{}{n+1}{i})(k+1-i{)}^n.$

Calculs de sommes

La somme alternée des nombres eulériens pour une valeur donnée de Modèle:Mvar 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)}{(\genfrac{}{}{0ex}{}{n-1}{k})}=0,$

$\sum _{k=0}^{n-1}(-1{)}^k\frac{A(n,k)}{(\genfrac{}{}{0ex}{}{n}{k})}=(n+1)B_n,$

où B_n est le nombre de Bernoulli de rang Modèle:Mvar.

Identités

• L’identité de WorpitzkyModèle:,Modèle:,Modèle:, 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)(\genfrac{}{}{0ex}{}{x+k}{n})$.

• On en déduit la série génératrice de la suite des puissances Modèle:Mvar-ièmes :

  $\sum _{i=1}^{\mathrm{\infty }}{i}^n{x}^i=\frac{\sum _{k=0}^{n-1}A(n,k)x^{k+1}}{(1-x{)}^{n+1}}=\frac{x{A}_n(x)}{(1-x{)}^{n+1}}$.

• On en déduit :

  $\sum _{n=0}^{\mathrm{\infty }}\frac{A_n(x)}{n!(1-x{)}^{n+1}}=\sum _{n=0}^{\mathrm{\infty }}\sum _{k=1}^{\mathrm{\infty }}\frac{k^n}{n!}{x}^{k-1}=\sum _{k=1}^{\mathrm{\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}^{\mathrm{\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,X_n=\lfloor S_n\rfloor$,

alors

$\mathbb{P}(k⩽S_n<k+1)=\mathbb{P}(X_n=k)=\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 Modèle:Mvar, tous les nombres entre les deux occurrences de Modèle:Mvar sont plus grands que Modèle:Mvar, est le produit des entiers impairs jusqu'à Modèle:Math (appelé parfois la double factorielle de Modèle:Math, et noté Modèle:Math) ; on a $(2n-1)!!=\prod _{k=1}^n(2k-1)=\frac{(2n)!}{2^{n}n!}$.

Le nombre eulérien de seconde espèce, noté $⟨⟨\genfrac{}{}{0ex}{}{n}{k}⟩⟩,$ dénombre celles de ces permutations ayant exactement Modèle:Mvar montées. Par exemple, pour Modèle:Mvar = 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 $⟨⟨\genfrac{}{}{0ex}{}{n}{k}⟩⟩$ vérifient la récurrence :

$⟨⟨\genfrac{}{}{0ex}{}{n}{k}⟩⟩=(2n-k-1)⟨⟨\genfrac{}{}{0ex}{}{n-1}{k-1}⟩⟩+(k+1)⟨⟨\genfrac{}{}{0ex}{}{n-1}{k}⟩⟩,$

avec les conditions initiales :

$⟨⟨\genfrac{}{}{0ex}{}{0}{k}⟩⟩=0\mathrm{p}\mathrm{o}\mathrm{u}\mathrm{r}k>0\mathrm{e}\mathrm{t}⟨⟨\genfrac{}{}{0ex}{}{0}{0}⟩⟩=1$.

On leur fait correspondre les polynômes eulériens de seconde espèce, notés ici Modèle:Mvar :

$P_n(x):=\sum _{k=0}^n⟨⟨\genfrac{}{}{0ex}{}{n}{k}⟩⟩x^k$ ;

des relations de récurrence précédentes, on déduit que les Modèle:Mvar vérifient la relation :

$P_{n+1}(x)=(2nx+1)P_n(x)-x(x-1)P_n^{\prime }(x),\mathrm{a}\mathrm{v}\mathrm{e}\mathrm{c}{P}_0(x)=1.$

On peut la réécrire :

$(x-1{)}^{-2n-2}{P}_{n+1}(x)={(x(1-x{)}^{-2n-1}{P}_n(x))}^{\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 },u_0=1,$

d'où l'on tire les polynômes sous la forme Modèle:Math ; puis les nombres eulériens de seconde espèce qui sont leurs coefficients.

Voici quelques valeurs de ces nombres ( Modèle: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 Modèle:Mvar est Modèle:Math.

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

Bibliographie

• Modèle:Ouvrage
• Modèle:Ouvrage.
• Modèle:Ouvrage. — Version révisée de 2005.

Liens externes

• Modèle:En Eulerian Polynomials sur le wiki de l'OEIS
• Modèle:En Eulerian Numbers sur MathPages
• Modèle:MathWorld
• Modèle:MathWorld
• Modèle:MathWorld
• Modèle:MathWorld
• Modèle:En Triangle d'Euler sur la page de Gottfried Helms, de l'université de Cassel