%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2020}
\articlenumber{59}
\addbibresource{bibli.bib}

%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}
\usepackage{inputenc}
\usepackage{mathtools}
\usepackage{graphics}
\usepackage{wrapfig}

%\usepackage{refcheck}

\usepackage{textcomp}

\usepackage{tikz}

\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{lemm}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{coro}[thm]{Corollary}

\theoremstyle{definition}
\newtheorem{defi}[thm]{Definition}
\newtheorem{exam}[thm]{Example}
\newtheorem{rema}[thm]{Remark}


\newcommand{\Ckl}{ \mathcal{C}_{k,t}^l }
\newcommand{\Ckmupl}{ \mathcal{C}_{k-1,t}^{l,p} }
\newcommand{\Ckmul}{ \mathcal{C}_{k-1,t}^{l} }
\newcommand{\Cmul}{ \mathcal{C}_{-1,t}^{l} }
\newcommand{\Cmupl}{ \mathcal{C}_{-1,t}^{l,p} }
\newcommand{\Cunl}{ \mathcal{C}_{1,t}^{l} }
\newcommand{\Czl}{ \mathcal{C}_{0,t}^{l} }
\newcommand{\Cvarl}[1]{ \mathcal{C}_{#1,t}^{l} }



%% define your title in the usual way
\title{Some properties of the parking function poset}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{B\'er\'enice Delcroix-Oger\thanks{\href{mailto:bdelcroix@irif.fr}{bdelcroix@irif.fr}.}\addressmark{1}, Matthieu Josuat-Verg\`es%\thanks{\href{mailto:blah}{blah}.}
\addressmark{1,3},\\ \and Lucas Randazzo%\thanks{\href{mailto:blah}{blah}.}
\addressmark{2} }

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}IRIF, Universit\'e de Paris, France \\ \addressmark{2}LIGM, Universit\'e Gustave Eiffel, Champs-sur-Marne, France \\ \addressmark{3}CNRS}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{In 1980, Edelman defined a poset on objects called the noncrossing 2-partitions.  They are closely related with noncrossing partitions and parking functions.  To some extent, his definition is a precursor of the parking space theory, in the framework of finite reflection groups.  We present some enumerative and topological properties of this poset.  In particular, we get a formula counting certain chains, that encompasses formulas for Whitney numbers (of both kinds).  We prove shellability of the poset, and compute its homology as a representation of the symmetric group.}

%% put your French abstract here, or comment this out if you don't have one
\resume{En 1980, Edelman a d\'efini un ordre partiel sur des objets appel\'es les 2-partitions non-crois\'ees.  Elles  sont intimement reli\'ees aux partitions non-crois\'ees et aux fonctions de stationnement.  Dans une certaine mesure, sa d\'efinition est un pr\'ecurseur de la th\'eorie des espaces de stationnement.  Nous pr\'esentons quelques propri\'et\'es \'enum\'eratives et topologiques de cet ordre.  En particulier, nous obtenons une formule comptant certaines cha\^ines, qui inclut des formules pour les nombres de Whitney (des deux esp\`eces).  Nous prouvons l'\'epluchabilit\'e du poset, et calculons son homologie en tant que repr\'esentation du groupe sym\'etrique.}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{parking functions, noncrossing partitions, poset topology, representations, symmetric group}


%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%  Matthieu:  Really ?  Why is that so ?  Just compile this file with your favorite Tex compiler and this will be fine, you don't need to touch our bibliography.  Unless you are still undecided about the style for references, which raises the question: why had this not been decided before we write our abstracts ? 

%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text


\newcommand{\pp}{\mathrlap{\;\scriptstyle{\overset{2}{\null}}}\Pi}
\newcommand{\ppp}{\mathrlap{\hspace{0.94mm}\scalebox{0.56}{$\overset{2}{\null}$}}\Pi}

\DeclareMathOperator{\rk}{rk}
\DeclareMathOperator{\im}{im}


\begin{document}

\maketitle

\section*{Introduction}

{\it Parking functions} are fundamental objects in algebraic combinatorics.  It is well known that the set of parking functions of length $n$ has cardinality ${n+1}^{n-1}$, and the natural action of the symmetric group $\mathfrak{S}_n$ on this set occurs in the deep work of Haiman~\cite{haiman} about diagonal coinvariants.  Generalizations to other finite reflection groups lead to the {\it parking space theory} of Armstrong, Reiner, Rhoades~\cite{ARR,rhoades}.

The poset mentioned in the title was introduced by Edelman~\cite{edelman} in 1980, as a variant of the {\it noncrossing partition lattice} introduced by Kreweras~\cite{kreweras} (hence the name {\it noncrossing 2-partitions} in~\cite{edelman}).  One striking feature of Edelman's definition is that it really fits well in the noncrossing parking space theory mentionned above, so it seems that this overlooked poset can give a new perspective on recent results about parking functions.

Our goal is to obtain new enumerative and topological properties of Edelman's poset.  Through various bijections, we will see that several variants of the same objects are relevant: 
\begin{itemize}
\item 2-noncrossing partitions (\cref{sec11}), 
\item some pairs of a noncrossing partition together with a permutation (\cref{secparkingspace}),
\item parking functions in the usual way (\cref{sec13}),
\item parking trees (\cref{sec13}).
\end{itemize}
The latter, which have the additional structure of a {\it species}, will be useful to write functional equations and get our enumerative results in \cref{sec2}.  What we get is a formula counting chains of $k$ elements whose top element has rank $\ell$.  A nice feature of this formula is that it encompasses a nice formula for Whitney numbers of the second kind at $k=1$ (this one being obtained by Edelman), and one for Whitney numbers of the first kind at $k=-1$.
 
Then we go on to topological properties: we will see in \cref{sec3} that the poset is shellable.  Unlike the case of noncrossing partitions which can be treated by EL-shellability, we need here the notion of {\it recursive atom ordering} (equivalent to the notion of CL-shellability).  Still, the EL-shellability of noncrossing partitions is a key tool.  There are well known consequences of shellability such as Cohen-Macauleyness, and hence that only one homology group of the poset is non trivial.  We use this fact in \cref{sec_homology} to compute the character of this homology group as a representation of $\mathfrak{S}_n$.


\section{Parking function posets}
\label{sec1}

\subsection{The poset of noncrossing 2-partitions}
\label{sec11}

A set partition $\pi$ of $\{1,\dots,n\}$ is {\it noncrossing} if there exists no $i<j<k<l$ such that $i,k\in B_1$ and $j,l\in B_2$ where $B_1$ and $B_2$ are two distinct blocks of $\pi$.  Endowed with the refinement order, noncrossing partitions of $\{1,\dots,n\}$ form a lattice denoted $NC_n$, first defined by Kreweras~\cite{kreweras}.  Note that we take the convention that the minimal element is $\{\{1,2,\dots,n\}\}$, the set partition with one block, and the maximal element is $\{\{1\},\{2\},\dots\}$.  

To each noncrossing partition $\pi\in NC_n$, we associate a permutation $\bar\pi$ defined by the conditions that for each block $B=\{b_1,b_2,\dots,b_k\}\in\pi$ we have $\bar\pi(b_i)=b_{i+1}$ if $i<k$ and $\bar\pi(b_k)=b_1$.  This permits us to define the {\it Kreweras complement} \cite{kreweras}: for $\pi\in NC_n$, it is $K(\pi)\in NC_n$ such that the associated permutation is $\bar\omega\bar\pi^{-1}$ where $\omega$ is the minimal noncrossing partition (so that $\bar\omega$ is a full cycle).  The map $\pi\mapsto K(\pi)$ defines an anti-automorphism of $NC_n$.  For example, $K(\{\{1,2\},\{3\},\{4,5\}\}) = \{\{1,3,4\},\{2\},\{5\}\}$ since in the symetric group we have $(12345)(12)(45)=(134)$.

\begin{defi}[Edelman~\cite{edelman}]  \label{defi_edelman}
A {\it noncrossing 2-partition} of $\{1, \ldots, n\}$ is a 
triple $(\pi,\rho,\lambda)$ where:
\begin{itemize}
 \item $\pi$ is a noncrossing partition of $\{1, \ldots, n\}$, $\rho$ is a set partition of $\{1, \ldots, n\}$,
 \item $\lambda$ is a bijection from (the blocks of) $\pi$ to (those of) $\rho$, and $\forall B\in \pi$, $\# \lambda(B) = \# B$.
\end{itemize}
This set is denoted $\pp_n$.  A partial order on $\pp_n$ is defined by $(\pi',\rho',\lambda') \geq (\pi,\rho,\lambda)$ iff:
\begin{itemize}
 \item $\pi'$ is a refinement of $\pi$, $\rho'$ is a refinement of $\rho$,
 \item if $ \biguplus_{i=1}^j B'_i = B$ where $B'_i\in \pi'$ and $B\in\pi$, then $\biguplus_{i=1}^j \lambda'(B'_i) = \lambda(B)$.
\end{itemize}
\end{defi}

For example, such a triple $(\pi,\rho,\lambda)$ is as follows: $\pi= \{\{1,5,6,8\},\{2,3\},\{4\},\{7\}\}$, $\rho$ and $\lambda$ are given by $\lambda(\{1,5,6,8\})=\{2,3,4,7\}$, $\lambda(\{2,3\})=\{5,8\}$, $\lambda(\{4\})=\{1\}$, $\lambda(\{7\})=\{6\}$.  Another representation will be given in \cref{secparkingspace} (in particular, see the example at the end).

The poset $\pp_n$ is ranked, with $\rk((\pi,\rho,\lambda)) = \#\pi-1$.  Let us mention a few other properties following from the definition.  Using the last condition above, we see that if $(\pi,\rho,\lambda) \leq (\pi',\rho',\lambda')$, $\lambda$ and $\rho$ are uniquely determined by $\pi',\rho',\lambda',\pi$.  It follows that the order ideal of $\pp_n$ containing all elements below $(\pi,\rho,\lambda)$ is isomorphic to an order ideal in the noncrossing partition lattice, so it is isomorphic to a product of noncrossing partition lattices $NC_{i_1}\times NC_{i_2} \times \cdots$ (here $i_1,i_2,\dots$ are the sizes of the blocks of $K(\pi)$).  Similarly, one can prove that the order filter of $\pp_n$ containing all elements above $(\pi,\rho,\lambda)$ is isomorphic to a product $\pp_{i_1}\times \pp_{i_2}\times \cdots$ (here $i_1,i_2,\dots$ are the sizes of the blocks of $\pi$).  Moreover, $\pp_n$ has one minimal element, and $n!$ maximal elements.

Edelman proved in \cite{edelman} that the $\zeta$-polynomial of this poset is given by $Z_{\ppp_n}(k+1)  = (nk+1)^{n-1}$. In particular, setting $k=1$ we see that noncrossing 2-partitions and parking functions are equienumerous. 
Another result from~\cite{edelman} is that for $0\leq k \leq n-1$, the number of elements of rank $\ell$ in $\pp_n$, called the $\ell$th {\it Whitney number of the second kind}, is
\begin{equation}  \label{edelman_whit2}
   W_\ell(\pp_n) = \ell! \binom{n}{\ell} S_2(n,\ell+1),
\end{equation}
where $S_2(n,k)$ are the Stirling numbers of the second kind.

There is a natural action of $\mathfrak{S}_n$ on set partitions of $\{1,\dots,n\}$ (see~\cite{BLL}, for example).  It extends to an action on $\pp_n$ by:
%\begin{equation}  \label{act_ontriples}
 $ \sigma \cdot (\pi,\rho,\lambda) = (\pi, \sigma\cdot\rho , \sigma \circ \lambda )$,
%\end{equation}
where in $\sigma \circ \lambda$ we identify $\sigma$ with its action on set partitions.  We will see below another way to think of this action, by defining a species of parking trees.  It is straightforward to check that the action preserves the order relation of $\pp_n$, so that it extends to an action on chains of the poset, and then on the homology.

\subsection{The parking space}
\label{secparkingspace}

It turns out that this action can be identified with one defined in the {\it parking space theory}, introduced by Armstrong, Reiner and Rhoades in \cite{ARR}.  In some sense, Edelman's poset is a precursor to this theory.  To clarify this link, let us mention a few facts.  

For $\pi\in NC_n$, we denote by $\mathfrak{S}_n(\pi)$ the set of $\sigma\in\mathfrak{S}_n$ such that $\sigma\cdot\pi=\pi$. Then $\mathfrak{S}_n(\pi)$ is a {\it parabolic subgroup} (it is conjugated to a Young subgroup).  The quotient $\mathfrak{S}_n / \mathfrak{S}_n(\pi)$ is acted on by $\mathfrak{S}_n$, by left multiplication.  The character of this action is $\mathrm{Ind}_{\mathfrak{S}_n(\pi)}^{\mathfrak{S}_n}(1)$, the trivial character of $\mathfrak{S}_n(\pi)$ induced to $\mathfrak{S}_n$.  Under the Frobenius map, it is sent to the {\it homogeneous symmetric function} $h_\lambda$, where $\lambda$ is the integer partition obtained by sorting block sizes of $\pi$.

Any pair $(\pi,\sigma)$ where $\pi\in NC_n$ and $\sigma \in \mathfrak{S}_n / \mathfrak{S}_n(\pi)$ can be identified with an element $(\pi,\rho,\lambda)\in\pp_n$ by letting $\rho=\sigma\cdot\pi$, and $\lambda$ is defined as the action of $\sigma$ on blocks of $\pi$.  This identification is compatible with the action of $\mathfrak{S}_n$. It follows that the character of the action of $\mathfrak{S}_n$ on $\pp_n$ is:
\[
  \sum_{\pi \in NC_n} \mathrm{Ind}_{\mathfrak{S}_n(\pi)}^{\mathfrak{S}_n}(1).
\]
Therefore it coincides with the {\it noncrossing parking space} from \cite{ARR}.  

In particular, the poset $\pp_n$ appears implicitly in \cite{rhoades}.  It follows from this reference that the character of $\mathfrak{S}_n$ acting on chains $\phi_1\leq \dots \leq \phi_k$ in $\pp_n$ is given by
\begin{align}  \label{char_chains}
  \sigma \mapsto (kn+1)^{z(\sigma)-1}
\end{align}
where $z(\sigma)$ is the number of cycles of $\sigma$.


Following the above discussion, it is natural to see $(\pi,\rho,\lambda)\in\pp_n$ as a pair $(\pi,\sigma)$ where $\sigma\in\mathfrak{S}_n$ is a minimal length coset representative in $\mathfrak{S}_n / \mathfrak{S}_n(\pi)$, i.e.~for each block $B=\{b_1,b_2,\ldots\}\in\pi$ we have $\sigma(b_1)<\sigma(b_2)<\cdots$.
The example given after \cref{defi_edelman} gives the pair
%\[
$ (\{\{1,5,6,8\},\{2,3\},\{4\},\{7\}\}, 2 5 8 1 3 4 6 7)$.
%\]
It can be represented as a noncrossing partition with labels:
%\[
 \begin{tikzpicture}[scale=0.6]
   \tikzstyle{ver} = [circle, draw, fill, inner sep=0.5mm]
   \tikzstyle{edg} = [line width=0.6mm]
   \node[ver] at (1,0) {};
   \node[ver] at (2,0) {};
   \node[ver] at (3,0) {};
   \node[ver] at (4,0) {};
   \node[ver] at (5,0) {};
   \node[ver] at (6,0) {};
   \node[ver] at (7,0) {};
   \node[ver] at (8,0) {};
   \node      at (1,-0.6) {2};
   \node      at (2,-0.6) {5};
   \node      at (3,-0.6) {8};
   \node      at (4,-0.6) {1};
   \node      at (5,-0.6) {3};
   \node      at (6,-0.6) {4};
   \node      at (7,-0.6) {6};
   \node      at (8,-0.6) {7};
   \draw[edg] (1,0) to[bend left=60] (5,0);
   \draw[edg] (5,0) to[bend left=60] (6,0);
   \draw[edg] (6,0) to[bend left=60] (8,0);
   \draw[edg] (2,0) to[bend left=60] (3,0);
 \end{tikzpicture}.
%\]

The cover relation is easily described in this representation.  To obtain $(\pi',\sigma')$ such that $(\pi',\sigma')\lessdot(\pi,\sigma)$, choose $\pi'\in NC_n$ such that $\pi'\lessdot \pi$, and $\sigma'$ is obtained by rearranging the labels so as to respect the increasing condition on the blocks of $\pi'$.

\subsection{The link with parking functions}
\label{sec13}

\begin{defi}
A {\it parking function} of length $n$ is a word $w_1\cdots w_n$ of positive integers, such that for all $k$ between $1$ and $n$, we have $ \# \{ \; i  \; : \; w_i\leq k  \} \geq k$. The symmetric group acts on parking functions as follows: for $\sigma\in\mathfrak{S}_n$,
$ \sigma \cdot ( w_1\cdots w_n ) = w_{\sigma^{-1}(1)} \cdots w_{\sigma^{-1}(n)}$.
\end{defi}

To each $(\pi,\rho,\lambda)\in\pp_n$, we associate a parking function $w_1\cdots w_n$ by the following condition: for each $B\in\pi$, we have $w_i=\min B$ if $i\in \lambda(B)$.  It can be checked that this defines a bijection that is compatible with the action of $\mathfrak{S}_n$.

It is worth making explicit what are the parking functions corresponding to $(\pi,\pi,I)$ where $I$ is the identity map, because these are orbit representatives.  It turns out that they are the parking functions $w_1\cdots w_n$ such that: i) $w_i\leq i$ for all $i$, and: ii) they are lexicographically maximal among parking functions in the same orbit and satisfying i). 

\begin{defi}
A \emph{parking tree} on a set $L$ is a rooted plane tree $T$ such that:
%\begin{itemize}
 i) the internal vertices of $T$ are labelled with nonempty subsets of $L$,
 ii) the above mentioned labels form a set partition of $L$, 
 iii) if an internal vertex has $i$ descendants then its label has cardinality $i$.
