Enumerating (2+2)-free posets by indistinguishable elements

Dukes, Mark and Kitaev, Sergey and Remmel, Jeffrey and Steingrimsson, Einar (2011) Enumerating (2+2)-free posets by indistinguishable elements. Journal of Combinatorics, 2 (1). pp. 139-163. (https://doi.org/10.4310/JOC.2011.v2.n1.a6)

Full text not available in this repository.Request a copy

Abstract

A poset is said to be (2+2)-free if it does not contain an induced subposet that is isomorphic to 2+2, the union of two disjoint 2-element chains. Two elements in a poset are indistinguishable if they have the same strict up-set and the same strict down-set. Being indistinguishable defines an equivalence relation on the elements of the poset. We introduce the statistic maxindist, the maximum size of a set of indistinguishable elements. We show that, under a bijection of Bousquet-Melou et al., indistinguishable elements correspond to letters that belong to the same run in the so-called ascent sequence corresponding to the poset. We derive the generating function for the number of (2+2)-free posets with respect to both maxindist and the number of different strict down-sets of elements in the poset. Moreover, we show that (2+2)-free posets P with maxindist(P) at most k are in bijection with upper triangular matrices of nonnegative integers not exceeding k, where each row and each column contains a nonzero entry. (Here we consider isomorphic posets to be equal.) In particular, (2+2)-free posets P on n elements with maxindist(P)=1 correspond to upper triangular binary matrices where each row and column contains a nonzero entry, and whose entries sum to n. We derive a generating function counting such matrices, which confirms a conjecture of Jovovic, and we refine the generating function to count upper triangular matrices consisting of nonnegative integers not exceeding k and having a nonzero entry in each row and column. That refined generating function also enumerates (2+2)-free posets according to maxindist. Finally, we link our enumerative results to certain restricted permutations and matrices.

ORCID iDs

Dukes, Mark ORCID logoORCID: https://orcid.org/0000-0002-2779-2680, Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647, Remmel, Jeffrey and Steingrimsson, Einar ORCID logoORCID: https://orcid.org/0000-0003-4611-0849;
CORE (COnnecting REpositories)