|
A simple and direct derivation for the number of noncrossing partitions
Author(s):
S.
C.
Liaw;
H.
G.
Yeh;
F.
K.
Hwang;
G.
J.
Chang
Journal:
Proc. Amer. Math. Soc.
126
(1998),
1579-1581.
MSC (1991):
Primary 05A18
Retrieve article in:
PDF
This article is available free of charge
Abstract |
References |
Similar articles |
Additional information
Abstract:
Kreweras considered the problem of counting noncrossing partitions of the set  , whose elements are arranged into a cycle in its natural order, into  parts of given sizes  (but not specifying which part gets which size). He gave a beautiful and surprising result whose proof resorts to a recurrence relation. In this paper we give a direct, entirely bijective, proof starting from the same initial idea as Kreweras' proof.
References:
- 1.
- H. W. Becker, Planar rhyme schemes, Bull. Amer. Math. Soc. 58 (1952) 39.
- 2.
- J. Bonin, L. Shapiro, and R. Simion, Some
 -analogues of the Schröder numbers arising from combinatorics on lattice paths, J. Stat. Planning & Inference 34 (1993) 35-55. MR 94e:05029 - 3.
- A. Denise and R. Simion, Two combinatorial statistics on Dyck paths, Disc. Math. 135 (1995) 155-176. MR 96e:05010
- 4.
- N. Dershowitz and S. Zaks, Ordered trees and non-crossing partitions, Disc. Math. 62 (1986) 215-218. MR 88c:05008
- 5.
- P. H. Edelman, Chain enumeration and non-crossing partitions, Disc. Math. 31 (1980) 171-180. MR 81i:01018
- 6.
- P. H. Edelman and R. Simion, Chains in the lattice of noncrossing partitions, Disc. Math. 126 (1994) 107-119. MR 95f:05012
- 7.
- G. Kreweras, Sur les partitions non croisées d'un cycle, Disc. Math. 1 (1972) 333-350. MR 46:8852
- 8.
- G. Kreweras, Une famille d'identités mettant en jeu toutes les partitions d'un ensemble fini de variables en un nombre donné de classes, C. R. Acad. Sci. Paris 270 (1970) 1140-1143. MR 41:3291
- 9.
- A. Nica and R. Speicher, A ``Fourier transform'' for multiplicative functions on non-crossing partitions, J. Algeb. Comb., 6 (1997), 141-160. CMP 97:09
- 10.
- Y. Poupard, Étude et dénombrement parallèles des partitions non croisées d'un cycle et des découpages d'un polygone convexe, Disc. Math. 2 (1972) 279-288. MR 46:3369
- 11.
- R. Simion, Combinatorial statistics on non-crossing partitions, J. Comb. Theory, Series A 66 (1994) 270-301. MR 95e:05009
- 12.
- R. Simion and D. Ullman, On the structure of the lattice on non-crossing partitions, Disc. Math. 98 (1991) 193-206. MR 92j:06003
- 13.
- R. Speicher, Multiplicative functions on the lattice of noncrossing partitions and free convolution, Math. Ann. 298 (1994) 611-628. MR 95h:05012
- 14.
- R. P. Stanley, Parking functions and noncrossing partitions, Elect. J. Comb. 4 (1997), no. 2, res. paper 20, approx. 14 pp. (electronic). CMP 97:11
Similar Articles:
Retrieve articles in Proceedings of the American Mathematical Society
with MSC
(1991):
05A18
Retrieve articles in all Journals with MSC
(1991):
05A18
Additional Information:
S.
C.
Liaw
Affiliation:
Department of Applied Mathematics, National Chiao Tung University, Hsinchu 30050, Taiwan
H.
G.
Yeh
Affiliation:
Department of Applied Mathematics, National Chiao Tung University, Hsinchu 30050, Taiwan
F.
K.
Hwang
Affiliation:
Department of Applied Mathematics, National Chiao Tung University, Hsinchu 30050, Taiwan
G.
J.
Chang
Affiliation:
Department of Applied Mathematics, National Chiao Tung University, Hsinchu 30050, Taiwan
Email:
gjchang@math.nctu.edu.tw
DOI:
10.1090/S0002-9939-98-04546-8
PII:
S 0002-9939(98)04546-8
Received by editor(s):
November 6, 1996
Additional Notes:
Liaw, Yeh, and Chang were supported in part by the National Science Council under grant NSC86-2115-M009-002.
Communicated by:
Jeffry N. Kahn
Copyright of article:
Copyright
1998,
American Mathematical Society
|
Comments: webmaster@ams.org