The \emph{species of parking functions} (or \emph{parking species}), denoted $\mathcal{P}_f$, is the species which associates to any finite set $V$ the set of parking trees on $V$.
\end{defi}

Note that a parking tree on $L$ has $\#L$ edges.  



\begin{exam} We represent below the parking trees on $\{1\}$, $\{1, 2\}$ and $\{1, 2, 3\}$:
\begin{align*}
\includegraphics{1.pdf}, \quad
\includegraphics{11.pdf}, \;
\includegraphics{12.pdf}, \;
\includegraphics{21.pdf}, \quad
\includegraphics{111.pdf}, \;
\includegraphics{112.pdf}, \;
\includegraphics{121.pdf}, \;
\includegraphics{211.pdf}, \;
\includegraphics{113.pdf},\\
\includegraphics{131.pdf}, \;
\includegraphics{311.pdf}, \;
\includegraphics{122.pdf}, \;
\includegraphics{212.pdf}, \;
\includegraphics{221.pdf}, \;
\includegraphics{123.pdf}, \;
\includegraphics{132.pdf}, \;
\includegraphics{213.pdf}, \;
\includegraphics{312.pdf}, \,
\includegraphics{231.pdf}, \;
\includegraphics{321.pdf}.
\end{align*}
\end{exam}

