Contents Online

# Journal of Combinatorics

## Volume 2 (2011)

### Number 1

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

Pages: 139 – 163

DOI: http://dx.doi.org/10.4310/JOC.2011.v2.n1.a6

#### Authors

#### Abstract

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.

#### Keywords

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

#### 2010 Mathematics Subject Classification

05A15, 06A07