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

Sergey Kitaev, Jeffrey Remmel

Research output: Contribution to conferencePoster

1 Citation (Scopus)

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. In a recent paper, Bousquet-Mélou et al. found, using so called ascent sequences, the generating function for the number of (2+2)-free posets: P(t)=∑n≥0 ∏i=1n ( 1-(1-t)i). We extend this result by finding the generating function for (2+2)-free posets when four statistics are taken into account, one of which is the number of minimal elements in a poset. We also show that in a special case when only minimal elements are of interest, our rather involved generating function can be rewritten in the form P(t,z)=∑n,k ≥0 pn,k tn zk = 1+ ∑n ≥0zt(1-zt)n+1∏i=1n (1-(1-t)i) where pn,k equals the number of (2+2)-free posets of size n with k minimal elements.
Résumé. Un poset sera dit (2+2)-libre s'il ne contient aucun sous-poset isomorphe à 2+2, l'union disjointe de deux chaînes à deux éléments. Dans un article récent, Bousquet-Mélou et al. ont trouvé, à l'aide de ``suites de montées'', la fonction génératrice des nombres de posets (2+2)-libres: c'est P(t)=∑n≥0 ∏i=1n ( 1-(1-t)i). Nous étendons ce résultat en trouvant la fonction génératrice des posets (2+2)-libres rendant compte de quatre statistiques, dont le nombre d'éléments minimaux du poset. Nous montrons aussi que lorsqu'on ne s'intéresse qu'au nombre d'éléments minimaux, notre fonction génératrice assez compliquée peut être simplifiée en P(t,z)=∑n,k ≥0 pn,k tn zk = 1+ ∑n ≥0 zt(1-zt)n+1∏i=1n (1-(1-t)i), où pn,k est le nombre de posets (2+2)-libres de taille n avec k éléments minimaux.

Conference

Conference22nd International Conference on Formal Power Series & Algebraic Combinatorics
CountryUnited States
CitySan Francisco
Period2/08/106/08/10

Fingerprint

Poset
Statistics
Generating Function
Union
Ascent
Disjoint
Isomorphic

Keywords

  • (2+2)-free posets
  • minimal elements
  • subposet

Cite this

