Skip to Main content Skip to Navigation
Conference papers

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

Abstract : 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.
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download

https://hal.inria.fr/hal-01186240
Contributor : Coordination Episciences Iam <>
Submitted on : Wednesday, December 14, 2016 - 3:54:10 PM
Last modification on : Monday, August 24, 2020 - 3:42:06 PM
Long-term archiving on: : Wednesday, November 25, 2015 - 4:30:12 PM

File

3196.pdf
Files produced by the author(s)

Identifiers

  • 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. 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010), 2010, San Francisco, United States. pp.821-832. ⟨hal-01186240⟩

Share

Metrics

Record views

125

Files downloads

653