Permutation alternée

En mathématiques, et plus particulièrement en combinatoire, une permutation alternée (ou permutation en zigzag ) sur 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 (définie par ${\sigma }^{\prime }(k)=n+1-\sigma (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 1881Modèle:,. Le problème d'André consiste en la détermination du nombre $A_n$ de permutations alternées ascendantes 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, ... : Modèle: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⩾2$. Les premières valeurs de $Z_n$ sont 1, 1, 2, 4, 10, 32, 122, 544, 2770, 15872, 101042, ... Modèle: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⩾1$Modèle:, :

$2A_{n+1}=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{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}^{\mathrm{\infty }}{A}_n\frac{x^n}{n!}$

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

$2\sum _{n⩾1}{A}_{n+1}\frac{x^{n+1}}{(n+1)!}=\sum _{n⩾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⩾0}{A}_k\frac{x^k}{k!}\right)\left(\sum _{j⩾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^{\prime }=\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 (\frac{x}{2}+\frac{\pi }{4})=\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}^{\mathrm{\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{2n{A}_{n-1}}{A_n}$.

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 la relation : $\tan x=\sum _{n=0}^{\mathrm{\infty }}{A}_{2n+1}\frac{x^{2n+1}}{(2n+1)!},|x|<\pi /2.$

Les premières valeurs sont 1, 2, 16, 272, 7936, ... (Modèle: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⩾1$.

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

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

Les premières valeurs sont 1, 1, 5, 61, 1385, 50521, ... Modèle:OEIS.

Par l'algorithme boustrophédon

Les nombres de permutations alternées $\sigma$ sur $\{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 suitModèle:,Modèle:,:

$E(0,0)=1$

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

$E(n,k)=E(n,k-1)+E(n-1,n-k)\text{ pour }1⩽k⩽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⩾1$, alternée lorsque $n$ est impair, s'exprime simplement à partir des nombres zigzag par la formule : $\sum _{k=0}^{+\mathrm{\infty }}\frac{(-1{)}^{kn}}{(2k+1{)}^n}=\frac{{\pi }^n}{2^{n+1}(n-1)!}{A}_{n-1}$.

Le développement d'Euler en somme d’éléments simples de la fonction sécante :

$\sec x=4\pi \sum _{k=0}^{+\mathrm{\infty }}\frac{(-1{)}^k(2k+1)}{(2k+1{)}^2{\pi }^2-(2x{)}^2}$ se transforme en :

$\sec x=4\pi \sum _{k=0}^{+\mathrm{\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}^{+\mathrm{\infty }}\frac{(-1{)}^k(2k+1)}{(2k+1{)}^2{\pi }^2}\sum _{p=0}^{+\mathrm{\infty }}{\left(\frac{2x}{(2k+1)\pi }\right)}^{2p}=\sum _{p=0}^{+\mathrm{\infty }}\frac{2^{2p+2}}{{\pi }^{2p+1}}\sum _{k=0}^{+\mathrm{\infty }}\frac{(-1{)}^k}{(2k+1{)}^{2p+1}}{x}^{2p}$.

donc, en identifiant terme à terme, $\frac{2^{2p+2}}{{\pi }^{2p+1}}\sum _{k=0}^{+\mathrm{\infty }}\frac{(-1{)}^k}{(2k+1{)}^{2p+1}}=\frac{A_{2p}}{(2p)!}$, et $\sum _{k=0}^{+\mathrm{\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#Série_de_Laurent.

Modèle:Démonstration/finNote : pour $n$ impair égal à $2p+1$, cette somme est égale à $\beta (2p+1)$ où $\beta$ est la fonction bêta de Dirichlet, pour $n$ pair égal à $2p$, cette somme est égale à $\lambda (2p)$ où $\lambda$ est la fonction lambda de Dirichlet.

Formule explicite utilisant uniquement les coefficients binomiaux

Partant de la relation $\sum _{n=1}^{\mathrm{\infty }}{A}_{n-1}\frac{x^n}{n!}=\underset{0}{\overset{x}{\int }}(\sec t+\tan t)dt=-\ln (1-\sin x)$, on obtient

$A_n=\sum _{k=1}^{n+1}\sum _{j=0}^k(-1{)}^j(\genfrac{}{}{0ex}{}{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 suitModèle:,

$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{array}{cc}(-1{)}^{\frac{r-1}{2}}(1+2^{-r})& \text{pour r impair}\\ (-1{)}^{\frac{r}{2}}& \text{pour r pair}\end{array},$

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

Liens externes

• Modèle:Article.
• Modèle:MathWorld
• "A Survey of Alternating Permutations", preprint de Richard P. Stanley