\begin{wrapfigure}{r}{6.2cm} \centering
1325271 

\vspace{2mm}

$\updownarrow$

\vspace{2mm}

$\scriptstyle{(\{1,7\}, \{3,5\}, \{2\}, \emptyset, \{4\}, \emptyset, \{6\})}$

\vspace{2mm}

$\updownarrow$ \\


\vspace{2mm}

\begin{tikzpicture}[grow=up, scale=0.7, sibling distance=24mm, level distance=12mm]
\node[draw, circle]{1,7}
    child {     
        node[draw, circle] {\small 6} child{}}
    child{
            node[draw, circle] {\small{3,5}}
        		child{node[draw, circle] {\small 4} child{}
        		} 
 	       		child{node[draw, circle] {\small 2}
        		child{} 
        		} 
        }              
;
\end{tikzpicture}
\end{wrapfigure}
Parking trees on $\{1,\dots,n\}$ are in bijection with parking functions in such a way that the action of $\mathfrak{S}_n$ coincides on both sets.  A parking function of length $n$ can be rewritten as a (weak) set composition $(A_1, \ldots A_n)$ of $\{1, \ldots, n\}$ satisfying $\sum_{i=1}^k |A_i| \geq k$ for any $1 \leq k \leq n$, by letting $A_i$ be the set of positions of letter $i$ in the parking function.
Then, the vertices of the parking trees are given by the sets of the composition,  and $A_i$ is the leftmost child of $A_{i-1}$ if $A_{i-1} \neq \emptyset$, and plugged in the next available place to the right otherwise.  The inverse bijection is given by reading nodes in a prefix order.  See the picture on the right.


