Parking functions and noncrossing partitions. (English) Zbl 0883.06001

Electron. J. Comb. 4, No. 2, Research paper R20, 14 p. (1997); printed version J. Comb. 4, No. 2, 261-274 (1997).
Summary: A parking function is a sequence \((a_1,\dots,a_n)\) of positive integers such that if \(b_1\leq b_2\leq \cdots\leq b_n\) is the increasing rearrangement of \(a_1,\dots, a_n\), then \(b_i\leq i\). A noncrossing partition of the set \([n]=\{1,2,\dots,n\}\) is a partition \(\pi\) of the set \([n]\) with the property that if \(a<b<c<d\) and some block \(B\) of \(\pi\) contains both \(a\) and \(c\), while some block \(B'\) of \(\pi\) contains both \(b\) and \(d\), then \(B=B'\). We establish some connections between parking functions and noncrossing partitions. A generating function for the flag \(f\)-vector of the lattice NC\(_{n+1}\) of noncrossing partitions of \([n+1]\) is shown to coincide (up to the involution \(\omega\) on symmetric function) with Haiman’s parking function symmetric function. We construct an edge labeling of NC\(_{n+1}\) whose chain labels are the set of all parking functions of length \(n\). This leads to a local action of the symmetric group \({\mathfrak S}_n\) on NC\(_{n+1}\).


06A07 Combinatorics of partially ordered sets
05E05 Symmetric functions and generalizations
05A15 Exact enumeration problems, generating functions
05E10 Combinatorial aspects of representation theory
05E25 Group actions on posets, etc. (MSC2000)
Full Text: EuDML EMIS