On a conjecture about enumerating (2+2)-free posets
A poset is said to be \((2+2)\)-free if it does not contain an induced subposet that is isomorphic to the union of two disjoint 2-element chains. Let \(p_n\) be the number of unlabeled \((2+2)\)-free posets on \(n\) elements and \(p_{n,k}\) be the number of these posets with \(k\) minimal elements, with the assumption \(p_{0,0}=1\). Using functional equations and the kernel method, \textit{M. Bousquet-Mélou, A. Claesson, M. Dukes} and \textit{S. Kitaev} [J. Comb. Theory, Ser. A 117, No. 7, 884--909 (2010; Zbl 1225.05026)] obtained the generating function for the number \(p_n\). Since there exists a bijection between unlabeled (2+2)-free posets and ascent sequences, \textit{S. Kitaev} and \textit{J. Remmel} [``Enumerating (2+2)-free posets by the number of minimal elements and other statistics, arXiv:1004.3220v1] deduced the generating function for the number \(p_{n,k}\) by counting ascent sequences with respect to the length and the number of zeros. Moreover, they conjectured that the function \(P(t,z)=\sum _{n\geq 0,k\geq 0}p_{n,k}z^{k}t^{n}\) can be written in a simpler form, namely \(P(t,z)=\sum _{n\geq 0}\prod _{i=1}^{n}(1-(1-t)^{i-1}(1-zt))\). In this paper a combinatorial proof of this conjecture is given, using two combinatorial structures: upper triangular matrices with non-negative integer entries such that all rows and columns contain at least one non-zero entry and upper triangular \((0,1)\)-matrices in which all columns contain at least one non-zero entry. Note that specializing \(z=1\) this implies a combinatorial proof of the formula which was proved by Bousquet-Mélou et al.
- scientific article; zbMATH DE number 6806834
- Enumerating \((\mathbf 2+\mathbf 2)\)-free posets by the number of minimal elements and other statistics
- Structure and enumeration of (3+1)-free posets (extended abstract).
- Structure and enumeration of \((3+1)\)-free posets
- Enumeration of functions from posets to chains
- (2+2)-free posets, ascent sequences and pattern avoiding permutations
- An obvious proof of Fishburn's interval order theorem
- Ascent sequences and upper triangular matrices containing non-negative integers
- ENUMERATION OF CHORD DIAGRAMS AND AN UPPER BOUND FOR VASSILIEV INVARIANTS
- Height counting of unlabeled interval and \(N\)-free posets.
- scientific article; zbMATH DE number 6806834 (Why is no real title available?)
- scientific article; zbMATH DE number 6157245 (Why is no real title available?)
- Vassiliev invariants and a strange identity related to the Dedekind eta-function
- Asymptotic enumeration of two-dimensional posets
- Enumeration of functions from posets to chains
- Total nonnegativity and (3+1)-free posets
- A new decomposition of ascent sequences and Euler-Stirling statistics
- Asymptotics and statistics on Fishburn matrices and their generalizations
- Structure and enumeration of \((3+1)\)-free posets
- On \(q\)-series identities related to interval orders
- scientific article; zbMATH DE number 6909264 (Why is no real title available?)
- Enumerating \((\mathbf 2+\mathbf 2)\)-free posets by the number of minimal elements and other statistics
- scientific article; zbMATH DE number 6806834 (Why is no real title available?)
- Decomposing labeled interval orders as pairs of permutations
- Catalan pairs and Fishburn triples
- Proof of a conjecture of Proctor and Scoppetta related to \(d\)-complete posets
- Composition matrices, \((2+2)\)-free posets and their specializations
- Structure and enumeration of (3+1)-free posets (extended abstract).
- Fishburn trees
- Enumerating \((2 + 2)\)-free posets by indistinguishable elements
- Bijective proof of a conjecture on unit interval posets
- Counting general and self-dual interval orders
- Equidistributed statistics on Fishburn matrices and permutations
- On naturally labelled posets and permutations avoiding 12--34
- Asymptotics for the number of row-Fishburn matrices
- (2+2)-free posets, ascent sequences and pattern avoiding permutations
This page was built for publication: On a conjecture about enumerating \((2+2)\)-free posets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q616386)
