A simple and direct derivation for the number of noncrossing partitions

Liaw, S.; Yeh, H.; Hwang, F.; Chang, G.

doi:10.1090/S0002-9939-98-04546-8

A simple and direct derivation for the number of noncrossing partitions
HTML articles powered by AMS MathViewer

by S. C. Liaw, H. G. Yeh, F. K. Hwang and G. J. Chang PDF

Proc. Amer. Math. Soc. 126 (1998), 1579-1581 Request permission

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

H. W. Becker, Planar rhyme schemes, Bull. Amer. Math. Soc. 58 (1952) 39.
Joseph Bonin, Louis Shapiro, and Rodica Simion, Some $q$-analogues of the Schröder numbers arising from combinatorial statistics on lattice paths, J. Statist. Plann. Inference 34 (1993), no. 1, 35–55. MR 1209988, DOI 10.1016/0378-3758(93)90032-2
Alain Denise and Rodica Simion, Two combinatorial statistics on Dyck paths, Discrete Math. 137 (1995), no. 1-3, 155–176. MR 1312450, DOI 10.1016/0012-365X(93)E0147-V
Nachum Dershowitz and Shmuel Zaks, Ordered trees and noncrossing partitions, Discrete Math. 62 (1986), no. 2, 215–218. MR 863045, DOI 10.1016/0012-365X(86)90120-2
I. M. Sheffer, Some properties of polynomial sets of type zero, Duke Math. J. 5 (1939), 590–622. MR 81
Paul H. Edelman and Rodica Simion, Chains in the lattice of noncrossing partitions, Discrete Math. 126 (1994), no. 1-3, 107–119. MR 1264480, DOI 10.1016/0012-365X(94)90257-7
G. Kreweras, Sur les partitions non croisées d’un cycle, Discrete Math. 1 (1972), no. 4, 333–350 (French). MR 309747, DOI 10.1016/0012-365X(72)90041-6
Germain 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 Sér. A-B 270 (1970), A1140–A1143 (French). MR 258645
A. Nica and R. Speicher, A “Fourier transform” for multiplicative functions on non-crossing partitions, J. Algeb. Comb., 6 (1997), 141–160.
Yves Poupard, Étude et dénombrement parallèles des partitions non-croisées d’un cycle et des découpages d’un polygone convexe, Discrete Math. 2 (1972), no. 3, 279–288 (French). MR 304234, DOI 10.1016/0012-365X(72)90008-8
Rodica Simion, Combinatorial statistics on noncrossing partitions, J. Combin. Theory Ser. A 66 (1994), no. 2, 270–301. MR 1275735, DOI 10.1016/0097-3165(94)90066-3
Rodica Simion and Daniel Ullman, On the structure of the lattice of noncrossing partitions, Discrete Math. 98 (1991), no. 3, 193–206. MR 1144402, DOI 10.1016/0012-365X(91)90376-D
Roland Speicher, Multiplicative functions on the lattice of noncrossing partitions and free convolution, Math. Ann. 298 (1994), no. 4, 611–628. MR 1268597, DOI 10.1007/BF01459754
R. P. Stanley, Parking functions and noncrossing partitions, Elect. J. Comb. 4 (1997), no. 2, res. paper 20, approx. 14 pp. (electronic).