Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 28 Février 2017 à 11:45

Motifs dans les treeshelves

par Sergey Kirgizov

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).

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr