Permutation alternée
En mathématiques, et plus particulièrement en combinatoire, une permutation alternée (ou permutation en zigzag ) sur l'ensemble est une permutation dont le résultat est tel que chaque terme est alternativement supérieur ou inférieur au terme précédent ; autrement dit, les différences : , ont des signes alternés.
Comme à toute permutation alternée commençant par une montée (), dite "ascendante", correspond une permutation alternée commençant par une descente (définie par ), et réciproquement, on ne considère en général que les permutations ascendantes[1]. Par exemple, pour , 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 de permutations alternées ascendantes de longueur . Les nombres sont appelés nombres zigzag. Lorsque est pair, le nombre est dit sécant, et tangent pour impair. Ceci vient de la fonction génératrice exponentielle de la suite qui fait intervenir les fonctions sécante et tangente.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/04/Bernoulli-zigzag.jpg/220px-Bernoulli-zigzag.jpg)
Expression des nombres zigzag
modifierPar 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 en commençant à sont : 1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, ... : suite A000111 de l'OEIS.
Si désigne le nombre de permutations alternées de longueur , ascendantes ou descendantes, il résulte de l'appariement donné ci-dessus que pour . Les premières valeurs de sont 1, 1, 2, 4, 10, 32, 122, 544, 2770, 15872, 101042, ... suite A001250 de l'OEIS.
Théorème d'André
modifierLes 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 suivant la valeur du dernier terme, on montre que pour tout [2],[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 :
En effet, (1) permet d'écrire :
où l'on a effectué les substitutions et . Ceci donne l'équation intégrale :
qui après dérivation donne l'équation différentielle .
Par séparation des variables, on obtient , ce qui donne, avec la condition initiale , la solution :
- ,
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 est égal à .
Cela permet d'obtenir l'équivalent :
ainsi que .
Obtention des nombres zigzag
modifierPar série génératrice
modifierLes nombres zigzag d'indice impair (ou nombres tangents) peuvent être définis par la relation :
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 :
pour .
Les nombres d'indices pairs (ou nombres sécants), sont les nombres d'Euler, définis par la relation :
Les premières valeurs sont 1, 1, 5, 61, 1385, 50521, ... suite A000364 de l'OEIS.
Par l'algorithme boustrophédon
modifierLes nombres de permutations alternées sur commençant par une descente et telles que , notés (nombres d'Entringer), peuvent se calculer par récurrence comme suit[5],[6],[3]:
- .
Le nombre d'Entringer n'est alors autre que le nombre zigzag , qui s'obtient donc par simple succession d'additions.
Application à l'expression de la somme des inverses des nombres impairs à la puissance n
modifierLa somme des inverses des nombres impairs élevés à la puissance , alternée lorsque est impair, s'exprime simplement à partir des nombres zigzag par la formule : .
Formule explicite utilisant uniquement les coefficients binomiaux
modifierPartant de la relation , on obtient [7]
- .
Formule explicite utilisant les nombres de Stirling de seconde espèce
modifierLes 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]
où
désigne la factorielle croissante, et désigne les nombres de Stirling de seconde espèce..
Voir aussi
modifierRéférences
modifier- (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).
- Louis Comtet, Analyse combinatoire, tome second, Presses universitaires de France, , p. 101
- Désiré André, « Sur les permutations alternées », Journal de Mathématiques Pures et Appliquées, vol. 7, , p. 167-184 (lire en ligne)
- (en) Jessica Millar, N.J.A. Sloane, Neal E. Young, « A New Operation on Sequences: the Boustrouphedon Transform », Journal of Combinatorial Theory, vol. 76, no 1, , p. 44–54 (lire en ligne)
- 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)
- (en) R. C. Entringer, « A Combinatorial Interpretation of the Euler and Bernoulli Numbers », Nieuw Arch. Wisk., vol. 14, , p. 241-246
- Weisstein, Eric W. "Entringer Number." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/EntringerNumber.html
- (en) Ross Tang, « An Explicit Formula for the Euler zigzag numbers (Up/down numbers) from power series », sur oeis.org,
- Mendes, « A Note on Alternating Permutations », The American Mathematical Monthly, vol. 114, no 5, , p. 437–440 (DOI 10.1080/00029890.2007.11920432, JSTOR 27642223)
- Mező et Ramírez, « The r-alternating permutations », Aequationes Mathematicae, (DOI 10.1007/s00010-019-00658-5)
Liens externes
modifier
- Henry et Wanner, « Zigzags with Bürgi, Bernoulli, Euler and the Seidel–Entringer–Arnol’d triangle », Elemente der Mathematik, vol. 74, no 4, , 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