The covering relations on parking trees corresponding to those of the $2$-partition poset are then given as follows.  From a parking tree $T$, another one $U$ such that $T\lessdot U$ is obtained from $T$ by a sequence of operations:
\begin{itemize}
\item choose a vertex $A$ and  partition it into two (non empty) sets $A_1$ and $A_2$,
\item deconcatenate the list of its (possibly empty) subtrees into three lists $L_1$, $L_2$ and $L_3$, such that $L_1$ is non empty and $L_2$ and $A_2$ have the same cardinality,
\item remove from the tree the elements of $A_2$ and $L_2$
\item add the elements of $A_2$ to the rightmost leaf of $A_1$ in $L_1$
\item add $L_2$ as the list of children of $A_2$.
\end{itemize} 

For the leftmost tree in \cref{fig:exple_cover}, $A_1=\{1,5,6\}$ and $A_2=\{2\}$, the possible lists are $(L_1, L_2, L_3) = ((\textcolor{blue}{\emptyset}),(\includegraphics{34.pdf}),(\textcolor{red}{\emptyset}, \textcolor{green}{\emptyset}))$, $((\textcolor{blue}{\emptyset},\includegraphics{34.pdf}),(\textcolor{red}{\emptyset}), (\textcolor{green}{\emptyset}))$ or $((\textcolor{blue}{\emptyset},\includegraphics{34.pdf},\textcolor{red}{\emptyset}), (\textcolor{green}{\emptyset}),())$, which gives each of the other trees in \cref{fig:exple_cover}.

