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

An unlabeled 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. Let pnpn denote the number of (2+2)-free posets of size nn. In a recent paper, Bousquet-Mélou et al. [1] found, using the so called ascent sequences, the generating function for the number of (2+2)-free posets of size nn: P(t)=∑n≥0pntn=∑n≥0∏i=1n(1−(1−t)i). We extend this result in two ways. First, we find 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. Second, we show that if pn,kpn,k equals the number of (2+2)-free posets of size nn with kk minimal elements, then P(t,z)=∑n,k≥0pn,ktnzk=1+∑n≥0zt(1−zt)n+1∏i=1n(1−(1−t)i). The second result cannot be derived from the first one by a substitution. Our enumeration results are extended to certain restricted permutations and to regular linearized chord diagrams through bijections in [1] and [2]. Finally, we define a subset of ascent sequences counted by the Catalan numbers and we discuss its relations with (2+2)- and (3+1)-free posets.

► We extend a recent result on enumeration of (2+2)-free posets (interval orders) in two ways.► (2+2)-free posets are enumerated subject to four statistics.► Two formulas enumerating (2+2)-free posets by the number of minimal elements are discussed.