Permutation alternée

En mathématiques, et plus particulièrement en combinatoire, une permutation alternée (ou permutation en zigzag ) sur l'ensemble ${\displaystyle \{1,2,3,...,n\}}$ est une permutation ${\displaystyle \sigma }$ dont le résultat ${\displaystyle (\sigma (1),\sigma (2),\cdots ,\sigma (n))}$ est tel que chaque terme est alternativement supérieur ou inférieur au terme précédent ; autrement dit, les ${\displaystyle n-1}$ différences : ${\displaystyle \sigma (2)-\sigma (1),\sigma (3)-\sigma (2),\cdots ,\sigma (n)-\sigma (n-1)}$, ont des signes alternés.

Comme à toute permutation alternée commençant par une montée (${\displaystyle \sigma (2)>\sigma (1)}$), dite "ascendante", correspond une permutation alternée commençant par une descente (définie par ${\displaystyle \sigma '(k)=n+1-\sigma (k)}$), et réciproquement, on ne considère en général que les permutations ascendantes^[1]. Par exemple, pour ${\displaystyle n=4}$, les cinq permutations alternées ascendantes ont pour résultats :

• (1, 3, 2, 4) : 1 < 3 > 2 < 4,
• (1, 4, 2, 3) : 1 < 4 > 2 < 3,
• (2, 3, 1, 4) : 2 < 3 > 1 < 4,
• (2, 4, 1, 3) : 2 < 4 > 1 < 3, et
• (3, 4, 1, 2) : 3 < 4 > 1 < 2.

Ce type de permutation a été étudié par Désiré André en 1881^[2],[3]. Le problème d'André consiste en la détermination du nombre ${\displaystyle A_{n}}$ de permutations alternées ascendantes de longueur ${\displaystyle n}$. Les nombres ${\displaystyle A_{n}}$ sont appelés nombres zigzag. Lorsque ${\displaystyle n}$ est pair, le nombre ${\displaystyle A_{n}}$ est dit sécant, et tangent pour ${\displaystyle n}$ impair. Ceci vient de la fonction génératrice exponentielle de la suite qui fait intervenir les fonctions sécante et tangente.

Par convention, l'unique permutation de longueur 0 (la permutation de l'ensemble vide ) et l'unique permutation de longueur 1 sont considérées comme alternées.

Les premières valeurs de ${\displaystyle A_{n}}$ en commençant à ${\displaystyle n=0}$ sont : 1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, ... : suite A000111 de l'OEIS.

Si ${\displaystyle Z_{n}}$ désigne le nombre de permutations alternées de longueur ${\displaystyle n}$, ascendantes ou descendantes, il résulte de l'appariement donné ci-dessus que ${\displaystyle Z_{n}=2A_{n}}$ pour ${\displaystyle n\geqslant 2}$. Les premières valeurs de ${\displaystyle Z_{n}}$ sont 1, 1, 2, 4, 10, 32, 122, 544, 2770, 15872, 101042, ... suite A001250 de l'OEIS.

Les nombres zigzag satisfont une relation de récurrence forte similaire à celle des nombres de Catalan : en classant les permutations alternées (montantes ou descendantes) de longueur ${\displaystyle n+1}$ suivant la valeur ${\displaystyle k}$ du dernier terme, on montre que pour tout ${\displaystyle n\geqslant 1}$^[2],[1] :

${\displaystyle 2A_{n+1}=\sum _{k=0}^{n}{\binom {n}{k}}A_{k}A_{n-k}\,(1)}$.

André a utilisé cette formule de récurrence pour obtenir une équation différentielle satisfaite par la fonction génératrice exponentielle de la suite ${\displaystyle (A_{n})}$ :

${\displaystyle A(x)=\sum _{n=0}^{\infty }A_{n}{\frac {x^{n}}{n!}}}$

En effet, (1) permet d'écrire :

${\displaystyle 2\sum _{n\geqslant 1}A_{n+1}{\frac {x^{n+1}}{(n+1)!}}=\sum _{n\geqslant 1}\sum _{k=0}^{n}{\frac {A_{k}}{k!}}{\frac {A_{n-k}}{(n-k)!}}{\frac {x^{n+1}}{n+1}}=\int \left(\sum _{k\geqslant 0}A_{k}{\frac {x^{k}}{k!}}\right)\left(\sum _{j\geqslant 0}A_{j}{\frac {x^{j}}{j!}}\right)\,dx-x}$

où l'on a effectué les substitutions ${\displaystyle j=n-k}$ et ${\displaystyle {\frac {x^{n+1}}{n+1}}=\int x^{k+j}\,dx}$. Ceci donne l'équation intégrale :

${\displaystyle 2(A(x)-1-x)=\int A^{2}(x)\,dx-x,}$

qui après dérivation donne l'équation différentielle ${\displaystyle A'={\frac {1}{2}}(A^{2}+1)}$.

Par séparation des variables, on obtient ${\displaystyle \arctan(A(x))={\frac {x}{2}}+\lambda }$, ce qui donne, avec la condition initiale ${\displaystyle A(0)=A_{0}/0!=1}$, la solution :

${\displaystyle A(x)=\tan \left({\frac {x}{2}}+{\frac {\pi }{4}}\right)={\frac {1+\sin x}{\cos x}}=\sec x+\tan x}$,

