Parking functions and noncrossing partitions
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}\).
scientific article; zbMATH DE number 1118064