Kitaev, S., & Remmel, J. (2010). Enumerating (2+2)-free posets by the number of minimal elements and other statistics. 821-832. Poster session presented at 22nd International Conference on Formal Power Series & Algebraic Combinatorics, San Francisco, United States.
Kitaev, Sergey ; Remmel, Jeffrey. / Enumerating (2+2)-free posets by the number of minimal elements and other statistics. Poster session presented at 22nd International Conference on Formal Power Series & Algebraic Combinatorics, San Francisco, United States.12 p.
@conference{5ed17e1d0b24432690618ee3f69bb9a5,
title = "Enumerating (2+2)-free posets by the number of minimal elements and other statistics",
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. In a recent paper, Bousquet-M{\'e}lou et al. found, using so called ascent sequences, the generating function for the number of (2+2)-free posets: P(t)=∑n≥0 ∏i=1n ( 1-(1-t)i). We extend this result by finding the generating function for (2+2)-free posets when four statistics are taken into account, one of which is the number of minimal elements in a poset. We also show that in a special case when only minimal elements are of interest, our rather involved generating function can be rewritten in the form P(t,z)=∑n,k ≥0 pn,k tn zk = 1+ ∑n ≥0zt(1-zt)n+1∏i=1n (1-(1-t)i) where pn,k equals the number of (2+2)-free posets of size n with k minimal elements.R{\'e}sum{\'e}. Un poset sera dit (2+2)-libre s'il ne contient aucun sous-poset isomorphe {\`a} 2+2, l'union disjointe de deux cha{\^i}nes {\`a} deux {\'e}l{\'e}ments. Dans un article r{\'e}cent, Bousquet-M{\'e}lou et al. ont trouv{\'e}, {\`a} l'aide de ``suites de mont{\'e}es'', la fonction g{\'e}n{\'e}ratrice des nombres de posets (2+2)-libres: c'est P(t)=∑n≥0 ∏i=1n ( 1-(1-t)i). Nous {\'e}tendons ce r{\'e}sultat en trouvant la fonction g{\'e}n{\'e}ratrice des posets (2+2)-libres rendant compte de quatre statistiques, dont le nombre d'{\'e}l{\'e}ments minimaux du poset. Nous montrons aussi que lorsqu'on ne s'int{\'e}resse qu'au nombre d'{\'e}l{\'e}ments minimaux, notre fonction g{\'e}n{\'e}ratrice assez compliqu{\'e}e peut {\^e}tre simplifi{\'e}e en P(t,z)=∑n,k ≥0 pn,k tn zk = 1+ ∑n ≥0 zt(1-zt)n+1∏i=1n (1-(1-t)i), o{\`u} pn,k est le nombre de posets (2+2)-libres de taille n avec k {\'e}l{\'e}ments minimaux.",
keywords = "(2+2)-free posets, minimal elements, subposet",
author = "Sergey Kitaev and Jeffrey Remmel",
year = "2010",
month = "8",
language = "English",
pages = "821--832",
note = "22nd International Conference on Formal Power Series & Algebraic Combinatorics ; Conference date: 02-08-2010 Through 06-08-2010",

}

Kitaev, S & Remmel, J 2010, 'Enumerating (2+2)-free posets by the number of minimal elements and other statistics' 22nd International Conference on Formal Power Series & Algebraic Combinatorics, San Francisco, United States, 2/08/10 - 6/08/10, pp. 821-832.

Enumerating (2+2)-free posets by the number of minimal elements and other statistics. / Kitaev, Sergey; Remmel, Jeffrey.

2010. 821-832 Poster session presented at 22nd International Conference on Formal Power Series & Algebraic Combinatorics, San Francisco, United States.

Research output: Contribution to conferencePoster

TY - CONF

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

AU - Kitaev, Sergey

AU - Remmel, Jeffrey

PY - 2010/8

Y1 - 2010/8

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. In a recent paper, Bousquet-Mélou et al. found, using so called ascent sequences, the generating function for the number of (2+2)-free posets: P(t)=∑n≥0 ∏i=1n ( 1-(1-t)i). We extend this result by finding the generating function for (2+2)-free posets when four statistics are taken into account, one of which is the number of minimal elements in a poset. We also show that in a special case when only minimal elements are of interest, our rather involved generating function can be rewritten in the form P(t,z)=∑n,k ≥0 pn,k tn zk = 1+ ∑n ≥0zt(1-zt)n+1∏i=1n (1-(1-t)i) where pn,k equals the number of (2+2)-free posets of size n with k minimal elements.Résumé. Un poset sera dit (2+2)-libre s'il ne contient aucun sous-poset isomorphe à 2+2, l'union disjointe de deux chaînes à deux éléments. Dans un article récent, Bousquet-Mélou et al. ont trouvé, à l'aide de ``suites de montées'', la fonction génératrice des nombres de posets (2+2)-libres: c'est P(t)=∑n≥0 ∏i=1n ( 1-(1-t)i). Nous étendons ce résultat en trouvant la fonction génératrice des posets (2+2)-libres rendant compte de quatre statistiques, dont le nombre d'éléments minimaux du poset. Nous montrons aussi que lorsqu'on ne s'intéresse qu'au nombre d'éléments minimaux, notre fonction génératrice assez compliquée peut être simplifiée en P(t,z)=∑n,k ≥0 pn,k tn zk = 1+ ∑n ≥0 zt(1-zt)n+1∏i=1n (1-(1-t)i), où pn,k est le nombre de posets (2+2)-libres de taille n avec k éléments minimaux.

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. In a recent paper, Bousquet-Mélou et al. found, using so called ascent sequences, the generating function for the number of (2+2)-free posets: P(t)=∑n≥0 ∏i=1n ( 1-(1-t)i). We extend this result by finding the generating function for (2+2)-free posets when four statistics are taken into account, one of which is the number of minimal elements in a poset. We also show that in a special case when only minimal elements are of interest, our rather involved generating function can be rewritten in the form P(t,z)=∑n,k ≥0 pn,k tn zk = 1+ ∑n ≥0zt(1-zt)n+1∏i=1n (1-(1-t)i) where pn,k equals the number of (2+2)-free posets of size n with k minimal elements.Résumé. Un poset sera dit (2+2)-libre s'il ne contient aucun sous-poset isomorphe à 2+2, l'union disjointe de deux chaînes à deux éléments. Dans un article récent, Bousquet-Mélou et al. ont trouvé, à l'aide de ``suites de montées'', la fonction génératrice des nombres de posets (2+2)-libres: c'est P(t)=∑n≥0 ∏i=1n ( 1-(1-t)i). Nous étendons ce résultat en trouvant la fonction génératrice des posets (2+2)-libres rendant compte de quatre statistiques, dont le nombre d'éléments minimaux du poset. Nous montrons aussi que lorsqu'on ne s'intéresse qu'au nombre d'éléments minimaux, notre fonction génératrice assez compliquée peut être simplifiée en P(t,z)=∑n,k ≥0 pn,k tn zk = 1+ ∑n ≥0 zt(1-zt)n+1∏i=1n (1-(1-t)i), où pn,k est le nombre de posets (2+2)-libres de taille n avec k éléments minimaux.

KW - (2+2)-free posets

KW - minimal elements

KW - subposet

UR - http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAN0160

M3 - Poster

SP - 821

EP - 832

ER -

Kitaev S, Remmel J. Enumerating (2+2)-free posets by the number of minimal elements and other statistics. 2010. Poster session presented at 22nd International Conference on Formal Power Series & Algebraic Combinatorics, San Francisco, United States.