\begin{figure}[h!tp]
    \centering
    \includegraphics[scale=0.7]{expleCover1.pdf}
    \qquad
    \includegraphics[scale=0.7]{expleCover2.pdf}
    \qquad
    \includegraphics[scale=0.7]{expleCover3.pdf}
    \qquad
    \includegraphics[scale=0.7]{expleCover4.pdf}
    \caption{A tree and some trees covering it.\label{fig:exple_cover}}
%\end{figure}

\bigskip

\includegraphics[scale=0.8]{cover.pdf}
%}
\caption{Covering relations in parking trees poset.\label{fig_covers}}

\bigskip

\includegraphics[scale=0.8]{ParkPos3i.pdf}
%}
\caption{The poset of parking trees on three elements.\label{fig_parkpos3}}
\end{figure}



\section{Enumeration of chains of parking functions}
\label{sec2}


\begin{prop}
The species $\mathcal{P}_f$ of parking trees satisfies:
\begin{equation}
\mathcal{P}_f = \sum_{k \geq 1} \mathbb{E}_k \times (\mathcal{P}_f)^k,
\end{equation}
where $\mathbb{E}_k(V) = \delta_{|V|=k} \mathbb{K}$ (where $\mathbb{K}$ is our ground field) and the species of non-empty sets is $\mathbb{E}-1=\sum_{k\geq 1} \mathbb{E}_k$.
\end{prop}

This is obtained from the tree structure, and accordingly we can write an equation in terms of symmetric functions for the Frobenius image of the characters of $\mathcal{P}_f$.

The set of \emph{weak $k$-chains} of parking functions on $I$ is
the set $\operatorname{PF}^I_k$ of $k$-tuples $(a_1,\ldots, a_k)$ 
where $a_i$ are parking functions on $I$ and $a_i \leq a_{i+1}$. 
The species which associates to any set $I$ the set 
$\operatorname{PF}^I_k$ is denoted by $\Ckl$.

\begin{thm} \label{thmspecies} We have:
\begin{equation*}
\Ckl = \sum_{p \geq 1} \Ckmupl \times \left( t\Ckl +1\right)^p,
\end{equation*}
where $\Ckmupl (V) = \delta_{|V|=p} \Ckmul (V)$ on any set $V$ of size $p$.

In terms of generating functions, this translates to:
\begin{equation} 
C_{k,t}^l = C_{k-1,t}^l \circ  \left( x \left( tC_{k,t}^l+1\right) \right)
\end{equation}
\end{thm}

Note that from the functional equation in terms of species, it is theoretically possible to find a formula for the character of $\mathfrak{S}_n$ acting on the chains as above.  Here we only consider the enumerative result. 

\begin{rema}
In terms of generating series, the computations are the same as if we considered chains in a poset of forests of rooted non planar trees, however the two species differ. Defining and studying the poset of forests of rooted trees linked with 2-partition posets will be done in a future work.
Note that the species $\Ckl$ is definitely different from the species $\mathcal{F}_{k,t}^l$ satisfying $\mathcal{F}_{k,t}^l = \left(\mathbb{E}-1\right) \circ (X \left(t\mathcal{F}_{k,t}^l+1\right)^k)$, in the same way that the action of the symmetric group on parking functions and forests of non planar rooted trees are completely different.
\end{rema}

From \cref{thmspecies}, we show by induction the following formula, for any $1 \leq i \leq k$, which leads to \cref{leCor}:
\begin{equation} 
C_{k,t}^l = C_{k-i,t}^l \circ  \left( x \left( tC_{k,t}^l+1\right)^i \right).
\end{equation}

\begin{coro} \label{leCor} The generating function of weak $k$-chains in the 2-partition posets satisfies:
\begin{equation} \label{eqfuncC}
C_{k,t}^l = \exp \left( x \left( tC_{k,t}^l+1\right)^k \right) -1.
\end{equation}
\end{coro}



From \eqref{eqfuncC},  $C_{k,t}^l$ is the compositional inverse of $\operatorname{ln}(1+x)\left(1+tx \right)^{-k}$.
By using Lagrange inversion, it is possible to extract the coefficients and we get:

\begin{coro} \label{coro_enumchains}
 The number of chains $\phi_1 \leq \dots \leq \phi_k$ in $\pp_n$ where $\rk(\phi_k)=\ell$ is:
 \begin{equation}  \label{eq_enumchains}
    \ell !  \binom{kn}{\ell} S_2(n,\ell+1).
 \end{equation}
\end{coro}

%More precisely, it is worth mentioning that the series 
%  \[
%     \sum_{n\geq 1} \sum_{\ell=0}^{n-1} \ell !  \binom{kn}{\ell} S_2(n,l+1) \frac{z^n}{n!},
%  \]
% i.e. the generating function of the numbers above, is the compositional inverse of
% \[
%    \log(1+x) \cdot (1+tx)^k
% \]
% with respect to $x$.
% 
Also, a bijective proof of this corollary will be given in the full version of this work.  
% Let us just mention that, denoting $\Gamma_{\ell,n}(k)$ the polynomial in $k$ given by Equation~\eqref{eq_enumchains}, the series
% \[
%   \sum_{n\geq1} \sum_{\ell=0}^{n-1} \Gamma_{\ell,n}(k) t^{\ell} \frac{z^n}{n!}
% \]
% is the compositional inverse (with respect to $z$) of $(1+tz)^k \log(1+z)$.
Clearly, the formula in \eqref{eq_enumchains} specializes to \eqref{edelman_whit2}, by letting $k=1$.
Also, using a general fact linking the $\zeta$-polynomial of a poset with its Möbius function, at $k=-1$ the formula above specializes to the {\it Whitney numbers of the first kind} of $\pp_n$, defined by:
\[
  w_{\ell}(\pp_n) = \sum_{\phi \in\ppp_n ,  \, \rk(\phi)=\ell }  \mu( \hat0 , \phi).
\] 
Note that the number $\mu( \hat0 , \phi)$ is a product of Catalan numbers.  Indeed, this interval is isomorphic to an interval in $NC_n$, so it follows from the result on the Möbius function of $NC_n$~\cite{kreweras}.  By letting $k=-1$ in \eqref{eq_enumchains}, we get 
\[
  w_{\ell}(\pp_n) = (-1)^{\ell} \ell! \binom{n+\ell-1}{n} S_2(n,\ell+1).
\]
In general, Whitney numbers of the first kind are the dimensions of the {\it Whitney modules}, which are useful to compute the homology of a poset (see \cref{sec_homology}).

\section{Shellability of the parking functions poset}
\label{sec3}

Let $\hat\pp_n$ denote the bounded poset obtained by adding a new maximal element $\hat 1$ on top of $\pp_n$.  The goal of this section is to prove that $\hat\pp_n$ is a {\it shellable poset}.  Some consequences of this property will be explained in the next section.  Our method is to show that there exists a {\it recursive atom ordering} of the poset. We refer to \cite{wachs} for this notion, as well as for the notion of {\it EL-labelling}. 
In this section, we see $\phi\in \pp_n$ as a pair $(\pi,\sigma)$ as explained at the end of \cref{secparkingspace}.


Note that if we have a covering relation $\pi\lessdot\rho$ in $NC_n$, $\pi$ is obtained from $\rho$ by merging two blocks and it follows that $\bar\pi \bar\rho^{-1}$ is a transposition.  Labelling each cover relation $\pi\lessdot\rho$ by $\bar\pi \bar\rho^{-1}$ defines an EL-labelling of $NC_n$, if we order transpositions by the lexicographic order on pairs $(i,j)$ such that $i<j$.  It follows that if we define a total order on the upper covers of $\pi \in NC_n$ by saying that $\rho$ precedes $\tau$ when $\bar\pi \bar\rho^{-1}$ precedes $\bar\pi \bar\tau^{-1}$ in the lexicographic order on pairs, we get a recursive atom ordering of $NC_n$.  This will be a tool in building the recursive atom ordering of $\hat \pp_n$. We also need:

\begin{defi}
The \emph{code} of a permutation $\sigma = \sigma_1\ldots \sigma_n$ is the word $\gamma(\sigma) = c_n\ldots c_1$, with $c_{i} = \# \{ \; j<i \; | \; \sigma^{-1}(j)>\sigma^{-1}(i) \; \}$. Combinatorially, $c_i$ corresponds to the number of integers smaller than $i$ on its right. For instance, $\gamma(15324)= 30100$.
\end{defi}

\begin{defi}
  For each cover relation $(\pi,\sigma) \lessdot (\rho,\tau) $ in $\pp_n$, we define a label:
  \[  
     \Lambda \big( (\pi,\sigma) , (\rho,\tau) \big) = \big( \gamma(\tau) , \bar\pi \bar\rho^{-1} \big).
  \]
  For each $(\pi,\sigma) \in \pp_n$, we define a total order on its upper covers by saying that $(\rho,\tau)$ precedes $(\rho',\tau')$ iff $\Lambda \big( (\pi,\sigma) , (\rho,\tau) \big) < \Lambda \big( (\pi,\sigma) , (\rho',\tau') \big)$, using the lexicographic order on pairs, lexicographic order on codes of permutations, lexicographic order on the set of transpositions as described above.
\end{defi}

Note that if $(\pi,\sigma)$ is maximal in $\pp_n$, it has a unique cover in $\hat\pp_n$ and we don't need to define a total order on its upper covers.

\begin{thm} \label{theo_rao}
The orders defined above form a recursive atom ordering of $\hat \pp_n$.
\end{thm}

It follows that the lexicographic order on maximal chains of $\hat \pp_n$ defines a shelling, and that this poset is shellable, hence Cohen-Macauley. 

The full proof of the theorem above is somewhat technical and is omitted here.  Let us just mention a few facts.  For example, the lexicographic order on codes is easily seen to be relevant here.  Indeed, if $(\sigma,\tau) \leq (\sigma',\tau')$ in $\pp_n$, it can be proved that their codes satisfy $\gamma(\tau) \leq \gamma(\tau')$.  Another property, used in the proof and of independent interest, is the fact that $\pp_n$ is a meet semi-lattice.  Together with a few other lemmas, proving the theorem becomes a case by case verification of the axioms.


\section{Homology of the parking function poset}
\label{sec_homology}

We now study the homology associated to the parking function poset.  The reader may read Wachs' article \cite{wachs} as a general reference on this subject (in particular for the Philip Hall theorem, the Hopf trace formula, Whitney homology).

Let $\pp'_n$ denote the {\it proper part} of $\pp_n$, i.e.~$\pp_n$ with its bottom element removed (the topology associated to $\pp_n$ is trivial so $\pp'_n$ is the poset to consider here).  We denote by $\Omega(\pp'_n)$ the {\it order complex} of $\pp'_n$, i.e.~the simplicial complex whose simplices are the strict chains in $\pp'_n$.  We are interested in the simplicial homology of $\Omega(\pp'_n)$, but let us be more explicit.

\begin{defi}
For $-1\leq m\leq n-2$, the $m$th space of chains is the vector space $\mathcal{C}_m$ freely generated by $m$-dimensional simplices in $\Omega(\pp'_n)$ (i.e.~strict chains $\phi_1<\dots<\phi_{m+1}$, where $\phi_i\in\pp'_n$).  For $0\leq m \leq n-2$, we define a linear map $\partial_m:\mathcal{C}_m\to \mathcal{C}_{m-1}$ as follows: if $\Delta=\{\phi_1,\dots,\phi_{m+1}\}\in\Omega(\pp'_n)$ with $\phi_1<\dots<\phi_{m+1}$, then
\[
  \partial_m( \Delta ) = \sum_{i=1}^{m+1} (-1)^i \cdot (\Delta\setminus\{\phi_i\}).
\]
It is straightforward to check that $\partial_{m}\circ\partial_{m+1}=0$.  For $-1\leq m \leq n-2$, the $m$th reduced homology space of $\pp'_n$ is $\tilde H_m(\pp'_n) = \ker \partial_{m} / \im \partial_{m+1}$. (By convention, $\ker \partial_{-1} = \im \partial_{n-1} = \{0\}$.)
\end{defi}

Note that the action of $\mathfrak{S}_n$ on chains in $\pp'_n$ permits us to view $\mathcal{C}_n$ as a $\mathfrak{S}_n$-module.  It is clear that the maps $\partial_m$ are module maps, so that $\tilde H_m(\pp'_n)$ is also a $\mathfrak{S}_n$-module.  

