06029141

j

06029141 Kitaev, Sergey Remmel, Jeffrey Enumerating $(\bold 2+\bold 2)$-free posets by the number of minimal elements and other statistics. Discrete Appl. Math. 159, No. 17, 2098-2108 (2011). 2011 Elsevier Science B.V. (North-Holland), Amsterdam EN free posets enumeration generating functions multiple-statistics minimal elements free posets Zbl 1225.05026 Zbl 1228.05232

doi:10.1016/j.dam.2011.07.010

Summary: 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 $p_{n}$ denote the number of (2+2)-free posets of size $n$. In a recent paper, {\it M. Bousquet-M\'elou} et al. [J. Comb. Theory, Ser. A 117, No. 7, 884--909 (2010; Zbl 1225.05026)] found, using the so called ascent sequences, the generating function for the number of (2+2)-free posets of size $$n:P(t)=\sum_{n\geq 0}p_{n}t^{n}=\sum_{n\geq 0}\prod^{n}_{i=1}(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 $p_{n,k}$ equals the number of (2+2)-free posets of size $n$ with $k$ minimal elements, then $$P(t,z)=\sum _{n,k\geq 0}p_{n,k}t^{n}z^{k}=1+\sum_{n\geq 0}\frac{zt}{(1-zt)^{n+1}}\prod_{i=1}^{n}(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 {\it M. Bousquet-M\'elou} et al. [loc. cit.] and {\it A.Claesson}, {\it M. Dukes} and {\it S. Kitaev} [Australas. J. Comb. 49, 47--59 (2011; Zbl 1228.05232)]. 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.