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

Mark Dukes, Sergey Kitaev, Jeffrey Remmel, Einar Steingrimsson

Research output: Contribution to journalArticle

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.
LanguageEnglish
Pages139-163
Number of pages25
JournalJournal of Combinatorics
Volume2
Issue number1
DOIs
Publication statusPublished - 2011

Fingerprint

Statistics

Keywords

  • enumerating
  • (2+2)-free posets
  • indistinguishable elements

Cite this

@article{2c1845bb1a23408784ff281c5b4122c0,
title = "Enumerating (2+2)-free posets by indistinguishable elements",
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.",
keywords = "enumerating, (2+2)-free posets, indistinguishable elements",
author = "Mark Dukes and Sergey Kitaev and Jeffrey Remmel and Einar Steingrimsson",
year = "2011",
doi = "10.4310/JOC.2011.v2.n1.a6",
language = "English",
volume = "2",
pages = "139--163",
journal = "Journal of Combinatorics",
issn = "2156-3527",
number = "1",

}

Enumerating (2+2)-free posets by indistinguishable elements. / Dukes, Mark; Kitaev, Sergey; Remmel, Jeffrey; Steingrimsson, Einar.

In: Journal of Combinatorics, Vol. 2, No. 1, 2011, p. 139-163.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Dukes, Mark

AU - Kitaev, Sergey

AU - Remmel, Jeffrey

AU - Steingrimsson, Einar

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

KW - enumerating

KW - (2+2)-free posets

KW - indistinguishable elements

UR - http://intlpress.com/site/pub/pages/journals/items/joc/content/vols/0002/0001/a006/index.html

UR - http://arxiv.org/abs/1006.2696

U2 - 10.4310/JOC.2011.v2.n1.a6

DO - 10.4310/JOC.2011.v2.n1.a6

M3 - Article

VL - 2

SP - 139

EP - 163

JO - Journal of Combinatorics

T2 - Journal of Combinatorics

JF - Journal of Combinatorics

SN - 2156-3527

IS - 1

ER -