Motifs dans les treeshelves

Les treeshelves sont des arbres binaires étiquetés et croissants où chaque fils est connecté à son antécédent par une arête gauche ou droite. Les treeshelves sont en bijections avec les permutations.

Nous étudions la distribution et la popularité des fils gauches sur les treeshelves évitant un motif de taille trois. [La popularité d’un motif dans une classe d’objets correspond au nombre total de motifs apparaissant dans tous les objets de cette classe.] Pour chaque motif exclu, nous fournissons les fonctions génératrices exponentielles (bivariées) pour la distribution et la popularité des fils gauches. Nous vérifions qu’elles ne sont pas D-finite et nous donnons des équivalents asymptotiques.

Enfin, nous présentons des bijections constructives entre les treeshelves évitant un motif de taille trois et d’autres types d’arbres binaires étiquetés.

Cet exposé est basé travail en collaboration avec Jean-Luc Baril et Vincent Vajnovszki (preprint accessible en ligne: https://arxiv.org/abs/1611.07793).