Introduction au Domaine de Recherche :Combinatoire énumérative et bijective des surfacesbranchantes et des permutations triables par pilesCorentin HenrietTable des matières1 Introduction 12 Polyominos parallélogrammes et permutations triables par une pile 22.1 Énumération des polyominos parallélogrammes . . . . . . . . . . . . . . .2 2.
2) Tri par pile de permutations . . . . . . . . . . . . . . . . . . . . . . . . . .3 2. 3) Permutations triables par une pile . . . . . . . . . . . . . . . . . . . . . .4 2.
4) Une caractérisation par évitance de motifs . . . . . . . . . . . . . . . . . .4 3 Poissons combattants et permutations triables par deux piles 53.
1) Poissons combattants et décompositions . . . . . . . . . . . . . . . . . . .5 3.2 Énumération des permutations triables par deux piles . . . . . . . . . . .8 3.
3) Aire moyenne des poissons combattants . . . . . . . . . . . . . . . . . . .11 4 Perspectives 115 Références 121 IntroductionLa combinatoire énumérative et bijective est un domaine de recherche fondamentalereprésentant un des principaux ponts entre les mathématiques et l"informatique.
Pré-cisément, les travaux qui l"étudient s"attachent à compter des structures combinatoiresselon divers paramètres (qui diffèrent selon les structures étudiées, mais peuvent être misen correspondance via des bijections), et ce de manière exacte, ou de manière asymp-totique par rapport à la taille, selon que l"on cherche à exhiber des liens structurelsentre des types d"objets combinatoires, ou que l"on cherche à connaître les propriétéslimites d"un objet aléatoire lorsque la taille de l"objet généré tend vers l"infini.
On se pro-pose d"esquisser dans le présent document divers problèmes d"énumération concernantles poissons combattants, surfaces branchantes introduites en 2016 par Duchi, Schaeffer,Rinaldi, et Guerrini, étendant la notion de polyominos parallélogrammes, et ayant une1aire asymptotique enn54, oùnest le paramètre de taille naturel, ce qui est un compor-tement non-standard.
On verra également qu"exhiber des bijections avec des objets déjàénumérés est un outil explicatif puissant qui aide à passer d"une classe d"objets à uneautre selon laquelle est la plus pratique pour travailler sur un problème donné.
En l"oc-currence, on développera la notion de permutation triable par pile, qui s"avère entretenirde fines relations avec les poissons combattants.
2) Polyominos parallélogrammes et permutations triablespar une pile2.1 Énumération des polyominos parallélogrammesLes polyominos sont des surfaces dans le plan obtenues en attachant des carrés uni-taires ensemble, popularisés par Gardner au début des années 1960.Définition 1.Un polyomino est une réunion finie de carrés unité (cellules) à sommetsdans le réseauZ2, d"intérieur connexe.Un polyomino est convexe si chacune de ses lignes et colonnes de cellules est convexe.Un polyomino est dit parallélogramme s"il est convexe et s"il possède une cellule Sud-Ouest(qui est plus au sud et plus à l"ouest que chacune des cellules du polyomino) et une celluleNord-Est.Figure 1 - 3 polyominos : un non-convexe, un convexe et un parallélogrammeDeux polyominos sont dits égaux s"ils sont égaux à translation près.
Le périmètred"un polyomino est toujours pair et nous appelleronstailled"un polyomino l"entierntelque le périmètre du polyomino soit2(n+ 1).
L"aired"un polyomino est les nombre decellules qui le composent.
Pour dénombrer les polyominos parallélogrames de taillen,nous allons les mettre en bijection avec les chemins de Dyck.Définition 2.Un mot de Dyck de taillenest un mot de longueur2nsur l"alphabetfu;dgcontenantnexemplaires de chacune des deux lettres dont chaque préfixe contientau moins autant deuque ded.
On peut représenter un tel mot par un chemin de Dyckde longueur2nqui est un chemin à sommets dansZ2de(0;0)à(0;2n)composé de pas(1;1)(u: montée) et(1;1)(d: descente).Par la suite, nous confondrons les deux notions de chemins et mots de Dyck.
Onse donne un chemin de DyckD.
On peut définir la hauteur de chaque sommet qui le2compose par l"ordonnée à laquelle il se trouve.
On va construire colonne par colonne unpolyomino parallélogrammeP(D)à partir deDde la manière suivante : on parcourtDde gauche à droite, à chaquepic(ud) rencontré, on crée une colonne composée d"autantde cellules que la hauteur du pic et on attache son flanc gauche sur le flanc droit dela dernière colonne du polyomino déjà construit, sur lesqcellules les plus au Nord decelle-ci, oùqest la hauteur de lavallée(du) précédant le pic considéré moins1.
On donneun exemple ci-dessous en guise d"illustration :231 !23Figure 2 - Un chemin de Dyck et le polyomino parallélogramme correspondantÀ partir d"un polyomino parallélogramme, on peut effectuer la transformation inverse,en le parcourant colonne par colonne.
Ainsi, on a une bijection entre les polyominosparallélogrammes de taillenet les chemins de Dyck de longueur2n, comptés par lesfameux nombres de Catalan, d"où :Théorème 1.Le nombre de polyominos parallélogrammes de taillenest le nombre deCatalanCn=1n+12nn2.
2) Tri par pile de permutationsEntréePileSortie3524152413524132415324153415324153214532453215321432145La notion de tri par une pile d"une per-mutation a d"abord été esquissée par Do-nald Knuth dans son célèbre monographeThe Art of Computer Programming, puis ensuitedéveloppée sous différentes formes.
L"algorithmeest le suivant : étant données une permutation=12:::ndansSnet une pile initialement vide,on crée une nouvelle permutations()en lisant àchaque étape le premier élément denon-encoreempilé : on l"empile au sommet de la pile si celle-ci estvide ou si son sommet est plus grand que l"élémentconsidéré, et sinon, on dépile le sommet de la pileet on ajoute l"élément dépilé à la fin de la sortie. Àtitre d"illustration, l"opération de tri sur35241donne32145et est décrite dans le tableau ci-contre.
3) On dit qu"une permutationesttriable par une pilesi la permutation obtenue parl"algorithme précédent est l"identité, autrement dits() = 12:::n.
Plus généralement,dans sa thèse de doctorat de 1990, West a initié l"intérêt autour des permutations quideviennent l"identité après un nombre donné de passages dans la pile.
Ainsi, on diraqu"une permutation esttriable par t piles(au sens de West) sist() = 12:::n. On noteraSSt(n)l"ensemble des permutations de taillentriables partpiles etWt(n)le cardinaldeSSt(n).
Avec ces notations, toute permutation deSnest triable parn1piles, caraprès l"itérationkde l"algorithme, leskvaleurs denk+1ànsont triées correctementà la fin de la permutation.2.
3) Permutations triables par une pileOn peut retracer la procédure de tri par une pile d"une permutation deSnen notantà chaque étape si l"on a empilé (noté paru) dans la pile ou si l"on a dépilé (d).
On obtientde cette façon un mot de Dyck. Avec l"exemple de la permutation35241ci-dessus, onobtient le motuduuduuddd.
En connaissant la permutation obtenue par la procédure detri, ainsi que le chemin de Dyck associé, on peut reconstruire la permutation initiale eneffectuant la procédure à l"envers.
Ainsi, on peut associer un chemin de Dyck à chaquepermutation triable par une pile de manière injective (puisque la permutation obtenue estl"identité).
Cette correspondance est même bijective : étant donné un chemin de DyckD,on numérote les descentes de1àndans leur ordre d"apparition, on parcourt les montéesdans l"ordre et on leur associe l"entier de la descente correspondante.1234515243Figure 3 - Le chemin de Dyck correspondant à la permutation triable par une pile15243Cette bijection entre permutations triables par une pile et chemins de Dyck faitcorrespondre certaines des statistiques de ces objets : les maximums de gauche à droitesont envoyés sur les montées partant de l"axex, les descentes ((i)> (i+ 1)) sur lesmontées doubles (uu), les montées ((i)< (i+ 1)) sur les pics (ud).
En composant lesdeux bijections précédentes, on obtient :Théorème 2.L"ensemble des permutations triables par une pile de taillenest en bijec-tion avec l"ensemble des polyominos parallélogrammes de taillen.
En particulier :W1(n) =1n+ 12nn2.
4) Une caractérisation par évitance de motifsLa description par Knuth de la procédure de tri par pile d"une permutation a donnénaissance au champ d"étude des permutations évitant un certain motif, ou un certain4ensemble de motifs.Définition 3.Soient=1:::n2Snet=1:::k2Skaveckn.
On dit quecontient une occurrence du motif, ou plus simplement quecontient, lorsqu"ilexiste des indices1i1< ::: < ikntels quei1:::ikait le même ordre relatif que=1:::k.
