Enumerating (2+2)-free posets by the number of minimal elements and other statistics

Résumé : Un poset sera dit (2+2)-libre s'il ne contient aucun sous-poset isomorphe à 2+2, l'union disjointe de deux chaînes à deux éléments. Dans un article récent, Bousquet-Mélou et al. ont trouvé, à l'aide de "suites de montées'', la fonction génératrice des nombres de posets (2+2)-libres: c'est $P(t)=∑_n≥ 0 ∏_i=1^n ( 1-(1-t)^i)$. Nous étendons ce résultat en trouvant la fonction génératrice des posets (\textrm2+2)-libres rendant compte de quatre statistiques, dont le nombre d'éléments minimaux du poset. Nous montrons aussi que lorsqu'on ne s'intéresse qu'au nombre d'éléments minimaux, notre fonction génératrice assez compliquée peut être simplifiée en$P(t,z)=∑_n,k ≥0 p_n,k t^n z^k = 1+ ∑_n ≥0\frac{zt}{(1-zt)^n+1}∏_i=1^n (1-(1-t)^i)$, où $p_n,k$ est le nombre de posets (2+2)-libres de taille $n$ avec $k$ éléments minimaux.
Type de document :
Communication dans un congrès
Billey, Sara and Reiner, Victor. 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010), 2010, San Francisco, United States. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AN, 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010), pp.821-832, 2010, DMTCS Proceedings
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01186240
Contributeur : Coordination Episciences Iam <>
Soumis le : mercredi 14 décembre 2016 - 15:54:10
Dernière modification le : mercredi 18 octobre 2017 - 14:38:05
Document(s) archivé(s) le : mercredi 25 novembre 2015 - 16:30:12

Fichier

3196.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01186240, version 1

Collections

Citation

Sergey Kitaev, Jeffrey Remmel. Enumerating (2+2)-free posets by the number of minimal elements and other statistics. Billey, Sara and Reiner, Victor. 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010), 2010, San Francisco, United States. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AN, 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010), pp.821-832, 2010, DMTCS Proceedings. 〈hal-01186240〉

Partager

Métriques

Consultations de la notice

68

Téléchargements de fichiers

60