Strathprints Home | Open Access | Browse | Search | User area | Copyright | Help | Library Home | SUPrimo

Enumerating (2+2) -free posets by the number of minimal elements and other statistics

Kitaev, Sergey and Remmel, Jeffrey (2011) Enumerating (2+2) -free posets by the number of minimal elements and other statistics. Discrete Mathematics, 159 (17). 2098 - 2108.

Full text not available in this repository. (Request a copy from the Strathclyde author)

Abstract

An unlabeled poset is said to be -free if it does not contain an induced subposet that is isomorphic to , the union of two disjoint 2-element chains. Let pn denote the number of -free posets of size n. In a recent paper, Bousquet-Mélou et al. [1] found, using the so called ascent sequences, the generating function for the number of -free posets of size n: . We extend this result in two ways. First, we find the generating function for -free posets when four statistics are taken into account, one of which is the number of minimal elements in a poset. Second, we show that if pn,k equals the number of -free posets of size n with k minimal elements, then . The second result cannot be derived from the first one by a substitution. Our enumeration results are extended to certain restricted permutations and to regular linearized chord diagrams through bijections in [1] and [2]. Finally, we define a subset of ascent sequences counted by the Catalan numbers and we discuss its relations with - and -free posets. An unlabeled poset is said to be -free if it does not contain an induced subposet that is isomorphic to , the union of two disjoint 2-element chains. Let pn denote the number of -free posets of size n. In a recent paper, Bousquet-Mélou et al. [1] found, using the so called ascent sequences, the generating function for the number of -free posets of size n: . We extend this result in two ways. First, we find the generating function for -free posets when four statistics are taken into account, one of which is the number of minimal elements in a poset. Second, we show that if pn,k equals the number of -free posets of size n with k minimal elements, then . The second result cannot be derived from the first one by a substitution. Our enumeration results are extended to certain restricted permutations and to regular linearized chord diagrams through bijections in [1] and [2]. Finally, we define a subset of ascent sequences counted by the Catalan numbers and we discuss its relations with - and -free posets. An unlabeled poset is said to be -free if it does not contain an induced subposet that is isomorphic to , the union of two disjoint 2-element chains. Let pn denote the number of -free posets of size n. In a recent paper, Bousquet-Mélou et al. [1] found, using the so called ascent sequences, the generating function for the number of -free posets of size n: . We extend this result in two ways. First, we find the generating function for -free posets when four statistics are taken into account, one of which is the number of minimal elements in a poset. Second, we show that if pn,k equals the number of -free posets of size n with k minimal elements, then . The second result cannot be derived from the first one by a substitution. Our enumeration results are extended to certain restricted permutations and to regular linearized chord diagrams through bijections in [1] and [2]. Finally, we define a subset of ascent sequences counted by the Catalan numbers and we discuss its relations with - and -free posets. An unlabeled poset is said to be -free if it does not contain an induced subposet that is isomorphic to , the union of two disjoint 2-element chains. Let pn denote the number of -free posets of size n. In a recent paper, Bousquet-Mélou et al. [1] found, using the so called ascent sequences, the generating function for the number of -free posets of size n: . We extend this result in two ways. First, we find the generating function for -free posets when four statistics are taken into account, one of which is the number of minimal elements in a poset. Second, we show that if pn,k equals the number of -free posets of size n with k minimal elements, then . The second result cannot be derived from the first one by a substitution. Our enumeration results are extended to certain restricted permutations and to regular linearized chord diagrams through bijections in [1] and [2]. Finally, we define a subset of ascent sequences counted by the Catalan numbers and we discuss its relations with - and -free posets. An unlabeled poset is said to be -free if it does not contain an induced subposet that is isomorphic to , the union of two disjoint 2-element chains. Let pn denote the number of -free posets of size n. In a recent paper, Bousquet-Mélou et al. [1] found, using the so called ascent sequences, the generating function for the number of -free posets of size n: . We extend this result in two ways. First, we find the generating function for -free posets when four statistics are taken into account, one of which is the number of minimal elements in a poset. Second, we show that if pn,k equals the number of -free posets of size n with k minimal elements, then . The second result cannot be derived from the first one by a substitution. Our enumeration results are extended to certain restricted permutations and to regular linearized chord diagrams through bijections in [1] and [2]. Finally, we define a subset of ascent sequences counted by the Catalan numbers and we discuss its relations with - and -free posets. An unlabeled poset is said to be -free if it does not contain an induced subposet that is isomorphic to , the union of two disjoint 2-element chains. Let pn denote the number of -free posets of size n. In a recent paper, Bousquet-Mélou et al. [1] found, using the so called ascent sequences, the generating function for the number of -free posets of size n: . We extend this result in two ways. First, we find the generating function for -free posets when four statistics are taken into account, one of which is the number of minimal elements in a poset. Second, we show that if pn,k equals the number of -free posets of size n with k minimal elements, then . The second result cannot be derived from the first one by a substitution. Our enumeration results are extended to certain restricted permutations and to regular linearized chord diagrams through bijections in [1] and [2]. Finally, we define a subset of ascent sequences counted by the Catalan numbers and we discuss its relations with - and -free posets.

Item type: Article
ID code: 34554
Keywords: computer science, enumeration, generating functions, multiple statistics, minimal elements, posets, Mathematics
Subjects: Science > Mathematics
Department: Faculty of Science > Computer and Information Sciences
Related URLs:
    Depositing user: Pure Administrator
    Date Deposited: 26 Oct 2011 11:48
    Last modified: 14 Dec 2012 15:49
    URI: http://strathprints.strath.ac.uk/id/eprint/34554

    Actions (login required)

    View Item