Parking functions and noncrossing partitions. (English) Zbl 0883.06001

Stanley, Richard P.

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}\).

MSC:

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)

Keywords:

parking function; noncrossing partition; generating function