Counting self-dual interval orders - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Discrete Mathematics and Theoretical Computer Science Année : 2011

Counting self-dual interval orders

Résumé

In this paper, we first derive an explicit formula for the generating function that counts unlabeled interval orders (a.k.a. (2+2)-free posets) with respect to several natural statistics, including their size, magnitude, and the number of minimal and maximal elements. In the second part of the paper, we derive a generating function for the number of self-dual unlabeled interval orders, with respect to the same statistics. Our method is based on a bijective correspondence between interval orders and upper-triangular matrices in which each row and column has a positive entry.
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.
Fichier principal
Vignette du fichier
dmAO0148.pdf (309.13 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01215055 , version 1 (13-10-2015)

Identifiants

Citer

Vít Jelínek. Counting self-dual interval orders. 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. pp.539-550, ⟨10.46298/dmtcs.2932⟩. ⟨hal-01215055⟩

Collections

INSMI TDS-MACS
26 Consultations
531 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More