Fraction continue pour les statistiques de permutation

Introduction

               Les fractions continues ont été très utilisées par des mathématiciens célèbres tels que Euler et Hyugens durant le 17ème et 18ème([15]). À l’heure actuelle, nombreuses sont les applications des fractions continues mais ce qui nous intéresse c’est l’interprétation combinatoire des fractions continues qui est due à Philippe Flajolet dans son livre intitulé « Combinatorial aspects of continued fractions »([10]). D’autre part, la notion de statistique de permutation fait partie des principaux sujets de recherche sur la combinatoire. Et c’est là que vient l’idée du développement en fraction continue des fonctions génératrices des statistiques de permutations qui sont utilisées ou étudiées dans ([13], [10], [3], [9]). Ce développement est basé sur différentes sortes de bijection entre le groupe symétrique et les chemins de Motzkin valués. L’article de Sergi Elizalde ([8]) concerne ce développement en fraction continue des statistiques de permutations en utilisant la bijection de Biane-Corteel entre permutations et l’ensemble de chemins de Motzkin valués appelé histoires de Laguerre pour avoir les fractions continues ([4]). C’est à partir de cet article que s’est inspiré ce mémoire mais sous une autre méthode qui est l’application des cours et des acquis durant le parcours universitaire ([13], [11]). Ce mémoire comporte 3 chapitres. Dans le premier chapitre, nous définirons quelques outils et donnerons des théories sur les fractions continues. Ensuite, nous allons faire la construction de la bijection de Françon et Viennot qui est la base du développement en fraction continue puis une application qui consiste à développer en fraction continue des fonctions génératrices des statistiques dans l’ensemble des permutations. Enfin, le troisième chapitre sera consacré aux fractions continues dans les permutations restreintes qui sont des permutations possédant une ou plusieurs particularités à savoir l’involution ([6], [7]), le dérangement ([12], [5]), le 321-interdit ([1], [9]) et la permutation non-croisée non-nichée à cycles unimodaux ([8]).

Statistiques de permutation

Définition 1.2.1. Une statistique de permutation est une application s de Sn dans N. Par exemple, cyc définie précédemment est une statistique de permutation.
Définitions 1.2.2. Soit σ ∈ Sn et 1 ≤ i ≤ n. On dit que i est :
(i) une excédance de σ si i < σ(i);
(ii) une double excédance ou biexcédance de σ si i < σ(i) < σ2(i);
(iii) un point fixe de σ si i = σ(i);
(iv) un record de σ si, dans la décomposition linéaire de σ, toute lettre à gauche de i est inférieure à i.
On note
— Exc(σ) l’ensemble des excédances de σ et exc(σ)=#Exc(σ) ;
— Dexc(σ) l’ensemble des biexcédances de σ et dexc(σ)=#Dexc(σ) ;
— Fix(σ) l’ensemble des points fixes de σ et fix(σ)=#Fix(σ) ;
— Rec(σ) l’ensemble des records de σ et rec(σ)=#Rec(σ) ;
Les applications exc, dexc, fix et rec sont des statistiques de permutation.

Permutation 321-interdite

Définition 3.4.1. Soient σ ∈ Sn, π ∈ Sk telles que k < n.
On dit que σ évite π s’il n’y a pas de sous-suite σ(i1)σ(i2). . . σ(ik) avec 1 ≤ i1 < i2 < . . . < ik ≤ n qui est isomorphe en ordre à π.
Par exemple, la permutation 135624 évite le motif 321 mais contient le motif 132 (dans la sous-suite 164 par exemple). La permutation π est appelée motif classique ou plus simplement motif. On dit que la permutation σ évite le motif π. On note Sn(π) l’ensemble des permutations de Sn qui évite π. Dans cette section nous étudierons l’ensemble Sn(321) et en utilisant la bijection suivant la décomposition linéaire. Soit σ ∈ Sn(321) et M1M2 . . . Mk sa d-décomposition.
Remarque 3.2. Par construction, on a pour tout i ≤ k, |Mi| ≤ 2.
Propriétés 3.4.2. Soit i ≤ k.
(1) Si |Mi| = 2 alors pour tout j < i tel que |Mj| = 2 on a
(i) F(Mj ) < F(Mi)
(ii) L(Mj ) < L(Mi)
(2) Pour tout i ≤ k, si |Mi| = 1 et s’il existe j < i tel que |Mj| = 2 et F(Mj ) >Mi > L(Mj ) alors pour tout l > i
* si |Ml| = 2 on a L(Ml) > Mi
* si |Ml| = 1 on a Ml > Mi.
Autrement dit il n’y a pas d’élément plus petit que Mi à sa droite.
Démonstration. Pour faciliter les notations, on va poser F(Mj ) = aj et L(Mj ) = bj et si |Mj | = 1, on note simplement Mj (pour tout j ≤ k).
(1) Soit i ≤ k tel que |Mi| = 2 et soit j < i tel que |Mj| = 2. On sait queσ = . . . aj bj. . . aibi. . ..
(i) Supposons que aj > ai. Par construction de la d-décomposition on a ai >bi. Par suite, la sous-suite ajaibi vérifie aj > ai > bi. Par conséquentσ /∈ Sn(321) donc contradiction ie aj < ai.
(ii) Supposons que bj > bi, connaissant aj > bj on obtient aj > bj > bi alors il y a contradiction ce qui nous donne bj < bi.
(2) Soit i ≤ k tel que |Mi| = 1 et supposons qu’il existe j < i tel que |Mj| = 2 et aj > Mi > bj et soit l > i. S’il existe un élément plus petit que Mi à sa droite que ce soit al, bl ou Ml, on aura toujours une contradiction puisque aj > Mi.

Conclusion

            On a obtenu plusieurs développements en fraction continue de Jacobi des statistiques de permutation, que ce soit dans l’ensemble des permutations soit dans quelques restrictions. Ce développement a été fait par le biais d’une bijection due à Françon et Viennot et une autre qui est la composée de la bijection de FrançonViennot avec celle de Foata. La bijection de Biane-Corteel a été utilisée par Elizalde certes, mais cette méthode semble être plus complexe. C’est pour cette raison qu’on s’est servi de ces bijections pour y parvenir. En effet, dans notre méthode, il est juste nécessaire de savoir les propriétés des statistiques de permutation et de l’ensemble de permutations ou de restrictions. Mais on ne se limitait pas simplement des ensembles énumérés dans l’article de Elizalde mais on y a ajouté quelque restriction. Sachant que notre méthode n’étant pas complexe, il existe des statistiques de permutations qui sont compliquées à étudier par cette méthode telles que les inversions, les croisements et les alignements. Ce qui nous amène à un nouveau problème qui consiste à bien approfondir s’il est possible d’utiliser cette méthode ou faudra-t-il trouver d’autre méthode.

Table des matières

Introduction
1 Préliminaires 
1.1 Permutation 
1.2 Statistiques de permutation
1.3 Fraction continue 
1.4 Chemins de Motzkin 
2 Bijections entre permutations et chemins de Motzkin valués 
2.1 Introduction 
2.2 Bijections 
2.3 Application
2.3.1 Point fixe
2.3.2 Nombre de cycles
2.3.3 Nombre d’excédances
2.3.4 Nombre de doubles excédances
2.3.5 Fraction continue
3 Fraction continue pour les permutations restreintes 
3.1 Involution 
3.2 Dérangement 
3.3 Permutation à cycles unimodaux
3.4 Permutation 321-interdite
3.5 Permutation non-croisée non-nichée à cycles unimodaux
Conclusion
Bibliographie

Télécharger le rapport complet