Voir la source de Permutation alternée

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

Comme à toute permutation alternée commençant par une montée (<math>\sigma(2)>\sigma(1)</math>), dite "ascendante", correspond une permutation alternée commençant par une descente (définie par <math>\sigma'(k)=n+1-\sigma(k)</math>), et réciproquement, on ne considère en général que les permutations ascendantes<ref name=":0">{{Ouvrage|auteur1=Louis Comtet|titre=Analyse combinatoire, tome second|éditeur=Presses universitaires de France|année=1970|passage=101}}</ref>. Par exemple, pour <math>n=4</math>, 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<ref name=":1">{{Article|auteur1=Désiré André|titre=Sur les permutations alternées|périodique=Journal de Mathématiques Pures et Appliquées|volume=7|pages=167-184|date=1881|lire en ligne=http://www.numdam.org/item/JMPA_1881_3_7__167_0.pdf}}</ref>{{,}}<ref name=":7">{{Article|langue=en|auteur1=Jessica Millar, N.J.A. Sloane,  Neal E. Young|titre=A New Operation on Sequences: the Boustrouphedon Transform|périodique=Journal of Combinatorial Theory|volume=76|numéro=1|pages=44–54|date=1996|lire en ligne=https://arxiv.org/pdf/math/0205218}}</ref>. Le '''problème d'André''' consiste en la détermination du nombre <math>A_n</math> de permutations alternées ascendantes de longueur <math>n</math>. Les nombres <math>A_n</math> sont appelés '''nombres zigzag'''. Lorsque <math>n</math> est pair, le nombre <math>A_n</math> est dit '''sécant''', et '''tangent''' pour <math>n</math> impair. Ceci vient de la [[Série génératrice|fonction génératrice exponentielle]] de la suite qui fait intervenir les fonctions [[Fonction trigonométrique|sécante]] et [[Fonction trigonométrique|tangente]].
[[Fichier:Bernoulli-zigzag.jpg|vignette| 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 <math>A_n</math> en commençant à <math>n=0</math> sont : 1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, ... : {{OEIS|id=A000111}}.

Si <math> Z_n</math> désigne le nombre de permutations alternées de longueur <math>n</math>, ascendantes ou descendantes, il résulte de l'appariement donné ci-dessus que <math> Z_n=2A_n</math> pour <math> n\geqslant2</math>. Les premières valeurs de  <math> Z_n</math> sont 1, 1, 2, 4, 10, 32, 122, 544, 2770, 15872, 101042, ... {{OEIS|A001250}}.

== Théorème d'André ==
Les nombres zigzag satisfont une relation de récurrence forte similaire à celle des [[Nombre de Catalan|nombres de Catalan]] : en classant les permutations alternées (montantes ou descendantes) de longueur <math>n+1</math>  suivant la valeur <math>k</math> du dernier terme, on montre que pour tout <math>n\geqslant1</math><ref name=":1" />{{,}}<ref name=":0" /> :

: <math> 2A_{n+1} = \sum_{k=0}^n \binom{n}{k} A_k A_{n-k}\,(1)</math>.

André a utilisé cette formule de récurrence pour obtenir une [[équation différentielle]] satisfaite par la [[Série génératrice|fonction génératrice exponentielle]] de la suite <math>(A_n)</math> :

: <math> A(x) = \sum_{n=0}^\infty A_n \frac{x^n}{n!}</math>

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

: <math>
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
</math>

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

: <math>
2(A(x) - 1 - x) = \int A^2(x)\,dx - x,
</math>

qui après dérivation donne l'équation différentielle <math>A'=\frac12 (A^2+1)</math>.

Par [[séparation des variables]], on obtient <math> \arctan (A(x))=\frac x2+\lambda</math>, ce qui donne, avec la [[condition initiale]] <math>A(0)=A_0/0!=1</math>, la solution :

: <math> A(x) = \tan \left(\frac x2+\frac\pi4  \right) = \frac{1+\sin x}{\cos x}=\sec x + \tan x</math>,

somme des fonctions [[Fonction trigonométrique|sécante]] et [[Fonction trigonométrique|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<ref>Philippe Henry, Gerhard Wanner, "Zigzags with Bürgi, Bernoulli, Euler and the Seidel–Entringer–Arnol’d triangle", Elemente der Mathematik 74 (4) : 141–168 (2019)</ref>.

Il résulte du théorème d'André que le [[rayon de convergence]] de la série <math> \sum_{n=0}^\infty A_n \frac{x^n}{n!}</math> est égal à  <math> \pi/2</math>.

Cela permet d'obtenir l'équivalent<ref>{{Article|langue=en|auteur1=Richard P. Stanley|titre=A survey of alternating permutations|périodique=Combinatorics and graphs, Contemporary Mathematics|volume=531|pages=4|date=2010|lire en ligne=https://arxiv.org/pdf/0912.4240}}</ref> :  

: <math> A_n \sim 2 \left(\frac{2}{\pi}\right)^{n + 1} n!\ </math>
ainsi que <math> \pi=\lim\frac{2nA_{n-1}}{A_{n}} </math>.

== Obtention des nombres zigzag ==

=== Par série génératrice ===
Les nombres zigzag d'indice impair (ou '''nombres tangents''') <math>A_{2n+1}</math> peuvent être définis par la relation : <math>\operatorname{tan} x=\sum_{n=0}^\infty A_{2n+1}\frac{x^{2n+1}}{(2n+1)!}, |x|<\pi/2.</math> 

Les premières valeurs sont 1, 2, 16, 272, 7936, ... ({{OEIS|id=A000182}}). Ils sont étroitement liés aux [[Nombre de Bernoulli|nombres de Bernoulli]] par la formule :

: <math>B_{2n} =(-1)^{n-1}\frac{2n}{4^{2n}-2^{2n}} A_{2n-1}</math>

pour <math> n\geqslant1</math>.

Les nombres <math>A_{2n}</math> d'indices pairs (ou '''nombres sécants)''', sont les [[Nombre d'Euler|nombres d'Euler]], définis par la relation :

<math>\sec x=\sum_{n=0}^\infty A_{2n}\frac{x^{2n}}{(2n)!}, |x|<\pi/2.</math> 

Les premières valeurs sont 1, 1, 5, 61, 1385, 50521, ... {{OEIS|id=A000364}}.

=== Par l'algorithme boustrophédon ===
{{Article détaillé|Transformation du boustrophédon}}

Les nombres de permutations alternées <math>\sigma</math> sur <math>\{1,2,\cdots,n+1\}</math> commençant par une descente et telles que <math>\sigma(1)=k+1</math> , notés <math>E(n,k)</math> (nombres d'Entringer), peuvent se calculer par récurrence comme suit<ref>{{Article|langue=en|auteur1=R. C. Entringer|titre=A Combinatorial Interpretation of the Euler and Bernoulli Numbers|périodique=Nieuw Arch. Wisk.|volume=14|pages=241-246|date=1966}}</ref>{{,}}<ref>Weisstein, Eric W. "Entringer Number." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/EntringerNumber.html</ref>{{,}}<ref name=":7" />:

: <math> E(0,0) = 1 </math>
: <math> E(n,0) = 0 \qquad \mbox{pour } n > 0 </math>
: <math> E(n,k) = E(n, k-1) + E(n-1, n-k)\mbox{ pour } 1\leqslant k\leqslant n </math>.

Le nombre d'Entringer <math>E(n,n)</math> n'est alors autre que le nombre zigzag <math>A_n</math>, 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 <math>n\geqslant1</math>, ''alternée lorsque <math>n</math> est impair'', s'exprime simplement à partir des nombres zigzag par la formule : <math>\sum_{k=0}^{+\infty}\frac{(-1)^{kn}}{(2k+1)^n}=\frac{\pi^n}{2^{n+1}(n-1)!}A_{n-1}</math>.

{{Démonstration/début}}

Le [[Fonction trigonométrique#Définitions à partir des séries entières|développement d'Euler en somme d’éléments simples de la fonction sécante]] :
:<math>\sec x=4\pi\sum_{k=0}^{+\infty}\frac{(-1)^k(2k+1)}{(2k+1)^2\pi^2-(2x)^2}</math> se transforme en :
:<math>\sec x=4\pi\sum_{k=0}^{+\infty}\frac{(-1)^k(2k+1)}{(2k+1)^2\pi^2}\frac1{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}</math>.

donc, en identifiant terme à terme, <math>\frac{2^{2p+2}}{\pi^{2p+1}}\sum_{k=0}^{+\infty}\frac{(-1)^{k}}{(2k+1)^{2p+1}}=\frac{A_{2p}}{(2p)!}</math>, et <math>\sum_{k=0}^{+\infty}\frac{(-1)^{k}}{(2k+1)^{2p+1}}=\frac{\pi^{2p+1}}{2^{2p+2}}\frac{A_{2p}}{(2p)!}</math>, ce qui donne la formule attendue pour <math>n=2p+1</math>.

La démonstration pour <math>n</math> pair se trouve dans l'article : [[Développement en éléments simples en analyse complexe#Série_de_Laurent]].

{{Démonstration/fin}}Note : pour <math>n</math> impair égal à <math>2p+1</math>, cette somme est égale à <math>\beta(2p+1)</math> où <math>\beta</math> est la [[fonction bêta de Dirichlet]], pour <math>n</math> pair égal à <math>2p</math>, cette somme est égale à <math>\lambda(2p)</math> où <math>\lambda</math> est la [[Série L de Dirichlet#Fonction lambda de Dirichlet|fonction lambda de Dirichlet]].

== Formule explicite utilisant uniquement les coefficients binomiaux ==
Partant de la relation <math>\sum_{n=1}^\infty A_{n-1}\frac{x^n}{n!}=\int_0^x(\sec t+\tan t)dt=-\ln(1-\sin x)</math>, on obtient <ref>{{Lien web |langue=en |auteur=Ross Tang |titre=An Explicit Formula for the Euler zigzag numbers (Up/down numbers) from power series |url=https://oeis.org/A000111/a000111.pdf |site=oeis.org |date=2010}}</ref>
: <math> 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} </math>.

== Formule explicite utilisant les nombres de Stirling de seconde espèce ==
Les relations des nombres zigzag avec les [[Nombre d'Euler|nombres d'Euler]] et les [[Nombre de Bernoulli|nombres de Bernoulli]] peuvent être utilisées pour prouver ce qui suit<ref>{{Article|auteur1=Mendes|prénom1=Anthony|titre=A Note on Alternating Permutations|périodique=The American Mathematical Monthly|volume=114|numéro=5|pages=437–440|année=2007|doi=10.1080/00029890.2007.11920432|jstor=27642223}}</ref>{{,}}<ref>{{Article|auteur1=Mező|prénom1=István|auteur2=Ramírez|prénom2=José L.|titre=The r-alternating permutations|périodique=Aequationes Mathematicae|année=2019|doi=10.1007/s00010-019-00658-5}}</ref>

: <math> 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)} </math>

où

: <math> 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}, </math>

<math>(x)^{(n)}=(x)(x+1)\cdots (x+n-1)</math> désigne la [[factorielle croissante]], et <math> S(r,k) </math> désigne les [[Nombre de Stirling|nombres de Stirling]] de seconde espèce..

== Voir aussi ==
* [[Transformation du boustrophédon|Transformation du Boustrophédon]]

== Références ==
{{Traduction/Référence|lang1=en|art1=Alternating permutation|id1=1165927592}}
{{Références}}

== Liens externes ==
{{liens}}
* {{Article|auteur1=Henry|prénom1=Philippe|auteur2=Wanner|prénom2=Gerhard|titre=Zigzags with Bürgi, Bernoulli, Euler and the Seidel–Entringer–Arnol’d triangle|périodique=Elemente der Mathematik|volume=74|numéro=4|pages=141–168|année=2019|date=|doi=10.4171/EM/393}}.
* {{MathWorld |titre=Alternating Permutation|urlname=AlternatingPermutation|nom_url=}}
* [http://www-math.mit.edu/~rstan/papers/altperm.pdf "A Survey of Alternating Permutations"], preprint de [[Richard Peter Stanley|Richard P. Stanley]]

{{Portail|mathématiques}}

[[Catégorie:Permutation]]
[[Catégorie:Pages avec des traductions non relues]]