Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



A simple and direct derivation
for the number of noncrossing partitions

Authors: S. C. Liaw, H. G. Yeh, F. K. Hwang and G. J. Chang
Journal: Proc. Amer. Math. Soc. 126 (1998), 1579-1581
MSC (1991): Primary 05A18
MathSciNet review: 1468196
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Kreweras considered the problem of counting noncrossing partitions of the set $\{1,2,\cdots,n\}$, whose elements are arranged into a cycle in its natural order, into $p$ parts of given sizes $n_1,n_2,\cdots,n_p$ (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 [Enhancements On Off] (What's this?)

  • 1. H. W. Becker, Planar rhyme schemes, Bull. Amer. Math. Soc. 58 (1952) 39.
  • 2. J. Bonin, L. Shapiro, and R. Simion, Some $q$-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

G. J. Chang

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
Article copyright: © Copyright 1998 American Mathematical Society

American Mathematical Society