%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentclass[12pt]{article} 
\usepackage{amssymb,latexsym}
\parskip0.20truein
\textwidth6.0truein
\textheight9.0truein

\begin{document}
\newcommand{\qbc}[2]{ {\left [{#1 \atop #2}\right ]}}
\newcommand{\anbc}[2]{{\left\langle {#1 \atop #2} \right\rangle}}
\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}
\newcommand{\nc}{\mathrm{NC}}
\newcommand{\ncn}{\mathrm{NC}_{n+1}}
\newcommand{\ncnk}{\mathrm{NC}_{n+1}^{(k)}}
\newcommand{\sn}{\mathfrak{S}_n}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\pfn}{\mathrm{PF}_n}
\newcommand{\pfnk}{\mathrm{PF}_n^{(k)}}

\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics 4, no. 2, (1997), \#R20\hfill} 
\thispagestyle{empty}

\title{Parking Functions and Noncrossing Partitions}
\author{Richard P.\ Stanley\footnote{Partially supported by NSF grant
    DMS-9500714.}\\
  Department of Mathematics\\
  Massachusetts Institute of Technology\\
  Cambridge, MA 02139\\
  \texttt{rstan@math.mit.edu}\\[.1in] 
 {\small Submitted: August 12, 1996;
 Accepted: November 12, 1996}\\[.1in]
    \emph{Dedicated to Herb Wilf on the occasion of his sixty-fifth birthday}
   } 
  \date{}

\maketitle

\vspace{-.2in}
\abstract{A \emph{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
\emph{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}$.
\vspace{.2in}

\noindent MR primary subject number: 06A07\\
MR secondary subject numbers: 05A15, 05E05, 05E10, 05E25
\vspace{.3in}

\textbf{1. Introduction.} A \emph{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$.\footnote{Minor variations of this definition
  appear in the literature, but they are equivalent to the definition
  given here. For instance, in \cite{rs:rota} parking functions are
  obtained from the definition given here by subtracting one from
  each coordinate.} Parking functions were introduced by Konheim
and Weiss \cite{k-w} in connection with a hashing problem (though the
term ``hashing'' was not used). See this reference for the
reason (formulated in a way which now would be considered politically
incorrect) 
for the terminology ``parking function.'' Parking functions
were subsequently related to labelled trees and to hyperplane
arrangements. For further information on these connections see
\cite{rs:rota} and the references given there. In this paper we will
develop a connection between parking functions and another topic,
viz., noncrossing partitions.

A \emph{noncrossing partition} of the set $[n]=\{1,2,\dots,n\}$ is a
partition $\pi$ of the set $[n]$ (as defined e.g.\ in \cite[p.\ 
33]{rs:ec}) 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'$. The study of noncrossing
partitions goes back at least to H. W. Becker \cite{becker}, where
they are called ``planar rhyme schemes.'' The systematic study of
noncrossing partitions began with Kreweras \cite{krew} and Poupard
\cite{poup}. For some further work on noncrossing partitions, see
\cite{e-s}\cite{n-s}\cite{simion}\cite{speicher} and the references
given there.

A fundamental property of the set of noncrossing partitions of $[n]$
is that it can be given a natural partial ordering. Namely, we define
$\pi\leq \sigma$ if every block of $\pi$ is contained in a block of
$\sigma$. In other words, $\pi$ is a \emph{refinement} of $\sigma$.
Thus the poset NC$_n$ of all noncrossing partitions of $[n]$ is an
induced subposet of the lattice $\Pi_n$ of all partitions of $[n]$
\cite[Example 3.10.4]{rs:ec}. In fact, NC$_n$ is a lattice with a
number of remarkable properties. We will develop additional properties
of the lattice NC$_n$ which connect it directly with parking
functions.

{\bf 2. The parking function symmetric function.} Let $P$ be a finite
graded poset of rank $n$ with $\hat{0}$ and $\hat{1}$ and with rank
function $\rho$. (See \cite[Ch.\
3]{rs:ec} for poset terminology and notation used here.) Let $S$ be a
subset of $[n-1]=\{1,2,\dots,n-1\}$, and define
$\alpha_P(S)$ to be the number of chains $\hat{0}=t_0<t_1<\cdots
<t_s=\hat{1}$ of $P$ such that $S=\{\rho(t_1),\rho(t_2),\dots,
\rho(t_{s-1})\}$. The function $\alpha_P$ is called the \emph{flag
  $f$-vector} of $P$. For $S\subseteq [n-1]$ further define
  $$ \beta_P(S) = \sum_{T\subseteq S} (-1)^{|S-T|} \alpha_P(T). $$
The function $\beta_P$ is called the \emph{flag $h$-vector} of
$P$. Knowing 
$\alpha_P$ is the same as knowing $\beta_P$ since
  $$ \alpha_P(S) = \sum_{T\subseteq S}\beta_P(T). $$
For further information on flag $f$-vectors and $h$-vectors (using a
different terminology), see \cite[Ch.\ 3.12]{rs:ec}.

There is a kind of generating function for the flag $h$-vector which
is often useful in understanding the combinatorics of $P$. Regarding
$n$ as fixed, let $S\subseteq [n-1]$ 
and define a formal power series $Q_S=Q_S(x) = Q_S(x_1,x_2,\dots)$ in
the (commuting) indeterminates $x_1,x_2,\dots$ by
  $$ Q_S = \sum_{{i_1\leq i_2\leq\cdots\leq i_n\atop i_j<i_{j+1}\ 
   \mathrm{if}\ j\in S}} x_{i_1}x_{i_2}\cdots x_{i_n}. $$
$Q_S$ is known as \emph{Gessel's quasisymmetric function}
   \cite{gessel} (see also \cite[{\S}5.4]{k-t}\cite{m-r}\cite[Ch.\
   9.4]{reut}). The functions $Q_S$, where $S$ ranges 
   over all subsets of $[n-1]$, are linearly independent over any
   field. For our ranked poset $P$ we then define
  $$ F_P = \sum_{S\subseteq [n-1]} \beta_P(S)Q_S. $$
This definition (in a different but equivalent form) was first
suggested by R. Ehrenborg \cite[Def.\ 4.1]{ehr} and is further
investigated in 
\cite{rs:eljc}. One of the results of \cite{rs:eljc} (Thm.\ 1.4)
is the following proposition (which is equivalent to a simple
generalization of \cite[Exercise 3.65]{rs:ec}).

{\bf 2.1 Proposition.} \emph{Let $P$ be as above. If every interval
  $[u,v]$ of $P$ is rank-symmetric (i.e., $[u,v]$ has as many elements
  of rank $i$ as of corank $i$), then $F_P$ is a symmetric function of
  $x_1, x_2, \dots$.}

We now consider the case $P=\nc_{n+1}$. (We take $\nc_{n+1}$ rather
than $\nc_n$ because $\nc_{n+1}$ has rank $n$.) It is well-known that
every interval in $\nc_{n+1}$ is self-dual and hence
rank-symmetric. (This follows from the 
fact that $\ncn$ is itself self-dual \cite[{\S}3]{krew}\cite[Thm.\ 
1.1]{s-u} and that every interval of $\ncn$ is a product of $\nc_i$'s
\cite[{\S}1.3]{n-s}.) Hence $F_{\nc_{n+1}}$ is a symmetric function,
  and we can ask whether it is already known. In fact, $F_{\ncn}$ has
  previously appeared in connection with parking functions, as stated
  below in Theorem 2.3. First we provide some background information
  related to parking functions.

Let ${\cal P}_n$ denote the set of all parking functions of length
$n$. The symmetric group $\sn$ acts on ${\cal P}_n$ by permuting
coordinates. Let PF$_n = \mathrm{PF}_n(x)$ denote the Frobenius
characteristic of the character of this action \cite[Ch.\ 1.7]{mac}.
Thus if
  $$ \mathrm{PF}_n = \sum_{\lambda\vdash n}
  \tau_{\lambda,n}s_\lambda $$
is the expansion of PF$_n$ in terms of Schur functions, then
  $\tau_{\lambda, n}$ is the multiplicity of the irreducible character
  of $\sn$ indexed by $\lambda$ in the action of $\sn$ on ${\cal
  P}_n$. The symmetric function PF$_n$ was first considered in the
  context of parking functions by Haiman \cite[{\S}{\S}2.6 and
  4.1]{haiman}. Following Haiman, we will give a formula for $\pfn$
  from which its expansion in terms of various symmetric function
  bases is immediate. The key observation (due to Pollack
  \cite[p.\ 13]{f-r} and repeated in \cite[p.\ 28]{haiman}) is the
  following (which we state in a slightly different form than Pollack). 
Let $\mathbb{Z}_{n+1}$ denote the set $\{1,2,\dots,
  n+1\}$, with addition modulo $n+1$. Then every coset of the subgroup
  $H$ of $\mathbb{Z}_{n+1}^n$ generated by $(1,1,\dots,1)$ contains exactly
  one parking function. From this it follows easily that 
  \beq  \pfn = \frac{1}{n+1} [t^n] H(t)^{n+1}, \label{eq:pff} \eeq
where $[t^n]G(t)$ denotes the coefficient of $t^n$ in the power series
$G(t)$, and where
  $$ H(t) = 1 + h_1t + h_2 t^2 + \cdots = \frac{1}{(1-x_1t)(1-x_2t)
    \cdots}, $$
the generating function for the complete symmetric functions
    $h_i$. (Throughout this paper we adhere to symmetric function
    terminology and notation as in Macdonald \cite{mac}.)

The following proposition summarizes some of the properties of $\pfn$
which follow easily from equation (\ref{eq:pff}).

{\bf 2.2 Proposition.} (a) \emph{We have the following expansions.}
  \begin{eqnarray} \pfn & = & \sum_{\lambda\vdash n} (n+1)^{\ell
   (\lambda)-1}z_\lambda^{-1}p_\lambda \label{eq:pfp}\\
    & = & \sum_{\lambda\vdash n} \frac{1}{n+1} s_\lambda(1^{n+1})
    s_\lambda \label{eq:pfs}\\ 
    & = & \sum_{\lambda\vdash n}\frac{1}{n+1}\left[ \prod_i {\lambda_i
    +n\choose n}\right] m_\lambda \label{eq:pfm}\\ & = &
    \sum_{\lambda\vdash n} \frac{n(n-1)\cdots(n-\ell(\lambda)+2)}
   {m_1(\lambda)!\cdots m_n(\lambda)!}
   h_\lambda. \label{eq:pfh}\\ \omega\pfn & = &
    \sum_{\lambda\vdash n}\frac{1}{n+1}\left[ \prod_i {n+1
    \choose \lambda_i}\right] m_\lambda. \label{eq:wpfm} \end{eqnarray}
\emph{Here $s_\lambda(1^{n+1})$ denotes $s_\lambda$ with $n+1$
  variables set equal to 1 and the others to 0, and is evaluated
  explicitly e.g.\ in \cite[Example 4, p.\ 45]{mac}. Moreover,
  $\ell(\lambda)$ is the number of parts of $\lambda$; $z_\lambda$ is
  as in \cite[p.\ 24]{mac}; $m_i(\lambda)$ denotes the number of parts
  of $\lambda$ equal to $i$; and $\omega$ is the standard involution
  \cite[pp.\ 21--22]{mac} on symmetric functions.}

  (b) \emph{We also have that}
  \beq \sum_{n\geq 0}\pfn\, t^{n+1} = \left( tE(-t)
    \right)^{\langle -1\rangle}, \label{eq:pflag} \eeq
\emph{where $E(t)=\sum_{n\geq 0}e_nt^n$, $e_n$ denotes the $n$th
  elementary symmetric function, and 
  $^{\langle -1\rangle}$ denotes compositional inverse.}

{\bf Proof.} (a) Let $C(x,y)=\prod_{i,j}(1-x_iy_j)^{-1}$, the
well-known ``Cauchy product.'' Then $H(t)^{n+1}$ is obtained by
setting $n+1$ of the $y_i$'s equal to $t$ and the others equal to 0.
 From this all the expansions in (a) follow from (\ref{eq:pff}) and
well-known expansions for $C(x,y)$ and $\omega_xC(x,y)$ (where
$\omega_x$ denotes $\omega$ acting on the $x$ variables only). To give
just one example (needed in the first proof of Theorem 2.3), we have
  $$ \omega_xC(x,y) = \sum_\lambda m_\lambda(x)e_\lambda(y). $$
Hence 
  $$ \omega\pfn = \sum_{\lambda\vdash n} \frac{1}{n+1}
    e_\lambda(1^{n+1}) m_\lambda. $$
Equation (\ref{eq:wpfm}) now follows from the simple fact that
$e_k(1^{n+1}) = {n+1\choose k}$. We should point out that
    (\ref{eq:pfp}) appears (in a dual form) in \cite[(9)]{g-j},
    (\ref{eq:pfs}) appears in \cite[(28)]{haiman}, and (\ref{eq:pfh})
appears (again in dual form) in \cite[(82)]{haiman}\cite[Example
    24(a), p.\ 35]{mac}. A $q$-analogue of PF$_n$ and of much of our
    Proposition~2.2 appears in \cite{g-h}.

(b) This is an immediate consequence of (\ref{eq:pff}), the fact that
  \beq \frac{1}{H(t)} = E(-t), \label{eq:he} \eeq 
and the Lagrange inversion formula, as in \cite[{\S}4.1]{haiman}.
See also \cite[Examples 2.24--2.25, pp.\ 35--36]{mac}.  $\ \Box$

Let $P$ be a Cohen-Macaulay poset with $\hat{0}$ and $\hat{1}$ such
that every interval is rank-symmetric. Thus $F_P$ is a symmetric
function. In \cite[Conj.\ 2.3]{rs:eljc} it was conjectured that $F_P$
is \emph{Schur positive}, i.e., a nonnegative linear combination of
Schur functions. Equation (\ref{eq:pfs}) confirms this conjecture in
the case $P=\ncn$. However, it turns out that the conjecture is in
fact \emph{false}. A counterexample is provided by the following poset
$P$. The elements of $P$ consist of all integer vectors
$(a_1,a_2,b_1,b_2,b_3,b_4)$ such that $0\leq a_1\leq 5$, $0\leq
a_2\leq 1$, $0\leq b_1\leq 3$, $0\leq b_2,b_3,b_4\leq 1$, and
$a_1+a_2= b_1+b_2+b_3 +b_4$, ordered componentwise. It can be shown
that $P$ is lexicographically shellable and hence
Cohen-Macaulay, and it is easy to see that $P$ is locally
rank-symmetric (even locally self-dual). Moreover,
  $$ F_P = s_6 + 7s_{51} + 6s_{42} + 2s_{33} +18s_{411}+10s_{321}
    -s_{222}+20s_{3111}+5s_{2211}+8s_{21111}. $$
    
The symmetric functions PF$_n$ also have an unexpected connection with
the multiplication of conjugacy classes in the symmetric group (the
work of Farahat-Higman \cite{f-h}). For further details see
\cite{g-j}\cite[Ch.\ I, Example 7.25, pp.\ 132--134]{mac}. This
connection was exploited by Goulden and Jackson \cite{g-j} to compute
some connection coefficients for the symmetric group.
  
The expansion (\ref{eq:pfh}) of $\pfn$ in terms of the $h_\lambda$'s
has a simple interpretation in terms of parking functions.  Suppose
that $a=(a_1,\dots, a_n) \in {\cal P}_n$. Let $r_1,\dots,r_k$ be the
positive multiplicities of the elements of the multiset
$\{a_1,\dots,a_n\}$ (so $r_1+\cdots +r_k=n$). Then the action of $\sn$
on the orbit $\sn a$ has characteristic $h_{r_1}\cdots h_{r_k}$. For
instance, a set of orbit representatives in the case $n=3$ is
$(1,1,1), (2,1,1), (3,1,1), (2,2,1)$, and $(3,2,1)$. Hence PF$_3 =
h_3+h_2h_1+h_2h_1 + h_2h_1 + h_1^3 = h_3 + 3h_{21} + h_{111}$. In
general it follows that the coefficient $q_\lambda$ of $h_\lambda$ in
$\pfn$ is equal to the number of orbits of parking functions of length
$n$ such that the terms of their elements have multiplicities
$\lambda_1,\lambda_2,\dots$ (in some order). Equation (\ref{eq:pfh})
then gives an explicit formula for this number. The \emph{total}
number of parking functions whose terms have multiplicities
$\lambda_1,\lambda_2,\dots$ is $q_\lambda$ times the size of the
orbit, i.e., $q_\lambda{n\choose \lambda_1,\lambda_2,\dots}$.
 
We are now ready to discuss the connection between PF$_n$ and
noncrossing partitions. The basic result is the following.

{\bf 2.3 Theorem.} \emph{For any $n\geq 0$ we have} 
  $$ F_{\ncn} = \omega\mathrm{PF}_n. $$
%
  {\bf Proof.} Let $\lambda=(\lambda_1,\dots,\lambda_\ell)$ be a
  partition of $n$ with $\lambda_\ell>0$. It is immediate from the
  definition of $F_P$ in Section 1 (see \cite[Prop.\ 1.1]{rs:eljc})
  that if 
  $F_P$ is symmetric and $F_P=\sum_\lambda c_\lambda m_\lambda$, then
  \beq c_\lambda= \alpha_P(\lambda_1, \lambda_1+\lambda_2,\dots,
   \lambda_1+\lambda_2+\cdots
  +\lambda_{\ell-1}). \label{eq:fpml} \eeq 
The proof now follows by comparing equation
  (\ref{eq:wpfm}) with the evaluation of $\alpha_{\ncn}(S)$ due to
  Edelman \cite[Thm.\ 3.2]{edel}. $\ \Box$

It follows from the above discussion that $\pfn$ encodes in a simple
way the flag $f$-vector and flag $h$-vector of $\ncn$, viz., (1) the
coefficient of $Q_S$ in the expansion of $\pfn$ in terms of Gessel's
quasisymmetric function is equal to $\beta_{\ncn}(S)$, and (2) if the
elements of $S\subseteq [n-1]$ are $j_1<\cdots<j_r$ and if $\lambda$
is the partition whose parts are the numbers $j_1, j_2-j_1, j_3-j_2,
\dots, n-j_r$, then the coefficient of $m_\lambda$ in the expansion of
$\pfn$ in terms of monomial symmetric functions is equal to
$\alpha_{\ncn}(S)$. 
There is a further statistic on $\ncn$ closely related to $\pfn$,
namely, the number of noncrossing partitions of $[n+1]$ of \emph{type}
$\lambda$, i.e., with block sizes $\lambda_1, \lambda_2, \dots$.

{\bf 2.4 Proposition.} \emph{Let $\lambda$ be a partition of $n$.
  The coefficient of $h_\lambda$ in the expansion of $\pfn$ in
  terms of complete symmetric functions is equal to
  the number $u_\lambda$ of noncrossing partitions of type $\lambda$.}

{\bf First proof.} Compare equation (\ref{eq:pfh}) with the explicit
value of the number of noncrossing partitions of type $\lambda$ found
by Kreweras \cite[Thm.\ 4]{krew}. $\ \Box$

{\bf Second proof.}  Our second proof is based on the following
noncrossing analogue of the exponential formula due to Speicher
\cite[p.\ 616]{speicher}. (For a more general result, see
\cite{n-s}.)
Given a function $f:\mathbb{N}\rightarrow R$
(where $R$ is a commutative ring with identity) with $f(0)=1$, define
a function $g:\mathbb{N}\rightarrow R$ by $g(0)=1$ and
  \beq g(n) = \sum_{\pi=\{B_1,\dots,B_k\}\in \nc_n} f(\#B_1)
   \cdots f(\#B_k). \label{eq:gn} \eeq
Let $F(t)=\sum_{n\geq 0}f(n)t^n$. Then
  \beq \sum_{n\geq 0}g(n)t^{n+1} = \left( \frac{t}{F(t)}\right)^
   {\langle -1\rangle}. \label{eq:speich} \eeq
In equation (\ref{eq:gn}) take $f(n)=h_n$, the complete symmetric
function. Then $g(n)$ becomes $\sum_{\lambda\vdash n} u_\lambda
h_\lambda$. But Proposition 2.2(b), together with equations
(\ref{eq:speich}) and (\ref{eq:he}), shows that $g(n)=\mathrm{PF}_n$,
and the proof follows. $\ \Box$

Note the curious fact that Theorem~2.3 refers to NC$_{n+1}$, while
Proposition~2.4 refers to NC$_n$.
Proposition~2.4, together with the definition of PF$_n$, show that the
number of noncrossing partitions of type $\lambda\vdash n$ is equal
to the number of $\sn$-orbits of parking functions of length $n$ and
part multiplicities $\lambda$. It is easy to give a bijective proof of
this fact (shown to me by R.\ Simion), which we omit.

{\bf 3. An edge labeling of the noncrossing partition lattice.} If $P$
is a locally finite poset, then an \emph{edge} of $P$ is a pair
$(u,v)\in P\times P$ such that $v$ covers $u$ (i.e., $u<v$ and no
element $t$ satisfies $u<t<v$). An \emph{edge labeling} of $P$ is a
map $\Lambda:{\cal E}(P)\rightarrow \mathbb{Z}$, where ${\cal E}(P)$
is the set of edges of $P$. Edge labelings of
posets have many applications; in particular, if $P$ has what is known
as an \emph{EL-labeling}, then $P$ is lexicographically shellable and
hence Cohen-Macaulay \cite{bj}\cite{b-w}. An EL-labeling of $\ncn$ was
defined by Bj\"orner \cite[Example 2.9]{bj} and further exploited by
Edelman and Simion \cite{e-s}. Here we define a new labeling, which up
to an unimportant reindexing is EL and is intimately related to
parking functions.  

Let $(\pi,\sigma)$ be an
edge of $\ncn$. Thus $\sigma$ is obtained from $\pi$ by merging
together two blocks $B$ and $B'$. Suppose that $\min B<\min B'$, where
$\min S$ denotes the minimum element of a finite set $S$ of
integers. Define 
  \beq \Lambda(\pi,\sigma) = \max\{i\in B: i<B'\}, \label{eq:lab} \eeq
where $i<B'$ denotes that $i$ is less than every element of $B'$. For
instance, if $B=\{2,4,5,15,17\}$ and $B'=\{7,10,12,13\}$, then
$\Lambda(\pi, \sigma)=5$. Note that $\Lambda(\pi,\sigma)$ always
exists since $\min B< B'$.

The labeling $\Lambda$ of the edges of $\ncn$ extends in a natural
(and well-known) way to a labeling of the maximal chains. Namely,
if $\mathfrak{m}:\hat{0}=\pi_0<\pi_1<\cdots<\pi_n=\hat{1}$ is a
maximal chain of 
$\ncn$, then set
  $$ \Lambda(\mathfrak{m}) = (\Lambda(\pi_0,\pi_1),\Lambda(\pi_1,\pi_2),\dots,
    \Lambda(\pi_{n-1},\pi_n)). $$

{\bf 3.1 Theorem.} \emph{The labels $\Lambda(\mathfrak{m})$ of the
  maximal chains 
  of $\ncn$ consist of the parking functions of length $n$, each
  occuring once.}

{\bf Proof.} If $\Lambda(\pi_j,\pi_{j+1})=i$, then the block of
$\pi_{j+1}$ containing $i$ also contains an element $k>i$. Hence the
number of $j$ for which $\Lambda(\pi_j,\pi_{j+1})=i$ cannot exceed
$n+1-i$, from which it follows that $\Lambda(\mathfrak{m})$ is a parking
function.

Suppose that $\mathfrak{m}$ and $\mathfrak{m}'$ are maximal chains of
$\ncn$ for which $\Lambda(\mathfrak{m}) = \Lambda(\mathfrak{m}')$. We
will prove by induction on $n$ that $\mathfrak{m}=\mathfrak{m}'$. The
assertion is clear for $n=0$. Assume true for $n-1$.  Let the elements
of $\mathfrak{m}$ be $\hat{0}=\pi_0<\pi_1<\cdots<\pi_n= \hat{1}$.
Suppose that $\Lambda(\mathfrak{m})=(a_1,\dots,a_n)$. Let $r=\max\{
a_i: 1\leq i\leq n\}$, and let $s=\max\{i: a_i=r\}$. We claim that one
of the blocks of $\pi_{s-1}$ is just the singleton set $\{r+1\}$.  If
$r$ and $r+1$ are in the same block of $\pi_{s-1}$, then we can't have
$\Lambda(\pi_{s-1},\pi_s)=r$, contradicting $a_s=r$.  Hence $r$ and
$r+1$ are in different blocks of $\pi_{s-1}$. If the block $B$ of
$\pi_{s-1}$ containing $r+1$ contained some element $t<r$, then by the
noncrossing property and the fact that $a_s=r$ we have that $B$ is
merged with the block $B_1$ of $\pi_{s-1}$ containing $r$ to get
$\pi_s$. But $\min B\leq t<r\in B_1$, contradicting $a_s=r$. Hence
every element of $B$ is greater than $r$. If $B$ contained some
element $t>r+1$, then (since $r+1 = \min B$) we would have $a_k=r+1$
for some $k<r$, contradicting maximality of $r$. This proves the
claim.

We next claim that $\pi_s$ is obtained from $\pi_{s-1}$ by merging the
block $B_1$ containing $r$ with the block $\{r+1\}$. Otherwise (since
$a_s=r$) $\pi_s$ is obtained by merging $B_1$ with some block $B_2$
all of whose elements are greater than $r+1$. For some $t>s$ we must
obtain $\pi_t$ from $\pi_{t-1}$ by merging the block $B_3$ containing
$r+1$ with the block $B_4$ containing $r$. Now $B_3$ can't contain an
element less than $r+1$ by the noncrossing property of $\pi_{s-1}$
(since $B_4$ contains both $r$ and an element greater than $r+1$). It
follows that $\Lambda(\pi_{t-1},\pi_t)=r$, contradicting the maximality
of $s$ and proving the claim.

It is now clear by induction that the chain $\mathfrak{m}$ can be
uniquely recovered from the parking function
$\Lambda(\mathfrak{m})=(a_1,\dots, a_n)$.  Namely, let $a'$ be the
sequence obtained from $\Lambda(\mathfrak{m})$ by removing $a_s$. Then
$a'$ is a parking function of length $n-1$. By induction there is a
unique maximal chain $\mathfrak{m}^*: \hat{0}=\pi_0^*<\pi_1^*<\cdots<
\pi_{n-1}^*=\hat{1}$ of NC$_n$ such that $\Lambda(\mathfrak{m}^*) =
a'$. By the discussion above we can then obtain $\mathfrak{m}$
uniquely from $\mathfrak{m}^*$ by (1) replacing each element $i>r$ of
the ambient set $[n]$ with $i+1$, (2) adjoining a singleton block
$\{r+1\}$ to each $\pi_i^*$ for $i\leq s-1$, (3) inserting between
$\pi_{s-1}^*$ and $\pi_s^*$ a new element obtained from $\pi_{s-1}^*$
by merging the block containing $r$ with the singleton block
$\{r+1\}$, and (4) for $i>s$ adjoining the element $r+1$ to the block
of $\pi_i^*$ containing $r$. Hence we have shown that if
$\Lambda(\mathfrak{m})=\Lambda(\mathfrak{m}')$, then
$\mathfrak{m}=\mathfrak{m}'$. But it is known \cite[Cor.\ 
5.2]{krew}\cite[Cor.\ 3.3]{edel} that NC$_{n+1}$ has $(n+1)^{n-1}$
maximal chains, which is just the number of parking functions of
length $n$ \cite[Lemma 1 and {\S}6]{k-w}\cite{f-r}. Thus every parking
function of length $n$ occurs exactly once among the sequences
$\Lambda(\mathfrak{m})$, and the proof is complete. $\ \Box$

The above proof of the injectivity of the map $\Lambda$ from maximal
chains to parking functions is reminiscent of the proof \cite[p.\
5]{moon} that 
the Pr\"ufer code of a labelled tree determines the tree. Our proof
``cheated'' by using the fact that the number of maximal chains is the
number of parking functions. We only gave a direct proof of the
injectivity of $\Lambda$. However, our proof actually suffices to
show also surjectivity since the argument of the above paragraph is
valid for any parking function, the key point being that removing an
occurrence of the largest element of a parking function preserves the
property of being a parking function.

If we define a new labeling $\Lambda^*$ of $\ncn$ by 
  $$ \Lambda^*(\pi,\sigma) = |\pi|-\Lambda(\pi,\sigma), $$
where $|\pi|$ is the number of blocks of $\pi$, 
then it is easy to check (using the fact that every interval of $\ncn$
is a product of $\nc_i$'s) that every interval $[\pi,\tau]$ has a
unique maximal 
chain $\mathfrak{m} :\,\pi=\pi_0<\pi_1<\cdots<\pi_j=\tau$ such that
  $$ \Lambda^*(\pi_0,\pi_1)\leq \Lambda^*(\pi_1,\pi_2)\leq
    \cdots\leq \Lambda^*(\pi_{k-1},\pi_k). $$
In other words, $\Lambda^*$ is an \emph{$R$-labeling} in the sense of
    \cite[Def.\ 3.13.1]{rs:ec}. Moreover, this maximal chain
    $\mathfrak{m} $ has 
    the lexicographically least label $\Lambda^*(\mathfrak{m} )$ of
    any maximal 
    chain of the interval $[\pi,\tau]$. Thus $\Lambda^*$ is in fact an
    \emph{EL-labeling}, as defined in \cite[Def.\ 2.2]{bj} (though
    there it is called just an ``L-labeling.''). For the significance
    of the EL-labeling property, see the first paragraph of this
    section. Here we will just be concerned with the weaker R-labeling
    property. 

Define the \emph{descent set} $D(a)$ of a parking function $a=(a_1,
\dots,a_n)$ by
  $$ D(a) = \{i: a_i>a_{i+1}\}. $$
 From the fact that $\Lambda^*$ is an R-labeling and \cite[Thm.\ 
3.13.2]{rs:ec}, we obtain the following proposition.

{\bf 3.2 Proposition.} (a) \emph{Let $S\subseteq [n-1]$. The number of
  parking functions $a$ of length $n$ satisfying $D(a)=S$ is equal to
  $\beta_{\ncn}([n-1]-S)$.}

(b) \emph{Let $S\subseteq [n-1]$. The number of parking functions $a$
  of length $n$ satisfying $D(a)\supseteq S$ is equal to
  $\alpha_{\ncn}([n-1]-S)$. This number is given explicitly by
  \cite[Thm.\ 3.2]{edel} or by equations (\ref{eq:pfm}) and
  (\ref{eq:fpml}).}

The labeling $\Lambda$ is closely related to a bijection between the
maximal chains of $\ncn$ and labelled trees, different from the
earlier bijection of Edelman \cite[Cor.\ 3.3]{edel}. Let
$\mathfrak{m}:\, \hat{0}=\pi_0<\pi_1<\cdots<\pi_n=\hat{1}$ be a
maximal chain of $\ncn$. Define a graph $\Gamma_{\mathfrak{m}}$ on the
vertex set $[n+1]$ as follows. There will be an edge $e_i$ for each
$1\leq i\leq n$. Suppose that $\pi_i$ is obtained from $\pi_{i-1}$ by
merging blocks $B$ and $B'$ with $\min B<\min B'$. Then the vertices
of $e_i$ are defined to be $\Lambda(\pi_{i-1},\pi_i)$ and $\min B'$.
It is easy to see that $\Gamma_{\mathfrak{m}}$ is a tree. Root
$\Gamma_{\mathfrak{m}}$ at the vertex 1 and erase the vertex labels. If
$v_i$ is the vertex of $e_i$ farthest from the root, then move the label
$i$ of the edge $e_i$ from $e_i$ to the vertex $v_i$. 
Label the root with 0 and unroot the tree.  We obtain a
labelled tree $T_{\mathfrak{m}}$ on $n+1$ vertices, and one can easily
check that the map $\mathfrak{m} \mapsto T_{\mathfrak{m}}$ is a
bijection between maximal chains of $\ncn$ and labelled trees on
$n+1$ vertices.

{\bf 4. A local action of the symmetric group.} Suppose that $P$ is a
graded poset of rank $n$ with $\hat{0}$ and $\hat{1}$ such that $F_P$
is a symmetric function. If $F_P$ is Schur positive, then it is the
Frobenius characteristic of a representation of ${\mathfrak S}_n$
whose dimension is the number of maximal chains of $P$. Thus we can
ask whether there is some ``nice'' representation of ${\mathfrak
  S}_n$ on the vector space $V_P$ (over a field of characteristic zero)
whose basis is the set of maximal chains of $P$. This question was
discussed in \cite[{\S}5]{rs:eljc}. A ``nice'' representation should
somehow reflect the poset structure. With this motivation, an action
of ${\mathfrak S}_n$ on $V_P$ is defined to be \emph{local}
\cite[{\S}5]{rs:eljc} if for every adjacent transposition $\sigma_i =
(i,i+1)$ and every maximal chain 
   \beq \mathfrak{m} :\, \hat{0}=t_0<t_1<\cdots<t_n=\hat{1},
   \label{eq:maxch} \eeq  
we have that $\sigma_i(\mathfrak{m} )$ is a linear combination of
maximal chains of the form $t_0<t_1<\cdots<t_{i-1}<t'_i<t_{i+1}<
\cdots< t_n$, i.e., of maximal chains which agree with $\mathfrak{m} $
except  possibly at $t_i$. 

Now let $P=\ncn$. Every interval $[\pi,\tau]$ of $\ncn$ of length two
contains either two or three elements in its middle level. In the
latter case, there are three blocks $B_1, B_2, B_3$ of $\pi$ such that
$\tau$ is obtained from $\pi$ by merging $B_1, B_2, B_3$ into a single
block. Moreover, any two of these blocks can be merged to form a
noncrossing partition. Let $\pi_{ij}$ be the noncrossing partition
obtained by merging $B_i$ and $B_j$, so that the middle elements of
the interval $[\pi,\tau]$ are $\pi_{12}, \pi_{13}, \pi_{23}$. Exactly
one of these partitions $\pi_{ij}$ will have the property that
$\Lambda(\pi,\pi_{ij}) = \Lambda(\pi_{ij},\tau)$, where $\Lambda$ is
defined by (\ref{eq:lab}). Let us call this partition $\pi_{ij}$ the
\emph{special} element of the interval $[\pi,\tau]$. Now define linear
transformations $\sigma'_i:V_{\ncn} \rightarrow V_{\ncn}$, $1\leq
i\leq n-1$ as follows. Let $\mathfrak{m} $ be a maximal chain of
$\ncn$ with elements $\hat{0}=\pi_0<\pi_1<\cdots <\pi_n=\hat{1}$.

\emph{Case 1.} The interval $[\pi_{i-1},\pi_{i+1}]$ contains exactly
two middle elements $\pi_i$ and $\pi'_i$. Then set
$\sigma'_i(\mathfrak{m} )=\mathfrak{m} '$, where $\mathfrak{m} '$ is
given by $\pi_0<\pi_1<\cdots<\pi_{i-1}<\pi'_i< \pi_{i+1} <
\cdots<\pi_n$.

\emph{Case 2.} The interval $[\pi_{i-1},\pi_{i+1}]$ contains exactly
three middle elements, of which $\pi_i$ is special. Then set
$\sigma'_i(\mathfrak{m} ) =\mathfrak{m} $.

\emph{Case 3.} The interval $[\pi_{i-1},\pi_{i+1}]$ contains exactly
three middle elements $\pi_i, \pi'_i$, and $\pi''_i$, of which
$\pi''_i$ is special. Then set $\sigma'_i(\mathfrak{m} )=\mathfrak{m}
'$, where $\mathfrak{m} '$ is given by
$\pi_0<\pi_1<\cdots<\pi_{i-1}<\pi'_i< \pi_{i+1} < \cdots<\pi_n$.

{\bf 4.1 Proposition.} \emph{The action of each $\sigma'_i$ on
  $V_{\ncn}$ defined above yields a local action of ${\mathfrak S}_n$
  on $V_{\ncn}$. Equivalently, there is a homomorphism $\varphi:
  {\mathfrak S}_n\rightarrow \mathrm{GL}(V_{\ncn})$ satisfying
  $\varphi(\sigma_i) =\sigma'_i$. The Frobenius characteristic of this
  action is given by $\pfn$.}

{\bf Proof.} Each maximal chain $\mathfrak{m} $ corresponds to a
parking function $\Lambda(\mathfrak{m} )$ \emph{via} Theorem 3.1. Thus
the natural action of $\sn$ on ${\cal P}_n$ defined in Section 2 may
be ``transferred'' to an action $\psi$ of $\sn$ on the set of maximal
chains of $\ncn$. It is easy to check that $\psi$ and $\varphi$ agree
on the $\sigma_i$'s, and the proof follows. $\ \Box$

The action $\varphi$ does not quite have the property mentioned at the
beginning of this section that its characteristic is $F_{\ncn}$. By
Theorem 2.3, the characteristic is actually $\omega F_{\ncn}$. However,
we only have to multiply $\varphi$ by the sign character
(equivalently, define a new action $\varphi'$ by $\varphi'(\sigma_i) =
-\varphi(\sigma_i)$) to get the desired property.

It is rather surprising that the simple ``local'' definition we have
given of $\varphi$ defines an action of $\sn$. Perhaps it would be
interesting to look for some more examples. (We need to exclude
trivial examples such as $w(\mathfrak{m})=\mathfrak{m}$ for all
$w\in\sn$ and all maximal chains $\mathfrak{m}$.) A few other examples
appear in the next section and in \cite[{\S}5]{rs:eljc}. A further
example (the posets of shuffles of C. Greene \cite{greene}) is
discussed in \cite{s-s} together with the rudiments of a systematic
theory of such actions, but much work needs to be done for a
satisfactory understanding of local $\sn$-actions.

{\bf 5. Generalizations.} In this section we will briefly discuss two
generalizations of what appears above. All proofs are entirely
analogous and will be omitted. Fix an integer $k\in\mathbb{P}$. A
\emph{$k$-divisible noncrossing partition} is a noncrossing partition
$\pi$ for which every block size is divisible by $k$. Thus $\pi$ is a
noncrossing partition of a set $[kn]$ for some $n\geq 0$. Let
$\nc_{n}^{(k)}$ be the poset of all $k$-divisible noncrossing partitions
of $[kn]$. ($\nc_{n}^{(k)}$ is actually a join-semilattice of $\nc_{kn}$. It
has $\hat{1}$ but not a $\hat{0}$ when $k>1$.) The combinatorial
properties of the poset $\nc_n^{(k)}$ were first considered by Edelman
\cite[{\S}4]{edel}. If a pair $(\pi,\sigma)$
is an edge of $\nc_n^{(k)}$ (i.e., $\sigma$ covers $\pi$ in
$\nc_n^{(k)}$), then $(\pi,\sigma)$ is an edge of $\nc_n$. Hence the
edge-labeling $\Lambda$ of $\nc_n$ restricts to an edge-labeling of
$\nc_n^{(k)}$. 

Define a \emph{$k$-parking function} of length $n$ to be 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 ki$. Let ${\cal P}_n^{(k)}$ denote the set of all
$k$-parking functions of length $n$. The argument of Pollack mentioned
in Section 2 that $\#{\cal P}_n = (n+1)^{n-1}$ easily extends to
${\cal P}_n^{(k)}$. Namely, let $\mathbb{Z}_{k(n+1)}$ denote the set
$\{1,2,\dots,k(n+1)\}$ with addition modulo $k(n+1)$. Then every coset
of the subgroup $H$ of $\mathbb{Z}_{k(n+1)}^n$ generated by
$(1,1,\dots,1)$ contains exactly $k$ $k$-parking functions. Hence
$\#{\cal P}_n^{(k)} = k(k(n+1))^{n-1}$. The symmetric group $\sn$ acts
on ${\cal P}_n^{(k)}$ by permuting coordinates, and we can consider
its Frobenius characteristic $\pfnk$ just as we did for ${\cal P}_n$.
The above generalization of Pollack's argument shows that
  $$ \pfnk = \frac{1}{n+1}[t^n] H(t)^{k(n+1)}. $$
Proposition 2.2 generalizes straightforwardly to the case of
$\pfnk$. In particular, Proposition 2.2(b) takes the form
  $$ \sum_{n\geq 0}\pfnk\, t^{n+1} = \left( tE(-t)^k\right)^{\langle
    -1\rangle}. $$ 

Theorem 3.1 generalizes as follows.

{\bf 5.1 Theorem.} \emph{The labels $\Lambda(\mathfrak{m})$ of the
  maximal chains of $\ncnk$ consist of the $k$-parking functions of
  length $n$, each occuring once.}

Proposition 3.2 requires some modification when extended to
$k$-parking functions because the posets $\ncnk$ do not have a
$\hat{0}$ when $k>1$. For these posets we regard the minimal elements
as having rank 0, and we define $\alpha_{\ncnk}(S)$ and
$\beta_{\ncnk}(S)$ for $S\subseteq \{0,1,\dots,n-1\}$. Thus for
instance $\alpha_{\ncnk}(\emptyset)=\beta_{\ncnk}(\emptyset)=1$, and
$\alpha_{\ncnk}(0)$ is the number of minimal elements of
$\ncnk$. Write $[0,n-1]=\{0,1,\dots,n-1\}$.

{\bf 5.2 Proposition.} (a) \emph{Let $S\subseteq [n-1]$. The number of
  $k$-parking functions $a$ of length $n$ satisfying $D(a)=S$ is equal
  to}
  $$ \beta_{\ncnk}([n-1]-S)+\beta_{\ncnk}([0,n-1]-S). $$

(b) \emph{Let $S\subseteq [n-1]$. The number of $k$-parking functions $a$
  of length $n$ satisfying $D(a)\supseteq S$ is equal to
  $\alpha_{\ncnk}([0,n-1]-S)$. This number is given explicitly by
  \cite[Thm.\ 4.2]{edel}.}

Note, however, that there does not seem to be a nice generalization of
Theorem 2.3. The quasisymmetric function $F_{\ncnk}$ is not a
symmetric function when $k>1$, and we know of no simple connection
between the flag $f$-vector of $\ncnk$ and the symmetric function
$\pfnk$, nor between the number of $k$-divisible noncrossing
partitions of a given type and $\pfnk$.

Proposition 4.1 extends straightforwardly to $\ncnk$. The natural
action of $\sn$ on ${\cal P}_n^{(k)}$ is transferred \emph{via} Theorem
5.1 to an action on $V_{\ncnk}$. This action is a permutation
representation on the maximal chains, and is readily seen to be local.
Its characteristic is $\pfnk$.

There is a different generalization of noncrossing partitions due to
Reiner \cite{reiner} (a special case had earlier appeared in a
different guise in \cite{mont}, as explained in \cite{reiner}) that we
have not looked at very closely. Reiner 
regards ordinary noncrossing partitions as corresponding to the root
system $A_n$ and constructs analogues for the root systems $B_n$ and
$D_n$. Actually, for every subset $S\subseteq [n]$ he constructs a
lattice $\mathrm{NC}_n^{BD}(S)$ interpolating between the $B_n$
analogue (the 
case $S=\emptyset$) and the $D_n$ analogue (the case $S=[n]$). The
lattices $\mathrm{NC}_n^{BD}(S)$ do not always have self-dual intervals
\cite[Remark on p.\ 13]{reiner}, but at least every interval is
rank-symmetric. Thus by Proposition 2.1, this implies that
$\mathrm{NC}_n^{BD}(S)$ is a
symmetric function. This symmetric function only depends on the
cardinality $s$ of $S$, so we write $F_n^{BD}(s)$ for
$F_{\mathrm{NC}_n^{BD}(S)}$. We also write $F_n^B$ for $F_n^{BD}(0)$. 

Let $[n]^n$ denote the set of all sequences $(a_1,\dots,a_n)$
of positive integers with $a_i\leq n$. We call such a sequence a
\emph{$B_n$-parking function}, for the following 
reason. Let $\pfn^B$ be the Frobenius characteristic of the action of
$\sn$ on $[n]^n$ obtained by permuting coordinates. It follows from
\cite[Prop.\ 7]{reiner} that 
  $$ F_n^B = \omega\pfn^B. $$
Thus in analogy with Theorem 2.3 it makes sense to think of the
elements of $[n]^n$ as $B_n$-parking functions. Reiner's result
\cite[Prop.\ 7]{reiner} makes it easy to give an analogue of
  Proposition 2.2. Let us simply mention the formula
  $$ \pfn^B = [t^n]H(t)^n, $$
 from which the analogues of all parts of Proposition 2.2 follow
easily. In particular, the analogue of Proposition 2.2(b) takes the
form
  \beq \sum_{n\geq 1} \pfn^B\, \frac{t^n}{n} = \log \frac{\left(
    tE(-t)\right)^{\langle -1\rangle}}{t}. \label{eq:bnpf} \eeq
Comparing Proposition 2.2 with equation (\ref{eq:bnpf}) yields the
curious result that
  $$ \exp \sum_{n\geq 1}\pfn^B\, \frac{t^n}{n} = \sum_{n\geq 0} \pfn\,
       t^n. $$

What is missing from the analogy between $A_n$ and $B_n$ noncrossing
partitions is the analogue of Theorem 3.1, i.e., a labeling of
$\ncn^B$ such that the labels of the maximal chains are the
$B_n$-parking functions. We have not looked at this question and
recommend it as an interesting open problem.

For the general case of $\mathrm{NC}_n^{BD}(S)$, it follows from
\cite[Thm.\ 11]{reiner} that
  $$ F_n^{BD}(s) = F_n^B - s\cdot\mathrm{PF}'_n, $$
where $\mathrm{PF}'_n$ is the Frobenius characteristic of the action
of $\sn$ on all sequences $(a_1,\dots,a_n)$ of positive integers whose
increasing rearrangement $b_1\leq\cdots\leq b_n$ satisfies $b_1=1$ and
$b_i\leq i-1$ for $2\leq i\leq n$. We have not considered further
properties of the symmetric function $F_n^{BD}(s)$.

\begin{thebibliography}{99}

\bibitem{becker} H. W. Becker, Planar rhyme schemes, \emph{Bull.\
  Amer.\ Math.\ Soc.}\ \textbf{58} (1952), 39.

\bibitem{bj} A. Bj\"orner, Shellable and Cohen-Macaulay partially
  ordered sets, \emph{Trans.\ Amer.\ Math.\ Soc.}\ \textbf{260}
  (1980), 159--183.

\bibitem{b-w} A. Bj\"orner and M. Wachs, On lexicographically
  shellable posets, \emph{Trans.\ Amer.\ Math.\ Soc.}\ \textbf{277}
  (1983), 323--341.

\bibitem{edel} P. H. Edelman, Chain enumeration and non-crossing
  partitions, \emph{Discrete Math.}\ \textbf{31} (1980), 171--180.

\bibitem{e-s} P. H. Edelman and R. Simion, Chains in the lattice of
  noncrossing partitions, \emph{Discrete Math.}\ \textbf{126} (1994),
  107--119. 

\bibitem{ehr} R. Ehrenborg, On posets and Hopf algebras,
\emph{Advances in Math.}\ \textbf{119} (1996), 1--25.

\bibitem{f-h} H. K. Farahat and G. Higman, The centres of symmetric
  group rings, \emph{Proc.\ Royal Soc.\ (A)} \textbf{250} (1959),
  212--221. 

\bibitem{f-r} D. Foata and J. Riordan, Mappings of acyclic and parking
  functions, \emph{aequationes math.}\ \textbf{10} (1974), 10--22.

\bibitem{g-h} A. M. Garsia and M. Haiman, A remarkable $q,t$-Catalan
sequence and $q$-Lagrange inversion, \emph{J.\ Algebraic
Combinatorics} \textbf{5} (1996), 191--244.

\bibitem{gessel} I. Gessel, Multipartite $P$-partitions and inner
  products of skew Schur functions, \emph{Contemporary Math.}\
  \textbf{34} (1984), 289--301.

\bibitem{g-j} I. P. Goulden and D. M. Jackson, Symmetric functions and
  Macdonald's result for top connexion coefficients in the symmetric
  group, \emph{J.\ Algebra} \textbf{166} (1994), 364--378.

\bibitem{greene} C. Greene, Posets of shuffles, \emph{J.\
Combinatorial Theory (A)} \textbf{46} (1988), 191--206.

\bibitem{haiman} M. Haiman, Conjectures on the quotient ring by
  diagonal invariants, \emph{J.\ Alg.\ Combinatorics} \textbf{3}
  (1994), 17--76.

\bibitem{k-w} A. G. Konheim and B. Weiss, An occupancy discipline and
  applications, \emph{SIAM J.\ Applied Math.}\ \textbf{14} (1966),
  1266--1274. 

\bibitem{krew} G. Kreweras, Sur les partitions non crois\'ees d'un
  cycle, \emph{Discrete Math.}\ \textbf{1} (1972), 333--350.

\bibitem{k-t} D. Krob and J.-Y. Thibon, Noncommutative symmetric
  functions IV: Quantum linear groups and Hecke algebras at $q=0$,
  Institut Blaise Pascal, Laboratoire Informatique Th\'eorique et
  Programmation, preprint LITP 96/12, March, 1996.

\bibitem{mac} I. G. Macdonald, \emph{Symmetric Functions and Hall
    Polynomials}, second ed., Oxford University Press, Oxford, 1995.

\bibitem{m-r} C. Malvenuto and C. Reutenauer, Duality between
  quasi-symmetric functions and the Solomon descent algebra, \emph{J.\
  Algebra} \textbf{177} (1995), 967--982.

\bibitem{mont} C. Montenegro, The fixed point non-crossing partition
  lattices, preprint, 1993.

\bibitem{moon} J. W. Moon, \emph{Counting Labelled Trees}, Canadian
  Mathematical Monographs, No.\ 1, Canadian Mathematical Congress,
  1970. 

\bibitem{n-s} A. Nica and R. Speicher, A ``Fourier transform'' for
  multiplicative functions on non-crossing partitions, \emph{J.\
  Algebraic Combinatorics}, to appear.

\bibitem{poup} Y. Poupard, \'Etude et denombrement paralleles des
  partitions non crois\'ees d'un cycle et des decoupage d'un polygone
  convexe, \emph{Discrete Math.}\ \textbf{2} (1972), 279--288.

\bibitem{reiner} V.\ Reiner, Non-crossing partitions for classical
  reflection groups, preprint dated March 1996. Available at the URL
  \textbf{ftp://s6.math.umn.edu/pub/papers/reiner/} or by anonymous
  ftp.

\bibitem{reut} C. Reutenauer, \emph{Free Lie Algebras}, Oxford
  University Press, Oxford, 1993.

\bibitem{simion} R. Simion, Combinatorial statistics on non-crossing
  partitions, \emph{J.\ Combinatorial Theory (A)} \textbf{66} (1994),
  270--301. 

\bibitem{s-s} R. Simion and R. Stanley, Flag-symmetry of the poset of
shuffles and a local action of the symmetric group, in preparation.

\bibitem{s-u} R. Simion and D. Ullman, On the structure of the lattice
  of noncrossing partitions, \emph{Discrete Math.}\ \textbf{98} (1991),
  193--206.

\bibitem{speicher} R. Speicher, Multiplicative functions on the
  lattice of noncrossing partitions and free convolution, \emph{Math.\
  Ann.}\ \textbf{298} (1994), 611--628.

\bibitem{rs:ec} R. Stanley, \emph{Enumerative Combinatorics}, vol.\ 1,
  Wadsworth and Brooks/Cole, Pacific Grove, CA, 1986; second printing,
  Cambridge University Press, Cambridge, 1996 or 1997.
  
\bibitem{rs:eljc} R. Stanley, Flag-symmetric and locally
  rank-symmetric partially ordered sets, \emph{Electronic J.\
  Combinatorics} \textbf{3}, R6 (1996), 22 pp.

\bibitem{rs:rota} R. Stanley, Hyperplane arrangements, parking
  functions and tree inversions, in \emph{Festschrift in Honor of
  Gian-Carlo Rota}, Birkh\"auser, Boston/Basel/Berlin, to appear.

\end{thebibliography}

\end{document}