On a conjecture about enumerating \((2+2)\)-free posets (Q616386): Difference between revisions

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.