Journal of Combinatorics

Volume 2 (2011)

Number 1

Enumerating $(\bf{2+2})$-free posets by indistinguishable elements

Pages: 139 – 163



Mark Dukes (Department of Computer and Information Sciences, University of Strathclyde, Glasgow, Scotland, United Kingdom)

Sergey Kitaev (School of Computer Science, Reykjavík University, Reykjavík, Iceland)

Jeffrey B. Remmel (Department of Mathematics, University of California at San Diego)

Einar Steingrímsson (Department of Computer and Information Sciences, University of Strathclyde, Glasgow, Scotland, United Kingdom)


A poset is said to be $(\mathbf{2+2})$-free if it does not contain aninduced subposet that is isomorphic to {$\mathbf{2+2}$}, the union oftwo disjoint 2-element chains. Two elements in a poset areindistinguishable if they have the same strict up-set and the samestrict down-set. Being indistinguishable defines an equivalencerelation on the elements of the poset. We introduce the statistic$\mathrm{maxindist}$, the maximum size of a set of indistinguishableelements. We show that, under a bijection of Bousquet-Mélou et al, indistinguishable elements correspond to letters thatbelong to the same run in the so-called ascent sequence correspondingto the poset. We derive the generating function for the number of$(\mathbf{2+2})$-free posets with respect to both $\mathrm{maxindist}$and the number of different strict down-sets of elements in the poset.Moreover, we show that $(\mathbf{2+2})$-free posets $P$ with$\mathrm{maxindist}(P)$ at most $k$ are in bijection with uppertriangular matrices of nonnegative integers not exceeding $k$, whereeach row and each column contains a nonzero entry. (Here we considerisomorphic posets to be equal.) In particular, $(\mathbf{2+2})$-freeposets $P$ on $n$ elements with $\mathrm{maxindist}(P) = 1$ correspondto upper triangular binary matrices where each row and column containsa nonzero entry, and whose entries sum to $n$. We derive a generatingfunction counting such matrices, which confirms a conjecture ofJovovic, and we refine the generating function to count uppertriangular matrices consisting of nonnegative integers not exceeding$k$ and having a nonzero entry in each row and column. That refinedgenerating function also enumerates $(\mathbf{2+2})$-free posetsaccording to $\mathrm{maxindist}$. Finally, we link our enumerativeresults to certain restricted permutations and matrices.


interval order, (2+2)-free poset, indistinguishable elements, upper triangular matrix, enumeration

2010 Mathematics Subject Classification

05A15, 06A07

Published 15 June 2011