Noncrossing partition posets
Richard Ehrenborg and Gábor Hetyei

Department of Mathematics, University of Kentucky,
Lexington, KY 40506-0027.

Department of Mathematics and Statistics, UNC Charlotte,
Charlotte NC 28223-0001.

[2020]

We introduce the poset
$\NC^{d}_{n}$ of all noncrossing partitions such that each block
has cardinality $1$ modulo $d$ and each block of the dual partition
also has cardinality $1$ modulo $d$.
We obtain the cardinality, the Möbius function, the rank numbers,
the antipode, and the number of maximal chains.
Generalizing work of Stanley, we give an edge labeling such that
the labels of the maximal chains are exactly the $d$-parking functions.
We also introduce two classes of labeled trees: the first class is in
bijective correspondence with the noncrossing partitions in
$\NC^{d}_{n}$ and the second class is in bijective
correspondence with the maximal chains.

§ INTRODUCTION

There has been a lot of work on subposets of the partition lattice.
Most notable is the $d$-divisible partition lattice, which has
been studied by
Stanley [22],
Calderbank–Hanlon–Robinson [2]
Wachs [27].
See also the papers by [5, 6]
which extend this lattice to more general partition posets.
In the $d$-divisible partition lattice the size of each block of each partition
is divisible by $d$. Note that that this condition is upward closed
in the partition lattice.
Another condition that is natural to impose on partitions is that
each block size is congruent to $1$ modulo $d$. See for instance
the subposet where all the block sizes are odd
in [2]
and also Wachs <cit.>
and the references therein.
Note that the cover relations in such posets may be described by listing
$d+1$ blocks of a partition which have to be merged into a single block
to obtain a partition covering the original partition.

The noncrossing partition lattice $\NC_{n}$ is a widely studied subposet of the partition lattice
having many applications;
see the references [1, 15, 19, 20, 21, 25].
One of its most striking features is that it is self-dual,
this fact was observed by Kreweras [15]
and Simion–Ullman [20].
For an example; see Figure <ref>.
In fact, Stanley pointed out that every interval
in the noncrossing partition lattice
is self-dual [25].
Also note Armstrong studied the subposet of noncrossing partitions where each block
size is divisible by $d$; see [1].

In this paper we will consider the subposet $\NC^{d}_{n}$ of the noncrossing partition lattice
where each block size is congruent to $1$ modulo $d$
and each block in the dual partition also
has cardinality congruent to $1$ modulo $d$.
That we require this cardinality condition on each partition and
its dual, makes the subposet $\NC^{d}_{n}$
naturally self-dual.
Unfortunately, this subposet is no longer a lattice;
Example <ref>.
On the other hand, many enumerative results for the
noncrossing partition lattice extend to the subposet $\NC^{d}_{n}$.
One less studied invariant is the antipode of a poset
which is the natural Hopf algebra extension of the Möbius function.
For the poset $\NC^{d}_{n}$ we obtain its antipode
in terms of noncrossing hypertrees,
generalizing the results in [4].
We also enumerate the maximal chains in the poset $\NC^{d}_{n}$
and show that via an edge labeling they are in
bijection with $d$-parking functions, as defined
by Stanley [24] and Yan [29].
Furthermore, these structures are also in bijective
correspondence with a class of trees that we call $d$-parking trees.

The paper is organized as follows.
In Section <ref>
we present basic results about the noncrossing partition lattice $\NC_{n}$
including the Kreweras dual and review basic generating function results.
Our main object of study, the poset $\NC^{d}_{n}$ is
introduced in Section <ref>.
We prove that intervals in this poset are products of smaller posets of the same form.
We furthermore characterize partitions in $\NC^{d}_{n}$
in terms of the blocks and the distance between adjacent elements in the blocks;
see Proposition <ref>.
In Section <ref>
we obtain enumerative results for our poset $\NC^{d}_{n}$.
Our approach is using generating functions;
see subsection <ref>.
This method generalizes results of Speicher [21];
see Remark <ref>.
The cardinality and Möbius function of the poset $\NC^{d}_{n}$ is obtained
in subsection <ref>
in subsection <ref>
the rank numbers are obtain using Good's inversion formula.
In Section <ref>
we obtain an expression for the antipode of $\NC^{d}_{n}$
in terms of noncrossing hypertrees.
A tree representation for noncrossing partitions in $\NC^{d}_{n}$
is introduced in
Section <ref>. This
representation allows to present a combinatorial proof of some
of the results stated in Section <ref>.
The number of maximal chains of the poset $\NC^{d}_{n}$
is obtained in Section <ref> using
the Abel polynomials and an associated Sheffer sequence.
In Section <ref>
we generalize Stanley's edge labeling of $\NC_{n}$ to $\NC^{d}_{n}$
and show that the maximal chains are in bijection with the set of all
$d$-parking functions.
We introduce the notion of a $d$-parking tree in
Section <ref>. These labeled trees are in bijection
with the $d$-parking functions and visually encode the block merging
processes represented by the maximal chains in $\NC^{d}_{n}$.
Finally, further research and open problems are
outlined in Section <ref>.

§ PRELIMINARIES

§.§ The noncrossing partition lattice

The partition lattice consists of all partitions of
the set $[n] = \{1,2, \ldots, n\}$.
Two different blocks $B$ and $C$ are noncrossing if there are no four
elements $i < j < k < \ell$ such that $i,k \in B$ and $j,\ell \in C$.
This condition is viewed geometrically as follows. Place the elements of the set $[n]$
in a circle in positive orientation. The two blocks $B$ and $C$ are noncrossing
if the convex hull of the two blocks are disjoint.
A partition is noncrossing if all pairs of blocks are noncrossing.
For an example,
the partition
$\pi = \{\{1\}, \{2,9,10\}, \{3\}, \{4,5,6,7,8\}, \{11\}\}$
is displayed in the first drawing in
Figure <ref>.
For short hand we write this partition as
We call these drawings of the noncrossing partition and its dual
the circle representation of the partition.

The Kreweras dual of a noncrossing partition is defined as follows.
First observe that the complement of the union of the convex hull of the blocks
form regions. For instance,
in the partition $\pi$ in
Figure <ref>
we have a region $R$ with the vertices $2$, $3$, $4$, $8$ and $9$.
However, to obtain the dual partition place the vertex $i^{\prime}$
between vertices $i$ and $i+1$.
That is, we have the cyclic order
$1 < 1^{\prime} <
2 < 2^{\prime} <
3 < 3^{\prime} <
\cdots <
n-1 < (n-1)^{\prime} <
n < n^{\prime} < 1$.
The region $R$ now correspond to the block
The blocks corresponding to the regions form the dual partition
which is noncrossing. In our example, we obtain
the dual partition $\pi^{\prime}$ given by

[scale = 0.40,inner sep=0.1mm]

[-] (0,0) circle (5);

[fill=gray!50] 2 – 9 – 10 – cycle;

[fill=gray!50] 4 – 5 – 6 – 7 – 8 – cycle;

įn 1, 2, ..., 11

at  $\k$};
\draw[-,fill] \gpp{\k} circle (0.1);
\end{tikzpicture}
\hspace*{7 mm}
\begin{tikzpicture}[scale = 0.40,inner sep=0.1mm]
% Draw the circle
\draw[-] (0,0) circle (5);

