Enumerating 2 2-free posets by the number of minimal elements and other statistics - Mathematics > CombinatoricsReport as inadecuate




Enumerating 2 2-free posets by the number of minimal elements and other statistics - Mathematics > Combinatorics - Download this document for free, or read online. Document in PDF available to download.

Abstract: An unlabeled poset is said to be 2+2-free if it does not contain an inducedsubposet 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 recentpaper, Bousquet-M\-elou et al.\cite{BCDK} found, using so called ascentsequences, the generating function for the number of 2+2-free posets of size$n$: $Pt=\sum {n \geq 0} p n t^n = \sum {n\geq 0} \prod {i=1}^{n}1-1-t^i$. We extend this result in two ways. First, we find the generatingfunction for 2+2-free posets when four statistics are taken into account, oneof 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$ minimalelements, then $Pt,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 bederived from the first one by a substitution. On the other hand, $Pt$ caneasily be obtained from $Pt,z$ thus providing an alternative proof for theenumeration result in \cite{BCDK}. Moreover, we conjecture a simpler form ofwriting $Pt,z$. Our enumeration results are extended to certain restrictedpermutations and to regular linearized chord diagrams through bijections in\cite{BCDK,cdk}. Finally, we define a subset of ascent sequences counted by theCatalan numbers and we discuss its relations with 2+2- and 3+1-free posets.



Author: Sergey Kitaev, Jeffrey Remmel

Source: https://arxiv.org/







Related documents