Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Enumerating (2+2)-fr ...
Conference paper

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

Sergey Kitaev ORCID (1), Jeffrey Remmel (2)
(1) The Mathematics Institute, Reyjavik University
(2) Department of Mathematics [Univ California San Diego]
Download article
Open on HAL
Imported on
January 31, 2017
Published on
December 31, 2009
Last modified on
March 31, 2025
Volume
DMTCS Proceedings vol. AN, 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010)
Proceedings
DOI
10.46298/dmtcs.2812
License
https://about.hal.science/hal-authorisation-v1
National Science Foundation
0654060
Combinatorial Structures for Permutation Enumeration and Macdonald Polynomials
Indicators
590
Views
579
Downloads

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

Sergey Kitaev ORCID (1), Jeffrey Remmel (2)
(1) The Mathematics Institute, Reyjavik University
(2) Department of Mathematics [Univ California San Diego]
Abstract
English
A poset is said to be (2+2)-free if it does not contain an induced subposet that is isomorphic to 2+2, the union of two disjoint 2-element chains. In a recent paper, Bousquet-Mélou et al. found, using so called ascent sequences, the generating function for the number of (2+2)-free posets: $P(t)=∑_n≥ 0 ∏_i=1^n ( 1-(1-t)^i)$. We extend this result by finding the generating function for (2+2)-free posets when four statistics are taken into account, one of which is the number of minimal elements in a poset. We also show that in a special case when only minimal elements are of interest, our rather involved generating function can be rewritten in the form $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)$ where $p_n,k$ equals the number of (2+2)-free posets of size $n$ with $k$ minimal elements.
French
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.
Keywords
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • (2+2)-free posets
  • minimal elements
  • generating function
Cited by

Source: OpenCitations

  • Ascent Sequences Avoiding Pairs of Patterns

    The Electronic Journal of Combinatorics

    Authors : Andrew M. Baxter, Lara K. Pudwell ORCID

    Journal reference : Volume 22, 2015, pp.

    DOI : 10.37236/4479
  • Equidistributed Statistics on Fishburn Matrices and Permutations

    The Electronic Journal of Combinatorics

    Authors : Dandan Chen ORCID, Sherry H.F. Yan, Robin D.P. Zhou ORCID

    Journal reference : Volume 26, 2019, pp.

    DOI : 10.37236/7926
  • Restricted ascent sequences and Catalan numbers

    Applicable Analysis and Discrete Mathematics

    Authors : David Callan, Toufik Mansour ORCID, Mark Shattuck ORCID

    Journal reference : Volume 8, 2014, pp. 288-303

    DOI : 10.2298/aadm140626007c
  • Asymptotics for the number of row-Fishburn matrices

    European Journal of Combinatorics

    Authors : Kathrin Bringmann ORCID, Yingkun Li ORCID, Robert C. Rhoades

    Journal reference : Volume 41, 2014, pp. 183-196

    DOI : 10.1016/j.ejc.2014.04.003
  • On q -series identities related to interval orders

    European Journal of Combinatorics

    Authors : George E. Andrews ORCID, Vít Jelínek ORCID

    Journal reference : Volume 39, 2014, pp. 178-187

    DOI : 10.1016/j.ejc.2014.01.003
  • Some enumerative results related to ascent sequences

    Discrete Mathematics

    Authors : Toufik Mansour ORCID, Mark Shattuck ORCID

    Journal reference : Volume 315-316, 2013, pp. 29-41

    DOI : 10.1016/j.disc.2013.10.006
  • Counting general and self-dual interval orders

    Journal of Combinatorial Theory Series A

    Authors : Vít Jelínek ORCID

    Journal reference : Volume 119, 2011, pp. 599-614

    DOI : 10.1016/j.jcta.2011.11.010
Preview
Loading PDF preview...