%%%% Draw the block {2,9,10}
\draw[fill=gray!50] \gpp{2} -- \gpp{9} -- \gpp{10} -- cycle;
%%%% Draw the block {4,5,6,7,8}
\draw[fill=gray!50] \gpp{4} -- \gpp{5} -- \gpp{6} -- \gpp{7} -- \gpp{8} -- cycle;
%%%% Draw the dual block {1',10',11'}
\draw[dashed,fill=gray!10] \gqq{1} -- \gqq{10} -- \gqq{11} -- cycle;
%%%% Draw the dual block {2',3',8'}
\draw[dashed,fill=gray!10] \gqq{2} -- \gqq{3} -- \gqq{8} -- cycle;

% Place the elements 1 through 11 and 1' through 11'.
\foreach \k in {1, 2, ..., 11}
\node at \hpp{\k} {$\k$};
\node at \hqq{\k} {$\k^{\prime}$};
\draw[-,fill] \gpp{\k} circle (0.1);
\draw[-,fill=white] \gqq{\k} circle (0.1);
\end{tikzpicture}
\hspace*{7 mm}
\begin{tikzpicture}[scale = 0.40,inner sep=0.1mm]
% Draw the circle
\draw[-] (0,0) circle (5);

%%%% Draw the dual block {1',10',11'}
\draw[dashed,fill=gray!10] \gqq{1} -- \gqq{10} -- \gqq{11} -- cycle;
%%%% Draw the dual block {2',3',8'}
\draw[dashed,fill=gray!10] \gqq{2} -- \gqq{3} -- \gqq{8} -- cycle;

% Place the elements 1' through 11'.
\foreach \k in {1, 2, ..., 11}
\node at \hqq{\k} {$\k^{\prime}$};
\draw[-,fill=white] \gqq{\k} circle (0.1);
\end{tikzpicture}
\end{center}
\caption{The noncrossing partition $\pi$ given by
its circle representation
and the Kreweras dual partition
\label{figure_example_noncrossing_partition}
\end{figure}

The other natural dual to a noncrossing partition
is the Simion--Ullman dual~[20], that we denote by $\SU(\pi)$.
It uses a different order on the set $1^{\prime}$ through $n^{\prime}$:
here we have
$1 < n^{\prime} <
2 < (n-1)^{\prime} <
\cdots <
n-1 < 2^{\prime} <
n < 1^{\prime} < 1$.
The Simion--Ullman dual is an involution, that is,
$\SU(\SU(\pi)) = \pi$.
In this paper we will use the Kreweras dual by default
as it yields an easier labeling of the dual partition.

We say that a block $B$ of the noncrossing partition $\pi$ and
a block $C^{\prime}$ of the dual partition are {\em adjacent}
if the block $B$ contains the two elements $i$ and $j$
(they could be the same element)
and the block $C^{\prime}$
contains the elements
Note that the $4$-gon
with vertices
$i$, $i^{\prime}$, $(j-1)^{\prime}$ and $j$
forms a channel between the block~$B$ and the dual block~$C^{\prime}$.

Following~\cite[Definitions~3.1 and~3.2]{Ehrenborg_Happ}
we make the following definition.
For a block $B$ in a noncrossing partition $\pi$ and
an adjacent block $C^{\prime}$ in the dual partition $\pi^{\prime}$
let $i$ and $j$ be the two vertices of the block~$B$
that are adjacent to the block~$C^{\prime}$
and pick
$\gamma(B,C^{\prime})$ be the vertex
of these two that is the most
negative orientation from the block $B$'s perspective.

A small note is in order at this point.
In the paper~[4]
they define $v_{R}(B)$. There are two differences
from the definition of $\gamma(B,C^{\prime})$.
First, here we work with the blocks of the dual partition, whereas
they use regions in the partition. Second, they pick the vertex
in the most positive orientation. We pick the vertex in the most
negative orientation. The reason for this difference is that
we would like to be consistent with the Kreweras notation of the dual;
see Section~\ref{section_A_tree_representation_of_noncrossing_partitions}.

Let $|\pi|$ denote the number of blocks of the partition $\pi$.
Let $\NC_{n}$ be the collection all noncrossing partitions on the set $[n]$
ordered by refinement. This poset is graded and is in fact a lattice.
Observe that the map $\pi \longmapsto \SU(\pi)$
is an order-reversing involution.
That is, the lattice $\NC_{n}$ is self-dual.
Also note that rank of a noncrossing partition $\pi$ is given by
$\rho(\pi) = n - |\pi|$
and that the identity $|\pi| + |\pi'| = n+1$ holds.

Consider a pair of noncrossing partitions $\pi$ and $\sigma$ in the
noncrossing partition lattice~$\NC_{n}$ such that $\pi \leq \sigma$.
The interval $[\pi,\sigma]$ is given by $\{\tau \in \NC_{n} : \pi \leq \tau \leq \sigma\}$.
It is well-known that intervals in the noncrossing partition lattice are isomorphic to
Cartesian products of noncrossing partition lattices~\cite[Proposition~1]{Speicher}.

\subsection{Generating functions}

We need the following classical results about generating functions.
Assume that the generating function $G(z)$ satisfies the algebraic equation
\begin{align}
G(z) & = z \cdot G(z)^{m}   + 1
\label{equation_algebraic_equation}
\end{align}
then the coefficient of $z^{n}$ of $G(z)^{\ell}$
is given by
\begin{align}
[z^{n}] G(z)^{\ell}
& =
\frac{\ell}{mn+\ell} \cdot \binom{mn+\ell}{n}
\frac{\ell}{mn+\ell-n} \cdot \binom{mn+\ell-1}{n} ,
\label{equation_coefficient_of_the_generating_function}
\end{align}
for $\ell \geq 1$;
see~\cite[Equations~(7.68) and~(7.69)]{Graham_Knuth_Patashnik}.
See also~\cite[Example~6.2.6]{Stanley_EC2}.

The Lagrange inversion formula allows one to obtain
the coefficients of a power series $f(z)$ that satisfies
the functional equation $f(z) = z \cdot g(f(z))$.
Good stated a multivariate extension of the Lagrange inversion formula~[10].
See also~\cite[Theorem~4]{Ehrenborg_Mendez}.
We will only need this extension in two variables and
hence we state it only in this case.
\begin{theorem}[Good's Inversion Formula for two variables.]
Let $g_{1}(z,w)$ and $g_{2}(z,w)$ be formal power series
with constant coefficients.
Assume that the formal power series $f_{1}(z,w)$ and $f_{2}(z,w)$ satisfy the equations
\begin{align*}
& =
z \cdot g_{1}(f_{1}(z,w),f_{2}(z,w)) ,
& =
z \cdot g_{2}(f_{1}(z,w),f_{2}(z,w)) .
\end{align*}
Then the coefficient of $z^{m} w^{n}$ of $f_{1}(z,w)^{k} \cdot f_{2}(z,w)^{\ell}$
is given by
\begin{align*}
[z^{m} w^{n}] f_{1}(z,w)^{k} \cdot f_{2}(z,w)^{\ell}
& =
[z^{m-k} w^{n-\ell}]
\det
\begin{pmatrix}
g_{1}^{m} - z \cdot \frac{\partial g_{1}}{\partial z} \cdot g_{1}^{m-1}
- w \cdot \frac{\partial g_{1}}{\partial w} \cdot g_{1}^{m-1}
\\
- z \cdot \frac{\partial g_{2}}{\partial z} \cdot g_{2}^{n-1}
g_{2}^{n} - w \cdot \frac{\partial g_{2}}{\partial w} \cdot g_{2}^{n-1}
\end{pmatrix} .
\end{align*}
\label{theorem_Good}
\end{theorem}

\section{The noncrossing partition poset $\NC^{d}_{n}$}
\label{section_NC^{d}_{n}}

Let $d$ be a positive integer.
We form a subposet $\NC_{n}^{d}$ of the noncrossing partition lattice $\NC_{n}$
by restricting our attention to partitions $\pi$ such that
all the blocks of the partition $\pi$ and the dual partition $\pi^{\prime}$
have cardinality congruent to $1$ modulo $d$,
that is,
\begin{align*}
\NC_{n}^{d}
& =
\{\pi \in \NC_{n} : \forall B \in \pi \: |B| \equiv 1 \bmod d \text{ and }
\forall C^{\prime} \in \pi^{\prime} \: |C^{\prime}| \equiv 1 \bmod d \} .
\end{align*}
As an example, the partition in
belongs the poset $\NC^{2}_{11}$
since all the blocks in the partition and the dual partition
have odd cardinality.

Observe that we can replace the Kreweras dual $\pi^{\prime}$
with the Simion--Ullman dual $\SU(\pi)$ in the
above definition
and it will not change the definition of the poset $\NC^{d}_{n}$.
However, the Simion--Ullman dual $\SU(\pi)$ is an order reversing
involution on the poset $\NC^{d}_{n}$ and
hence this poset is self-dual.

We now characterize the values of $n$ for which the poset $\NC^{d}_{n}$
is nonempty.
\begin{lemma}
If the set $\NC^{d}_{n}$ is nonempty then $n \equiv 1 \bmod d$.
In other words, if $n \not \equiv 1 \bmod d$ then
the set $\NC^{d}_{n}$ is empty.
\label{lemma_fundamental}
\end{lemma}
\begin{proof}
Assuming that $\NC^{d}_{n}$ is nonempty,
let $\pi$ be a noncrossing partition in $\NC^{d}_{n}$.
Then we have the following string of congruences
$n = \sum_{B \in \pi} |B| \equiv  \sum_{B \in \pi} 1 = |\pi| \bmod d$.
Similarly, we obtain
$n \equiv |\pi'| \bmod d$.
Adding these two congruences yields
$2n \equiv |\pi| + |\pi'| = n+1 \bmod d$, that is,
$n \equiv 1 \bmod d$.
\end{proof}

Note that when $n \equiv 1 \bmod d$ then $\NC^{d}_{n}$
is nonempty since it contains the noncrossing partition~$\{[n]\}$.
Furthermore, this partition~$\{[n]\}$ is the maximal element in $\NC^{d}_{n}$
and the noncrossing partition $\{\{1\}, \{2\}, \ldots,\{n\}\}$ is the minimal element.

By the same the same reasoning as in Lemma~\ref{lemma_fundamental}
we have the next lemma.
\begin{lemma}
Let $n$ be a positive integer such that $n \equiv 1 \bmod d$ and
let $\pi$ be a noncrossing partition in $\NC_{n}$.
Assume that all blocks $B$ in $\pi$ satisfy $|B| \equiv 1 \bmod d$.
Assume furthermore
that all blocks~$C'$ but one in the dual partition $\pi'$ satisfy $|C'| \equiv 1 \bmod d$.
Then the noncrossing partition~$\pi$ belongs to~$\NC^{d}_{n}$.
\label{lemma_all_but_one}
\end{lemma}
\begin{proof}
Let $D'$ be the block in the dual partition $\pi'$ for which we do not have a congruence.
We have the following string of congruences:
\begin{align*}
& =
n - \sum_{\substack{C' \in \pi' \\ C' \neq D'}} |C'|
\equiv
n - (|\pi'| - 1)
n + 1 - |\pi'|
\equiv
\equiv
\sum_{B \in \pi} |B|
\equiv
\equiv
1 \bmod d.
\qedhere
\end{align*}
\end{proof}

\begin{lemma}
Assume that the noncrossing partition $\pi$ belongs to the noncrossing partition poset $\NC^{d}_{n}$.
Then the two following equalities hold:
\begin{align*}
\frac{|\pi'| - 1}{d}
& =
\sum_{B \in \pi} \frac{|B| - 1}{d} ,
\frac{|\pi| - 1}{d}
& =
\sum_{C' \in \pi'} \frac{|C'| - 1}{d} ,
\end{align*}
where all the summands are integers.
\label{lemma_blocks_versus_dual_partition}
\end{lemma}
\begin{proof}
By duality it is enough to prove the first identity.
We have $|\pi'| - 1 = n - |\pi| = \sum_{B \in \pi} (|B| - 1)$,
and the result follows by dividing by $d$.
By the definition of $\NC^{d}_{n}$, all summands in the statement are integers.
\end{proof}

\begin{lemma}
Let  $\sigma$ be a noncrossing partition in the noncrossing partition poset $\NC^{d}_{n}$
such that $\sigma$ is a coatom in $\NC^{d}_{n}$.
That is, $\sigma$ is covered by the maximal element~$\ho$.
Then the partition $\sigma$ consists of $d+1$ blocks.
\end{lemma}
\begin{proof}
We prove the contrapositive statement:
a noncrossing partition
$\pi$ with $dr+1$ blocks, where $r \geq 2$,
is not a coatom.
By Lemma~\ref{lemma_blocks_versus_dual_partition}
we know that
$r = \sum_{C' \in \pi'} (|C'| - 1)/d$.
We now have two cases.
The first case is when this sum has at least two non-zero summands.
Pick one of those nonzero terms
corresponding to the block $D'$ in the dual partition.
Now form the noncrossing partition $\sigma$ from $\pi$ by joining all blocks
adjacent to the block $D'$.
The second case is when this sum
$\sum_{C' \in \pi'} (|C'| - 1)/d$
consists of one non-zero summand. Again, let this term correspond to
the dual block $D'$ which has cardinality $dr+1$.
Say $D'$ is given by $\{i'_{1} < i'_{2} < \cdots < i'_{dr+1}\}$.
Now join the $d+1$ blocks of $\pi$ that contain the elements
$i_{1}$ through $i_{d+1}$ to obtain a new noncrossing partition $\sigma$.
In both cases, the partition $\sigma$ belongs to $\NC^{d}_{n}$ and does not consist of one block.
In the first case the block $D'$ is replaced by all singleton blocks.
In the second case $D'$ is replaced by
the singleton blocks $\{i'_{1}\}$ through $\{i'_{d}\}$
and the block $\{i'_{d+1}, i'_{d+2}, \ldots, i'_{rd+1}\}$.
Hence we conclude that $\pi$ is not a coatom.
\end{proof}

\begin{lemma}
Let  $\sigma$ be a coatom in the noncrossing partition poset $\NC^{d}_{n}$,
and assume that $\sigma = \{B_{1},B_{2}, \ldots, B_{d+1}\}$.
Then the interval $[\hz,\sigma]$ in $\NC^{d}_{n}$ factors as
\begin{align*}
& \cong
\prod_{i=1}^{d+1} \NC^{d}_{|B_{i}|} .
\end{align*}
\label{lemma_one_small_step}
\end{lemma}
\begin{proof}
Let $\tau$ be a noncrossing partition in the interval~$[\hz,\sigma]$,
that is, $\tau \leq \sigma$.
Let $\tau_{i}$ be the restriction of the partition $\tau$ to the block $B_{i}$.
Note that $|B_{i}| \equiv 1 \bmod d$.
Furthermore, each block $B$ of $\tau_{i}$
is a block of $\tau$ and hence satisfies $|B| \equiv 1 \bmod d$.
Note that all but one of the blocks of the dual partition $\tau_{i}'$
is a block of the dual partition $\tau'$
and thus satisfies $|C'| \equiv 1 \bmod d$.
Hence by Lemma~\ref{lemma_all_but_one}
we conclude that $\tau_{i}$ belongs to $\NC^{d}_{|B_{i}|}$.

Furthermore, the map from the interval~$[\hz,\sigma]$
to the Cartesian product $\prod_{i=1}^{d+1} \NC^{d}_{|B_{i}|}$,
sending $\tau$ to the $(d+1)$-tuple
$(\tau_{1},\tau_{2}, \ldots, \tau_{d+1})$ is bijective
and order preserving.
\end{proof}

\begin{lemma}
The noncrossing partition poset $\NC^{d}_{n}$ is graded of rank $(n-1)/d$
and the rank function is given by $\rho(\pi) = (n-|\pi|)/d$.
\label{lemma_graded_and_rank_function}
\end{lemma}
\begin{proof}
It is enough to show that every maximal chain in the poset $\NC^{d}_{dk+1}$
has length $k$. We prove this by induction on $k$. When $k=0$ the statement
is directly true. Assume now that it is true for noncrossing partition posets with smaller value
of $k$ and we prove it for $k$.
Consider a maximal chain ${\bf m} = \{\hz \coveredby \cdots \coveredby \sigma \coveredby \ho\}$,
where the coatom $\sigma$ is given by $\{B_{1}, B_{2}, \ldots, B_{d+1}\}$.
Since the interval $[\hz,\sigma]$ is given by a product of $\NC^{d}_{|B_{i}|}$,
where each factor is graded, the poset~$[\hz,\sigma]$ is graded.
Its rank is given by the sum
$\sum_{i=1}^{d+1} (|B_{i}|-1)/d = (n-d-1)/d = (n-1)/d-1$.
Since the rank of $[\hz,\sigma]$ is independent of the coatom $\sigma$,
the poset $\NC^{d}_{n}$ is graded and its rank is one more than $(n-1)/d-1$.

Next observe that the suggested rank function satisfies
$\rho(\hz) = 0$, $\rho(\ho) = (n-1)/d$ and is strictly increasing.
Hence it is the unique rank function.
\end{proof}

\begin{corollary}
Let $\pi \coveredby \sigma$ be a cover relation in the noncrossing
partition poset $\NC^{d}_{n}$. Then $\sigma$ is obtained by joining
$d+1$ blocks of $\pi$.
\label{corollary_cover_relation}
\end{corollary}
\begin{proof}
Since $\rho(\pi) + 1 = \rho(\sigma)$ we obtain that $|\pi| = |\sigma|+d$.
But since every block size of $\pi$ and $\sigma$ is congruent to $1$ modulo $d$,
the only option is to join $d+1$ blocks of $\pi$.
\end{proof}

By Lemma~\ref{lemma_one_small_step}
and the dual version of this lemma, we have the following proposition.

\begin{proposition}
Let $\pi$ and $\sigma$ be two noncrossing partitions in $\NC^{d}_{n}$
such that $\pi \leq \sigma$ holds.
Then the interval $[\pi,\sigma]$ in $\NC^{d}_{n}$ is isomorphic to
the Cartesian product of smaller
posets of the form $\NC^{d}_{k}$.
\label{proposition_Cartesian_product}
\end{proposition}

For two sets $B \subseteq \{1,2,  \ldots, n\}$
and $C' \subseteq \{1',2',  \ldots, n'\}$
define the {\em intertwining number} $i(B,C')$
to be the number of times we move from the set $B$ to set $C'$
when reading the entries of $B \cup C'$ in the
cyclic order
$1 < 1^{\prime} <
2 < 2^{\prime} <
3 < 3^{\prime} <
\cdots <
n-1 < (n-1)^{\prime} <
n < n^{\prime} < 1$.
Note that $i(B,C') = 0$ if and only if $B$ or $C'$ is the empty set.
Given two noncrossing partitions $\pi$ and $\sigma$ in $\NC^{d}_{n}$
such that $\pi \leq \sigma$.
Then the interval $[\pi,\sigma]$ in $\NC^{d}_{n}$ is isomorphic to
the Cartesian product
\begin{align*}
& \cong
\prod_{B \in \sigma}
\prod_{C' \in \pi'}
\NC^{d}_{i(B,C')} .
\end{align*}
However, we do not need this statement and hence omit its proof.

We also have the following characterization of the noncrossing partitions
in the poset $\NC^{d}_{n}$.
\begin{proposition}
The noncrossing partition $\pi$ belongs to $\NC^{d}_{n}$
if and only if
the following two conditions are satisfied
$n \equiv 1 \bmod d$;
for each pair of cyclically consecutive elements $i$ and $j$
of a nonsingleton block $B$ in a noncrossing partition $\pi$,
the number of elements in $[n]$ strictly between $i$ and $j$ in the cyclic order
is divisible by~$d$.
\label{proposition_characterization}
\end{proposition}
\begin{proof}
The forward implication that $n \equiv 1 \bmod d$ follows directly by
The other forward implication follows by
constructing the noncrossing partition $\tau$ on the half open cyclic interval~$[i,j)$
by letting
\begin{align*}
\tau
& =
\{\{i\}\}
\cup
\{D \in \pi : D \subseteq (i,j)\} .
\end{align*}
Note that this construction amounts to restricting $\pi$ to the cyclic interval~$[i,j]$
and identifying the two elements $i$ and $j$.
Note that the block $B$ becomes
the singleton block~$\{i\}$.
Every block $D \neq B$ of $\pi$ is either contained in the open interval $(i,j)$ or it is disjoint from it,
yielding $|D| \equiv 1 \bmod d$ for the blocks in $\tau$.
Also observe that any block $C'$ in the dual partition $\tau'$ is a dual block of $\pi$
and hence satisfies $|C'| \equiv 1 \bmod d$.
That is, the partition $\tau$ belongs $\NC^{d}_{|[i,j)|}$ and
the previous lemma implies that $|[i,j)| \equiv 1 \bmod d$, proving the lemma.

Now consider the opposite implication.
Given a block $B$ in $\pi$ of size $k$, that is,
$B = \{i_{1}, i_{2}, \ldots, i_{k}\}$. Note that
the set $[n]$ is the disjoint union of $B$ and all the open cyclic intervals $(i_{j},i_{j+1})$.
Consider the cardinality modulo $d$, that is,
$|B| \equiv |B| + \sum_{j=1}^{k} |(i_{j},i_{j+1})| = n \equiv 1 \bmod d$.
Hence every block has cardinality congruent to $1$ modulo~$d$.

Next, let $i'$ and $j'$ be two cyclically consecutive elements
of a nonsingleton block $C'$ in the dual partition $\pi'$.
Note that the elements $j$ and $i+1$ are two cyclically consecutive elements
of a block $B$ of $\pi$.
Hence by the second condition the open cyclic interval
$(j,i+1) = \{j+1, j+2, \ldots, i\}$ has its size to be a multiple of $d$.
Now the open interval $(i',j') = \{(i+1)',(i+2)',\ldots,(j-1)'\}$ has the same
size as
$\{i+1, i+2, \ldots, j-1\}
\{j, j+1,\ldots, i\}$.
Again, by considering the cardinality modulo~$d$ we obtain
$|(i',j')| \equiv n - 1 - |(j,i+1)| \equiv 0 \bmod d$.
Hence the second condition of the proposition holds for the
dual partition $\pi'$.
Finally, by the argument in the previous paragraph of this proof,
every block~$C'$ in the dual partition $\pi'$
satisfies $|C'| \equiv 1 \bmod d$ and the proposition follows.
\end{proof}

\begin{example}
We observe that $\NC^{d}_{n}$ is not a lattice in general.
For instance, when $d=2$ and $n=7$ we have that the
two partitions $1|234|5|6|7$ and $1|2|345|6|7$
are covered by
the two partitions $12345|6|7$ and $1|23456|7$.
\label{example_not_a_lattice}
\end{example}

\section{Enumerative results for the poset $NC^{d}_{n}$}
\label{section_Enumerative}

\subsection{Generating function approach}
\label{subsection_Generating}

We now introduce generating functions in order to obtain
enumerative results for the noncrossing partition poset $\NC^{d}_{n}$.
Let $a(0) = 1, a(1), a(2), \ldots$
and $a^{*}(0) = 1, a^{*}(1), a^{*}(2), \ldots$
be two given sequences.
For a noncrossing partition $\pi$ in the poset $\NC^{d}_{dk+1}$
define its weight by the product:
\begin{align*}
\wt(\pi)
& =
\prod_{B \in \pi} a\left(\frac{|B|-1}{d}\right)
\cdot
\prod_{C^{\prime} \in \pi^{\prime}} a^{*}\left(\frac{|C^{\prime}|-1}{d}\right)
\cdot
\cdot
t^{({|\pi^{\prime}|-1})/{d}} .
\end{align*}
Note that the power of the variable $s$ is the corank of the partition $\pi$
and that the power of $t$ is the rank of $\pi$
in the poset $\NC^{d}_{dk+1}$.
Hence every monomial $s^{i} t^{j} \cdot x^{k}$ that occurs
satisfies $i+j=k$.
We are interested in  exploring the following sum and its ordinary generating function:
\begin{align}
& =
\sum_{\pi \in \NC^{d}_{dk+1}}
\wt(\pi) ,
& =
\sum_{k \geq 0} b(k) \cdot x^{k} .
\label{equation_b_k}
\end{align}
Let $A(x)$ and $A^{*}(x)$ be the two ordinary generating functions
\begin{align*}
A(x) & = \sum_{k \geq 0} a(k) \cdot x^{k} ,
A^{*}(x) & = \sum_{k \geq 0} a^{*}(k) \cdot x^{k} .
\end{align*}
In order to obtain information about $B(x)$, we consider the two following partial sums
and their generating functions
\begin{align*}
& =
\sum_{\substack{\pi \in \NC^{d}_{dk+1} \\ \{1\} \in \pi}}
\wt(\pi) ,
& =
\sum_{k \geq 0} c(k) \cdot x^{k} , \\
& =
\sum_{\substack{\pi \in \NC^{d}_{dk+1} \\ \{1^{\prime}\} \in \pi^{\prime}}}
\wt(\pi) ,
& =
\sum_{k \geq 0} c^{*}(k) \cdot x^{k} .
\end{align*}
That is, $c(k)$ and its generating function $C(x)$, enumerate
noncrossing partitions which has a given element as a singleton block.
Similarly, $c^{*}(k)$ and $C^{*}(x)$ enumerate partitions
with a given element as a singleton block in the dual.

\begin{theorem}
The following three generating function identities hold:
\begin{align}
\label{equation_C_and_C*}
& =
A^{*}\left(x \cdot s \cdot C^{*}(x)^{d}\right) ,
& =
A\left(x \cdot t \cdot C(x)^{d}\right) , \\
B(x) & = C(x) \cdot C^{*}(x) .
\end{align}
Furthermore, the first two equations uniquely determine
the generating functions $C(x)$ and $C^{*}(x)$.
\label{theorem_generating_functions_C_and_C*}
\end{theorem}
\begin{proof}
Observe that the first two  identities are dual to each other. Hence it
is enough
that we prove the second identity.
We are considering the case where the singleton block $\{1^{\prime}\}$
belongs to the dual partition. That is, the partition contains a block $B$
such that
\begin{align*}
& =
\{1 = i_{1} < i_{2} < \cdots < i_{dr+1} = n\} .
\end{align*}
By Proposition~\ref{proposition_characterization}
each difference $i_{j+1} - i_{j}$ is congruent to $1$ modulo $d$.
Let $\tau_{j}$ now be the restriction of the partition $\pi$
to the union $[i_{j},i_{j+1}] \cup B$ and identify all the elements of the block $B$.
This construction is equivalent to letting $\tau_{j}$ be the restriction to the
open interval $(i_{j},i_{j+1})$ and adding a singleton block.
Keeping track of the blocks in~$\pi$ we have that
\begin{align*}
|\pi| - 1
& =
(|\tau_{1}| - 1)
+ \cdots +
(|\tau_{dr}| - 1) .
\end{align*}
Counting the blocks in the dual partition we obtain
\begin{align*}
|\pi^{\prime}| - 1
& =
+ \cdots +
(|\tau^{\prime}_{1}| - 1)
+ \cdots +
(|\tau^{\prime}_{dr}| - 1) .
\end{align*}
Hence the weight $\wt(\pi)$ factors as
\begin{align*}
\wt(\pi)
& =
\cdot
\cdot
\wt(\tau_{1})
\cdots
\wt(\tau_{dr}) .
\end{align*}
Now we express $c^{*}(k)$ as the sum
\begin{align}
\label{equation_recursion_for_c*}
& =
\sum_{r \geq 1}
\cdot
\cdot
\sum_{
\substack{1 = i_{1} < i_{2} < \cdots < i_{dr+1} = n \\
i_{j+1} - i_{j} \equiv 1 \bmod d}
\sum_{\tau_{1}}
\cdots
\sum_{\tau_{dr}}
\prod_{j=1}^{dr}
\wt(\tau_{j}) \\
\nonumber
& =
\sum_{r \geq 1}
\cdot
\cdot
\sum_{
\substack{1 = i_{1} < i_{2} < \cdots < i_{dr+1} = n \\
i_{j+1} - i_{j} \equiv 1 \bmod d}
\prod_{j=1}^{dr}
c\left( \frac{i_{j+1} - i_{j} - 1}{d} \right) ,
\end{align}
where each $\tau_{j}$ ranges over partitions in
with a given singleton block.
Observe that $k$ is given by the sum
\begin{align*}
& =
r + \frac{i_{2} - i_{1} - 1}{d}
+ \cdots + \frac{i_{dr+1} - i_{dr} - 1}{d} .
\end{align*}
Hence multiply with $x^{k}$ and sum over all $k \geq 1$.
\begin{align*}
\sum_{k \geq 1} c^{*}(k) \cdot x^{k}
& =
\sum_{r \geq 1}
a(r) \cdot t^{r} \cdot x^{r} \cdot
\sum_{
\substack{1 = i_{1} < i_{2} < \cdots < i_{dr+1} = n \\
i_{j+1} - i_{j} \equiv 1 \bmod d}
\prod_{j=1}^{dr}
c\left( \frac{i_{j+1} - i_{j} - 1}{d} \right)
\cdot
x^{({i_{j+1} - i_{j} - 1})/{d}} \\
& =
\sum_{r \geq 1}
a(r) \cdot t^{r} \cdot x^{r} \cdot C(x)^{dr} .
\end{align*}
Lastly, adding the constant $c^{*}(0) = 1$ yields the second equation.

Equation~\eqref{equation_recursion_for_c*} and its dual
yield recursions for the two sequences $c(k)$ and $c^{*}(k)$.
That is,
are expressing $c(k)$
in terms of $c^{*}(0), \ldots, c^{*}(k-1)$.
The dual equation
expresses $c^{*}(k)$
in terms of $c(0), \ldots, c(k-1)$.
Hence with the initial condition that $c(0) = c^{*}(0) = 1$,
the two functions $C(x)$ and $C^{*}(x)$ are unique.

Now we prove the third identity.
Given a partition $\pi$ in $\NC^{d}_{dk+1}$.
Let $j$ be the largest element in the block $B$ containing $1$.
Proposition~\ref{proposition_characterization} implies
that $j \equiv 1 \bmod d$, hence let $j = dr+1$.
Similarly, then $j^{\prime}$ is the smallest element in
block of the dual partition containing $n^{\prime}$.
Let $\sigma$ be the restriction $\pi$ to the interval $[1,j]$,
which has cardinality $dr+1$.
Let $\tau$ be the restriction of $\pi$ to the union $[j+1,n] \cup B$
and identify all elements of the block~$B$.
Note that $\tau$ is a partition on a set of size $d(k-r) + 1$.
Note that $\sigma$ has a given singleton block in the dual
and $\tau$ has also a given singleton block.
Enumerating the blocks in $\pi$ and the blocks in the dual partition
we have
\begin{align*}
|\pi| -1 & = |\sigma| -1 + |\tau| - 1 , &
|\pi^{\prime}| -1 & = |\sigma^{\prime}| -1 + |\tau^{\prime}| - 1 .
\end{align*}
Hence the weight of $\pi$ factors as
\begin{align*}
\wt(\pi)
& =
\wt(\tau) \cdot \wt(\sigma) .
\end{align*}
Now sum over all partitions $\pi$ in $\NC^{d}_{dk+1}$, multiply with
$x^{k} = x^{r} \cdot x^{k-r}$ and sum over all
$k \geq 0$ yields the desired identity.
\end{proof}

\begin{remark}
In the case of the noncrossing partition lattice,
that is, $d=1$ and when
$s = t = a^{*}(k) = 1$ for all $k$,
Speicher has a generating function identity;
see~\cite[Theorem on page~616]{Speicher}.
Note that $A^{*}(x) = 1/(1-x)$
$C(x) = 1/(1 - x \cdot C^{*}(x))$,
that is,
$1 = C(x) - x \cdot C(x) \cdot C^{*}(x) = C(x) - x \cdot B(x)$.
This last equation, $C(x) = 1 + x \cdot B(x)$
can be obtained combinatorially by removing the singleton block $\{1\}$.
Speicher defines the functions
$\overline{A}(x) = 1 + \sum_{n \geq 0} a(n) \cdot x^{n+1} = 1 + x \cdot A(x)$
$\overline{B}(x) = 1 + \sum_{n \geq 0} b(n) \cdot x^{n+1} = 1 + x
\cdot B(x) = C(x)$.
Now we have
\begin{align*}
\overline{B}(x)
& =
1 + x \cdot B(x)
1 + x \cdot C(x) \cdot C^{*}(x)
1 + x \cdot C(x) \cdot A(x \cdot C(x)) \\
& =
1 + x \cdot \overline{B}(x) \cdot A(x \cdot \overline{B}(x))
\overline{A}(x \cdot \overline{B}(x)) ,
\end{align*}
which is Speicher's identity.
\label{remark_Speicher}
\end{remark}

In the next two subsections we mostly apply
in the special case when $a(k)=a^{*}(k)$
holds for all $k\geq 0$. In this special case we have
$A(x)=A^{*}(x)$ and that the weight
$\wt(\pi^{\prime})$ is obtained from $\wt(\pi)$ by
exchanging the variables $s$ and $t$. Sometimes we write
$C(s,t,x)$ and $C^{*}(s,t,x)$ instead of $C(x)$ and $C^{*}(x)$ to
indicate that the coefficients of these power series of $x$ are
polynomials of $s$ and~$t$. Due to the variable-swapping rule connecting
$\wt(\pi)$ and $\wt(\pi^{\prime})$, we have
\begin{align*}
& =
\end{align*}
when $a(k)=a^{*}(k)$ holds for all $k$.

\subsection{Cardinality and the M\"obius function}
\label{subsection_Cardinality}

We now apply the generating functions to obtain
the cardinality of the poset $\NC^{d}_{n}$
and its M\"obius function.

\begin{theorem}
\label{theorem_bigblocks}
The cardinality of the poset $\NC^{d}_{dk+1}$ is given by
\begin{align*}
\left| \NC^{d}_{dk+1} \right|
& =
\frac{2}{dk+2} \cdot \binom{dk+k+1}{k} .
\end{align*}
The number of noncrossing partitions in $\NC^{d}_{dk+1}$
that contains the singleton block $\{1\}$ is given by
\begin{align*}
\frac{1}{dk+1} \cdot \binom{dk+k}{k} .
\end{align*}
\end{theorem}
\begin{proof}
Set $a(k) = a^{*}(k) = s = t = 1$. Then the weight
$b(k)$ is the cardinality of $\NC^{d}_{dk+1}$.
Note that $A(x) = A^{*}(x) = 1/(1-x)$.
By symmetry $C(x) = C^{*}(x)$ and
simplifies to
$C(x) = 1 + x \cdot C(x)^{d+1}$.
This is a case of equation~\eqref{equation_algebraic_equation}
and hence equation~\eqref{equation_coefficient_of_the_generating_function}
\begin{align*}
& =
[x^{k}] B(x)
[x^{k}] C(x)^{2}
\frac{2}{dk+2} \cdot \binom{dk+k+1}{k} .
\end{align*}
Similarly, the number of partitions containing $\{1\}$ as
a singleton block is given by
$c(k) = [x^{k}] C(x)$ and again the result follows
\end{proof}

\begin{theorem}
\label{theorem_smallblocks}
The number of noncrossing partitions on $dk+1$ elements where
each block size is either $1$ or $d+1$
each block size of the dual partition is also either $1$ or $d+1$
is given by
\begin{align*}
\frac{2}{dk+2} \cdot \binom{dk+2}{k} .
\end{align*}
If we further assume that the partition contains
the singleton block $\{1\}$, the number reduces to
\begin{align*}
\frac{1}{dk+1} \cdot \binom{dk+1}{k} .
\end{align*}
\end{theorem}
\begin{proof}
In this case we use $A(x) = A^{*}(x) = 1 + x$ and $s = t = 1$.
By symmetry we have $C(x) = C^{*}(x)$
and this generating function satisfies
$C(x) = 1 + x \cdot C(x)^{d}$.
Again equation~\eqref{equation_coefficient_of_the_generating_function}
yields these two results.
\end{proof}

\begin{theorem}
The M\"obius function of the poset $\NC^{d}_{dk+1}$ is given by
\begin{align}
\mu( \NC^{d}_{dk+1} )
& =
(-1)^{k} \cdot \frac{1}{2dk-k+1} \cdot \binom{2dk}{k} .
\label{equation_Mobius}
\end{align}
\label{theorem_Mobius}
\end{theorem}
\begin{proof}
Let $a(k)$ be the quantity on the right hand-side of equation~\eqref{equation_Mobius}.
By Proposition~\ref{proposition_Cartesian_product} every interval of
factors into a product with terms of the form
$\NC^{d}_{dr+1}$ for $0 \leq r \leq k$,
and the M\"obius function is multiplicative $\mu(P \times Q) = \mu(P) \cdot \mu(Q)$,
it is enough to verify that
\begin{align*}
\sum_{\pi \in \NC^{d}_{dk+1}}
\prod_{B \in \pi} a\left(\frac{|B|-1}{d}\right)
& =
\delta_{k,0} ,
\end{align*}
where $\delta_{k,0}$ denotes the Kronecker delta.
We can express this sum using the weights and generating functions
by letting $a^{*}(k) = s = t = 1$. Then it is enough to show that
$B(x) = 1$.

Directly we have $A^{*}(x) = 1/(1-x)$.
Since the sequence
$(-1)^{k} \cdot a(k) = \frac{1}{2dk-k+1} \cdot \binom{2dk}{k}$
is described in~\eqref{equation_coefficient_of_the_generating_function},
its generating function
satisfies the algebraic equation~\eqref{equation_algebraic_equation}.
the generating function of $a(k)$ satisfies the equation
\begin{align}
A(x) + x \cdot A(x)^{2d} & = 1.
\label{equation_A(x)}
\end{align}
Introduce a new variable $y = x^{1/(2d-1)}$
such that $x = y^{2d-1}$ and $x \cdot y = y^{2d}$.
equation~\eqref{equation_A(x)} by $y$ to obtain
$y \cdot A(y^{2d-1}) + y^{2d} \cdot A(y^{2d-1})^{2d} = y$.
That is, the function $f(y) = y \cdot A(y^{2d-1})$ is
the compositional inverse of $g(y) = y + y^{2d}$.
Expanding $f(g(y)) = y$ yields
$(y + y^{2d}) \cdot A((y + y^{2d})^{2d-1}) = y$,
that is,
$A(y^{2d-1} \cdot (1 + y^{2d-1})^{2d-1}) = 1/(1 + y^{2d-1})$.
Returning to the variable $x = y^{2d-1}$ we have
\begin{align}
A(x \cdot (1+x)^{2d-1}) & = 1/(1 + x) .
\label{equation_A(x)_second}
\end{align}

Let the function $C(x)$ satisfy the equation
$C(x)^{d} - C(x)^{d-1} = x$ and $C(0) = 1$.
Furthermore, let $C^{*}(x) = 1/C(x)$.
We show that these two functions
satisfies the two equations in~\eqref{equation_C_and_C*}.
First we obtain
\begin{align*}
A^{*}(x \cdot C^{*}(x)^{d})
& =
\frac{1}{1 - x \cdot C^{*}(x)^{d}}
\frac{C(x)^{d}}{C(x)^{d} - x}
\frac{C(x)^{d}}{C(x)^{d-1}}
C(x) .
\end{align*}
Next, observe that
$x \cdot C(x)^{d} = (C(x)^{d} - C(x)^{d-1}) \cdot C(x)^{d} = (C(x) - 1) \cdot C(x)^{2d-1}$.
Hence we have
\begin{align*}
A(x \cdot C(x)^{d})
& =
A((C(x) - 1) \cdot C(x)^{2d-1})
C^{*}(x) ,
\end{align*}
where in the second step we used equation~\eqref{equation_A(x)_second}.
By the uniqueness of $C(x)$ and $C^{*}(x)$ the result follows.
\end{proof}

Note that in the classical case, that is, $d=1$,
the generating function $C(x)$ is given by $1+x$.
This fact is straightforward to observe combinatorially.

\subsection{The rank numbers}
\label{subsection_The_rank_numbers}

We now apply Theorem~\ref{theorem_generating_functions_C_and_C*}
in the case when $a(k) = a^{*}(k) = 1$ to obtain the rank numbers.
Since the noncrossing partition poset $\NC^{d}_{n+1}$ is self-dual
the rank numbers are palindromic.

\begin{theorem}
The number of partitions of rank $j$
in the noncrossing partition poset $\NC^{d}_{dk+1}$,
for $k = i+j \geq 1$, is given by
\begin{align}
\label{equation_F_coefficients}
\binomial{i+dj-1}{i-1} \cdot \binomial{di+j-1}{j-1}
d^{2} \cdot \binomial{i+dj-1}{i-2} \cdot \binomial{di+j-1}{j-2} \\
\nonumber + &
\binomial{i+dj-1}{i-1} \cdot \binomial{di+j-1}{j}
d^{2} \cdot \binomial{i+dj-1}{i-2} \cdot \binomial{di+j-1}{j-1} \\
\nonumber + &
\binomial{i+dj-1}{i} \cdot \binomial{di+j-1}{j-1}
d^{2} \cdot \binomial{i+dj-1}{i-1} \cdot \binomial{di+j-1}{j-2} .
\end{align}
Furthermore, the number of partitions of rank $j$
in the noncrossing partition poset $\NC^{d}_{dk+1}$
that contains $\{1\}$ as a singleton block
is given by
\begin{align}
\label{equation_G_coefficients_I}
\binomial{i+dj-1}{i-1} \cdot \binomial{di+j-1}{j}
d^{2} \cdot \binomial{i+dj-1}{i-2} \cdot \binomial{di+j-1}{j-1}  \\
\label{equation_G_coefficients_II}
= &
\frac{(i+dj)! \cdot (di+j-1)!}
{i! \cdot (di-1)! \cdot j! \cdot (dj+1)!} .
\end{align}
\label{theorem_rank_numbers}
\end{theorem}
\begin{proof}
We set $a(k) = a^{*}(k) = 1$
and our goal is to determine the coefficients of the power series $C(s,t,x)$ and $B(s,t,x)$.
We subtract the constant $1$ from the generating functions $C(s,t,x)$ and $C^{*}(s,t,x)$
and work with the generating functions
\begin{align*}
D(s,t,x) & = C(s,t,x) - 1, & D^{*}(s,t,x) & = C^{*}(s,t,x) - 1  .
\end{align*}
Rewrite the two equations in~\eqref{equation_C_and_C*},
recalling that $A(x) = A^{*}(x) = 1/(1-x)$, as
\begin{align*}
& =
sx \cdot (1+D) \cdot (1+D^{*})^{d} , &
& =
tx \cdot (1+D)^{d} \cdot (1+D^{*}) .
\end{align*}
Note that every monomial that occurs has the form $s^{i} t^{j} \cdot x^{i+j}$.
At this point we set $x=1$ since all the information is carried by the coefficients
of the monomials in the variables $s$ and $t$.
We apply Good's inversion formula, Theorem~\ref{theorem_Good}, using
$g_{1}(s,t) = (1+s) \cdot (1+t)^{d}$
$g_{2}(s,t) = (1+s)^{d} \cdot (1+t)$.
Let $M$ be the $2 \times 2$ matrix whose entries are given by
\begin{align*}
& =
g_{1}(s,t)^{i} - s \cdot \frac{\partial g_{1}}{\partial s} \cdot g_{1}(s,t)^{i-1}
& =
- t \cdot \frac{\partial g_{1}}{\partial t} \cdot g_{1}(s,t)^{i-1} \\
& =
(1+s)^{i} \cdot (1+t)^{di} - s \cdot (1+s)^{i-1} \cdot (1+t)^{di}
& =
- d \cdot t \cdot (1+s)^{i} \cdot (1+t)^{di-1} , \\
& =
(1+s)^{i-1} \cdot (1+t)^{di} , \\
& =
- d \cdot s \cdot (1+s)^{dj-1} \cdot (1+t)^{j} ,
& =
(1+s)^{dj} \cdot (1+t)^{j-1} .
\end{align*}
Note that the determinant is given by
\begin{align*}
\det(M)
& =
(1 - d^{2} \cdot st)
\cdot
(1+s)^{i+dj-1} \cdot (1+t)^{di+j-1}  .
\end{align*}
Applying Good's inversion formula we have for $(i,j) \neq (0,0)$ that
\begin{align}
\nonumber
[s^{i} t^{j}] D
& =
[s^{i-1} t^{j}] \det(M) \\
\nonumber
& =
[s^{i-1} t^{j}]
(1 - d^{2} \cdot st)
\cdot
(1+s)^{i+dj-1} \cdot (1+t)^{di+j-1} \\
& =
\label{equation_G_coefficient_as_a_difference}
\binomial{i+dj-1}{i-1} \cdot \binomial{di+j-1}{j}
d^{2} \cdot \binomial{i+dj-1}{i-2} \cdot \binomial{di+j-1}{j-1} \\
\nonumber
& =
\frac{(i+dj-1)! \cdot (di+j-1)!}
{(i-1)! \cdot (dj+1)! \cdot j! \cdot (di)!}
\cdot
\left(
(dj+1) \cdot di
d^{2} \cdot (i-1) \cdot j
\right) \\
\nonumber
& =
\frac{(i+dj-1)! \cdot (di+j-1)!}
{(i-1)! \cdot (dj+1)! \cdot j! \cdot (di)!}
\cdot d \cdot (i+dj) ,
\end{align}
which simplifies to equation~\eqref{equation_G_coefficients_II}.
Also note that~\eqref{equation_G_coefficient_as_a_difference}
is equation~\eqref{equation_G_coefficients_I}.
Similarly we have
\begin{align}
\label{equation_toward_F}
[s^{i} t^{j}] D \cdot D^{*}
& =
[s^{i-1} t^{j-1}] \det(M) \\
\nonumber
& =
\binomial{i+dj-1}{i-1} \cdot \binomial{di+j-1}{j-1}
d^{2} \cdot \binomial{i+dj-1}{i-2} \cdot \binomial{di+j-1}{j-2} .
\nonumber
\end{align}
Now expanding $B(s,t)$ in terms of $D$ and $D^{*}$ we have
\begin{align}
\label{equation_B_in_terms_of_D_and_D*}
[s^{i} t^{j}] B(s,t)
& =
[s^{i} t^{j}] C(s,t) \cdot C^{*}(s,t) \\
& =
\nonumber
[s^{i} t^{j}] (D+1) \cdot (D^{*}+1) \\
& =
\nonumber
[s^{i} t^{j}] D \cdot D^{*}
[s^{i} t^{j}] D
[s^{i} t^{j}] D^{*}.
\end{align}
Now by adding equations~\eqref{equation_G_coefficient_as_a_difference},
the symmetric version of~\eqref{equation_G_coefficient_as_a_difference}
equation~\eqref{equation_toward_F} we obtain
\end{proof}

\begin{theorem}
Let $k \geq 1$.
The number of noncrossing partitions in $\NC^{d}_{dk+1}$ such that
the partition only has blocks of size $1$ and $d+1$ and
the dual partition also only has blocks of size $1$ and $d+1$
of rank $i$ is given by
\begin{align*}
\binomial{dj}{i-1} \cdot \binomial{di}{j-1}
d^{2} \cdot \binomial{dj-1}{i-2} \cdot \binomial{di-1}{j-2} \\
+ &
\binomial{dj}{i-1} \cdot \binomial{di}{j}
d^{2} \cdot \binomial{dj-1}{i-2} \cdot \binomial{di-1}{j-1} \\
+ &
\binomial{dj}{i} \cdot \binomial{di}{j-1}
d^{2} \cdot \binomial{dj-1}{i-1} \cdot \binomial{di-1}{j-2} .
\end{align*}
\end{theorem}
\begin{proof}
This proof is similar to the proof of Theorem~\ref{theorem_rank_numbers}
and hence we highlight the differences.
Let $D(s,t,x) = C(s,t,x) - 1$ and $D^{*}(s,t,x) = C^{*}(s,t,x) - 1$.
Rewrite the two equations in~\eqref{equation_C_and_C*}
recalling that in this case we have $A(x) = A^{*}(x) = 1+x$, as
\begin{align*}
& =
sx \cdot (1+D^{*})^{d} , &
& =
tx \cdot (1+D)^{d} .
\end{align*}
Set $x=1$ and apply Good's inversion formula using
$g_{1}(s,t) = (1+t)^{d}$
$g_{2}(s,t) = (1+s)^{d}$.
Let $M$ be the matrix given by
\begin{align*}
& =
g_{1}(s,t)^{i} - s \cdot \frac{\partial g_{1}}{\partial s} \cdot g_{1}(s,t)^{i-1}
(1+t)^{di} ,
& =
- d \cdot t \cdot (1+t)^{di-1} , \\
& =
- s \cdot \frac{\partial g_{2}}{\partial s} \cdot g_{2}(s,t)^{j-1}
- d \cdot s \cdot (1+s)^{dj-1} ,
& =
(1+s)^{dj} .
\end{align*}
Its determinant is given by
\begin{align*}
\det(M)
& =
(1+s)^{dj} \cdot (1+t)^{di}
d^{2} \cdot st
\cdot
(1+s)^{dj-1} \cdot (1+t)^{di-1}  .
\end{align*}
Good's inversion formula now implies
\begin{align}
\nonumber
[s^{i} t^{j}] D
& =
[s^{i-1} t^{j}] \det(M)
\binomial{dj}{i-1} \cdot \binomial{di}{j}
d^{2} \cdot \binomial{dj-1}{i-2} \cdot \binomial{di-1}{j-1}
\nonumber
\end{align}
\begin{align}
\nonumber
[s^{i} t^{j}] D \cdot D^{*}
& =
[s^{i-1} t^{j-1}] \det(M)
\binomial{dj}{i-1} \cdot \binomial{di}{j-1}
d^{2} \cdot \binomial{dj-1}{i-2} \cdot \binomial{di-1}{j-2} .
\nonumber
\end{align}
As in equation~\eqref{equation_B_in_terms_of_D_and_D*}
we have for $(i,j) \neq (0,0)$ that
\begin{align*}
[s^{i} t^{j}] B(s,t)
& =
[s^{i} t^{j}] D \cdot D^{*}
[s^{i} t^{j}] D
[s^{i} t^{j}] D^{*}.
\end{align*}
Hence the result follows by adding the two previous identities and
the symmetric version for $[s^{i} t^{j}] D^{*}$.
\end{proof}

\section{The antipode of the poset $NC^{d}_{n}$}
\label{section_antipode}

Let ${\mathcal P}$ denote the linear span of all the isomorphism classes of all finite posets
with that has a minimal element $\hz$ and a maximal element $\ho$.
The vector space ${\mathcal P}$ forms a Hopf algebra. That is, there is
a product, a coproduct, a unit, a counit and an antipode.
For more details; see~[3, 18].
The antipode is described by the following expression due to
\begin{align}
& =
\sum_{k \geq 0}
\sum_{c}
\cdot
[x_{0},x_{1}] \cdot [x_{1},x_{2}] \cdots [x_{k-1},x_{k}] ,
\label{equation_Schmitt_antipode}
\end{align}
where the sum is over all chains
$c = \{\hz = x_{0} < x_{1} < \cdots < x_{k} = \ho\}$
taking $k$ steps.
Observe that this is a generalization of Philip Hall's
formula for the M\"obius function.
The disadvantage with the above sum is that it yields
an expression that may contain a lot of cancellations.

A {\em hypergraph $G$} on a vertex set ${\mathcal V}$
is a collection ${\mathcal E}$ of subsets of ${\mathcal V}$
such that the subsets $E \in {\mathcal E}$ have cardinality at least $2$.
The subsets in ${\mathcal E}$ are called edges.
A hypergraph is connected if for every pair of vertices $x$ and $y$ there is a
sequence of edges $E_{1}, E_{2}, \ldots, E_{k} \in {\mathcal E}$ such that
$x \in E_{1}$, $y \in E_{k}$ and the intersection
$E_{i} \cap E_{i+1}$ is nonempty for all $1 \leq i \leq k-1$.
A connected hypergraph is a hypertree if
$\sum_{E \in {\mathcal E}} (|E|-1) = |{\mathcal V}| - 1$.
Note that if all the edges have cardinality $2$ we have a tree.

Einziger~[8, 9]
proved the following result for the antipode of the noncrossing partition lattice.
A proof using a sign reversing involution was given in~[4].

\begin{theorem}[Einziger]
The antipode of the noncrossing partition lattice $\NC_{n}$ is given by the sum
\begin{align*}
& =
\sum_{T}
\cdot
\prod_{E \in T} \NC_{|E|} ,
\end{align*}
where $T$ ranges over all noncrossing hypertrees on the set $[n]$.
\end{theorem}

We now extend this result to the noncrossing partition poset $\NC^{d}_{n}$.

\begin{theorem}
Let $n$ and $d$ be positive integers such that $n \equiv 1 \bmod d$.
Then the antipode of the noncrossing partition poset $\NC^{d}_{n}$ is given by the sum
\begin{align*}
& =
\sum_{T}
\cdot
\prod_{E \in T} \NC^{d}_{|E|} ,
\end{align*}
where $T$ ranges over all noncrossing hypertrees on the set $[n]$
such that each edge $E$ of $T$ satisfies $|E| \equiv 1 \bmod d$.
\label{theorem_antipode}
\end{theorem}

Recall that
in subsection~\ref{subsection_The_noncrossing_partition_lattice}
for a block $B$ of a partition $\pi$ and
an adjacent block $C'$ in the dual partition $\pi'$, we defined the notion
$\gamma(B,C')$ to be the vertex of $B$ adjacent to the block $C'$
that is the most negative orientation from the block $B$'s perspective.

Next, for two noncrossing partitions~$\pi$ and~$\sigma$ in
in $\NC^{d}_{n}$ such that $\pi < \sigma$ define the
hypergraph $\varphi(\pi,\sigma)$ as follows.
For each block $C^{\prime}$ in the dual partition
and a maximal collection of blocks
$B_{1}, B_{2}, \ldots, B_{j}$ of~$\pi$, where $j \geq 2$,
which are adjacent to the block $C^{\prime}$
and are all contained in one block of the partition~$\sigma$, add
the edge
$\{\gamma(B_{1},C^{\prime}),\gamma(B_{2},C^{\prime}), \ldots, \gamma(B_{j},C^{\prime})\}$
to the hypergraph $\varphi(\pi,\sigma)$.
It is important to note that $j$ satisfies the congruence
$j \equiv 1 \bmod d$.

For a chain $c = \{\hz = \pi_{0} < \pi_{1} < \cdots < \pi_{r} = \ho\}$
in the noncrossing partition poset $\NC^{d}_{n}$
define the hypergraph $\varphi(c)$ to be the union
$\cup_{i=1}^{r} \varphi(\pi_{i-1},\pi_{i})$.

Similar to \cite[Lemma~3.3 and Corollary~3.5]{Ehrenborg_Happ}
we have the next result whose proof we omit.
\begin{lemma}
For a chain $c$ in the poset $\NC^{d}_{n}$
the isomorphism holds
\begin{align*}
\prod_{i=1}^{r} [\pi_{i-1},\pi_{i}]
& \cong
\prod_{E \in \varphi(c)} \NC^{d}_{|E|} .
\end{align*}
\label{lemma_Ehrenborg_Happ_Lemma_3.3_Corollary_3.5}
\end{lemma}
Finally, their Lemma~3.6 becomes:
\begin{lemma}
For a chain $c$ in the poset $\NC^{d}_{n}$
the hypergraph $\varphi(c)$ is a noncrossing hypertree where each edge
$E$ satisfies $|E| \equiv 1 \bmod d$.
\label{lemma_Ehrenborg_Happ_Lemma_3.6}
\end{lemma}
The only difference in the proof of this lemma is the factor of $d$
in the following chain of equalities:
\begin{align*}
\sum_{E \in \varphi(c)} (|E|-1)
d \cdot \sum_{E \in \varphi(c)} \rho\left(\NC^{d}_{|E|}\right)
d \cdot \sum_{i=1}^{r} \rho([\pi_{i-1},\pi_{i}])
%%d \cdot \sum_{i=1}^{r} (\rho(\pi_{i}) - \rho(\pi_{i-1}))
d k = n-1 .
\end{align*}
Finally, Proposition~4.3 in~[4] states:
\begin{proposition}[Ehrenborg--Happ]
For a noncrossing hypertree $H$ on $n$ elements with $r$ edges,
the following alternating sum holds:
\begin{align*}
\sum_{c \in \varphi^{-1}(H)} (-1)^{\ell(c)}
& =
(-1)^{r} .
\end{align*}
\label{proposition_fiber}
\end{proposition}

\begin{proof}[Proof of Theorem~\ref{theorem_antipode}.]
By combining the Schmitt expression for the antipode \eqref{equation_Schmitt_antipode}
and Proposition~\ref{proposition_fiber} the result follows.
\end{proof}

By combining Theorems~\ref{theorem_Mobius}
using Philip Hall's formula for the M\"obius function,
we obtain:

\begin{corollary}
Let $k$ and $d$ be nonnegative integers such that $d \geq 1$.
Then the following holds
\begin{align*}
(-1)^{k} \cdot \frac{1}{2dk-k+1} \cdot \binom{2dk}{k}
& =
\sum_{T} (-1)^{|T|} ,
\end{align*}
where $T$ ranges over all noncrossing hypertrees on the set $[dk+1]$
such that each edge $E$ of $T$ satisfies $|E| \equiv 1 \bmod d$.
\end{corollary}

\section{A tree representation of noncrossing partitions}
\label{section_A_tree_representation_of_noncrossing_partitions}

In this section we introduce a labeled tree representation of a
noncrossing partition which simultaneously represents the blocks of a
noncrossing partition and the blocks of its Kreweras dual. This
representation allows to present a combinatorial proof of some
of the statements stated in Section~\ref{section_Enumerative}.
representation is a variant of the ``dual tree representation''
discussed by Kortchemski and Marzouk~\cite[Section 2]{Kortchemski_Marzouk}
relying on a bijection introduced by Janson and
Stef\'ansson~[13]. In particular, the topological
structure and two-coloring of our trees is the same, the labeling and
the choice of the root are slightly different.

We begin with the description of a {\em labeled topological tree}
encoding a noncrossing partition. Recall that a {\em topological graph}
is a graph enriched with a fixed cyclic order of the incident edges
around each vertex.

\begin{figure}[ht]
% Angle between nodes.
\newcommand{\app}{360/11}
% Shift such that the node 1 on top.
\newcommand{\bpp}{90-360/11}
% Placing the elements
\newcommand{\gpp}[1]{({5*cos(\app*#1+\bpp)},{5*sin(\app*#1+\bpp)})}
% Placing the numbers
\newcommand{\hpp}[1]{({5.7*cos(\app*#1+\bpp)},{5.7*sin(\app*#1+\bpp)})}
% Node 1' shifted over.
\newcommand{\bqq}{90-360/11+360/22}
% Placing the dual elements
\newcommand{\gqq}[1]{({5*cos(\app*#1+\bqq)},{5*sin(\app*#1+\bqq)})}
% Placing the dual numbers
\newcommand{\hqq}[1]{({5.7*cos(\app*#1+\bqq)},{5.7*sin(\app*#1+\bqq)})}
% Radius of the nodes
\newcommand{\rrr}{0.24}
\begin{center}
\begin{tikzpicture}[scale = 0.40,inner sep=0.1mm]
% Draw the circle
\draw[-] (0,0) circle (5);

%%%% Draw the block {2,9,10}
\draw[fill=gray!50] \gpp{2} -- \gpp{9} -- \gpp{10} -- cycle;
%%%% Draw the block {4,5,6,7,8}
\draw[fill=gray!50] \gpp{4} -- \gpp{5} -- \gpp{6} -- \gpp{7} -- \gpp{8} -- cycle;
%%%% Draw the dual block {1',10',11'}
\draw[dashed,fill=gray!10] \gqq{1} -- \gqq{10} -- \gqq{11} -- cycle;
%%%% Draw the dual block {2',3',8'}
\draw[dashed,fill=gray!10] \gqq{2} -- \gqq{3} -- \gqq{8} -- cycle;

%%%% Placing the internal nodes
%%%% {2,9,10}
\node (blockone) at (2,1.8) {};
%%%% {4,5,6,7,8}
\node (blocktwo) at (-1,-3) {};
%%%% {1',10',11'}
\node (dualblockone) at (1.5,4.3) {};
%%%% {2',3',8'}
\node (dualblocktwo) at (-1,0.5) {};

%%%% Draw the edges
\draw[-,thick] \gpp{1} -- (dualblockone);
\draw[-,thick] (dualblockone) -- \gpp{11};
\draw[-,thick] (dualblockone) -- (blockone);
\draw[-,thick] (blockone) -- \gqq{9};
\draw[-,thick] (blockone) -- (dualblocktwo);
\draw[-,thick] (dualblocktwo) -- \gpp{3};
\draw[-,thick] (dualblocktwo) -- (blocktwo);
\draw[-,thick] (blocktwo) -- \gqq{4};
\draw[-,thick] (blocktwo) -- \gqq{5};
\draw[-,thick] (blocktwo) -- \gqq{6};
\draw[-,thick] (blocktwo) -- \gqq{7};

% Place the elements 1 through 11 and 1' through 11'.
\foreach \k in {1, 2, ..., 11}
\node at \hpp{\k} {$\k$};
\node at \hqq{\k} {$\k^{\prime}$};
\draw[-,fill] \gpp{\k} circle (0.1);
\draw[-,fill=white] \gqq{\k} circle (0.1);

%%%% Internal nodes (drawing them).
%%%% {2,9,10}
\draw[-,fill] (blockone) circle (\rrr);
%%%% {4,5,6,7,8}
\draw[-,fill] (blocktwo) circle (\rrr);
%%%% {1',10',11'}
\draw[-,fill=white] (dualblockone) circle (\rrr);
%%%% {2',3',8'}
\draw[-,fill=white] (dualblocktwo) circle (\rrr);

%%%% Nodes (leaves)
\draw[-,fill] \gpp{1} circle (\rrr);
\draw[-,fill] \gpp{3} circle (\rrr);
\draw[-,fill] \gpp{11} circle (\rrr);
\draw[-,fill=white] \gqq{4} circle (\rrr);
\draw[-,fill=white] \gqq{5} circle (\rrr);
\draw[-,fill=white] \gqq{6} circle (\rrr);
\draw[-,fill=white] \gqq{7} circle (\rrr);
\draw[-,fill=white] \gqq{9} circle (\rrr);
\end{tikzpicture}
\hspace*{20 mm}
\renewcommand{\rrr}{0.21}
\begin{tikzpicture}[scale = 0.45,inner sep=0.1mm]
% Place the nodes of the tree
\node (nodeone) at (0,5) {};
\node (nodetwo) at (0,3) {};
\node (nodethree) at (-1.5,1) {};
\node (nodefour) at (1.5,1) {};
\node (nodefive) at (-3.0,-1) {};
\node (nodesix) at (0,-1) {};
\node (nodeseven) at (-4.5,-3) {};
\node (nodeeight) at (-1.5,-3) {};
\node (nodenine) at (-4.5,-5) {};
\node (nodeten) at (-2.5,-5) {};
\node (nodeeleven) at (-0.5,-5) {};
\node (nodetwelve) at (1.5,-5) {};

% Draw the edges of the tree
\draw[-,thick] (nodeone) --node[right]{\small $1$} (nodetwo);
\draw[-,thick] (nodetwo) --node[anchor=south east]{\small $10$} (nodethree);
\draw[-,thick] (nodetwo) --node[anchor=south west]{\small $11$} (nodefour);
\draw[-,thick] (nodethree) --node[anchor=south east]{\small $2$} (nodefive);
\draw[-,thick] (nodethree) --node[anchor=south west]{\small $9$} (nodesix);
\draw[-,thick] (nodefive) --node[anchor=south east]{\small $3$} (nodeseven);
\draw[-,thick] (nodefive) --node[anchor=south west]{\small $8$} (nodeeight);
\draw[-,thick] (nodeeight) --node[anchor=south east]{\small $4$} (nodenine);
\draw[-,thick] (nodeeight) --node[anchor=15]{\small $5\:$} (nodeten);
\draw[-,thick] (nodeeight) --node[anchor=165]{\small $\:6$}  (nodeeleven);
\draw[-,thick] (nodeeight) --node[anchor=south west]{\small $7$}  (nodetwelve);

% Draw the nodes of the tree
\draw[-,fill] (nodeone) circle (\rrr);
\draw[-,fill=white] (nodetwo) circle (\rrr);
\draw[-,fill] (nodethree) circle (\rrr);
\draw[-,fill] (nodefour) circle (\rrr);
\draw[-,fill=white] (nodefive) circle (\rrr);
\draw[-,fill=white] (nodesix) circle (\rrr);
\draw[-,fill] (nodeseven) circle (\rrr);
\draw[-,fill] (nodeeight) circle (\rrr);
\draw[-,fill=white] (nodenine) circle (\rrr);
\draw[-,fill=white] (nodeten) circle (\rrr);
\draw[-,fill=white] (nodeeleven) circle (\rrr);
\draw[-,fill=white] (nodetwelve) circle (\rrr);
\end{tikzpicture}
\end{center}
\caption{A noncrossing partition and its plane tree representation}
\label{figure_nctree}
\end{figure}

In our definitions and proofs in this section we will consider the
circle representation of a noncrossing partition $\pi$ of
$\{1,2,\ldots,n\}$. On the left hand side
of Figure~\ref{figure_nctree} we see the circle representation of the
noncrossing partition $\pi=1|2,9,10|3|4,5,6,7,8|11$ that was introduced in
Figure~\ref{figure_example_noncrossing_partition}. The non-singleton
blocks of its Kreweras dual
partition $\pi'=1^{\prime},10^{\prime},11^{\prime}|2^{\prime},3^{\prime},8^{\prime}|4^{\prime}|5^{\prime}|6^{\prime}|7^{\prime}|9^{\prime}$
are polygons with dashed line boundaries.

Recall that we defined the notion of a block $B$ of noncrossing
partition $\pi$ and a block $C^{\prime}$ in the dual partition $\pi^{\prime}$
to be adjacent
if the block $B$ contains the two elements $i$ and $j$
and the dual block $C^{\prime}$ contains the two elements $i^{\prime}$
and $(j-1)^{\prime}$.
Note that $i$ and $j$ could be the same element
and similarly, $i^{\prime}$ and $(j-1)^{\prime}$
could also be the same element.
in subsection~\ref{subsection_The_noncrossing_partition_lattice}
we defined
to be the element in
the most in the negative orientation of $i$ and $j$ from the block~$B$'s
Observe that this is the element $i$
since it has $i$ in the block $B$ and
$i^{\prime}$ in the dual block $C^{\prime}$.

\begin{definition}
\label{definition_toptree}
The {\em labeled topological tree representing the noncrossing partition
$\pi\in\NC_{n}$} is a two vertex-colored tree with $n$ labeled
edges, defined as follows:
\begin{enumerate}
\item
The black nodes represent the blocks of $\pi$, the white
nodes represent the blocks of $\pi'$.
\item
If a block $B$ of $\pi$ and a block $C^{\prime}$ in the dual partition
are adjacent then the associated nodes are connected with an edge.
\item
Label the edge between the two nodes representing the two adjacent blocks
$B$ and $C^{\prime}$
with the canonical element $\gamma(B,C^{\prime})$.
\end{enumerate}
\end{definition}
The labeled topological tree associated to the noncrossing partition $\pi$ is
shown on the left hand side of Figure~\ref{figure_nctree} in such a way
that the vertex representing a non-singleton (dual) block is inside the polygon
representing the same block, whereas the vertices representing the
singleton (dual) blocks appear at correct place representing the
respective point $i$ ($i'$) on the circle. So far our representation is
essentially the same as the dual tree representation in~\cite[Section
2]{Kortchemski_Marzouk}, the only difference being that they draw the
edge labels near the respective black vertex. In particular our
labeled tree representation of the noncrossing partition
$1,3,5|2| 4| 6,7,11,12| 8| 9,10$, and of its Kreweras
dual $1',2'|3',4'|5',12'|6'|7',8',10'|9'$ (shown
in~\cite[Figure~2]{Kortchemski_Marzouk}) may be obtained from the
leftmost tree shown in~\cite[Figure~2]{Kortchemski_Marzouk} by shifting
all labels from the black end of the edges towards their middle. We
place the same labels in the middle of each vertex, and we think of the
label $i$ as the representative of $i$ in the block of $\pi$ associated
to the black end of the edge and as the representative of $i'$ in the
block of $\pi'$ associated to the white end of the same edge. This
slight shift of the labels allows us to use the same tree as the
simultaneous representative of a noncrossing partition $\pi$ and of its
dual $\pi'$.
\begin{remark}
Switching to the dual noncrossing partition is not just a matter of
inverting the colors as taking the Kreweras dual is not an involution:
the dual of the dual is obtained from the original noncrossing partition
by a cyclic relabeling of the elements of $\{1,2,\ldots,n\}$.
\end{remark}
As in~\cite[Section~2]{Kortchemski_Marzouk}, the following statement is
a direct consequence of this construction.
\begin{proposition}
\label{proposition_injective1}
The operation associating to each noncrossing partition its labeled
topological tree is injective.
\end{proposition}

Next we turn our labeled topological tree into a {\em (rooted) plane
tree}. This is where our choices differ
from~\cite[Section~2]{Kortchemski_Marzouk} substantially, as we define
the root and its leftmost child (called sometimes ``corner''
in~\cite[Section~2]{Kortchemski_Marzouk}) in a different fashion.

\begin{definition}
\label{definition_planetree}
Given a noncrossing partition $\pi\in\NC_{n}$ we define its {\em labeled
plane tree} as the drawing of its labeled topological tree in the
plane subject to the following rules.
\begin{enumerate}
\item The root of the tree represents the block $B_{1}$ of $\pi$ containing the element~$1$.
\item The leftmost child of each vertex is connected to it by the edge whose
label is the least among the labels of all edges connecting the vertex
to its children.
\end{enumerate}
\end{definition}
The labeled plane tree representation of the noncrossing partition shown
in Figure~\ref{figure_nctree} is on the right hand side of the figure.
In Definition~\ref{definition_planetree} we omit the mention of the
two-coloring of the vertices, as it is unnecessary: a tree is a
connected bipartite graph, assigning the color black to the root
determines the two-coloring uniquely. It is also direct that there is
exactly one way to draw each labeled topological tree as a plane tree,
subject to the rules stated in Definition~\ref{definition_planetree}. As a
consequence of Proposition~\ref{proposition_injective1} we obtain the following
\begin{corollary}
\label{corollary_injective2}
The operation associating to each noncrossing partition its labeled
plane tree is injective.
\end{corollary}

Next we show that keeping track of the labels is not necessary either,
as it may be uniquely reconstructed from the plane tree structure. The
following statement plays a key role in seeing this. Since the vertices
represent (dual) blocks of a noncrossing partition, by a slight abuse of
notation we will denote the label on the edge connecting the vertices
$u$ and $v$ also by $\gamma(u,v)$.
\begin{proposition}
\label{proposition_labelkey}
The labeling of a labeled plane tree representing a noncrossing
partition $\pi\in\NC_{n}$ has the following properties:
\begin{enumerate}
\item The labels on the edges are the elements of the set
$\{1,2,\ldots,n\}$ each appearing exactly once.
\item For each vertex in the tree, the labels on the edges connecting it
to its children increase left to right.
\item For each nonroot black (white) vertex $u$ in the tree the largest
(least) label appearing on an edge connecting $u$ to another vertex is
on the edge connecting $u$ to its parent in the tree.
\item For each vertex in the tree the set of all labels appearing in its
subtree form an interval $[i,j]=\{i,i+1,\ldots,j\}$ of consecutive
\item For each black (white) vertex in the tree, the least (largest)
label in its subtree labels the edge connecting the root of the
subtree to its leftmost (rightmost) child.
\item If $v_{1}$ and $v_{2}$ are children of the same vertex $v$ and $v_{1}$
is to the left from $v_{2}$ then $\gamma(v,v_{1})$ is smaller than the label
on any edge in the subtree of $v_{2}$, and $\gamma(v,v_{2})$ is greater
than the label on any edge in the subtree of $v_{1}$.
\end{enumerate}
\end{proposition}
\begin{proof}
In our proof we use the fact that each black vertex represents a block
$\{i_{1},i_{2},\ldots,i_{r}\}$ of a noncrossing partition, here we assume
$i_{1}<i_{2}<\cdots<i_{r}$. Similarly, each white vertex represents a dual
block $\{j_{1}',j_{2}',\ldots,j_{s}'\}$, here we assume

Property~(1) is a consequence of
Definition~\ref{definition_toptree}. It is also a consequence of this
definition that for each vertex in the tree, the labels on the edges
connecting it to its children follow the counterclockwise order. By
part~(2) of Definition~\ref{definition_planetree} each such cyclic list of
labels begins with its least element, this implies property~(2).
Next we prove part~(3). There is nothing to show for the root
vertex, which represents a block $\{i_{1},i_{2},\ldots,i_{r}\}$ satisfying $i_{1}=1$.
Any other black vertex represents a block $\{i_{1},i_{2},\ldots,i_{r}\}$
where $1<i_{1}<\cdots<i_{r}$. The edge connecting this vertex to its
parent crosses the side $\{i_{1},i_{r}\}$ because this line separates the
polygon from the point $1$. The label of this edge is $i_{r}$. The proof
of property~(3) for white vertices is similar. (Note that a
white vertex can never be the root of the entire tree). A white vertex
represents a dual block $\{j_{1}',j_{2}',\ldots,j_{s}'\}$, where
$j_{1}<j_{2}<\cdots<j_{s}$. Once again the edge
connecting this vertex to its parent crosses the side $\{j_{1}',i_{s}'\}$
because this line separates the polygon from the point $1$.

We prove the remaining parts~(4), (5) and (6) at once. Consider first a
nonroot black vertex $u$ representing the block  $\{i_{1},i_{2},\ldots,i_{r}\}$ where
$1<i_{1}<i_{2}<\cdots<i_{r}$. The set of labels appearing in its subtree is
$\{i_{1},i_{1}+1,\ldots,i_{r}-1\}$, because the points appearing on the
counterclockwise (half open) arc $[i_{1},i_{r})$ in our circle representation are
$i_{1},i_{1}',(i_{1}+1),(i_{1}+1)',\ldots,i_{r}-1, (i_{r}-1)'$. (Keep in mind that
$i_{r}$ is the label of the edge connecting our vertex to its parent.)
Furthermore, the set $\{i_{1},i_{2},\ldots,i_{r-1}\}$ is
used to label the edges connecting $u$ to its children. The labels
strictly between $i_{t}$ and $i_{t+1}$ (for $1\leq t\leq r-1$) are the
ones appearing in the subtree of the child $v$ of $u$ satisfying

For the root vertex representing the block  $\{i_{1},i_{2},\ldots,i_{r}\}$ where
$1=i_{1}<i_{2}<\cdots<i_{r}$, we need to amend slightly the above
reasoning. The subtree of the root is the entire tree, containing all
labels. The set $\{i_{1},i_{2},\ldots,i_{r}\}$ is
used to label the edges connecting the root to its children. The labels
strictly between $i_{t}$ and $i_{t+1}$ (for $1\leq t\leq r-1$) are the
ones appearing in the subtree of the child $v$ of $u$ satisfying
$\gamma(u,v)=i_{t}$, and the labels appearing in the subtree of the last
child of the root are the larger than all other labels.

For white vertices parts~(4), (5) and (6) may be shown in a similar
fashion. A white vertex represents a dual block
where $j_{1}<j_{2}<\cdots<j_{s}$ holds. The label of
the edge connecting our white vertex to its parent is $j_{1}'$, and the
labels appearing in the subtree of our vertex are
$\{j_{1}+1,\ldots,j_{s}\}$, because the points appearing on the
counterclockwise (half open) arc $(j_{1}',j_{s}']$ in our circle representation are
$j_{1}+1,(j_{1}+1)',(j_{1}+2),(j_{1}+2)',\ldots,j_{s},j_{s}'$. The set
$\{j_{2},j_{3}\ldots,j_{s}\}$ is used to label the edges connecting~$u$ to its
children. The labels
strictly between $j_{t-1}$ and $j_{t}$ for $2\leq t\leq s$ are the ones
appearing in the subtree of of the child $v$ of $u$ satisfying
\end{proof}

\begin{proposition}
\label{proposition_unique}
Given a plane tree with $n+1$ vertices, there is a unique way to label
its edges in such a way that the conditions stated in
Proposition~\ref{proposition_labelkey} are satisfied.
\end{proposition}
\begin{proof}
We prove by induction on the number of labels the following statement:
given a vertex, and the set of labels on the edges of its subtree, there
is at most one way to place the labels on the edges. The statement is
obviously true for the empty set, and we will prove the induction step
for the subtree of a black vertex $u$: the case of the subtree of a
white vertex is completely analogous.

Assume that the set of children of $u$ is $\{v_{1},\ldots,v_{k}\}$, listed in
the left to right order, and the label of the edge $\{v,v_{t}\}$ is $i_{t}$
for $t=1,2,\ldots,k$. By property~(2) we have $i_{1}<i_{2}<\cdots <i_{k}$ and
by property~(5) the label $i_{1}$ is the least element of the set of all
labels appearing in the subtree. By property (4) the set of all labels
in the subtree is a set of consecutive integers, the same holds for the
subtrees of $v_{1}$, $v_{2}$, \ldots and $v_{k}$. Combining properties~(3)
through (5) we obtain that the labels in the subtree of $u$ must be
listed in the following increasing order: $i_{1}$, labels in the subtree
of $v_{1}$, $i_{2}$, labels in the subtree of $v_{2}$, \ldots, $i_{k}$, labels
in the subtree of $v_{k}$. (Keep in mind that each $v_{t}$ is a white vertex.)
There is exactly one way to partition the set of labels and assign them
to the subtrees of each $v_{t}$ and to the edges connecting $u$ to its
\end{proof}
\begin{theorem}
\label{theorem_treerep}
The operation assigning to each noncrossing partition $\pi\in\NC_{n}$
its labeled plane tree is a bijection. Furthermore the range of this
operation is the set of all labeled plane trees on $n+1$ vertices that
satisfy the conditions stated in Proposition~\ref{proposition_labelkey}.
\end{theorem}
\begin{proof}
The operation is an injection by Proposition~\ref{proposition_injective1} and
Corollary~\ref{corollary_injective2}. By Proposition~\ref{proposition_unique}, no
information is lost either if we remove the labels of the edges. The
surjectivity now follows from the well known fact that the
noncrossing partitions of $\{1,2, \ldots, n\}$ and the plane
trees on $n+1$ vertices are enumerated by the same Catalan number.
\end{proof}

Since the degree of each vertex in our tree representations equals the
number of elements of the block it represents, we obtain the following
corollaries to Theorem~\ref{theorem_treerep}.

\begin{corollary}
The cardinality of the poset $\NC^{d}_{n}$ is
the number of rooted plane trees on $n+1$ vertices
such that the degree of each vertex is congruent to $1$ modulo $d$.
\end{corollary}
\begin{corollary}
\label{corollary_bigblocks}
The number of noncrossing partitions in $\NC^{d}_{dk+1}$
that contains the singleton block~$\{1\}$ is the number of rooted trees
on $dk+1$ vertices such that the number of children of each vertex is a
multiple of $d$.
\end{corollary}
Indeed, an element of $\NC^{d}_{dk+1}$ contains the singleton block
$\{1\}$ if and only if the root of the corresponding plane tree on
$dk+2$ vertices has a single child. Such plane trees correspond
bijectively to the plane trees on $dk+1$ vertices obtained by removing
the root and designating its only child as the new root. Using the same
idea we also obtain the following corollary.
\begin{corollary}
\label{corollary_smallblocks}
The number of noncrossing partitions in $\NC^{d}_{dk+1}$ having only
has blocks and dual blocks of size $1$ and $d+1$ and
containing the singleton block $\{1\}$ is the number of rooted $d$-ary
trees on $dk+1$ vertices.
\end{corollary}
Hence the second statement in Theorem~\ref{theorem_smallblocks} is a
direct consequence of the well-known fact that the number of rooted
$d$-ary trees is a Fuss--Catalan number. We may also derive the second
statement of Theorem~\ref{theorem_bigblocks} from
Corollary~\ref{corollary_bigblocks}  by proving the following
combinatorial statement.
\begin{proposition}
Let $d\geq 2$ and $k\geq 1$ be integers. Consider the set  ${\mathcal
T}_{d+1}^{(d+1)k+1}$ of plane rooted $(d+1)$-ary trees on $(d+1)k+1$
vertices and the map $\Psi$ assigning to each $T\in{\mathcal
T}_{d+1}^{(d+1)k+1}$ the plane tree obtained by contracting all edges
of $T$ that connect a vertex to its rightmost child. This map is a
bijection between ${\mathcal T}_{d+1}^{(d+1)k+1}$ and the set of all
plane rooted trees on $dk+1$ vertices which have the property that the
number of children of each vertex is a multiple of $d$.
\end{proposition}
\begin{proof}
An instance of the map $\Psi$ defined in the statement is shown in
\begin{figure}[ht]
\newcommand{\rrr}{0.08}
\newcommand{\shift}{5.5}
\begin{center}
\begin{tikzpicture}[scale = 1.3, inner sep=0.1mm]
%% First tree
% Place the nodes of the tree
\node (a) at (0,5) {};
\node (b) at (1,{5-1/3}) {};
\node (c) at (2,{5-2/3}) {};
\node (d) at (-1.5,4) {};
\node (e) at (-0.5,4) {};
\node (f) at (0.5,4) {};
\node (g) at (1.5,4) {};
\node (h) at (-0.5,{4-1/3}) {};
\node (i) at (-2,3) {};
\node (j) at (-1,3) {};
\node (k) at (-1,{3-1/3}) {};
\node (l) at (-2.5,2) {};
\node (m) at (-1.5,2) {};
\node (n) at (-0.5,{2-1/3}) {};
\node (o) at (0.5,{2-2/3}) {};
\node (p) at (-1.8,1) {};
\node (q) at (-1.2,1) {};
\node (r) at (-0.8,1) {};
\node (s) at (-0.2,1) {};

% Draw the edges of the tree
\draw[-,line width=2pt] (a) -- (b) -- (c);
\draw[-,thick] (a) -- (d);
\draw[-,thick] (a) -- (e);
\draw[-,thick] (a) -- (f);
\draw[-,thick] (a) -- (g);
\draw[-,line width=2pt] (d) -- (h);
\draw[-,thick] (d) -- (i);
\draw[-,thick] (d) -- (j);
\draw[-,line width=2pt] (i) -- (k);
\draw[-,thick] (i) -- (l);
\draw[-,thick] (i) -- (m);
\draw[-,line width=2pt] (m) -- (n) -- (o);
\draw[-,thick] (m) -- (p);
\draw[-,thick] (m) -- (q);
\draw[-,thick] (n) -- (r);
\draw[-,thick] (n) -- (s);
% Draw the nodes of the tree
\draw[fill=white] (a) circle (\rrr);
\draw[fill=white] (b) circle (\rrr);
\draw[fill=white] (c) circle (\rrr);
\draw[fill=black] (d) circle (\rrr);
\draw[fill=black] (e) circle (\rrr);
\draw[fill=black] (f) circle (\rrr);
\draw[fill=black] (g) circle (\rrr);
\draw[fill=black] (h) circle (\rrr);
\draw[fill=white] (i) circle (\rrr);
\draw[fill=white] (j) circle (\rrr);
\draw[fill=white] (k) circle (\rrr);
\draw[fill=black] (l) circle (\rrr);
\draw[fill=black] (m) circle (\rrr);
\draw[fill=black] (n) circle (\rrr);
\draw[fill=black] (o) circle (\rrr);
\draw[fill=white] (p) circle (\rrr);
\draw[fill=white] (q) circle (\rrr);
\draw[fill=white] (r) circle (\rrr);
\draw[fill=white] (s) circle (\rrr);

%%% The arrow
\draw[->,,line width=1.5pt] (2,3) --node[above]{\Large $\Psi$} (3,3);

%% Second tree
% Place the nodes of the tree
\node (aa) at ({\shift+0},5) {};
\node (dd) at ({\shift-1.5},4) {};
\node (ee) at ({\shift-0.5},4) {};
\node (ff) at ({\shift+0.5},4) {};
\node (gg) at ({\shift+1.5},4) {};
\node (ii) at ({\shift-2},3) {};
\node (jj) at ({\shift-1},3) {};
\node (ll) at ({\shift-2.5},2) {};
\node (mm) at ({\shift-1.5},2) {};
\node (pp) at ({\shift-3},1) {};
\node (qq) at ({\shift-2},1) {};
\node (rr) at ({\shift-1},1) {};
\node (ss) at ({\shift-0},1) {};

% Draw the edges of the tree
\draw[-,thick] (aa) -- (dd);
\draw[-,thick] (aa) -- (ee);
\draw[-,thick] (aa) -- (ff);
\draw[-,thick] (aa) -- (gg);
\draw[-,thick] (dd) -- (ii);
\draw[-,thick] (dd) -- (jj);
\draw[-,thick] (ii) -- (ll);
\draw[-,thick] (ii) -- (mm);
\draw[-,thick] (mm) -- (pp);
\draw[-,thick] (mm) -- (qq);
\draw[-,thick] (mm) -- (rr);
\draw[-,thick] (mm) -- (ss);
% Draw the nodes of the tree
\draw[fill=white] (aa) circle (\rrr);
\draw[fill=black] (dd) circle (\rrr);
\draw[fill=black] (ee) circle (\rrr);
\draw[fill=black] (ff) circle (\rrr);
\draw[fill=black] (gg) circle (\rrr);
\draw[fill=white] (ii) circle (\rrr);
\draw[fill=white] (jj) circle (\rrr);
\draw[fill=black] (ll) circle (\rrr);
\draw[fill=black] (mm) circle (\rrr);
\draw[fill=white] (pp) circle (\rrr);
\draw[fill=white] (qq) circle (\rrr);
\draw[fill=white] (rr) circle (\rrr);
\draw[fill=white] (ss) circle (\rrr);
\end{tikzpicture}
\end{center}
\caption{An example of the map $\Psi$.}
\label{figure_d-ary_tree}
\end{figure}
On the left hand side we see a ternary tree with $3\cdot 6+1=19$
vertices, hence we have $d=2$ and $k=6$. The number of
edges in a tree on $(d+1)k+1$ vertices is $(d+1)k$, counting each edge
(representing a parent-child relation) at the parent end we can see that
the number of nonleaf vertices in our $(d+1)$-ary tree must be
$k$. Contracting each nonleaf vertex with its rightmost child results in
a plane tree with $dk+1$ vertices. As a result of these contractions,
the parent ends of $d$-tuples of remaining edges get identified, hence
in the resulting plane tree the number of children of each vertex is a
multiple of $d$. The inverse of this map is easily constructed: if a
vertex $v$ has $dm$ children, we replace this vertex with a path $v_{0} -
v_{2}- \cdots -v_{m}$ where each $v_{i+1}$ is the rightmost child of $v_{i}$
for $i=0,1,\ldots,m-1$. The leftmost $d$ children of $v$ become the children of
$v_{0}$, the next $d$ of $v_{1}$, and so on, $v_{m}$ will become a leaf. If
the parent of $v$ is $u$ in the $(d+1)$-ary tree then the appropriate
copy of $u$ becomes the parent of $v_{0}$ in the image (keep in mind that
the parent of $v_{j}$ is $v_{j-1}$ for $j\geq 1$).
\end{proof}
\begin{remark}
The second statements in Theorems~\ref{theorem_bigblocks} and
\ref{theorem_smallblocks} are about noncrossing partitions which
correspond to plane trees in which the root has a single child. We
removed the leaf root and designated its only child to be the new
root. As a consequence, the root of the tree on the right hand side of
Figure~\ref{figure_d-ary_tree} represents a dual block, we color it white. The
two-coloring on the vertices on the right hand side is the only
proper two-coloring of the vertices in which the root is white. On the
left hand side we assigned to each vertex the color of its image. The
resulting two-coloring is not proper: each nonleaf vertex has the same
color as its rightmost child. The bijection exists only at the level of
plane trees, but it does not preserve the two-coloring of their
\end{remark}

\begin{remark}
Proposition~6.2.1 in~[26]
presents six classes of objects that are in bijection with each other.
See also the historical remarks in the Notes in~\cite[Chapter~6]{Stanley_EC2}.
We add a seventh class to this collection.
Let $S$ be a subset of the positive integers $\Ppp$
and let $n$ and $m$ be two positive integers.
The set of noncrossing partitions $\pi$ in the set $\NC_{n}$ such that
for all blocks $B$ of $\pi$ and the blocks $C^{\prime}$ of~$\pi^{\prime}$
the block sizes belongs
to the set $\{1\} \cup (S+1)$,
the singleton block $\{1\}$ belongs to the partition $\pi$
there are $m+1$ singleton blocks total among the two
partitions $\pi$ and the dual $\pi^{\prime}$.
For instance in the case $S = \{2,3\}$, $n=6$ and $m=4$, the noncrossing partition $1|2|3,4,5,6$
corresponds to the tree in~\cite[Proposition~6.2.1, part~(i)]{Stanley_EC2}.
\end{remark}

\section{The number of maximal chains in $NC^{d}_{n}$}
\label{section_maximal_chains}

We now turn our attention to the number of maximal chains in our poset.
Note that $m(P \times Q) = \binom{\rho(P) + \rho(Q)}{\rho(P)} \cdot m(P) \cdot m(Q)$
for two graded posets $P$ and $Q$,
where $m$ denotes the number of maximal chains.
More generally, for graded posets $P_{1}, \ldots, P_{e}$ we have
\begin{align}
\label{chains_product}
m(P_{1} \times \cdots \times P_{e})
& =
\binom{\rho(P_{1}) + \cdots + \rho(P_{e})}{\rho(P_{1}), \ldots, \rho(P_{e})}
\cdot m(P_{1}) \cdots m(P_{e}) .
\end{align}

\begin{theorem}
The number of maximal chains in $NC^{d}_{n}$ is $n^{k-1}$ where $n = dk+1$.
\label{theorem_maximal_chains}
\end{theorem}

Before proving this theorem, let $A_{k}(x)$ and $s_{k}(x)$ be the two polynomial
\begin{align*}
A_{k}(x) & = x \cdot (x+dk)^{k-1} ,
s_{k}(x) & = (x+dk)^{k} ;
\end{align*}
The first sequence is formed by the Abel polynomials which satisfy ``the binomial theorem''
\begin{align*}
A_{k}(x+y) = \sum_{j=0}^{k} \binom{k}{j} \cdot A_{j}(x) \cdot A_{k-j}(y).
\end{align*}
The corresponding multinomial theorem is
\begin{align*}
& =
\sum_{\vec{j}} \binom{k}{\vec{j}} \cdot A_{j_{1}}(y_{1}) \cdots A_{j_{d}}(y_{d})
\end{align*}
where the multi-index $\vec{j} = (j_{1}, \ldots, j_{d})$
ranges over all $d$-tuples of nonnegative integers
satisfying $j_{1} + \cdots + j_{d} = k$.
The second sequence $s_{k}(x)$ is a Sheffer sequence with respect to the Abel polynomials,
that is,
\begin{align*}
s_{k}(x+y) = \sum_{j=0}^{k} \binom{k}{j} \cdot s_{j}(x) \cdot A_{k-j}(y).
\end{align*}
By expanding the last term, we have
\begin{align}
& =
\sum_{\vec{j}} \binom{k}{\vec{j}} \cdot s_{j_{0}}(x) \cdot A_{j_{1}}(y_{1}) \cdots A_{j_{d}}(y_{d})
\label{equation_big_convolution}
\end{align}
where $\vec{j} = (j_{0}, \ldots, j_{d})$ and $j_{0} + \cdots + j_{d} = k$.

\begin{proof}[Proof of Theorem~\ref{theorem_maximal_chains}]
The proof is by strong induction on $k$, the rank of the poset $\NC^{d}_{n}$.
The result is directly true for $k=0$ and $k=1$.
Assume that it is true for all posets $\NC^{d}_{n}$ of rank at most~$k$
and we consider the case $n = d(k+1)+1$,
that is, the poset of rank $k+1$.
The first step of in selecting a maximal chain is to select
an element $\pi$ of rank~$1$, that is, to pick
a $(d+1)$-block $B = \{i_{1} < i_{2} < \cdots < i_{d+1}\}$.
By Proposition~\ref{proposition_characterization} it is necessary and
sufficient that all the consecutive differences $i_{r+1} - i_{r}$ satisfy
the congruence
$i_{r+1} - i_{r} \equiv 1 \bmod d$.
Hence for $1 \leq r \leq d$ let $j_{r}$ be given by
$d j_{r} + 1 = i_{r+1} - i_{r}$.
Finally let $j_{0}$ be given by wrap around formula
$d j_{0} + 1 = i_{1} - i_{d+1} + n$.
Note that all the $j_{r}$'s are nonnegative integers
and their sum is given by
\begin{align*}
j_{0} + j_{1} + \cdots + j_{d}
& =
\frac{i_{1} - i_{d+1} + n - 1}{d}
\frac{i_{2} - i_{1} - 1}{d}
\cdots
\frac{i_{d+1} - i_{d} - 1}{d}
\end{align*}
The vector $\vec{j} = (j_{0}, j_{1}, \ldots, j_{d})$
does not determine the block $B$, as
there are $dj_{0}+1$ ways to choose the element $i_{1}$.
Hence there are
$dj_{0}+1$ possible blocks $B$ that yield the same vector~$\vec{j}$.
Next we continue choosing a maximal chain in the interval
\begin{align*}
\cong
\NC^{d}_{dj_{0} + 1}
\times
\NC^{d}_{dj_{1} + 1}
\times
\cdots
\times
\NC^{d}_{dj_{d} + 1} .
\end{align*}
By our strong induction hypothesis and by \eqref{chains_product} the
number of maximal chains is given by
\begin{align*}
\sum_{\vec{j}} (dj_{0}+1) \cdot \binom{k}{\vec{j}} \cdot
(dj_{0}+1)^{j_{0}-1} \cdot (dj_{1}+1)^{j_{1}-1} \cdots (dj_{d}+1)^{j_{d}-1} ,
\end{align*}
where $\vec{j}$ ranges over all $(d+1)$-tuples
of nonnegative integers such that
$j_{0} + j_{1} + \cdots + j_{d} = k$.
But this sum is a special case of
when setting $x = y_{1} = \cdots = y_{d} = 1$
and hence it is given by $(d(k+1)+1)^{k}$,
completing the strong induction.
\end{proof}

\section{Edge labeling of the poset $NC^{d}_{n}$}
\label{section_Edge_labeling_of_the_poset}

We define an edge labeling of the noncrossing partition poset $\NC^{d}_{n}$ as follows.
Let $\pi \coveredby \sigma$ be a cover relation is the poset $\NC^{d}_{n}$.
By Corollary~\ref{corollary_cover_relation}
there are $d+1$ blocks of $\pi$ that are joined to form a block of $\sigma$.
Let us denote the joined blocks by $B_{1}, B_{2},\ldots, B_{d+1}$
and assume that the inequalities $\min(B_{1}) < \min(B_{2}) < \cdots < \min(B_{d+1})$ hold.
Then let the edge label $\lambda(\pi,\sigma)$ be given by
\begin{align*}
\lambda(\pi,\sigma)
& =
\max(\{i \in B_{1} : i < \min(B_{2})\}) .
\end{align*}
This edge labeling generalizes the edge labeling of $\NC_{n}$ introduced
by Stanley~[25].
For a maximal chain
${\bf m} = \{\hz = \pi_{0} \coveredby \pi_{1} \coveredby \cdots  \coveredby \pi_{k} = \ho\}$
in the poset $\NC^{d}_{n}$
define the labeling of the chain ${\bf m}$ to be
\begin{align*}
\lambda({\bf m})
& =
\lambda(\pi_{1},\pi_{2}),
\ldots,
\lambda(\pi_{k-1},\pi_{k})) .
\end{align*}

Define a {\em $d$-parking function} to be a list
$(a_{1}, a_{2}, \ldots, a_{k})$
of positive integers such that
when the list is ordered
$(a_{(1)} \leq a_{(2)} \leq \cdots \leq a_{(k)})$,
it satisfies the inequality
$a_{(i)} \leq d \cdot (i-1) + 1$.
This definition is a shift from the definitions occurring in the two papers~[24, 29],
where the entries are nonnegative integers.

The purpose of this section is to prove the following theorem.
\begin{theorem}
The map of sending a maximal chain ${\bf m}$ of $\NC^{d}_{dk+1}$
to its list of labels $\lambda({\bf m})$
is a bijection between all
maximal chains of $\NC^{d}_{dk+1}$
and all $d$-parking functions of length $k$.
\label{theorem_list_of_labels_bijection}
\end{theorem}

The proof of this theorem is by Lemmas~\ref{lemma_d-parking_function}

\begin{lemma}
The list of labels $\lambda({\bf m})$
of a maximal chain ${\bf m}$ in $\NC^{d}_{n}$
is a $d$-parking function.
\label{lemma_d-parking_function}
\end{lemma}
\begin{proof}
Let $R$ be a subset of $[n] \times [n]$ defined by
$(\lambda_{i},h) \in R$ if and only if
$\lambda_{i} = \lambda(\pi_{i},\pi_{i+1})$
and $h \in \{\min(B_{2}), \min(B_{3}), \ldots, \min(B_{d+1})\}$
and $B_{1}$ through $B _{d+1}$ are the blocks
that are joined in the cover relation
$\pi_{i} \coveredby \pi_{i+1}$
ordered by
$\min(B_{1}) < \min(B_{2}) < \cdots < \min(B_{d+1})$.
Observe that if $(\lambda_{i},h), (\lambda_{j},h) \in R$
then $i = j$ since $h$ can only once be
the minimal element of a block being joined to another block
with an even smaller minimal element.
Also note that $(\lambda_{i},h) \in R$ implies the inequality $\lambda_{i} < h$.

Assume now that the list
$\lambda({\bf m})$
has $r$ elements $\ell_{1}$ through $\ell_{r}$
that are greater than or equal to $s$.
Then we have the following block of size $d \cdot r$:
\begin{align*}
\{h \:\: : \:\: \exists i \: (\ell_{i},h) \in R\} \subseteq \{s+1, s+2, \ldots, n\} = [n] - [s].
\end{align*}
Hence we have the inequality $d \cdot r \leq n-s = dk+1-s$.
In other words, $r$ is bounded above by $k - \lceil (s-1)/d\rceil$.
This bound is equivalent to the definition of a $d$-parking function.
\end{proof}

\begin{lemma}
Let ${\bf m} = \{\hz = \pi_{0} \coveredby \pi_{1} \coveredby \cdots \coveredby \pi_{k} = \ho\}$
be a maximal chain in $\NC^{d}_{dk+1}$
let $\lambda({\bf m}) = (a_{1},a_{2}, \ldots, a_{k})$.
Let $r$ be the largest label occurring among these labels,
that is, $r = \max(a_{1}, a_{2}, \ldots, a_{k})$.
Furthermore, let $s$ be the last position this label occurs, that is,
$s = \max(\{i : a_{i} = r\})$.
Then the partition $\pi_{s-1}$ contains the singleton blocks
$\{r+1\}, \{r+2\}, \ldots, \{r+d\}$.
\label{lemma_d_singleton_blocks}
\end{lemma}
\begin{proof}
We claim that for $0 \leq e \leq d$ that
the partition $\pi_{s-1}$ contains the singleton blocks
$\{r+1\}, \{r+2\}, \ldots, \{r+e\}$.
We prove this by induction on $e$.
The basis case is $e=0$ which is directly true.

Assume now that the statement is true for $0 \leq e \leq d-1$ and
we prove it for $e+1$.
Let $B$ be the block of $\pi_{s-1}$ that contains the element $r+e+1$.
We claim that the block $B$ does not contain the element $r$.
If $e=0$ note that $\{r,r+1\} \subseteq B$ contradicts that
$\lambda(\pi_{s-1},\pi_{s}) = r$.
If $e \geq 1$
then we have a block in the dual partition whose cardinality lies strictly
between $1$ and $d+1$, which leads to a contradiction.
Hence we may assume that $r$ and $r+e+1$ lie in different blocks,
proving the claim.
If $r+e+1$ is the smallest element in the block~$B$, then this
contradicts that the largest label of the maximal chain is $r$.
Hence assume there is an element $t$ such that $1 \leq t < r$ in the block~$B$.
Let $B_{1}$ be the block of $\pi_{s-1}$ that contains the element $r$.
Since $\lambda(\pi_{s-1},\pi_{s}) = r$ we know that $B_{1}$ is
joined with $d$ other blocks $B_{2}$ through $B_{d+1}$
to obtain the partition $\pi_{s}$.
These other blocks must have their minimal elements greater than $r$.
By the noncrossing property, the only such blocks are
the singletons $\{r+1\}$ through $\{r+e\}$. But there are fewer than $d$
of these blocks. Hence there is no such element $t$ and we conclude
that the element $r+e+1$ forms a singleton block, proving the induction step.
\end{proof}

\begin{lemma}
With the same notation as in
the partition $\pi_{s}$ is obtained from
the partition $\pi_{s-1}$
by joining the block $B_{1}$ containing the element $r$
with the $d$ singleton blocks
$\{r+1\}$ through $\{r+d\}$.
\label{lemma_joining_with_the_d_singleton_blocks}
\end{lemma}
\begin{proof}
Since $\lambda(\pi_{s-1},\pi_{s}) = r$, the block $B_{1}$ is joined
by $d$ blocks whose elements are all greater than~$r$.
Assume that $h$ of these blocks are from the singleton blocks
$\{r+1\}$ through $\{r+d\}$.
We would to establish that $h=d$.
If $1 \leq h \leq d-1$ then the dual partition of $\pi_{s}$ has
a block of size strictly between $2$ and $d$, yielding a contradiction.
Hence the case $h=0$ remains.
Let $j$ be the next smallest element in the the block of $\pi_{s}$ that contains $r$.
That is, $j$ is strictly greater than $r+d$.
By the noncrossing property, what happens to the elements $r+1$ through $r+j-1$
is independent of what happens outside this interval.
At some point further up the maximal chain the block containing the element $r+1$
must join the block containing the element $r$. This yields a label of $r$ in the maximal
chain, contradicting that $s$ was chosen to be maximal.
Hence $h=d$ and the lemma follows.
\end{proof}

\begin{lemma}
Given a $d$-parking function $\vec{a} = (a_{1}, a_{2}, \ldots, a_{k})$
we can reconstruct a maximal chain ${\bf m}$ in $\NC^{d}_{dk+1}$ such that
$\lambda({\bf m}) = \vec{a}$.
\label{lemma_reconstructing_maximal_chain}
\end{lemma}
\begin{proof}
We proceed by induction on $k$. The base case is $k=0$ which is direct.
As in Lemma~\ref{lemma_d_singleton_blocks}
let $r =\max(a_{1}, a_{2}, \ldots, a_{k})$ and $s = \max(\{i : a_{i} = r\})$.
Observe that
\begin{align*}
\vec{b} & = (b_{1}, b_{2}, \ldots, b_{k-1}) = (a_{1}, a_{2}, \ldots, a_{s-1}, a_{s+1}, \ldots, a_{k})
\end{align*}
is a $d$-parking function.
By induction we have a maximal chain
${\bf n} = \{\hz = \sigma_{0} \coveredby \sigma_{1} \coveredby \cdots \coveredby \sigma_{k-1} = \ho\}$
in $\NC^{d}_{d(k-1)+1}$
such that
$\lambda({\bf n}) = \vec{b}$.
Let $f : [d(k-1)+1] \longrightarrow[dk+1]$
be the following relabeling function: we set
\begin{align}
& =
\begin{cases}
j     & \text{ if } 1    \leq j \leq r, \\
j+d & \text{ if } r+1 \leq j \leq d(k-1)+1.
\end{cases}
\label{equation_relabeling_function}
\end{align}
Define the maximal chain
${\bf m} = \{\hz = \pi_{0} \coveredby \pi_{1} \coveredby \cdots \coveredby \pi_{k} = \ho\}$
\begin{align*}
\pi_{i}
& =
\{f(B) \: : \: B \in \sigma_{i}\} \cup \{\{r+1\}, \ldots, \{r+d\}\}
\end{align*}
for $0 \leq i \leq s-1$
\begin{align*}
\pi_{i}
& =
\{f(B) \: : \: r \notin B \in \sigma_{i-1}\}
\cup
\{f(B) \cup \{r+1, \ldots, r+d\} \: : \: r \in B \in \sigma_{i-1}\}
\end{align*}
for $s \leq i \leq k$.
Note that the relabeling function $f$ opens up for an interval of $d$ new elements,
that is, $r+1$ through $r+d$.
Let $a$ and $b$ be two elements in the cyclic order on $[d(k-1)+1]$.
Then the number elements between $a$ and $b$ in the cyclic order is congruent to the
number of elements between $f(a)$ and $f(b)$ in the cyclic order on
$[dk+1]$ modulo $d$.
Hence by Proposition~\ref{proposition_characterization}
we know that the partition $\pi_{i}$ belongs to the poset $\NC^{d}_{dk+1}$ for all $i$.
We also obtain $\lambda({\bf m}) = \vec{a}$.
\end{proof}

Combining Lemmas~\ref{lemma_d_singleton_blocks}
we have proven the next result.
\begin{lemma}
For two maximal chains ${\bf m}$ and ${\bf m}^{\prime}$
in the noncrossing partition poset $\NC^{d}_{dk+1}$
the equality $\lambda({\bf m}) = \lambda({\bf m}^{\prime})$
implies ${\bf m} = {\bf m}^{\prime}$.
\label{lemma_lambda_injective}
\end{lemma}

Observe now that Lemmas~\ref{lemma_d-parking_function}
prove Theorem~\ref{theorem_list_of_labels_bijection}.
Next we show that the order complex of the poset $\NC^{d}_{n}$
is shellable.

\begin{proposition}
The labeling
$\lambda^{*}(\pi,\sigma) = |\pi| - \lambda(\pi,\sigma)$
is an $EL$-labeling of the noncrossing partition poset~$\NC^{d}_{n}$.
\label{proposition_EL}
\end{proposition}
\begin{proof}
We first show that the poset $\NC^{d}_{n}$ has a unique rising
chain. Consider a rising maximal chain
\begin{align*}
{\bf m} & = \{\hz = \pi_{0} \coveredby \pi_{1} \coveredby \cdots \coveredby \pi_{k} = \ho\} .
\end{align*}
Since ${\bf m}$ is a maximal chain we have
$|\pi_{i}|=|\pi_{i+1}|+d$ for $0 \leq i \leq k-1$
using Lemma~\ref{lemma_graded_and_rank_function}.
Hence the rising condition
$\lambda^{*}(\pi_{i-1},\pi_{i}) \leq \lambda^{*}(\pi_{i},\pi_{i+1})$
$\lambda(\pi_{i-1},\pi_{i}) \geq \lambda(\pi_{i},\pi_{i+1}) + d$.
As a consequence the $d$-parking function
$\vec{a} = (a_{1}, a_{2}, \ldots, a_{k})$ associated to ${\bf m}$ must satisfy
\begin{align*}
(a_{1}, a_{2}, \ldots, a_{k}) & \geq ((k-1)d+1, (k-2)d+1, \ldots,d+1, 1)
\end{align*}
coordinate-wise. Rearranging the entries of $\vec{a}$ into increasing
order, the resulting vector satisfies
\begin{align*}
(a_{(1)}, a_{(2)}, \ldots, a_{(k)}) & \geq (1, d+1,\ldots, (k-1)d+1)
\end{align*}
By the definition of a $d$-parking function
the above lower bound for $\vec{a}$ is also an upper bound.
That is, equality holds.
Hence the only rising chain ${\bf m}$ is the one
associated to the $d$-parking function
$((k-1)d+1, (k-2)d+1, \ldots,d+1, 1)$.

Next we show that the unique rising chain of $\NC^{d}_{n}$
described above is also lexicographically first. Consider any other
maximal chain
${\bf n} = \{\hz = \sigma_{0} \coveredby \sigma_{1} \coveredby \cdots \coveredby \sigma_{k} = \ho\}$
associated to the $d$-parking function $\vec{b} = (b_{1}, b_{2}, \ldots,
b_{k})$. Let $i$ be the least index such that $a_{i}\neq b_{i}$
holds. As a consequence of $a_{1}=b_{1}$, $a_{2}=b_{2}$, \ldots,
$a_{i-1}=b_{i-1}$, the first $i-1$ coordinates of $\vec{b}$ are also its
$i-1$ largest coordinates, and $b_{i}$ must satisfy $b_{i}\leq
(k-i+1)d$. Hence
$\lambda^{*}(\sigma_{i},\sigma_{i+1})>\lambda^{*}(\pi_{i},\pi_{i+1})$ must
be satisfied, while
$\lambda^{*}(\sigma_{j},\sigma_{j+1})=\lambda^{*}(\pi_{j},\pi_{j+1})$ holds
for all $j<i$. Therefore ${\bf m}$ precedes ${\bf n}$ in the
lexicographic order.

As noted by Stanley~[25] about the $d=1$ case, the statement
is easily generalized to an arbitrary interval of $\NC^{d}_{n}$ using
the fact that any such interval is a direct product of smaller copies of
\end{proof}

\begin{corollary}
The number of $d$-parking functions $(a_{1}, a_{2}, \ldots, a_{k})$
such that $a_{i} \leq a_{i+1} + d-1$ for all indices $i$ is given by
\label{corollary_falling_chains}
\end{corollary}
\begin{proof}
This result follows from the formula for the M\"obius function of the
poset $\NC^{d}_{dk+1}$ stated in Theorem~\ref{theorem_Mobius}
and Proposition~\ref{proposition_EL}.
Recall that the M\"obius function times the sign $(-1)^{k}$ enumerates
the number of falling chains.
\end{proof}

\section{A tree representation of the maximal chains in $\NC^{d}_{n}$}
\label{section_tree_representation}

Parsing a maximal chain of $\NC^{d}_{dk+1}$ amounts to describing a process
each step of which consists of merging $d+1$ blocks of a partition. In this
section we describe a tree representation which offers a visual record
of this process.

\begin{definition}
A {\em $d$-parking tree} is a labeled rooted plane tree on $n=dk+1$ vertices, such that
the number of children of each vertex is a multiple of $d$ and the
labeling satisfies the following conditions:
\begin{enumerate}
\item The label of the root is $\infty$.
\item The label of any other vertex is of the form $i_{j}$ where $i\in
\{1,2,\ldots,k\}$ and $j\in \{1,2,\ldots,d\}$.
\item For each fixed $i$, the vertices labeled $i_{1},\ldots,i_{d}$ are
consecutive labels in the left-to-right order of the same parent.
\item Each $i\in \{1,2,\ldots,k\}$ is only used to label one $d$-element
set of siblings.
\item If $i_{j}$ and $i'_{j'}$ are children of the same vertex and $i<i'$
holds then the vertex labeled $i_{j}$ is to the {\em right} of the vertex
labeled $i'_{j'}$.
\end{enumerate}
\end{definition}

Note that for $d=1$ our definition yields a labeled rooted plane tree
with no restriction on the degrees of the vertices.
A $2$-parking tree is shown on the left hand side of
Figure~\ref{figure_p_tree}. We consider $d$-parking trees as labeled
trees with {\em distinct vertices}. To identify the vertices in the
tree, in this paper we rely on the {\em depth-first search ordering
using the interval $[1,n]$}.
For a tree $T$ and a vertex $u$ in the tree~$T$, let $T(u)$ be the subtree
that has the node~$u$ as a root, that is, $T(u)$ consists of all
vertices that are descendants of $u$.

\begin{definition}
Given a plane tree $T$ on $n$ vertices and a positive integer $a$, the
{\em depth-first search ordering of $T$ using the interval $[a,a+n-1]$}
is defined by the following procedure:
\begin{itemize}
\item[(1)] We label the root $r$ of the tree $T$ with the number $a$,
that is, we set $\omega(r) = a$.
\item[(2)] Suppose $r_{1},r_{2},\ldots,r_{s}$ are the children of the root~$r$ in
the left-to-right order and let $T_{i}$ be the subtree~$T(r_{i})$ for
$i=1,2,\ldots,s$. We label each subtree $T_{i}$ recursively with
depth-first search ordering using the
interval $[a+|T_{1}|+\cdots+|T_{i-1}|+1,a+|T_{1}|+\cdots+|T_{i}|]$.
\end{itemize}
\end{definition}

The right hand side of Figure~\ref{figure_p_tree}
shows the {\em depth-first search ordering} of the vertices.
\begin{remark}
{\em Essentially the same $d$-parking trees (the mirror images of the
present ones) were also defined
in~\cite[Section~6]{Hetyei} as part of a different model that was used
to encode {\em Athanasiadis-Linusson diagrams}. The key difference between the
two models is that a breadth-first search ordering was used to identify
the vertices in~\cite[Section~6]{Hetyei}.}
\end{remark}

\begin{figure}[ht]
\newcommand{\shift}{5.5}
\begin{center}
\begin{tikzpicture}[scale = 1.3, inner sep=0.6mm]
%% First tree
% Place the nodes of the tree
\node (a) at (0,5) {$\infty$};
\node (b) at (-1.5,4) {$4_{1}$};
\node (c) at (-0.5,4) {$4_{2}$};
\node (d) at (0.5,4) {$2_{1}$};
\node (e) at (1.5,4) {$2_{2}$};
\node (f) at (-2,3) {$1_{1}$};
\node (g) at (-1,3) {$1_{2}$};
\node (h) at (-3.5,2) {$5_{1}$};
\node (i) at (-2.5,2) {$5_{2}$};
\node (j) at (-1.5,2) {$3_{1}$};
\node (k) at (-0.5,2) {$3_{2}$};

% Draw the edges of the tree
\draw[-,line width=1pt] (a) -- (b);
\draw[-,line width=1pt] (a) -- (c);
\draw[-,line width=2pt] (a) -- (d);
\draw[-,line width=2pt] (a) -- (e);
\draw[-,line width=2pt] (b) -- (f);
\draw[-,line width=2pt] (b) -- (g);
\draw[-,line width=1pt] (f) -- (h);
\draw[-,line width=1pt] (f) -- (i);
\draw[-,line width=2pt] (f) -- (j);
\draw[-,line width=2pt] (f) -- (k);

%% Second tree
% Place the nodes of the tree
\node (aa) at ({\shift+0},5) {$1$};
\node (bb) at ({\shift-1.5},4) {$2$};
\node (cc) at ({\shift-0.5},4) {$9$};
\node (dd) at ({\shift+0.5},4) {$10$};
\node (ee) at ({\shift+1.5},4) {$11$};
\node (ff) at ({\shift-2},3) {$3$};
\node (gg) at ({\shift-1},3) {$8$};
\node (hh) at ({\shift-3.5},2) {$4$};
\node (ii) at ({\shift-2.5},2) {$5$};
\node (jj) at ({\shift-1.5},2) {$6$};
\node (kk) at ({\shift-0.5},2) {$7$};

% Draw the edges of the tree
\draw[-,line width=1pt] (aa) -- (bb);
\draw[-,line width=1pt] (aa) -- (cc);
\draw[-,line width=2pt] (aa) -- (dd);
\draw[-,line width=2pt] (aa) -- (ee);
\draw[-,line width=2pt] (bb) -- (ff);
\draw[-,line width=2pt] (bb) -- (gg);
\draw[-,line width=1pt] (ff) -- (hh);
\draw[-,line width=1pt] (ff) -- (ii);
\draw[-,line width=2pt] (ff) -- (jj);
\draw[-,line width=2pt] (ff) -- (kk);
\end{tikzpicture}
\end{center}
\caption{A $2$-parking tree and
the associated depth-first search ordering.
This example corresponds to the $2$-parking function $(2,1,3,1,3)$.}
\label{figure_p_tree}
\end{figure}

Recall there is a bijection between $d$-parking functions of length $k$ and
maximal chains in the noncrossing partition poset $\NC^{d}_{dk+1}$;
see Theorem~\ref{theorem_list_of_labels_bijection}.
We now include $d$-parking trees in this bijective family.
We begin with a key observation, that is applicable in all situations
when we identify the vertices of a plane tree using an {\em increasing ordering}.
\begin{definition}
Given a plane tree $T$ on $n$ vertices an {\em increasing ordering} of the
vertices of $T$ is a bijection $\omega$ from the vertex set of $T$ to
the set $\{1,2,\ldots,n\}$ such that for every cover relation $u \prec v$ in the tree,
that is, $u$ is the parent of~$v$, the inequality $\omega(u) < \omega(v)$ holds.
\end{definition}
Clearly, the depth-first search ordering and any breadth-first search
are increasing orderings.
\begin{lemma}
\label{lemma_parking}
Let $T$ be a $d$-parking tree on $n=dk+1$ vertices and let $\omega$ be
an increasing ordering of its vertices. For all $1 \leq i \leq k$
we define $a_{i}$ as the label $\omega(p)$ of the common parent of the
vertices $\omega(i_{1}),\omega(i_{2}), \ldots, \omega(i_{d})$.
Then the resulting vector $\vec{a}_{\omega}(T) = \vec{a} = (a_{1},a_{2}, \ldots, a_{k})$ is a
$d$-parking function.
\end{lemma}
\begin{proof}
Note that the number $j$ appears in the list $\vec{a}$ if and only if
the vertex $\omega^{-1}(j)$ is not a leaf. If $\omega^{-1}(j)$ has
$d \cdot c(j)$ children then $j$ appears in the list $\vec{a}$
exactly $c(j)$ times. Consider the ordered list
$a_{(1)} \leq a_{(2)} \leq \cdots \leq a_{(k)}$ obtained from $\vec{a}$.
Let us relabel the vertices of the $d$-parking tree in such a way that
the order $(1_{1},1_{2},\ldots, 1_{d}, \ldots, k_{1}, k_{2},\ldots, k_{d})$
corresponds to listing all children of the vertex
$\omega^{-1}(a_{(1)})$, then of $\omega^{-1}(a_{(2)})$, and so on,
finally of $\omega^{-1}(a_{(k)})$
in the left-to-right order. In the case when $a_{(i)}=a_{(i+1)}$ we list
all children only at once, but we list them in increasing order of the
value of $\omega$, and we  will consider the first $d$
children associated to the first copy, the next $d$ children associated
to the second copy, and so on.

Let us call the resulting $d$-parking tree
the {\em straightened $d$-parking tree with respect to $\omega$}. The
straightened $2$-parking tree with respect to the depth-first search
order, obtained from the $2$-parking tree shown in
Figure~\ref{figure_p_tree} is represented in
\begin{figure}[ht]
\newcommand{\shift}{5.5}
\begin{center}
\begin{tikzpicture}[scale = 1.3, inner sep=0.6mm]
%% First tree
% Place the nodes of the tree
\node (a) at (0,5) {$\infty$};
\node (b) at (-1.5,4) {$1_{1}$};
\node (c) at (-0.5,4) {$1_{2}$};
\node (d) at (0.5,4) {$2_{1}$};
\node (e) at (1.5,4) {$2_{2}$};
\node (f) at (-2,3) {$3_{1}$};
\node (g) at (-1,3) {$3_{2}$};
\node (h) at (-3.5,2) {$4_{1}$};
\node (i) at (-2.5,2) {$4_{2}$};
\node (j) at (-1.5,2) {$5_{1}$};
\node (k) at (-0.5,2) {$5_{2}$};

% Draw the edges of the tree
\draw[-,line width=1pt] (a) -- (b);
\draw[-,line width=1pt] (a) -- (c);
\draw[-,line width=1pt] (a) -- (d);
\draw[-,line width=1pt] (a) -- (e);
\draw[-,line width=1pt] (b) -- (f);
\draw[-,line width=1pt] (b) -- (g);
\draw[-,line width=1pt] (f) -- (h);
\draw[-,line width=1pt] (f) -- (i);
\draw[-,line width=1pt] (f) -- (j);
\draw[-,line width=1pt] (f) -- (k);

%% Second tree
% Place the nodes of the tree
\node (aa) at ({\shift+0},5) {$1$};
\node (bb) at ({\shift-1.5},4) {$2$};
\node (cc) at ({\shift-0.5},4) {$9$};
\node (dd) at ({\shift+0.5},4) {$10$};
\node (ee) at ({\shift+1.5},4) {$11$};
\node (ff) at ({\shift-2},3) {$3$};
\node (gg) at ({\shift-1},3) {$8$};
\node (hh) at ({\shift-3.5},2) {$4$};
\node (ii) at ({\shift-2.5},2) {$5$};
\node (jj) at ({\shift-1.5},2) {$6$};
\node (kk) at ({\shift-0.5},2) {$7$};

% Draw the edges of the tree
\draw[-,line width=1pt] (aa) -- (bb);
\draw[-,line width=1pt] (aa) -- (cc);
\draw[-,line width=1pt] (aa) -- (dd);
\draw[-,line width=1pt] (aa) -- (ee);
\draw[-,line width=1pt] (bb) -- (ff);
\draw[-,line width=1pt] (bb) -- (gg);
\draw[-,line width=1pt] (ff) -- (hh);
\draw[-,line width=1pt] (ff) -- (ii);
\draw[-,line width=1pt] (ff) -- (jj);
\draw[-,line width=1pt] (ff) -- (kk);
\end{tikzpicture}
\end{center}
\caption{The straightened of the $2$-parking tree in Figure~\ref{figure_p_tree}
with respect to the depth-first search.
This example corresponds to the $2$-parking function $(1,1,2,3,3)$.}
\label{figure_p_tree_straightened}
\end{figure}
For $1 \leq i \leq k$ consider the list of children associated
to the parents in the initial segment $a_{(1)} \leq
a_{(2)} \leq \cdots \leq a_{(i-1)}$. In the straightened $d$-parking tree
this is exactly the list of the first $d\cdot(i-1)$ entries of the list $(1_{1},1_{2},\ldots, 1_{d}, \ldots, k_{1}, k_{2},\ldots,
k_{d})$. Observe that $a_{(i)}$ is exactly the value of
$\omega(p)$ for the common parent of $i_{1}, i_{2},\ldots,i_{d}$ in the
straightened parking tree.  Consider any nonroot-vertex $v$ that is not
yet listed. The parent $p(v)$ of $v$ satisfies $\omega(p(v))\geq
a_{(i)}$. Since the ordering $\omega$ is increasing on subtrees we must
also have $\omega(v)> a_{(i)}$. We obtained that the label of any
non-yet listed nonroot vertex is greater than the label $a_{(i)}$. There are
$n-(d(i-1)+1)$ such vertices which forces $a_{(i)} \leq d(i-1)+1$.
\end{proof}
Every $d$-parking tree may be turned into a $1$-parking tree, using the
following simple relabeling.
\begin{definition}
\label{definition_expansion}
Let $T$ be a $d$-parking tree on $n=dk+1$ vertices. We call the {\em
expansion of $T$} the $1$-parking tree obtained by replacing each
label $i_{j}$ with $(i-1)d+j$ for $1 \leq i \leq k$ and $1 \leq j \leq d$.
\end{definition}
The following statement is a direct consequence of
Lemma~\ref{lemma_parking} and Definition~\ref{definition_expansion}.
\begin{corollary}
Let $T$ be a $d$-parking tree on $n=dk+1$ vertices, let $\omega$ be
an increasing ordering of its vertices and let $\vec{a}_{\omega}(T)=\vec{a}=(a_{1},\ldots,a_{k})$ be
the $d$-parking function associated to $T$ ordered by~$\omega$ in Lemma~\ref{lemma_parking}.
Let $U$ be the expansion of the tree $T$.
Then the parking function $\vec{b}=\vec{a}_{\omega}(U)$
is the vector obtained  by replacing each entry $a_{i}$ in $\vec{a}$ by a
list of $d$ consecutive copies of $a_{i}$.
\end{corollary}
\begin{example}
{\rm The $2$-parking tree shown in Figure~\ref{figure_p_tree}
corresponds to the $2$-parking function $\vec{a}=(2,1,3,1,3)$ with respect to he
depth-first search ordering. Its expansion corresponds to the parking
function $\vec{b}=(2,2,1,1,3,3,1,1,3,3)$. The fourth coordinate of
$\vec{a}$ is $1$ because the common parent $\infty$ of $4_{1}$ and $4_{2}$
satisfies $\omega(\infty)=1$. In the expansion $4_{1}$ becomes $3\cdot
2+1=7$ and $4_{2}$ becomes $3\cdot 2+2=8$. The seventh and eighth
coordinates of $\vec{b}$ are both $1$.}
\end{example}

In the remainder of the section we assume that
the increasing ordering $\omega$ is the depth-first search ordering.
In this case we will write
$\vec{a}(T)$ for $\vec{a}_{\omega}(T)$
and call $\vec{a}(T)$
{\em the $d$-parking function associated to the $d$-parking tree $T$}.

\begin{theorem}
The map $T \longmapsto \vec{a}(T)$ from $d$-parking trees on $n = dk+1$ vertices
to the $d$-parking functions of length $k$ is a bijection.
\label{theorem_parking_function_parking_tree}
\end{theorem}
\begin{proof}
It suffices to show that given a $d$-parking function $\vec{a} =
(a_{1},a_{2}, \ldots, a_{k})$ there is exactly one $d$-parking tree $T$
on $n=dk+1$ whose associated $d$-parking function is $\vec{a}$.

Observe first that we may restrict our attention to straightened
$d$-parking trees (defined in the proof of Lemma~\ref{lemma_parking})
and $d$-parking functions $\vec{a} = (a_{1},a_{2}, \ldots, a_{k})$
satisfying $a_{1} \leq a_{2} \leq \cdots \leq a_{k}$. Indeed, given any
permutation $\pi$ on the set $\{1,2,\ldots,k\}$, let $T_{\pi}$ be the
$d$-parking tree obtained from the $d$-parking tree $T$ by  replacing the labels
$i_{1},i_{2},\ldots, i_{d}$ with $\pi(i)_{1},\pi(i)_{2},\ldots,\pi(i)_{d}$ for each
$i\in \{1,2,\ldots,k\}$. If $\vec{a} = (a_{1},a_{2}, \ldots, a_{k})$ is
the $d$-parking function associated to $T$ then
$\vec{a}_{\pi} = (a_{\pi(1)},a_{\pi(2)}, \ldots, a_{\pi(k)})$ is the
$d$-parking function associated to $T_{\pi}$. In other words, once we
prove the statement for straightened $d$-parking trees and $d$-parking
functions $\vec{a} = (a_{1},a_{2}, \ldots, a_{k})$ satisfying $a_{1}\leq
a_{2}\leq \cdots \leq a_{k}$, the general statement may be obtained by
permuting the labels.

Consider now a $d$-parking function $\vec{a} = (a_{1},a_{2}, \ldots, a_{k})$
satisfying $a_{1} \leq a_{2} \leq \cdots \leq a_{k}$.
As in the proof of Lemma~\ref{lemma_parking} let $c(j)$ be the number of
times the number $j$ occurs in $\vec{a}$. Let
$\{j_{1}<j_{2}<\cdots<j_{m}\}$ be the set of integers satisfying $c(j) \geq 1$.
Since $a_{1}=1$, we must have $c(1)\geq 1$, $j_{1}=1$, and the
straightened $d$-parking tree $T$ giving rise to
$\vec{a}$ must have exactly $d \cdot c(1)$ children: $1_{1},1_{2},\ldots, 1_{d},
\ldots, c(1)_{1}, c(1)_{2}, \ldots, c(1)_{d}$. The numbers $2,3,\ldots,j_{2}-1$
do not appear in $\vec{a}$, they must be numbers of leaves in the
depth-first search ordering, and these $j_{2}-2$ leaves must be the
leftmost $j_{2}-2$ children of the root. The vertex $j_{2}$ in the
depth-first search order is then child number $j_{2}-1$ of the root. This
assignment is possible if and only if
\begin{equation}
\label{inequality_parking_2}
j_{2} \leq d \cdot c(1) + 1
\end{equation}
holds, as this is the number of children of the root. Observe also that we have
$a_{1}=a_{2}=\cdots=a_{c(1)}=1$ and $j_{2}$ is the common value of
$a_{c(1)+1}=a_{c(1)+2}=\cdots=a_{c(1)+c(j_{2})}$. The
inequality~\eqref{inequality_parking_2} is equivalent to
$a_{c(1)+1} \leq d \cdot c(1) + 1$ which is the $d$-parking condition for
$a_{c(1)+1}$. (It is worth noting that the parking conditions for
$a_{2}=\cdots=a_{c(1)}=1$  are automatically satisfied, and they follow
from~\eqref{inequality_parking_2} for

We proceed now by induction of $m$, the number of distinct values listed
in $\vec{a}$. Assume that we have already found a unique straightened
parking tree $T'$ on $d \cdot (c(j_{1})+c(j_{2})+\cdots+c(j_{m-1}))+1$ vertices whose
associated $d$-parking function is
$(a_{1},a_{2},\ldots,a_{c(j_{1})+c(j_{2})+\cdots+c(j_{m-1})})$. By our
construction, $v$ is a nonleaf vertex of $T'$ if and only if $\omega(v)$
belongs to the set $\{j_{1},j_{2},\ldots,j_{m-1}\}$.  Now we want to
add $d \cdot c(j_{m})$ children to the vertex labeled $j_{m}$ in $T'$, to obtain
the tree $T$. In the depth-first search ordering this will increase the
value of $\omega$ by $d \cdot c(j_{m})$ for the vertices $v$ of $T$ that satisfy
$\omega(v)>j_{m}$, but by $j_{m-1}<j_{m}$ all these vertices are leaves, and
the $d$-parking function associated to $T$ will agree with the one
associated to $T'$ in the first $c(j_{1})+c(j_{2})+\cdots+c(j_{m-1})$
coordinates. The insertion of children is possible if and only if
\begin{equation}
\label{inequality_parking_m}
j_{m-1} < j_{m} \leq d \cdot (c(j_{1})+c(j_{2})+\cdots+c(j_{m-1})) + 1
\end{equation}
holds. The upper bound is equivalent to
\begin{align*}
& \leq d \cdot (c(j_{1})+c(j_{2})+\cdots+c(j_{m-1})) + 1,
\end{align*}
the $d$-parking condition for
$a_{c(j_{1})+c(j_{2})+\cdots+c(j_{m-1})+1}$. If this condition is satisfied,
the weaker conditions for $a_{c(j_{1})+c(j_{2})+\cdots+c(j_{m-1})+1},
\ldots, a_{c(j_{1})+c(j_{2})+\cdots+c(j_{m})}$ are also satisfied. The
\begin{align*}
j_{m-1} < d \cdot (c(j_{1})+c(j_{2})+\cdots+c(j_{m-1})) + 1
\end{align*}
needed to have at least one choice for $j_{m}$ is also a direct
consequence of the $d$-parking condition for
\end{proof}

establishes a bijection between the set of all maximal chains in
$\NC^{d}_{dk+1}$ and the set of all $d$-parking functions of length~$k$.
Combining this bijection with
Theorem~\ref{theorem_parking_function_parking_tree} above we obtain a
bijection between the set of all maximal chains in
$\NC^{d}_{dk+1}$ and the set of all $d$-parking trees on $n=dk+1$
vertices. The correspondence is visually straightforward, as exhibited
in the following example.

\begin{example}
Consider the $2$-parking function $(a_{1}, \ldots, a_{5}) = (2,1,3,1,3)$,
corresponding to the $2$-parking tree in Figure~\ref{figure_p_tree}.
Note that $5_{1}$ and $5_{2}$ has the node $1_{1}$ as their parent
and the depth-first search label of $1_{1}$ is $\omega(1_{1}) = 3 = a_{5}$.
Furthermore, this $2$-parking function
corresponds to
the following maximal chain in the noncrossing partition poset $\NC^{2}_{11}$:
\begin{align*}
\hz
& \coveredby
\coveredby
1,10,11|2,3,8|4|5|6|7|9 \\
& \coveredby
\coveredby
\coveredby
\ho .
\end{align*}
In the $3$rd step we join together the blocks containing the elements
$\omega(1_{1}) = 3$,
$\omega(3_{1}) = 6$ and
$\omega(3_{2}) = 7$.
Note that the node $1_{1}$ is the parent of $3_{1}$ and $3_{2}$.
This relation is explained in the next theorem.
\end{example}
\begin{theorem}
Let ${\bf m} = \{\hz = \pi_{0} \coveredby \pi_{1} \coveredby \cdots \coveredby \pi_{k} = \ho\}$
be a maximal chain in $\NC^{d}_{dk+1}$
and let $T$ be the $d$-parking tree such that $\lambda({\bf m}) = \vec{a} = \vec{a}(T)$.
Then $\pi_{i}$ is the noncrossing partition whose blocks consist of the connected
components of the graph containing all edges that connect a vertex~$j_{s}$
to its parent for some $1 \leq j \leq i$ and some $1 \leq s \leq d$.
In particular, the cover relation from the partition $\pi_{i-1}$ to the
partition $\pi_{i}$ is obtained by joining the blocks containing the $d+1$ elements
$\omega(p_{i}), \omega(i_{1}), \omega(i_{2}), \ldots, \omega(i_{d})$, where
$p_{i}$ is the common parent of $i_{1}$ through $i_{d}$.
\label{theorem_parking_noncrossing}
\end{theorem}
\begin{proof}
%[First proof of Theorem~\ref{theorem_parking_noncrossing}.]
We proceed by induction on $k$.
When $k=0$ there is is nothing to prove completing the induction basis.
Assume now that the result is true for $k-1$ and we prove it for $k$.

Let $r$ and $s$ be defined
as in Lemma~\ref{lemma_d_singleton_blocks}.
That is, $r$ is the largest entry in the $k$-parking function $\vec{a} = (a_{1},a_{2}, \ldots, a_{k})$
and $s$ is the last entry such that $a_{s} = r$.
Lemma~\ref{lemma_d_singleton_blocks} implies that
the partition $\pi_{s-1}$ contains the singleton blocks
$\{r+1\}, \{r+2\}, \ldots, \{r+d\}$.
As in Lemma~\ref{lemma_reconstructing_maximal_chain}
let $\vec{b} = (b_{1}, b_{2}, \ldots, b_{k-1}) = (a_{1}, a_{2}, \ldots, a_{s-1}, a_{s+1}, \ldots, a_{k})$
be the $d$-parking function where we remove the $a_{s}$ entry.
Let $U$ be the $d$-parking tree corresponding to the $d$-parking function~$\vec{b}$,
that is, we define $U$ by $\vec{a}(U) = \vec{b}$.

Construct a new tree $T^{*}$ by the following two steps:
\begin{itemize}
\item[(1)]
Relabel the nodes $i_{j}$ in the tree $U$ where $i \geq s$ to be $(i+1)_{j}$.
Note that after the relabeling, there are no nodes with the labels $s_{1}$ through $s_{d}$.
\item[(2)]
Let $p$ be the node in the tree $U$ such that $\omega_{U}(p) = r$.
Attach the new leaves $s_{1}$ through $s_{d}$ to the node $p$
such that they are the $d$ right-most children of the node $p$.
Note that these nodes in the depth-first search labeling
receive the labels $r+1$ through $r+d$, that is,
$\omega_{T^{*}}(s_{j}) = r+j$ for $1 \leq j \leq d$.
\end{itemize}
The node $x$ in the tree $U$ satisfies
$f(\omega_{U}(x)) = \omega_{T^{*}}(x)$ where $f$ is the relabeling function
defined in~\eqref{equation_relabeling_function}
Hence $\vec{a}(T^{*}) = \vec{a}$ holds.
Since the correspondence between $d$-parking trees and $d$-parking functions
is a bijection, we conclude that $T^{*}$ is the tree $T$.

Consider the cover relation $\pi_{i-1} \coveredby \pi_{i}$
in the chain ${\bf m}$.
By the induction hypothesis
when $i \neq s$
the partition $\pi_{i}$ is obtained from $\pi_{i-1}$ by joining the blocks containing the elements
$f(\omega_{U}(p_{i}))$, $f(\omega_{U}(i_{1}))$, $f(\omega_{U}(i_{2}))$, $\ldots$, $f(\omega_{U}(i_{d}))$.
But these are exactly the elements
$\omega_{T}(p_{i}), \omega_{T}(i_{1}), \omega_{T}(i_{2}), \ldots, \omega_{T}(i_{d})$.
Finally, when $i$ is $s$ by the above construction we are joining
$\omega_{T}(p), \omega_{T}(s_{1}), \omega_{T}(s_{2}), \ldots, \omega_{T}(s_{d})$
which are the elements $r$ through $r+d$, completing the induction.
\end{proof}

\begin{remark}
In~[25] Stanley mentions (about the case $d=1$ of all
noncrossing partitions) that ``The above proof of the injectivity of
the map $\Lambda$ from maximal chains to parking functions is
reminiscent of the proof [20, p.\ 5] that the Pr\"ufer code of a labelled
tree determines the tree.'' It is a direct consequence of the proof
of~\cite[Theorem~6.10]{Hetyei} (which uses a homogenized variant of the
Pr\"ufer code algorithm) that the number of $d$-parking trees is
\end{remark}

It is an immediate consequence of the definitions that for a $d$-parking
function $\vec{a}=(a_{1},a_{2},\ldots,a_{k})$
and a permutation $\tau$ of the set $\{1,2,\ldots,k\}$ the vector
$\tau(\vec{a})=(a_{\tau(1)},a_{\tau(2)},\ldots,a_{\tau(k)})$ is also a
$d$-parking function. Since $d$-parking functions bijectively label the
maximal chains of $\NC^{d}_{dk+1}$, the above action of the symmetric
group $\mathfrak{S}_{k}$ on the set of $d$-parking functions of
length $k$ induces an action of the same group on the maximal chains of
$\NC^{d}_{dk+1}$. As a direct consequence of
Theorem~\ref{theorem_parking_noncrossing} we obtain the following

\begin{corollary}
\label{corollary_permutations}
Two maximal chains of $\NC^{d}_{dk+1}$ are in the same orbit of the
above described action of the symmetric group if and only if the
removal of the labels on the $d$-parking trees associated to them yields
the same plane tree.
\end{corollary}

Theorem~\ref{theorem_parking_noncrossing} and
Corollary~\ref{corollary_permutations} have the following consequence.

\begin{corollary}
\label{corollary_parkingblocks}
Let $n=dk+1$. If a partition $\pi$ of $[n]$ belongs to the noncrossing
partition poset $\NC^{d}_{n}$ then there is a $d$-parking tree
$T$ and an $s\in\{0,1,\ldots,k\}$ such that the blocks of $\pi$
are the connected components of the graph obtained from the tree $T$ by
deleting all the edges connecting each vertex $i_{j}$ to its parent
for all $i>s$ and $j\in\{1,2,\ldots,d\}$. Conversely, if there is a
$d$-parking tree $T$ and a subset $S$ of $\{1,2,\ldots,k\}$, such that
the connected components of the graph obtained from the tree $T$ by
deleting all the edges connecting each vertex $i_{j}$ to its parent
for all $i\in S$ and $j\in\{1,2,\ldots,d\}$ are the blocks of~$\pi$, then
$\pi$  belongs to $\NC^{d}_{n}$.
\end{corollary}

For $d=1$ Corollary~\ref{corollary_parkingblocks} yields the following

\begin{corollary}
\label{corollary_ncparkingblocks}
A partition $\pi$ of $[n]$ is a noncrossing partition
if and only if its blocks are the
connected components of a graph obtained from a plane tree ordered by
the depth-first search order after deleting an arbitrary subset of its
\end{corollary}

\section{Concluding remarks}
\label{section_Concluding_remarks}

Many of the enumerative results
involve the sequence given
These numbers count many combinatorial objects from Raney lattice paths
to $d$-ary trees. Could the bijective results stated in
Corollaries~\ref{corollary_bigblocks} and \ref{corollary_smallblocks}
extended to bijective proofs of more general statements on
Also, is there a combinatorial proof for

The quasisymmetric function of a graded poset
encodes all of the flag $f$-vector information of the poset;
Stanley observed that if every interval of a poset $P$
is self-dual then the quasisymmetric function of $P$
is a symmetric function; see~\cite[Theorem~1.4]{Stanley_Flag}.
Hence the noncrossing partition poset~$\NC^{d}_{n}$
has a symmetric quasisymmetric function.
In the paper~[25]
Stanley explores the quasisymmetric function
of the noncrossing partition lattice $\NC_{n}$.
Are there similar results for the noncrossing partition poset $\NC^{d}_{n}$?

The set of $d$-parking functions are known to be in bijection with
the regions of the extended Shi-arrangement via the Pak-Stanley
labeling~\cite[2.1 Theorem]{Stanley_Flag}. By our results the same
$d$-parking functions also label the maximal chains of the poset
$\NC^{d}_{n}$. Is there a geometric way to directly connect the poset
$\NC^{d}_{n}$ with the extended Shi arrangement?

Einziger explored the Hopf algebra structure
of the sub Hopf algebra of $\mathcal{P}$
generated by the noncrossing partition lattice $\NC_{n}$;
see~[8, 9].
Would the sub Hopf algebra generated by
$\NC^{d}_{n}$, for a fixed~$d$, have similar structure?

Noncrossing partitions have connections with free probability.
Does the subposet $\NC^{d}_{n}$ of the lattice $\NC_{n}$ have a similar

There are noncrossing partitions for other Coxeter systems; see~[1, 16].
The authors are currently developing the analogous results for
noncrossing partitions of these types.

\section*{Acknowledgements}

%%% We thank .... for comments on an earlier draft.
This work was partially supported by a grant from the
Simons Foundation
(\#854548 to Richard Ehrenborg
\#514648 to G\'abor Hetyei).

\newcommand{\journal}[6]{{\sc #1,} #2, {\it #3} {\bf #4} (#5), #6.}
\newcommand{\book}[4]{{\sc #1,} ``#2,'' #3, #4.}
\newcommand{\bookf}[5]{{\sc #1,} ``#2,'' #3, #4, #5.}
\newcommand{\arxiv}[3]{{\sc #1,} #2, {\tt #3}.}
\newcommand{\thesis}[4]{{\sc #1,} ``#2,'' Doctoral dissertation, #3,~#4.}
\newcommand{\preprint}[3]{{\sc #1,} #2, preprint {(#3)}.}
\newcommand{\preparation}[2]{{\sc #1,} #2, in preparation.}
\newcommand{\toappear}[3]{{\sc #1,} #2, to appear in {\it #3}.}

\begin{thebibliography}{99}

[1]
{\sc D.\ Armstrong,}
{Generalized noncrossing partitions and combinatorics of Coxeter groups,}
Mem.\ Amer.\ Math.\ Soc.
{\bf 202} (2009), no.\ 949.

[2]
\journal{A.\ R.\ Calderbank, P.\ Hanlon and R.\ W.\ Robinson}
{Partitions into even and odd block size and
some unusual characters of the symmetric groups}
{Proc.\ London Math.\ Soc.\ (3)}

[3]
\journal{R.\ Ehrenborg}
{On posets and Hopf algebras}
{Adv.\ Math.}

[4]
\journal{R.\ Ehrenborg and A.\ Happ}
%%%%\journal{Richard Ehrenborg and Alex Happ}
{The antipode of the noncrossing partition lattice}
{Adv.\ in Appl.\ Math.}
%%%%            {Advances in Applied Mathematics}

[5]
\journal{R.\ Ehrenborg and D.\ Hedmark}
{Filters in the partition lattice}
{J.\ Algebraic Combin.}

[6]
\journal{R.\ Ehrenborg and J.\ Jung}
{The topology of restricted partition posets}
{J.\ Algebraic Combin.}

[7]
\journal{R.\ Ehrenborg and M.\ M\'endez}
{A bijective proof of infinite variated Good's inversion}
{Advances in Mathematics}

[8]
\thesis{H.\ Einziger}
{Incidence Hopf Algebras: Antipodes, Forest Formulas,
and Noncrossing Partitions}
{The George Washington University}

[9]
\preprint{H.\ Einziger}
{A forest formula for the antipode in incidence Hopf algebras}
arXiv:0911.2168 [math.CO]

[10]
\journal{I.\ J.\ Good}
{Generalizations to several variables of Lagrange's expansion,
with applications to stochastic processes}
{Proc.\ Cambridge Philos.\ Soc.}

[11]
\book{R.\ L.\ Graham, D.\ E.\ Knuth and O.\ Patashnik}
%%%\book{Ronald L.\ Graham, Donald E.\ Knuth and Oren Patashnik}
{Concrete mathematics}
{Addison-Wesley Publishing Company}
{Reading, MA, 1989}

[12]
\preprint{G.\ Hetyei}
{Labeling regions in deformations of graphical arrangements}
arXiv:2312.06513 [math.CO]

[13]
\journal{S.\ Janson and S.\ \"O.\ Stef\'ansson}
{Scaling limits of random planar maps with a unique large face}
{Ann.\ Probab.\ }

[14]
\journal{I.\ Kortchemski and C.\ Marzouk}
{Simply generated non-crossing partitions}
{Combin.\ Probab.\ Comput.\ }

[15]
\journal{G.\ Kreweras}
{Sur les partitions non croisees d'un cycle}
{Discrete Math.}

[16]
\journal{V.\ Reiner}
%%%\journal{Victor Reiner}
{Non-crossing partitions for classical reflection groups}
{Discrete Math.}

[17]
\journal{G.-C.\ Rota, D.\ Kahaner and A.\ Odlyzko}
{On the foundations of combinatorial theory. VIII. Finite operator calculus}
{J.\ Math.\ Anal.\ Appl.}

[18]
\journal{W.\ R.\ Schmitt}
{Antipodes and incidence coalgebras}
{J.\ Combin.\ Theory Ser.\ A}

[19]
\journal{R.\ Simion}
{Noncrossing partitions}
{Discrete Math.}

[20]
\journal{R.\ Simion and D.\ Ullman}
{On the structure of the lattice of noncrossing partitions}
{Discrete Math.}

[21]
\journal{R.\ Speicher}
{Multiplicative functions on the lattice of non-crossing partitions and free convolution}
{Math.\ Ann.}

[22]
\journal{R.\ P.\ Stanley}
{Exponential structures}
{Studies Appl.\ Math}

[23]
{\sc R.\ P.\ Stanley},
Flag-symmetric and locally rank-symmetric partially ordered sets.
The Foata Festschrift,
{\em Electron.\ J.\ Combin.}
{\bf 3} (1996), no. 2, Research Paper 6, 22pp.

[24]
R.\ P.\  Stanley,
Hyperplane arrangements, parking functions and tree inversions,
in: Mathematical essays in honor of Gian-Carlo Rota (Cambridge, MA,
1996), 359--375. {\bf Progr. Math., 161}
Birkh\"auser Boston, Inc., Boston, MA, 1998

[25]
{\sc R.\ P.\ Stanley},
Parking functions and noncrossing partitions.
The Wilf Festschrift,
{\em Electron.\ J.\ Combin.}
{\bf 4} (1997), no. 2, Research Paper 20, 14pp.

[26]
\book{R.\ P.\ Stanley}
{Enumerative Combinatorics, Vol. II}
{Cambridge University Press}

[27]
\journal{M.\ L.\ Wachs}
{A basis for the homology of the $d$-divisible partition lattice}
{Adv.\ Math.}

[28]
{\sc M.\ L.\ Wachs,}
Poset topology: tools and applications.Geometric combinatorics, 497–615.
IAS/Park City Math. Ser., 13
American Mathematical Society, Providence, RI, 2007.

[29]
\journal{C.\ H.\ Yan}
{Generalized tree inversions and $k$-parking functions}
{J.\ Combin.\ Theory Ser.\ A}

\end{thebibliography}

\end{document}