somme des fonctions sécante et tangente. Ce résultat est connu sous le nom de théorème d'André. Une interprétation géométrique de ce résultat peut être donnée en utilisant une généralisation d'un théorème de Johann Bernoulli^[4].

Il résulte du théorème d'André que le rayon de convergence de la série ${\displaystyle \sum _{n=0}^{\infty }A_{n}{\frac {x^{n}}{n!}}}$ est égal à ${\displaystyle \pi /2}$.

Cela permet d'obtenir l'équivalent :

${\displaystyle A_{n}\sim 2\left({\frac {2}{\pi }}\right)^{n+1}n!\ }$

ainsi que ${\displaystyle \pi =\lim {\frac {2nA_{n}}{A_{n-1}}}}$.

Les nombres zigzag d'indice impair (ou nombres tangents) ${\displaystyle A_{2n+1}}$ peuvent être définis par la relation : ${\displaystyle \operatorname {tan} x=\sum _{n=0}^{\infty }A_{2n+1}{\frac {x^{2n+1}}{(2n+1)!}},|x|<\pi /2.}$

Les premières valeurs sont 1, 2, 16, 272, 7936, ... (suite A000182 de l'OEIS). Ils sont étroitement liés aux nombres de Bernoulli par la formule :

${\displaystyle B_{2n}=(-1)^{n-1}{\frac {2n}{4^{2n}-2^{2n}}}A_{2n-1}}$

pour ${\displaystyle n\geqslant 1}$.

Les nombres ${\displaystyle A_{2n}}$ d'indices pairs (ou nombres sécants), sont les nombres d'Euler, définis par la relation :

${\displaystyle \sec x=\sum _{n=0}^{\infty }A_{2n}{\frac {x^{2n}}{(2n)!}},|x|<\pi /2.}$

Les premières valeurs sont 1, 1, 5, 61, 1385, 50521, ... suite A000364 de l'OEIS.

Les nombres de permutations alternées ${\displaystyle \sigma }$ sur ${\displaystyle \{1,2,\cdots ,n+1\}}$ commençant par une descente et telles que ${\displaystyle \sigma (1)=k+1}$ , notés ${\displaystyle E(n,k)}$ (nombres d'Entringer), peuvent se calculer par récurrence comme suit^[5],[6],[3]:

${\displaystyle E(0,0)=1}$

${\displaystyle E(n,0)=0\qquad {\mbox{pour }}n>0}$

${\displaystyle E(n,k)=E(n,k-1)+E(n-1,n-k){\mbox{ pour }}1\leqslant k\leqslant n}$.

Le nombre d'Entringer ${\displaystyle E(n,n)}$ n'est alors autre que le nombre zigzag ${\displaystyle A_{n}}$, qui s'obtient donc par simple succession d'additions.

La somme des inverses des nombres impairs élevés à la puissance ${\displaystyle n\geqslant 1}$, alternée lorsque ${\displaystyle n}$ est impair, s'exprime simplement à partir des nombres zigzag par la formule : ${\displaystyle \sum _{k=0}^{+\infty }{\frac {(-1)^{kn}}{(2k+1)^{n}}}={\frac {\pi ^{n}}{2^{n+1}(n-1)!}}A_{n-1}}$.

Partant de la relation ${\displaystyle \sum _{n=1}^{\infty }A_{n-1}{\frac {x^{n}}{n!}}=\int _{0}^{x}(\sec t+\tan t)dt=-\ln(1-\sin x)}$, on obtient ^[7]

${\displaystyle A_{n}=\sum _{k=1}^{n+1}\sum _{j=0}^{k}(-1)^{j}{\binom {k}{j}}{\frac {(k-2j)^{n+1}}{k.2^{k}}}{\text{i}}^{n+1-k}}$.

Les relations des nombres zigzag avec les nombres d'Euler et les nombres de Bernoulli peuvent être utilisées pour prouver ce qui suit^[8],[9]

${\displaystyle A_{r}=-{\frac {4^{r}}{a_{r}}}\sum _{k=1}^{r}{\frac {(-1)^{k}\,S(r,k)}{k+1}}\left({\frac {3}{4}}\right)^{(k)}}$

où

${\displaystyle a_{r}={\begin{cases}(-1)^{\frac {r-1}{2}}(1+2^{-r})&{\mbox{pour r impair}}\\(-1)^{\frac {r}{2}}&{\mbox{pour r pair}}\end{cases}},}$

${\displaystyle (x)^{(n)}=(x)(x+1)\cdots (x+n-1)}$ désigne la factorielle croissante, et ${\displaystyle S(r,k)}$ désigne les nombres de Stirling de seconde espèce..

• Transformation du Boustrophédon

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Alternating permutation » (voir la liste des auteurs).

• Henry et Wanner, « Zigzags with Bürgi, Bernoulli, Euler and the Seidel–Entringer–Arnol’d triangle », Elemente der Mathematik, vol. 74, n^o 4,‎ 2019, p. 141–168 (DOI 10.4171/EM/393).
• (en) Eric W. Weisstein, « Alternating Permutation », sur MathWorld
• "A Survey of Alternating Permutations", preprint de Richard P. Stanley

• Portail des mathématiques