As a consequence of shellability, $\Omega(\pp'_n)$ has the homotopy type of a bouquet of $n-2$-dimensional spheres, so $\dim \tilde H_m(\pp'_n)=0$ for $m \neq n-2$. 

\begin{thm} \label{theo_charhomology}
The character of $\tilde H_{n-2}(\pp'_n)$ as a representation of $\mathfrak{S}_n$ is given by:
\begin{align}  \label{formula_charhomology}
  \sigma \mapsto (-1)^{n-z(\sigma)} (n-1)^{z(\sigma)-1}.
\end{align}
\end{thm}

\begin{proof}
We can use the result in \cite[Proposition~1.7]{sppp}, and it follows that the desired character is $(-1)^{n-1}$ times the specialization at $k=-1$ of \eqref{char_chains}.  Let us just mention that this result in \cite{sppp} relies on the {\it Hopf trace formula}:
\[
  \sum_{i=-1}^{n-2} (-1)^{i+1} \mathcal{C}_i = \sum_{i=-1}^{n-2} (-1)^{i+1} \tilde H_i ( \pp'_n ),
\]
and on a combinatorial argument to relate strict chains in $\pp'_n$ with large chains in $\pp_n$.
\end{proof}

\begin{coro}
The Möbius invariant of $\hat\pp_n$ is $\mu ( \hat \pp_n ) = (-1)^n (n-1)^{n-1}$.
\end{coro}

\begin{proof}
By the Philip Hall's theorem, $\mu( \hat \pp_n)$ is the Euler characteristic of $\Omega(\pp'_n)$. So it is also $(-1)^n\dim \tilde H_{n-2}(\pp'_n)$.  This comes from taking $\sigma=\mathrm{id}$ in~\eqref{formula_charhomology}.
\end{proof}

\begin{rema}
 Another method to compute the character in \cref{theo_charhomology} would be to use {\it Whitney homology}. The Whitney modules can be obtained explicitly as follows:
\[
  \mathcal{W}_{\ell}(\pp_n) = \sum_{\pi\in NC_n, \; \rk(\pi)=\ell } \bigg(\prod_{b\in K(\pi)} \mathrm{Cat}_{\# b -1} \bigg) \mathrm{Ind}_{\mathfrak{S}_n(\pi)}^{\mathfrak{S}_n}(1)
\]
where $\mathrm{Cat}_n$ is the $n$th Catalan number, and $K(\pi)$ is the Kreweras complement of $\pi$.  
Then we have 
\[
  \tilde H_{n-2}(\pp'_n)  =  (-1)^{n-1} \sum_{\ell = 0 }^{n-1} (-1)^{\ell} \mathcal{W}_{\ell}(\pp_n).
\]
Computing this alternating sum can be done by relating the character in~\eqref{char_chains} with the Fu\ss-Catalan numbers $\mathrm{Cat}^{(m)}_n$, and using the reciprocity $\mathrm{Cat}^{(-1)}_n = (-1)^{n-1}\mathrm{Cat}_{n-1}$.  We omit details.
\end{rema}

\begin{rema}
In the context of the parking space theory, there is a character closely connected to the one in~\eqref{formula_charhomology}.  Say that a noncrossing partition $\pi_n$ has {\it full support} if $1$ and $n$ are in the same block.  Denote by $NCF_n\subset NC_n$ the set of noncrossing partitions with full support.  The {\it primitive noncrossing parking space} is defined as:
\[
  \sum_{\pi \in NCF_n }  \mathrm{Ind}_{\mathfrak{S}_n(\pi)}^{\mathfrak{S}_n}(1). 
\]
It is also given by the action of $\mathfrak{S}_n$ on {\it primitive} parking functions (i.e.~parking functions $w_1\cdots w_n$ such that $\#\{ \; i \; | \; w_i \leq k\}>k$ for $1\leq k <n$).
According to the theory, this character is given explicitly by $\sigma\mapsto (n-1)^{z(\sigma)-1}$.  So it is related to the character in \eqref{formula_charhomology} by tensoring with the sign character of $\mathfrak{S}_n$.
\end{rema}


\section{Perspective}

Among the further questions arising from this work, let us first mention that there should be a generalization to finite well-generated complex reflection groups. Indeed, these have an associated noncrossing partition lattice, and a noncrossing parking space.  New methods might be needed to prove shellability in this general setting.

Before going to other reflection groups, several points might be clarified about the case of the symmetric group.  For example, the remark at the end of the previous section shows that the homology of $\pp'_n$ makes a bridge between the parking space and the primitive parking space.  It would be nice to explain this connection in a more direct way.  A closely related question is the following.  Besides shellability, a more geometric method to characterize the topology of $\pp_n$ might be to use the {\it cluster complex}.  Indeed, this has been done by Kenny~\cite{kenny} in the case of the noncrossing partition lattice, using poset fiber theorems.  Similarly it is possible to build a poset (of ``cluster parking functions'') that projects to $\pp_n$, and we hope it will be useful to understand the topology of $\pp'_n$.



\printbibliography


\end{document}
