Counting self-dual interval orders

Résumé : Dans cet article, on obtient une expression explicite pour la fonction génératrice du nombre des ensembles partiellement ordonnés (posets) qui évitent le motif (2+2). La fonction compte ces ensembles par rapport à plusieurs statistiques naturelles, incluant le nombre d'éléments, le nombre de niveaux, et le nombre d'éléments minimaux et maximaux. Dans la deuxième partie, on obtient une expression similaire pour la fonction génératrice des posets autoduaux évitant le motif (2+2). On obtient ces résultats à l'aide d'une bijection entre les posets évitant (2+2) et les matrices triangulaires supérieures dont chaque ligne et chaque colonne contient un élément positif.
Type de document :
Communication dans un congrès
Bousquet-Mélou, Mireille and Wachs, Michelle and Hultman, Axel. 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), pp.539-550, 2011, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01215055
Contributeur : Coordination Episciences Iam <>
Soumis le : mardi 13 octobre 2015 - 15:05:47
Dernière modification le : mardi 7 mars 2017 - 15:12:43
Document(s) archivé(s) le : jeudi 27 avril 2017 - 00:09:48

Fichier

dmAO0148.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01215055, version 1

Collections

Citation

Vít Jelínek. Counting self-dual interval orders. Bousquet-Mélou, Mireille and Wachs, Michelle and Hultman, Axel. 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), pp.539-550, 2011, DMTCS Proceedings. 〈hal-01215055〉

Partager

Métriques

Consultations de la notice

54

Téléchargements de fichiers

128