Parking functions and noncrossing partitions (Q1378532)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Parking functions and noncrossing partitions
scientific article

    Statements

    Parking functions and noncrossing partitions (English)
    0 references
    0 references
    15 February 1998
    0 references
    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}\).
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    parking function
    0 references
    noncrossing partition
    0 references
    generating function
    0 references