Permutation alternée

En mathématiques, et plus particulièrement en combinatoire, une permutation alternée (ou permutation en zigzag ) de l'ensemble $\{1,2,3,...,n\}$ est une permutation $\sigma$ dont le résultat $(\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 $n-1$ différences : $\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 ($\sigma (2)>\sigma (1)$), dite "ascendante", correspond une permutation alternée commençant par une descente ($\sigma '(k)=\sigma (n+1-k)$), et réciproquement, on ne considère en général que les permutations ascendantes. Par exemple, pour $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. Le problème d'André consiste en la détermination du nombre $A_{n}$ de permutations alternées montantes de longueur $n$. Les nombres $A_{n}$ sont appelés nombres zigzag. Lorsque $n$ est pair, le nombre $A_{n}$ est dit sécant, et tangent pour $n$ impair. Ceci vient de la fonction génératrice exponentielle de la suite qui fait intervenir les fonctions sécante et tangente.

Les nombres zigzag dans Bernoulli (1742), Opera Omnia vol. 4, p. 105

Expression des nombres zigzag

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 $A_{n}$ en commençant à $n=0$ sont : 1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, ... : suite A000111 de l'OEIS.

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

Théorème d'André

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 $n+1$ suivant la valeur $k$ du dernier terme, on montre que pour tout $n\geqslant 1$ :

$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 $(A_{n})$ :

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

En effet, (1) permet drécrire :

$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 $j=n-k$ et ${\frac {x^{n+1}}{n+1}}=\int x^{k+j}\,dx$. Ceci donne l'équation intégrale :

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

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

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

$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.

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

Cela permet d'obtenir l'équivalent :

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

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

Obtention des nombres zigzag

Par série génératrice

Les nombres zigzag d'indice impair (ou nombres tangents) $A_{2n+1}$ peuvent être définis par $\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 :

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

pour $n\geqslant 1$.

Les nombres $A_{2n}$ d'indices pairs (ou nombres sécants), sont les nombres d'Euler définis par $\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.

Par l'algorithme boustrophédon

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

$E(0,0)=1$

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

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

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

Application à l'expression de la somme des inverses des nombres impairs à la puissance n

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

Démonstration

Le développement d'Euler en somme d’éléments simples de la fonction sécante : $\sec x=4\pi \sum _{k=0}^{+\infty }{\frac {(-1)^{k}(2k+1)}{(2k+1)^{2}\pi ^{2}-(2x)^{2}}}$ se transforme en :

$\sec x=4\pi \sum _{k=0}^{+\infty }{\frac {(-1)^{k}(2k+1)}{(2k+1)^{2}\pi ^{2}}}{\frac {1}{1-\left({\frac {2x}{(2k+1)\pi }}\right)^{2}}}=4\pi \sum _{k=0}^{+\infty }{\frac {(-1)^{k}(2k+1)}{(2k+1)^{2}\pi ^{2}}}\sum _{p=0}^{+\infty }\left({\frac {2x}{(2k+1)\pi }}\right)^{2p}=\sum _{p=0}^{+\infty }{\frac {2^{2p+2}}{\pi ^{2p+1}}}\sum _{k=0}^{+\infty }{\frac {(-1)^{k}}{(2k+1)^{2p+1}}}x^{2p}$.

donc ${\frac {2^{2p+2}}{\pi ^{2p+1}}}\sum _{k=0}^{+\infty }{\frac {(-1)^{k}}{(2k+1)^{2p+1}}}={\frac {A_{2p}}{(2p)!}}$, et $\sum _{k=0}^{+\infty }{\frac {(-1)^{k}}{(2k+1)^{2p+1}}}={\frac {\pi ^{2p+1}}{2^{2p+2}}}{\frac {A_{2p}}{(2p)!}}$, ce qui donne la formule attendue pour $n=2p+1$.

La démonstration pour $n$ pair se trouve dans l'article : Développement en éléments simples en analyse complexe.

Formule explicite utilisant uniquement les coefficients binomiaux

Partant de la relation $\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

$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}$.

Formule explicite utilisant les nombres de Stirling de seconde espèce

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

$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ù

$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}},$

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

Voir aussi

• Transformation du Boustrophédon

Références

• (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).

Liens externes

• 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