ON THE STRUCTURE OF THE LATTICE OF NONCROSSING PARTITIONS

被引：91

作者：

SIMION, R

ULLMAN, D

机构：

[1] Department of Mathematics, The George Washington University, Washington

来源：

DISCRETE MATHEMATICS | 1991年 / 98卷 / 03期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1016/0012-365X(91)90376-D

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We show that the lattice of noncrossing (set) partitions is self-dual and that it admits a symmetric chain decomposition. The self-duality is proved via an order-reversing involution. Two proofs are given of the existence of the symmetric chain decomposition, one recursive and one constructive. Several identities involving Catalan numbers emerge from the construction of the symmetric chain decomposition.

引用

页码：193 / 206

页数：14

共 16 条

[1]

[Anonymous], 1979, COMBINATORIAL THEORY

[2]

BJORNER A, 1984, CONT MATH, V34, P179

[3]

CANFIELD R, 1978, B AM MATH SOC, V84, P164

[4]

COMTET L, 1974, ADV COMBINATORICS

[5] SHUFFLE OF PARENTHESIS SYSTEMS AND BAXTER PERMUTATIONS [J].

CORI, R ;

DULUCQ, S ;

VIENNOT, G .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 1986, 43 (01) :1-22

[6]

DEBRUIJN NG, 1952, NIEUW ARCH WISK, V23, P191

[7]

EDELMAN P, 1989, UNPUB CHAINS LATTICE

[8] MULTICHAINS, NON-CROSSING PARTITIONS AND TREES [J].

EDELMAN, PH .

DISCRETE MATHEMATICS, 1982, 40 (2-3) :171-179

[9] CHAIN ENUMERATION AND NON-CROSSING PARTITIONS [J].

EDELMAN, PH .

DISCRETE MATHEMATICS, 1980, 31 (02) :171-180

[10]

EGECIOGLU O, 1983, FIBONACCI QUART, V21, P65

← 1 2 →