# On $q$-Counting of Noncrossing Chains and
Parking Functions

Yen-Jen Cheng  Department of Applied Mathematics, National Yang Ming Chiao
Tung University, Hsinchu 300093, Taiwan, ROC<EMAIL_ADDRESS>,  Sen-Peng
Eu  Department of Mathematics, National Taiwan Normal University, Taipei
116325, and Chinese Air Force Academy, Kaohsiung 820009, Taiwan, ROC
<EMAIL_ADDRESS>,  Tung-Shan Fu  Department of Applied Mathematics,
National Pingtung University, Pingtung 900391, Taiwan, ROC
<EMAIL_ADDRESS>and  Jyun-Cheng Yao  Department of Mathematics, National
Taiwan Normal University, Taipei 116325, Taiwan, ROC<EMAIL_ADDRESS>
###### Abstract.

For a finite Coxeter group $W$, Josuat-Vergès derived a $q$-polynomial
counting the maximal chains in the lattice of noncrossing partitions of $W$ by
weighting some of the covering relations, which we call bad edges, in these
chains with a parameter $q$. We study the connection of these weighted chains
with parking functions of type $A$ ($B$, respectively) from the perspective of
the $q$-polynomial. The $q$-polynomial turns out to be the generating function
for parking functions (of either type) with respect to the number of cars that
do not park at their preferred spaces. In either case, we present a bijective
result that carries bad edges to unlucky cars while preserving their relative
order. Using this, we give an interpretation of the $\gamma$-positivity of the
$q$-polynomial in the case that $W$ is the hyperoctahedral group.

###### Key words and phrases:

noncrossing partition, parking functions, Coxeter group, absolute order

###### 2020 Mathematics Subject Classification:

05A19, 05E16, 20F55

##  1\. Introduction

For a finite Coxeter group $W$ of rank $n$, Josuat-Vergès [18] derived a
polynomial $M(W,q)$ (as shown in Theorem 1.1) which enumerates the maximal
chains in the lattice of noncrossing partitions of $W$ by weighting some of
the covering relations, called _bad edges_ (as defined below), in these chains
with a parameter $q$. When the polynomial specialized at $q=1$, the value in
the case of symmetric group $\mathfrak{S}_{n+1}$ (hyperoctahedral group
$B_{n}$, respectively) is $(n+1)^{n-1}$ ($n^{n}$, respectively), which is
known to be the number of parking functions of type $A$ ($B$, respectively) of
size $n$. The polynomial turns out to be the generating function which counts
parking functions (of either type) by the number of cars that do not park at
their preferred spaces. Biane [6] established a bijection between the maximal
chains in the lattice of noncrossing partitions of $\mathfrak{S}_{n+1}$
($B_{n}$, respectively) and parking functions of type $A$ ($B$, respectively).
However, these two bijections are not established with respect to the
polynomial. In either case, we come up with a bijection that not only carries
the bad edges of a maximal chain to the unlucky cars of the corresponding
parking function but also preserves their relative order (Theorems 1.2 and
1.3). A highlight of our results is that in the case of $W=B_{n}$ we prove the
$\gamma$-positivity of the polynomial, in terms of words over an alphabet with
$n$ letters (Theorem 5.1), and give interpretations of the
$\gamma$-coefficients using parking functions and the weighted chains (Theorem
1.4).

###  1.1. Noncrossing lattices of $W$

Let $S$ be the set of simple generators of $W$. Let $T=\\{\omega
s\omega^{-1}:\omega\in W,s\in S\\}$, whose elements are the _reflections_ in
$W$ with respect to roots. For any $\omega\in W$, the _length_
$\ell_{S}(\omega)$ of $\omega$ is the minimum integer $r$ such that there
exists an expression $\omega=s_{1}s_{2}\cdots s_{r}$ with $s_{i}\in S$. Write
$\omega\rightarrow\omega^{\prime}$ if $\omega^{\prime}=\omega t$ for some
$t\in T$ with $\ell_{S}(\omega)<\ell_{S}(\omega^{\prime})$. The (_strong_)
_Bruhat order_ $\leq_{B}$ on $W$ is defined by setting
$\omega<_{B}\omega^{\prime}$ if there is a sequence
$\omega=\omega_{0}\rightarrow\omega_{1}\rightarrow\cdots\rightarrow\omega_{m}=\omega^{\prime}$.
On the other hand, the _reflection length_ $\ell_{T}(\omega)$ of $\omega$ is
the minimum integer $r$ such that there exists an expression
$\omega=t_{1}t_{2}\cdots t_{r}$ with $t_{i}\in T$. The _absolute order_ $\leq$
on $W$ is defined by setting $\omega<\omega^{\prime}$ if
$\ell_{T}(\omega^{\prime})=\ell_{T}(\omega)+\ell_{T}(\omega^{-1}\omega^{\prime})$.

Relative to a Coxeter element $c\in W$, the $c$-_noncrossing partition
lattice_ ${\mathrm{NC}}(W,c)$ is defined as the interval in the group $W$
between the identity element $e$ and the Coxeter element $c$ under the
absolute order (e.g. [4], [10], [11]),

${\mathrm{NC}}(W,c):=\\{\omega\in W:e\leq\omega\leq c\\}.$ (1.1)

The structure of ${\mathrm{NC}}(W,c)$ is independent of $c$ (e.g. [20]).
Deligne [15] obtained the formula

$\frac{n!h^{n}}{|W|},$ (1.2)

where $h$ is the Coxeter number of $W$, counting the number of factorizations
of $c$ into $n$ reflections. Chapoton [12, Proposition 9] rediscovered the
expression (1.2) by counting the maximal chains in the lattice
${\mathrm{NC}}(W,c)$. Recently, Chapuy and Douvropoulos [13] gave a case-free
Coxeter-theoretic derivation of this chain number formula.

An _edge_ of ${\mathrm{NC}}(W,c)$ is a pair $(\mu,\nu)$ of elements in $W$
such that $\nu$ _covers_ $\mu$ (i.e., $\mu<\nu$ and no element $\omega$ with
$\mu<\omega<\nu$). An edge $(\mu,\nu)$ is said to be _good_ (_bad_ ,
respectively) if $\mu<_{B}\nu$ ($\mu>_{B}\nu$, respectively). The notion of
good and bad edges comes from [18, Definition 3.1]; see also [7, Definition
4.10].

Given a maximal chain
${\mathbf{w}}:e=\omega_{0}<\omega_{1}<\cdots<\omega_{n}=c$ in
${\mathrm{NC}}(W,c)$, let ${\mathsf{bad}}({\mathbf{w}})$ denote the number of
bad edges in ${\mathbf{w}}$, i.e.,
${\mathsf{bad}}({\mathbf{w}}):=\\#\\{(\omega_{i-1},\omega_{i}):\omega_{i-1}>_{B}\omega_{i},1\leq
i\leq n\\}$. Define

$M(W,q):=\sum_{{\mathbf{w}}}q^{{\mathsf{bad}}({\mathbf{w}})},$ (1.3)

summed over all maximal chains ${\mathbf{w}}$ in ${\mathrm{NC}}(W,c)$. As a
refinement of (1.2), Josuat-Vergès [18, Proposition 3.6] obtained the
following result.

######  Theorem 1.1 (Josuat-Vergès).

We have

$M(W,q)=\frac{n!}{|W|}\prod_{i=1}^{n}\big{(}d_{i}+q(h-d_{i})\big{)},$

where the integers $d_{1},d_{2},\dots,d_{n}$ are the fundamental degrees of
$W$.

We shall study the connection of parking functions of type $A$ ($B$,
respectively) with the maximal chains in ${\mathrm{NC}}(W,c)$ by the
polynomial $M(\mathfrak{S}_{n+1},q)$ ($M(B_{n},q)$, respectively).

###  1.2. Parking functions of type $A$

Consider a one-way street with $n$ parking spaces numbered from 1 to $n$ and a
line of $n$ cars $C_{1},\dots,C_{n}$ with preferred parking spaces
$a_{1},\dots,a_{n}$, accordingly. The cars arrive sequentially and each car
attempts to park at its preferred space. If that space is occupied, the car
moves on and parks at the next available space. If there is no such parking
space, the car leaves the street without parking. The preference list
$\alpha=(a_{1},\dots,a_{n})$ is called a _parking function_ (of type $A$) of
_size_ $n$ if all cars park successfully. For each $i$, assume that the $i$th
car $C_{i}$ parks at space $p_{i}$. The $n$-tuple $\pi=(p_{1},\dots,p_{n})$ is
called the _outcome_ of $\alpha$. A car $C_{i}$ is said to be _lucky_
(_reluctant_ , respectively) if $p_{i}=a_{i}$ ($p_{i}\neq a_{i}$,
respectively). Let ${\mathsf{lucky}}(\alpha)$ (${\mathsf{reluc}}(\alpha)$,
respectively) denote the number of lucky (reluctant, respectively) cars of
$\alpha$. Note that ${\mathsf{lucky}}(\alpha)+{\mathsf{reluc}}(\alpha)=n$. The
${\mathsf{lucky}}$ statistic for parking functions was studied by Gessel and
Seo [16]. We refer the readers to [23] for a survey on various aspects of
parking functions.

Let ${\mathrm{PF}}^{A}_{n}$ denote the set of parking functions of size $n$.
In the case of $W=\mathfrak{S}_{n+1}$, we have

$M(\mathfrak{S}_{n+1},q)=\prod_{k=1}^{n-1}\big{(}n-k+1+kq\big{)},$ (1.4)

which coincides with the generating function for parking functions with
respect to their reluctant cars (cf. [16, Theorem 10.1]), i.e.,

$M(\mathfrak{S}_{n+1},q)=\sum_{\alpha\in{\mathrm{PF}}^{A}_{n}}q^{{\mathsf{reluc}}(\alpha)}.$
(1.5)

Biane [6] established a bijection between the maximal chains ${\mathbf{w}}$ in
${\mathrm{NC}}(\mathfrak{S}_{n+1},c)$ and the parking functions $\alpha$ in
${\mathrm{PF}}^{A}_{n}$. This bijection turns out to be equivalent to a result
by Stanley [22]. However, this bijection does not carry the bad edges in
${\mathbf{w}}$ to the reluctant cars of $\alpha$. One of our main results is
the following bijection.

######  Theorem 1.2.

There is a bijection
$\varphi_{A}:\alpha\mapsto{\mathbf{w}}:e=\omega_{0}<\omega_{1}<\cdots<\omega_{n}=c$
between the parking functions in ${\mathrm{PF}}^{A}_{n}$ and the maximal
chains in ${\mathrm{NC}}(\mathfrak{S}_{n+1},c)$ such that the $i$th car of
$\alpha$ is reluctant if and only if $(\omega_{i-1},\omega_{i})$ is a bad
edge.

###  1.3. Parking functions of type $B$

Now, arrange the $n$ parking spaces in a circle. There are still $n$ cars with
preferred parking spaces $a_{1},\dots,a_{n}$, accordingly. Starting just
before space 1, each car in turn moves around the circle to park at its
preferred space if possible; otherwise, it moves on to the next available
space. Each car will eventually park. An $n$-tuple
$\alpha=(a_{1},\dots,a_{n})$ of positive integers is a _parking function of
type $B$_ of _size_ $n$ if $a_{i}\leq n$ for all $i$. The outcome of $\alpha$
and the statistics ${\mathsf{lucky}}(\alpha)$ and ${\mathsf{reluc}}(\alpha)$
are defined in the same manner as that of a type-$A$ parking function. Let
${\mathrm{PF}}^{B}_{n}$ denote the set of parking functions of type $B$ of
size $n$.

Let $[n]:=\\{1,\dots,n\\}$ and let $[\pm
n]:=\\{1,2,\dots,n,-1,-2,\dots,-n\\}$. A _signed permutation_ of the set $[\pm
n]$ is a bijection $\omega$ of the set onto itself such that
$\omega(-i)=-\omega(i)$ for all $i\in[n]$. The _hyperoctahedral group_ $B_{n}$
is the group of signed permutations of $[\pm n]$. In the case of $W=B_{n}$, we
have

$M(B_{n},q)=\prod_{k=0}^{n-1}\big{(}n-k+kq\big{)}.$ (1.6)

It is easy to see that this polynomial is the generating function for parking
functions of type $B$ with respect to their reluctant cars, i.e.,

$M(B_{n},q)=\sum_{\alpha\in{\mathrm{PF}}^{B}_{n}}q^{{\mathsf{reluc}}(\alpha)}.$
(1.7)

Biane [6] gave an edge labeling of ${\mathrm{NC}}(B_{n},c)$ that establishes a
bijection between the maximal chains ${\mathbf{w}}$ in
${\mathrm{NC}}(B_{n},c)$ and the parking functions $\alpha$ in
${\mathrm{PF}}^{B}_{n}$. However, this bijection is not in respect of the
statistics ${\mathsf{bad}}({\mathbf{w}})$ and ${\mathsf{reluc}}(\alpha)$,
either. We present a bijection that carries the bad edges in ${\mathbf{w}}$ to
the reluctant cars of $\alpha$ while preserving their relative order.

######  Theorem 1.3.

There is a bijection
$\varphi_{B}:\alpha\mapsto{\mathbf{w}}:e=\omega_{0}<\omega_{1}<\cdots<\omega_{n}=c$
between the parking functions in ${\mathrm{PF}}^{B}_{n}$ and the maximal
chains in ${\mathrm{NC}}(B_{n},c)$ such that the $i$th car of $\alpha$ is
reluctant if and only if $(\omega_{i-1},\omega_{i})$ is a bad edge.

###  1.4. Gamma-positivity of $M(B_{n},q)$

A polynomial $C(q)=c_{0}+c_{1}q+\cdots+c_{n}q^{n}$ with palindromic
coefficients (i.e., $c_{n-i}=c_{i}$) can be written as a sum of polynomials of
the form $q^{j}(1+q)^{n-2j}$,

$C(q)=\sum_{j=0}^{\lfloor n/2\rfloor}\gamma_{j}\,q^{j}(1+q)^{n-2j}.$

The palindromic polynomial $C(q)$ is said to be $\gamma$-_positive_ if
$\gamma_{j}\geq 0$ for all $j$. Several of the initial polynomials of
$M(B_{n},q)$ are listed below:

$\displaystyle M(B_{1},q)$ $\displaystyle=1,$ $\displaystyle M(B_{2},q)$
$\displaystyle=2+2q,$ $\displaystyle M(B_{3},q)$ $\displaystyle=6+15q+6q^{2},$
$\displaystyle M(B_{4},q)$ $\displaystyle=24+104q+104q^{2}+24q^{3},$
$\displaystyle M(B_{5},q)$
$\displaystyle=120+770q+1345q^{2}+770q^{3}+120q^{4}.$

These terms appear in an OEIS sequence [21, A071208]. Notice that these
palindromic polynomials can be expanded as follows.

$\displaystyle M(B_{1},q)$ $\displaystyle=1,$ $\displaystyle M(B_{2},q)$
$\displaystyle=2(1+q),$ $\displaystyle M(B_{3},q)$
$\displaystyle=6(1+q)^{2}+3q,$ $\displaystyle M(B_{4},q)$
$\displaystyle=24(1+q)^{3}+32q(1+q),$ $\displaystyle M(B_{5},q)$
$\displaystyle=120(1+q)^{4}+290q(1+q)^{2}+45q^{2}.$

For $0\leq k\leq\lfloor\frac{n-1}{2}\rfloor$, let $B(n,k)$ be the set of
$k$-tuples $(b_{1},b_{2},\dots,b_{k})$ of integers such that
$1<b_{1}<b_{2}<\cdots<b_{k}<n$ and $b_{i+1}-b_{i}>1$ for each $i\in[k-1]$. We
present the following interpretation of $\gamma$-positivity of the polynomial
$M(B_{n},q)$.

######  Theorem 1.4.

For all $n\geq 1$, we have

$M(B_{n},q)=\sum_{j=0}^{\lfloor(n-1)/2\rfloor}\gamma_{n,j}q^{j}(1+q)^{n-1-2j},$

where $\gamma_{n,j}$ counts the following objects:

  1. (i)

the parking functions $\alpha$ in ${\mathrm{PF}}^{B}_{n}$ with
${\mathsf{reluc}}(\alpha)=j$ such that there are no two consecutive reluctant
cars, and the last car of $\alpha$ is lucky;

  2. (ii)

the maximal chains ${\mathbf{w}}:e=\omega_{0}<\omega_{1}<\cdots<\omega_{n}=c$
in ${\mathrm{NC}}(B_{n},c)$ with ${\mathsf{bad}}({\mathbf{w}})=j$ such that
there are no two consecutive bad edges, and $(\omega_{n-1},\omega_{n})$ is a
good edge.

Moreover, $\gamma_{n,j}$ can be calculated by

$\gamma_{n,j}=n!\cdot\sum_{(b_{1},b_{2},\cdots,b_{j})\in
B(n,j)}\prod_{i=1}^{j}\left(\frac{n-b_{i}}{b_{i}}\right).$ (1.8)

The rest of this paper is organized as follows. We establish the bijections in
Theorems 1.2 and 1.3 in Sections 2 and 3, respectively. To prove the
$\gamma$-positivity of $M(B_{n},q)$, we prepare a bijective result, with words
on an alphabet with $n$ letters, for the enumeration of $\gamma$-coefficients
in Section 4. The proof of Theorem 1.4 is given in Section 5.

##  2\. Noncrossing partitions and parking functions of type $A$

###  2.1. Noncrossing partitions of type $A$

A _noncrossing partition_ of $[n]$ is a set partition with the condition that
there are no $a,b,c,d$ with $1\leq a<b<c<d\leq n$, $\\{a,c\\}$ contained in
some block of the partition, and $\\{b,d\\}$ contained in some other block.
The set of noncrossing partitions of $[n]$ forms a lattice
${\mathrm{NC}}_{n}$, ordered by reverse refinement, with maximum element
$\\{\\{1,2,\dots,n\\}\\}$ and minimum element
$\\{\\{1\\},\\{2\\},\dots,\\{n\\}\\}$.

Fix the symmetric group $\mathfrak{S}_{n+1}$ on $[n+1]$ and the Coxeter
element $c=(1,2,\dots,n+1)$. If we associate every permutation
$\sigma\in\mathfrak{S}_{n+1}$ with the partition of $[n+1]$ given by the cycle
structure of $\sigma$, this defines a poset isomorphism from
${\mathrm{NC}}(\mathfrak{S}_{n+1},c)$ to ${\mathrm{NC}}_{n+1}$ [5]. The
reflections of $\mathfrak{S}_{n+1}$ are the transpositions, i.e.,
$T=\\{(i,j):1\leq i<j\leq n+1\\}$. A maximal chain
${\mathbf{w}}:e=\omega_{0}<\omega_{1}<\cdots<\omega_{n}=c$ in
${\mathrm{NC}}(\mathfrak{S}_{n+1},c)$ corresponds to a factorization
$t_{1}t_{2}\cdots t_{n}$ of $c$ into $n$ reflections, where
$\omega^{-1}_{i-1}\omega_{i}=t_{i}\in T$.

Suppose $\delta=(d_{1},\dots,d_{m})$ is a cycle of $\sigma$ and $t$ is a
reflection with $t\leq\delta$ (in absolute order), say $t=(d_{i},d_{j})$,
where $i<j$. If we perform $t$ and then $\sigma$, observe that $\delta$ is
split into two cycles $(d_{1},\dots,d_{i},d_{j+1},\dots,d_{m})$ and
$(d_{i+1},\dots,d_{j})$ of $\sigma t$. Let ${\mathsf{cyc}}(\sigma)$ denote the
number of _cycles_ in $\sigma$. Notice that (e.g. [2, Lemma 4.1.5])

$\ell_{T}(\sigma)=n+1-{\mathsf{cyc}}(\sigma).$ (2.1)

Let $\sigma=\sigma(1)\sigma(2)\cdots\sigma(n+1)$. An _inversion_ of $\sigma$
is a pair $(\sigma(i),\sigma(j))$ such that $\sigma(i)>\sigma(j)$, $1\leq
i<j\leq n+1$. The _inversion number_ ${\mathsf{inv}}(\sigma)$ of $\sigma$ is
defined to be the number of inversions of $\sigma$. It is known [9,
Proposition 1.5.2] that

$\ell_{S}(\sigma)={\mathsf{inv}}(\sigma).$ (2.2)

Recall that $(\mu,\nu)$ is a good (bad, respectively) edge in
${\mathrm{NC}}(W,c)$ if $\ell_{S}(\mu)<\ell_{S}(\nu)$
($\ell_{S}(\mu)>\ell_{S}(\nu)$, respectively). By (2.1) and (2.2), we have the
following observations.

######  Lemma 2.1.

Let $(\mu,\nu)$ be an edge in ${\mathrm{NC}}(\mathfrak{S}_{n+1},c)$ with
$\mu^{-1}\nu=(i,j)$. We have

  1. (i)

$(\mu,\nu)$ is a good edge if ${\mathsf{inv}}(\mu)<{\mathsf{inv}}(\nu)$, and a
bad edge if ${\mathsf{inv}}(\mu)>{\mathsf{inv}}(\nu)$.

  2. (ii)

The entries $i$ and $j$ occur in the same cycle of $\nu$, and in two different
cycles of $\mu$.

######  Example 2.2.

Let $\nu=2\,3\,4\,5\,6\,7\,8\,1$, written in cycle notation as
$\nu=(1,2,\dots,8)$. Consider the transposition $t=(5,8)$. We obtain $\mu=\nu
t=2\,3\,4\,5\,1\,7\,8\,6$, written in cycle notation as
$\mu=(1,2,3,4,5)(6,7,8)$. Since ${\mathsf{inv}}(\nu)=7$ and
${\mathsf{inv}}(\mu)=6$, $(\mu,\nu)$ is a good edge.

The following observation will be used in Proposition 2.4 to distinguish
between good and bad edges in ${\mathrm{NC}}(\mathfrak{S}_{n+1},c)$.

######  Lemma 2.3.

If $\mu^{-1}\nu=(i,j)$ and $i<j$, we have
${\mathsf{inv}}(\mu)>{\mathsf{inv}}(\nu)$ if and only if $\nu(i)<\nu(j)$.

###### Proof.

Note that $\mu(i)=\nu(j)$, $\mu(j)=\nu(i)$ and $\mu(k)=\nu(k)$ for $k\neq
i,j$. The result follows from the definition of inversion number of a
permutation. ∎

######  Proposition 2.4.

Let $(\mu,\nu)$ be an edge of ${\mathrm{NC}}(\mathfrak{S}_{n+1},c)$ with
$\mu^{-1}\nu=(i,j)$, where $i<j$. Suppose $(d_{1},d_{2},\dots,d_{k})$ is the
cycle of $\nu$ containing $i$ and $j$ for some integers
$d_{1}<d_{2}<\cdots<d_{k}$. We have

  1. (i)

$(\mu,\nu)$ is a bad edge if $i,j\in\\{d_{1},\dots,d_{k-1}\\}$.

  2. (ii)

$(\mu,\nu)$ is a good edge if $i\in\\{d_{1},\dots,d_{k-1}\\}$ and $j=d_{k}$.

###### Proof.

Note that $\nu(d_{k})=d_{1}$ and $\nu(d_{r})=d_{r+1}$ for each $r\in[k-1]$. By
Lemmas 2.1 and 2.3, $(\mu,\nu)$ is a bad (good, respectively) edge if
$\nu(i)<\nu(j)$ ($\nu(i)>\nu(j)$, respectively). In the former case, we have
$i,j\in\\{d_{1},\dots,d_{k-1}\\}$, and in the latter case
$i\in\\{d_{1},\dots,d_{k-1}\\}$ and $j=d_{k}$. ∎

######  Example 2.5.

Suppose $\delta=(1,2,3,7,8)$ is a cycle of an element
$\nu\in{\mathrm{NC}}(\mathfrak{S}_{8},c)$ and $(\mu,\nu)$ is an edge with
$\mu^{-1}\nu\leq\delta$. Note that $(\mu,\nu)$ is a bad edge if
$\mu^{-1}\nu\in\\{(1,2),(2,3),(3,7),(1,3)$, $(2,7),(1,7)\\}$, and a good edge
if $\mu^{-1}\nu\in\\{(1,8),(2,8),(3,8),(7,8)\\}$.

By Proposition 2.4, note that there are $\binom{k}{2}$ edges $(\mu,\nu)$ with
transposition $\mu^{-1}\nu\leq\delta$, where
$\delta=(d_{1},d_{2},\dots,d_{k})$ is a cycle of $\nu$. Among them, $k-1$
edges are good. In the following result, these edges are partitioned into
$k-1$ sets with exactly one good edge in each set.

######  Lemma 2.6.

Suppose $\delta=(d_{1},\dots,d_{k})$ is a cycle of an element
$\nu\in{\mathrm{NC}}(\mathfrak{S}_{n+1},c)$ for some integers
$d_{1}<\cdots<d_{k}$, let $E_{1},\dots,E_{k-1}$ be a partition of the edges
$(\mu,\nu)$ with $\mu^{-1}\nu\leq\delta$, defined by

$E_{j}:=\\{(\mu,\nu):\mu^{-1}\nu=(d_{i},d_{i+j}),1\leq i\leq k-j\\}.$ (2.3)

Then the following properties hold.

  1. (i)

$|E_{j}|=k-j$.

  2. (ii)

Each $E_{j}$ contains exactly one good edge.

  3. (iii)

For any $(\mu,\nu)\in E_{j}$, the cycle $\delta$ is split by the transposition
$\mu^{-1}\nu$ into a $(k-j)$-cycle and a $j$-cycle.

###### Proof.

(i) That $|E_{j}|=k-j$ is clear. (ii) By Proposition 2.4, the edge $(\mu,\nu)$
with $\mu^{-1}\nu=(d_{k-j},d_{k})$ is the only good edge in $E_{j}$. (iii) For
any $(\mu,\nu)\in E_{j}$, say $\mu^{-1}\nu=(d_{i},d_{i+j})$, we observe that
$(d_{1},\dots,d_{i},d_{i+j+1},\dots,d_{k})$ and $(d_{i+1},\dots,d_{i+j})$ are
two cycles of $\mu$. ∎

###  2.2. The bijection $\varphi_{A}$

In what follows we shall establish a bijection $\varphi_{A}$ between the
parking functions in ${\mathrm{PF}}^{A}$ and the maximal chains in
${\mathrm{NC}}(\mathfrak{S}_{n+1},c)$.

Let $\alpha=(a_{1},\dots,a_{n})\in{\mathrm{PF}}^{A}_{n}$ with outcome
$\pi=(p_{1},\dots,p_{n})$. The following result shows that every entry $p_{i}$
determines a decomposition of the prefix $a_{1},\dots,a_{i-1}$ of $\alpha$
into two parking functions of certain sizes.

######  Lemma 2.7.

For all $j<i$, we have

  1. (i)

$p_{j}<p_{i}$ if and only if $a_{j}<p_{i}$;

  2. (ii)

$p_{j}>p_{i}$ if and only if $a_{j}>p_{i}$.

###### Proof.

Let $p_{i}=\ell$. Since the $j$th car precedes the $i$th car, the parking
space $\ell$ is empty when the $j$th car has parked. Thus, $a_{j}<\ell$
implies $p_{j}<\ell$. Since $a_{j}\leq p_{j}$, it follows that $p_{j}<\ell$
implies $a_{j}<\ell$. Thus, the assertion (i) follows.

The assertion (ii) is proved by the same argument. ∎

Let $\varphi_{A}(\alpha)={\mathbf{w}}$, where
${\mathbf{w}}:e=\omega_{0}<\omega_{1}<\cdots<\omega_{n}=c$, be the
corresponding maximal chain of $\alpha$, and let $t_{1}t_{2}\cdots t_{n}$ be
the corresponding factorization of $c=(1,2,\dots,n+1)$, where
$t_{i}=\omega^{-1}_{i-1}\omega_{i}$. We shall construct
$t_{1},t_{2},\dots,t_{n}$ in reverse order by the following procedure. When
working on $t_{i}$, the cycles of $\omega_{i}$ have been ordered
$\delta_{1}\cdots\delta_{n-i+1}$, and each cycle $\delta_{r}$ is associated
with a tuple $\zeta_{r}$ of consecutive integers of the same size as
$\delta_{r}$, where $\zeta_{1},\dots,\zeta_{n-i+1}$ form an interval partition
of $[n+1]$. In terms of parking spaces, this interval partition is obtained by
cutting after every empty space, i.e., the non-maximal entries of each
interval $\zeta_{r}$ have been occupied. Initially, we associate
$\omega_{n}=\delta_{1}$ with the $(n+1)$-tuple $\zeta_{1}=(1,2,\dots,n+1)$.

Algorithm A

For $i=n,\dots,1$, the reflection $t_{i}$ is determined by $a_{i}$ and $p_{i}$
as follows.

(i) Among the tuples $\zeta_{1},\dots,\zeta_{n-i+1}$, find the tuple that
contains the integer $p_{i}$, say $\zeta_{r}$. Let
$\zeta_{r}=(h+1,h+2,\dots,h+m+1)$ for some integers $h$ and $m$, say
$a_{i}=h+j$ and $p_{i}=h+k$, where $j\leq k$. Suppose the cycle $\delta_{r}$
is $(d_{1},d_{2},\dots,d_{m+1})$ for some integers
$d_{1}<d_{2}<\cdots<d_{m+1}$.

(ii) Set $t_{i}=(d_{j},d_{m+1-k+j})$. Note that $\delta_{r}$ is split by
$t_{i}$ into a $k$-cycle $\delta_{r,1}$ and a $(m-k+1)$-cycle $\delta_{r,2}$,
written in the order $\delta_{r,1}\delta_{r,2}$, where

$\delta_{r,1}=(d_{1},\dots,d_{j},d_{m+2-k+j},\dots,d_{m+1}),\qquad\delta_{r,2}=(d_{j+1},\dots,d_{m+1-k+j}).$
(2.4)

Their associated tuples $\zeta_{r,1},\zeta_{r,2}$ are obtained by cutting
$\zeta_{r}$ at the immediate right of $p_{i}$, i.e.,

$\zeta_{r,1}=(h+1,\dots,h+k),\qquad\zeta_{r,2}=(h+k+1,\dots,h+m+1).$ (2.5)

######  Example 2.8.

For $n=7$, let $\alpha=(2,2,6,1,6,1,3)$ with outcome $\pi=(2,3,6,1,7,4,5)$.
Let $\varphi_{A}(\alpha)=t_{1}t_{2}\cdots t_{7}$, where
$t_{i}=\omega^{-1}_{i-1}\omega_{i}$. The construction of
$t_{1},t_{2},\cdots,t_{7}$ is shown in Table 1, where the good and bad edges
are indicated by $\circ$ and $\times$, respectively, in the last column. Some
initial steps are described below.

  * •

$a_{7}=3$ and $p_{7}=5$. By $\delta_{1}=(1,\dots,8)$, we set $t_{7}=(3,6)$ and
then the cycle $\delta_{1}$ is split into $\delta_{1,1}=(1,2,3,7,8)$ and
$\delta_{1,2}=(4,5,6)$ associated with the tuples $\zeta_{1,1}=(1,2,3,4,5)$
and $\zeta_{1,2}=(6,7,8)$, respectively.

  * •

$a_{6}=1$ and $p_{6}=4$. Note that $p_{6}$ is contained in the tuple
$\zeta_{1}=(1,2,3,4,5)$ associated to
$\delta_{1}=(d_{1},\dots,d_{5})=(1,2,3,7,8)$. We set
$t_{6}=(d_{1},d_{2})=(1,2)$ and then the cycle $\delta_{1}$ is split into
$\delta_{1,1}=(1,3,7,8)$ and $\delta_{1,2}=(2)$ associated with the tuples
$\zeta_{1,1}=(1,2,3,4)$ and $\zeta_{1,2}=(5)$, respectively.

Table 1. The construction of the maximal chain $\varphi_{A}(\alpha)=t_{1}t_{2}\cdots t_{7}$ in Example 2.8. $i$ |  | $a_{i}$ | $p_{i}$ | $t_{i}$ | $\omega_{i}$ | $\zeta_{1}\cdots\zeta_{n-i+1}$ |  | $\circ\times$
---|---|---|---|---|---|---|---|---
7 |  | 3 | 5 |  | $(1,2,3,4,5,6,7,8)$ | $(1,2,3,4,5,6,7,8)$ |  |
|  |  |  | $(3,6)$ |  |  |  | $\times$
6 |  | 1 | 4 |  | $(1,2,3,7,8)(4,5,6)$ | $(1,2,3,4,5)(6,7,8)$ |  |
|  |  |  | $(1,2)$ |  |  |  | $\times$
5 |  | 6 | 7 |  | $(1,3,7,8)(2)(4,5,6)$ | $(1,2,3,4)(5)(6,7,8)$ |  |
|  |  |  | $(4,5)$ |  |  |  | $\times$
4 |  | 1 | 1 |  | $(1,3,7,8)(2)(4,6)(5)$ | $(1,2,3,4)(5)(6,7)(8)$ |  |
|  |  |  | $(1,8)$ |  |  |  | $\circ$
3 |  | 6 | 6 |  | $(1)(3,7,8)(2)(4,6)(5)$ | $(1)(2,3,4)(5)(6,7)(8)$ |  |
|  |  |  | $(4,6)$ |  |  |  | $\circ$
2 |  | 2 | 3 |  | $(1)(3,7,8)(2)(4)(6)(5)$ | $(1)(2,3,4)(5)(6)(7)(8)$ |  |
|  |  |  | $(3,7)$ |  |  |  | $\times$
1 |  | 2 | 2 |  | $(1)(3,8)(7)(2)(4)(6)(5)$ | $(1)(2,3)(4)(5)(6)(7)(8)$ |  |
|  |  |  | $(3,8)$ |  |  |  | $\circ$
0 |  |  |  |  | $(1)(3)(8)(7)(2)(4)(6)(5)$ | $(1)(2)(3)(4)(5)(6)(7)(8)$ |  |

######  Proposition 2.9.

We have

  1. (i)

The maximal chain $\varphi_{A}(\alpha)$ is well-defined.

  2. (ii)

For $1\leq i\leq n$, $(\omega_{i-1},\omega_{i})$ is a bad edge in
$\varphi_{A}(\alpha)$ if and only if the $i$th car of $\alpha$ is reluctant.

###### Proof.

(i) By the determination of $t_{i}$ in Algorithm A, it suffices to prove that
$a_{i}$ occurs in the same tuple as $p_{i}$ for each $i$. In the initial step,
the entries $a_{n},p_{n}$ are in the $(n+1)$-tuple
$\zeta_{1}=(1,2,\dots,n+1)$.

For $i\leq n$, suppose the entries $a_{i},p_{i}$ occur in the tuple
$\zeta_{r}=(h+1,\dots,h+m+1)$ associated to a cycle
$\delta_{r}=(d_{1},\dots,d_{m+1})$ of $\omega_{i}$, say $a_{i}=h+j$ and
$p_{i}=h+k$. By (2.5), the tuples $\zeta_{r,1}$ and $\zeta_{r,2}$ are obtained
from $\zeta_{r}$ by cutting after the entry $p_{i}$. By Lemma 2.7, $a_{i-1}$
occurs in the same tuple as $p_{i-1}$. Hence $\varphi_{A}(\alpha)$ is well-
defined.

(ii) We set $t_{i}=(d_{j},d_{m+1-k+j})$, where
$t_{i}=\omega_{i-1}^{-1}\omega_{i}$. By Proposition 2.4,
$(\omega_{i-1},\omega_{i})$ is a good (bad, respectively) edge if $j=k$
($j<k$, respectively), in which case $a_{i}=p_{i}$ ($a_{i}<p_{i}$,
respectively). The result follows. ∎

The map $\varphi_{A}^{-1}$ can be established by a reverse operation. Given a
maximal chain ${\mathbf{w}}:e=\omega_{0}<\omega_{1}<\cdots<\omega_{n}=c$ in
${\mathrm{NC}}(\mathfrak{S}_{n+1},c)$, let $t_{1}t_{2}\cdots t_{n}$ be the
factorization of $c$, where $t_{i}=\omega^{-1}_{i-1}\omega_{i}$. We shall
construct the corresponding parking function
$\varphi_{A}^{-1}({\mathbf{w}})=(a_{1},\dots,a_{n})$ with outcome
$\pi=(p_{1},\dots,p_{n})$ in reverse order by the following procedure.
Likewise, when working on $a_{i}$ and $p_{i}$, the cycles of $\omega_{i}$ have
been ordered $\delta_{1}\cdots\delta_{n-i+1}$ with an interval partition
$\zeta_{1},\dots,\zeta_{n-i+1}$ of $[n+1]$. Initially, we associate
$\omega_{n}=\delta_{1}$ with the $(n+1)$-tuple $\zeta_{1}=(1,2,\dots,n+1)$.

Algorithm B

For $i=n,\dots,1$, the entries $a_{i}$ and $p_{i}$ are determined by $t_{i}$
as follows.

(i) Among the cycles $\delta_{1},\dots,\delta_{n-i+1}$ of $\omega_{i}$, find
the cycle that is comparable with $t_{i}$, say $t_{i}\leq\delta_{r}$. Let
$\delta_{r}=(d_{1},\dots,d_{m+1})$ for some integers $d_{1}<\cdots<d_{m+1}$
and let $\zeta_{r}=(h+1,\dots,h+m+1)$ for some integer $h$. Suppose
$t_{i}=(d_{j},d_{k})$, where $j<k$.

(ii) Set $a_{i}=h+j$ and $p_{i}=h+m+1-k+j$. Note that the cycle $\delta_{r}$
is split by $t_{i}$ into a $(m+1-k+j)$-cycle $\delta_{r,1}$ and a
$(k-j)$-cycle $\delta_{r,2}$, where

$\delta_{r,1}=(d_{1},\dots,d_{j},d_{k+1},\dots,d_{m+1});\qquad\delta_{r,2}=(d_{j+1},\dots,d_{k}).$

For their associated tuples, we cut $\zeta_{r}$ after the entry $p_{i}$ into

$\zeta_{r,1}=(h+1,\dots,h+m+1-k+j);\qquad\zeta_{r,2}=(h+m+2-k+j,\dots,h+m+1).$

The proof of Theorem 1.2 is completed. The correspondence of the bijection
$\varphi_{A}$ for $n=3$ is listed in Table 2 for reference.

Table 2. The map $\varphi_{A}:\alpha\mapsto{\mathbf{w}}=t_{1}t_{2}t_{3}$ for all $\alpha\in{\mathrm{PF}}^{A}_{3}$. $\alpha$ |  | $\pi$ |  |  | ${\mathbf{w}}$ |  | $\circ\times$
---|---|---|---|---|---|---|---
123 |  | 123 |  |  | $(1,2)(2,3)(3,4)$ |  | $\circ\circ\circ$
132 |  | 132 |  |  | $(1,2)(3,4)(2,4)$ |
213 |  | 213 |  |  | $(2,3)(1,3)(3,4)$ |
231 |  | 231 |  |  | $(2,3)(3,4)(1,4)$ |
312 |  | 312 |  |  | $(3,4)(1,2)(2,4)$ |
321 |  | 321 |  |  | $(3,4)(2,4)(1,4)$ |
121 |  | 123 |  |  | $(1,3)(3,4)(1,2)$ |  | $\circ\circ\times$
122 |  | 123 |  |  | $(1,2)(2,4)(2,3)$ |
131 |  | 132 |  |  | $(1,4)(2,3)(1,3)$ |
211 |  | 213 |  |  | $(3,4)(1,4)(1,2)$ |
212 |  | 213 |  |  | $(2,4)(1,4)(2,3)$ |
311 |  | 312 |  |  | $(2,3)(1,4)(1,3)$ |
113 |  | 123 |  |  | $(1,3)(1,2)(3,4)$ |  | $\circ\times\circ$
221 |  | 231 |  |  | $(2,4)(2,3)(1,4)$ |
111 |  | 123 |  |  | $(1,4)(1,3)(1,2)$ |  | $\circ\times\times$
112 |  | 123 |  |  | $(1,4)(1,2)(2,3)$ |

Let $A_{n}(q):=M(\mathfrak{S}_{n+1},q)$. We observe that the polynomial
$A_{n}(q)$ satisfies the following recurrence relation.

######  Proposition 2.10.

For all $n\geq 1$, we have

$A_{n}(q)=\sum_{k=1}^{n}\big{(}1+(n-k)q\big{)}\binom{n-1}{k-1}A_{k-1}(q)A_{n-k}(q),$

with $A_{0}(q)=1$.

###### Proof.

We enumerate the factorization $t_{1}t_{2}\cdots t_{n}$ of $c$ into
transpositions inductively, which corresponds to a maximal chain in
${\mathrm{NC}}(\mathfrak{S}_{n+1},c)$.

Consider a family $T_{1},\dots,T_{n}$ of sets of transpositions given by

$T_{k}:=\\{(j,j+k):1\leq j\leq n+1-k\\}.$ (2.6)

The transposition $t_{n}$ is in one of the sets $T_{1},\dots,T_{n}$, say
$t_{n}\in T_{k}$. There are $n+1-k$ choices for $t_{n}$ (i.e.,
$|T_{k}|=n+1-k$). By Lemma 2.6, we observe that $(\omega_{n-1},\omega_{n})$ is
a bad edge if $t_{n}=(j,j+k)$ for each $j\in[n-k]$, and a good edge if
$t_{n}=(n+1-k,n+1)$. Moreover, $\omega_{n}$ is split by $t_{n}$ into an
$(n+1-k)$-cycle $\delta_{1}$ and a $k$-cycle $\delta_{2}$, and among
$t_{1},t_{2},\dots,t_{n-1}$ there are $n-k$ ($k-1$, respectively)
transpositions which are comparable with $\delta_{1}$ ($\delta_{2}$,
respectively). The generating $q$-polynomial for the maximal chains in the
$\delta_{1}$-noncrossing partition lattice ($\delta_{2}$-noncrossing partition
lattice, respectively) is $A_{n-k}(q)$ ($A_{k-1}(q)$, respectively). The
result follows. ∎

##  3\. Noncrossing partitions and parking functions of type $B$

###  3.1. Noncrossing partitions of type $B$

A set partition ${\mathcal{P}}$ of $[\pm n]$ is _invariant_ under sign change
if $P$ is a block of ${\mathcal{P}}$ then $-P$ is also a block of
${\mathcal{P}}$, where $-P=\\{-x:x\in P\\}$. We identify ${\mathcal{P}}$ with
a partition of $[2n]$ by sending $i\mapsto i$ for $i\in\\{1,2,\dots,n\\}$ and
$i\mapsto n-i$ for $i\in\\{-1,-2,\dots,-n\\}$. As introduced by Reiner [19],
the lattice ${\mathrm{NC}}^{B}_{n}$ of noncrossing partitions of type $B$ is
defined to be the sublattice of ${\mathrm{NC}}_{2n}$ consisting of partitions
which are invariant under sign change. An invariant block $P=-P$ of a
partition is called _zero block_. By the noncrossing condition, there is at
most one zero block in ${\mathcal{P}}$ and the nonzero blocks come in pairs.

Consider the group $B_{n}$ of signed permutations. Every permutation
$\omega\in B_{n}$ maps to the partition of $[\pm n]$ given by the cycle
structure of $\omega$. With respect to the Coxeter element

$c=(1,2,\dots,n,-1,-2,\dots,-n),$

this map defines a poset isomorphism from ${\mathrm{NC}}(B_{n},c)$ to
${\mathrm{NC}}^{B}_{n}$ (see [4], [10], [11]). In one-line notation, we write
$\omega=\omega(1)\omega(2)\cdots\omega(n)$ with bars to indicate negative
numbers. We also write $\omega$ in disjoint cycles. For example, if $\omega$
is determined by $\omega(1)=-3$, $\omega(2)=-2$, $\omega(3)=5$, $\omega(4)=4$,
$\omega(5)=6$ and $\omega(6)=-1$, we write

$\omega=\overline{3}\,\overline{2}\,5\,4\,6\,\overline{1}=(1,-3,-5,-6)(-1,3,5,6)(2,-2)(4)(-4).$

Note that $\omega$ maps to $\\{\\{1,-3,-5,-6\\}$, $\\{-1,3,5,6\\}$,
$\\{2,-2\\}$, $\\{4\\},\\{-4\\}\\}$, which is a noncrossing partition of type
$B$ with zero block $\\{2,-2\\}$.

The reflections of $B_{n}$ are signed permutations of the following three
kinds [9, Proposition 8.1.5]:

$\displaystyle(i,-i)$ for all $1\leq i\leq n$, (3.1)
$\displaystyle(i,j)(-i,-j)$ for all $1\leq i<j\leq n$,
$\displaystyle(i,-j)(-i,j)$ for all $1\leq i<j\leq n$.

A maximal chain ${\mathbf{w}}:e=\omega_{0}<\omega_{1}<\cdots<\omega_{n}=c$ in
${\mathrm{NC}}(B_{n},c)$ corresponds to a factorization $t_{1}t_{2}\cdots
t_{n}$ of $c$ into $n$ reflections, where $t_{i}=\omega^{-1}_{i-1}\omega_{i}$.

For any $\omega\in{\mathrm{NC}}(B_{n},c)$, the cycle structure of $\omega$
consists of at most one cycle of the form
$\delta_{0}=(d_{1},\dots,d_{k},-d_{1},\dots,-d_{k})$ and some pairs of the
form

$\delta_{1}=(d_{1},\dots,d_{\ell},-d_{\ell+1},\dots,-d_{k})(-d_{1},\dots,-d_{\ell},d_{\ell+1},\dots,d_{k}),$
(3.2)

where $0<d_{1}<\cdots<d_{k}$ and $1\leq\ell\leq k$. Following [10], we call
$\delta_{0}$ ($\delta_{1}$, respectively) a _balanced cycle_ (_paired cycle_ ,
respectively). Note that a reflection $t$ satisfies $t\leq\delta_{0}$ if
$t=(i,-i)$ or $(i,j)(-i,-j)$ for some $i,j\in\\{\pm d_{1},\dots,\pm d_{k}\\}$,
and $t\leq\delta_{1}$ if $t=(i,j)(-i,-j)$ for some
$i,j\in\\{d_{1},\dots,d_{\ell},-d_{\ell+1},\dots,-d_{k}\\}$. Let
${\mathsf{npc}}(\omega)$ denote the number of paired cycles of $\omega$. Note
that

$\ell_{T}(\omega)=n-{\mathsf{npc}}(\omega).$ (3.3)

We recall some facts about signed permutations; see [9, Section 8.1] for
details. The inversion number of $\omega$, denoted
${\mathsf{inv}}_{B}(\omega)$, can be calculated by

${\mathsf{inv}}_{B}(\omega):={\mathsf{inv}}(\omega(1)\cdots\omega(n))+\sum_{\\{j\in[n]\,:\,\omega(j)<0\\}}|\omega(j)|.$
(3.4)

For example, if $\omega=\overline{3}\,\overline{2}\,5\,4\,6\,\overline{1}$,
then ${\mathsf{inv}}_{B}(\omega)=4+6=10$. It is known [9, Proposition 8.1.1]
that

$\ell_{S}(\omega)={\mathsf{inv}}_{B}(\omega).$ (3.5)

The following results come from [9, Proposition 8.1.6], which will be used in
Propositions 3.2 and 3.5 to distinguish between good and bad edges in
${\mathrm{NC}}(B_{n},c)$.

######  Lemma 3.1.

For any edge $(\mu,\nu)$ of ${\mathrm{NC}}(B_{n},c)$, the following results
hold.

  1. (i)

If $\mu^{-1}\nu=(i,-i)$, where $1\leq i\leq n$, we have
${\mathsf{inv}}_{B}(\mu)>{\mathsf{inv}}_{B}(\nu)$ if and only if $\nu(i)>0$.

  2. (ii)

If $\mu^{-1}\nu=(i,j)(-i,-j)$, where $1\leq i<j\leq n$, we have
${\mathsf{inv}}_{B}(\mu)>{\mathsf{inv}}_{B}(\nu)$ if and only if
$\nu(i)<\nu(j)$ or, equivalently, $\nu(-j)<\nu(-i)$.

  3. (iii)

If $\mu^{-1}\nu=(i,-j)(-i,j)$, where $1\leq i<j\leq n$, we have
${\mathsf{inv}}_{B}(\mu)>{\mathsf{inv}}_{B}(\nu)$ if and only if
$\nu(-i)<\nu(j)$ or, equivalently, $\nu(-j)<\nu(i)$.

The following results characterize the good and bad edges whose reflections
are comparable with a balanced cycle.

######  Proposition 3.2.

Suppose $(\mu,\nu)$ is an edge in ${\mathrm{NC}}(B_{n},c)$ with reflection
$t=\mu^{-1}\nu\leq\delta$, where
$\delta=(d_{1},\dots,d_{m},-d_{1},\dots,-d_{m})$ is the balanced cycle of
$\nu$, for some integers $0<d_{1}<\cdots<d_{m}$. Then the following results
hold.

  1. (i)

For $t=(i,-i)$, where $i>0$, $(\mu,\nu)$ is a bad edge if
$i\in\\{d_{1},\dots,d_{m-1}\\}$, and a good edge if $i=d_{m}$.

  2. (ii)

For $t=(i,j)(-i,-j)$, where $0<i<j$, $(\mu,\nu)$ is a bad edge if
$i,j\in\\{d_{1},\dots,d_{m-1}\\}$, and a good edge if
$i\in\\{d_{1},\dots,d_{m-1}\\}$ and $j=d_{m}$.

  3. (iii)

For $t=(i,-j)(-i,j)$, where $0<i<j$, $(\mu,\nu)$ is a bad edge for all
$i,j\in\\{d_{1},\dots,d_{m}\\}$.

###### Proof.

(i) Note that $\nu(d_{m})=-d_{1}$ and $\nu(d_{r})=d_{r+1}$ for each
$r\in[m-1]$. For $t=(i,-i)$ and $i>0$, if $\nu(i)>0$ then by Lemma 3.1(i) we
have ${\mathsf{inv}}_{B}(\mu)>{\mathsf{inv}}_{B}(\nu)$ and hence $(\mu,\nu)$
is a bad edge. In this case, $i\in\\{d_{1},\dots,d_{m-1}\\}$. Otherwise,
$\nu(i)<0$. In this case, $i=d_{m}$ and $(\mu,\nu)$ is a good edge.

(ii) For $t=(i,j)(-i,-j)$ and $0<i<j$, if $\nu(i)<\nu(j)$ then by Lemma
3.1(ii) we have ${\mathsf{inv}}_{B}(\mu)>{\mathsf{inv}}_{B}(\nu)$ and hence
$(\mu,\nu)$ is a bad edge. In this case, $i,j\in\\{d_{1},\dots,d_{m-1}\\}$.
Otherwise, $\nu(i)>\nu(j)$. In this case, $i\in\\{d_{1},\dots,d_{m-1}\\}$,
$j=d_{m}$, and $(\mu,\nu)$ is a good edge.

(iii) For $t=(i,-j)(-i,j)$ and $0<i<j$, note that $\nu(-i)<\nu(j)$ for all
$i,j\in\\{d_{1},\dots,d_{m}\\}$ since $\nu(d_{m})=-d_{1}$ and
$\nu(-d_{r})=-d_{r+1}$ for each $r\in[m-1]$. By Lemma 3.1(iii),
${\mathsf{inv}}_{B}(\mu)>{\mathsf{inv}}_{B}(\nu)$ and hence $(\mu,\nu)$ is a
bad edge. ∎

By Proposition 3.2, there are $m^{2}$ edges $(\mu,\nu)$ with reflection
$\mu^{-1}\nu\leq\delta$, where $\delta=(d_{1},\dots,d_{m}$,
$-d_{1},\dots,-d_{m})$ is the balanced cycle of $\nu$. Among them, $m$ edges
are good. For convenience, we write $\delta=(d_{1},\dots,d_{2m})$ and use the
notation $d_{m+i}$ ($d_{2m+i}$, respectively) to stand for $-d_{i}$ ($d_{i}$,
respectively) for all $i\in[m]$ when working with congruence of indices modulo
$2m$.

######  Lemma 3.3.

Suppose $\delta=(d_{1},\dots,d_{2m})$ is the balanced cycle of an element
$\nu\in{\mathrm{NC}}(B_{n},c)$, where $0<d_{1}<\cdots<d_{m}$ and
$d_{m+i}=-d_{i}$ for all $i\in[m]$. Let $E_{1},\dots,E_{m}$ be a partition of
the edges $(\mu,\nu)$ with $\mu^{-1}\nu\leq\delta$, defined by

$E_{j}:=\begin{cases}\\{(\mu,\nu):\mu^{-1}\nu=(d_{i},d_{j+i})(d_{m+i},d_{m+j+i}),1\leq
i\leq m\\}&\text{if $1\leq j\leq m-1$;}\\\
\\{(\mu,\nu):\mu^{-1}\nu=(d_{i},d_{m+i}),1\leq i\leq m\\}&\text{if
$j=m$.}\end{cases}$

Then for $1\leq j\leq m$ the following properties hold.

  1. (i)

$|E_{j}|=m$.

  2. (ii)

Each $E_{j}$ contains exactly one good edge.

  3. (iii)

For any $(\mu,\nu)\in E_{j}$, the reflection $\mu^{-1}\nu$ splits the cycle
$\delta$ into a balanced cycle of size $2(m-j)$ and a paired cycle of size
$j$.

###### Proof.

(i) That $|E_{j}|=m$ is clear. (ii) By Proposition 3.2, the edge $(\mu,\nu)$
with $\mu^{-1}\nu=(d_{m},d_{2m})$ is the only good edge in $E_{m}$, and the
edge with $\mu^{-1}\nu=(d_{m-j},d_{m})(d_{2m-j},d_{2m})$ is the only good edge
in $E_{j}$ for $1\leq j\leq m-1$.

(iii) For any edge $(\mu,\nu)\in E_{m}$, say $\mu^{-1}\nu=(d_{i},d_{m+i})$,
the cycle $\delta$ is split by $\mu^{-1}\nu$ into a paired cycle
$(d_{1},\dots,d_{i},d_{m+i+1},\dots,d_{2m})(d_{m+1},\dots,d_{m+i}$,
$d_{i+1},\dots,d_{m})$ of size $m$. For $1\leq j\leq m-1$ and any edge
$(\mu,\nu)\in E_{j}$, say $\mu^{-1}\nu=(d_{i},d_{j+i})(d_{m+i},d_{m+j+i})$,
the cycle $\delta$ is split by $\mu^{-1}\nu$ into a balanced cycle
$(d_{1},\dots,d_{i},d_{i+j+1},\dots,d_{m+i},d_{m+i+j+1},\dots,d_{2m})$ and a
paired cycle $(d_{i+1},\dots,d_{i+j})(d_{m+i+1},\dots,d_{m+i+j})$. The result
follows. ∎

######  Example 3.4.

Suppose $\delta=(1,2,7,8,-1,-2,-7,-8)$ is the balanced cycle of $\nu$ and
$(\mu,\nu)$ is an edge in ${\mathrm{NC}}(B_{8},c)$ with
$\mu^{-1}\nu\leq\delta$. Note that $(\mu,\nu)$ is a good edge if
$\mu^{-1}\nu\in\\{(8,-8)$, $(1,8)(-1,-8)$, $(2,8)(-2,-8),(7,8)(-7,-8)\\}$.
Moreover, the reflections comparable with $\delta$ can be partitioned into the
following sets such that each set contains one reflection corresponding to a
good edge, i.e.,

$\displaystyle\\{(1,2)(-1,-2),(2,7)(-2,-7),(7,8)(-7,-8),(1,-8)(-1,8)\\};$
$\displaystyle\\{(1,7)(-1,-7),(2,8)(-2,-8),(1,-7)(-1,7),(2,-8)(-2,8)\\};$
$\displaystyle\\{(1,8)(-1,-8),(1,-2)(-1,2),(2,-7)(-2,7),(7,-8)(-7,8)\\};$
$\displaystyle\\{(1,-1),(2,-2),(7,-7),(8,-8)\\}.$

The following results characterize the good and bad edges in
${\mathrm{NC}}(B_{n},c)$ whose reflections are comparable with a paired cycle.

######  Proposition 3.5.

Suppose $(\mu,\nu)$ is an edge in ${\mathrm{NC}}(B_{n},c)$ with reflection
$t=\mu^{-1}\nu\leq\delta$, where
$\delta=(d_{1},\dots,d_{\ell},-d_{\ell+1},\dots,-d_{k})(-d_{1},\dots,-d_{\ell},d_{\ell+1},\dots,d_{k})$
is a paired cycle of $\nu$, for some integers $0<d_{1}<\cdots<d_{k}$ and
$1\leq\ell\leq k$. Write $\delta=(e_{1},\dots,e_{k})(-e_{1},\dots,-e_{k})$,
where

$e_{r}=\begin{cases}d_{r}&\mbox{if $1\leq r\leq\ell$;}\\\ -d_{r}&\mbox{if
$\ell+1\leq r\leq k$.}\end{cases}$

Then $t=(e_{i},e_{j})(-e_{i},-e_{j})$ for some $1\leq i<j\leq k$. Moreover,
$(\mu,\nu)$ is a good edge if $i$ and $j$ satisfy one of the following
conditions; otherwise, $(\mu,\nu)$ is a bad edge:

  1. (i)

$1\leq i<\ell$ and $j=\ell$;

  2. (ii)

$\ell\leq i<k$ and $j=k$.

###### Proof.

If $\ell=k$ then $\delta=(d_{1},\dots,d_{\ell})(-d_{1},\dots,-d_{\ell})$,
where $0<d_{1}<\cdots<d_{\ell}$. By the same argument as in the proof of
Proposition 3.2(ii), $(\mu,\nu)$ is a bad edge if
$e_{i},e_{j}\in\\{d_{1},\dots,d_{\ell-1}\\}$, and a good edge if
$e_{i}\in\\{d_{1},\dots,d_{\ell-1}\\}$ and $e_{j}=d_{\ell}$.

Let $\ell<k$. Note that $\nu(d_{\ell})=-d_{\ell+1}$, $\nu(d_{k})=-d_{1}$, and
$\nu(d_{r})=d_{r+1}$ for each $r\neq\ell,k$.

Case 1. If $e_{i}e_{j}>0$ then either
$e_{i},e_{j}\in\\{d_{1},\dots,d_{\ell}\\}$ or
$e_{i},e_{j}\in\\{-d_{\ell+1},\dots,-d_{k}\\}$. Note that if
$e_{i}\in\\{d_{1},\dots,d_{\ell-1}\\}$ and $e_{j}=d_{\ell}$ then
$\nu(e_{i})>\nu(e_{j})$ and that if $e_{i}\in\\{-d_{\ell+1},\dots,-d_{k-1}\\}$
and $e_{j}=-d_{k}$ then $\nu(e_{j})>\nu(e_{i})$. By Lemma 3.1(ii),
${\mathsf{inv}}_{B}(\mu)<{\mathsf{inv}}_{B}(\nu)$ and hence $(\mu,\nu)$ is a
good edge. Otherwise, $e_{i},e_{j}\in\\{d_{1},\dots,d_{\ell-1}\\}$
($e_{i},e_{j}\in\\{-d_{\ell+1},\dots,-d_{k-1}\\}$, respectively). In this
case, $\nu(e_{i})<\nu(e_{j})$ ($\nu(e_{j})<\nu(e_{i})$, respectively) and
hence $(\mu,\nu)$ is a bad edge.

Case 2. If $e_{i}e_{j}<0$, there are four cases:

  * •

$e_{i}\in\\{d_{1},\dots,d_{\ell-1}\\}$ and
$e_{j}\in\\{-d_{\ell+1},\dots,-d_{k-1}\\}$. We have
$\nu(e_{i})=\nu(d_{i})=d_{i+1}$ and $\nu(e_{j})=\nu(-d_{j})=-d_{j+1}$. Thus,
$\nu(e_{j})<\nu(e_{i})$. By Lemma 3.1(iii),
${\mathsf{inv}}_{B}(\mu)>{\mathsf{inv}}_{B}(\nu)$ and hence $(\mu,\nu)$ is a
bad edge.

  * •

$e_{i}=d_{\ell}$ and $e_{j}\in\\{-d_{\ell+1},\dots,-d_{k-1}\\}$. We have
$\nu(e_{i})=\nu(d_{\ell})=-d_{\ell+1}$ and $-d_{\ell+2}\geq\nu(e_{j})\geq-
d_{k}$. Thus, $\nu(e_{j})<\nu(e_{i})$. By Lemma 3.1(iii),
${\mathsf{inv}}_{B}(\mu)>{\mathsf{inv}}_{B}(\nu)$ and hence $(\mu,\nu)$ is a
bad edge.

  * •

$e_{i}\in\\{d_{1},\dots,d_{\ell-1}\\}$ and $e_{j}=-d_{k}$. We have
$d_{2}\leq\nu(e_{i})\leq d_{\ell}$ and $\nu(e_{j})=\nu(-d_{k})=d_{1}$. Thus,
$\nu(e_{j})<\nu(e_{i})$. By Lemma 3.1(iii),
${\mathsf{inv}}_{B}(\mu)>{\mathsf{inv}}_{B}(\nu)$ and hence $(\mu,\nu)$ is a
bad edge.

  * •

$e_{i}=d_{\ell}$ and $e_{j}=-d_{k}$. Since
$\nu(e_{j})=\nu(-d_{k})=d_{1}>-d_{\ell+1}=\nu(d_{\ell})=\nu(e_{i})$, by Lemma
3.1(iii), ${\mathsf{inv}}_{B}(\mu)<{\mathsf{inv}}_{B}(\nu)$ and hence
$(\mu,\nu)$ is a good edge.

The result follows. ∎

######  Example 3.6.

Suppose $\delta=(2,3,-7,-8,-9)(-2,-3,7,8,9)$ is a paired cycle of $\nu$ and
$(\mu,\nu)$ is an edge in ${\mathrm{NC}}(B_{9},c)$ with
$\mu^{-1}\nu\leq\delta$. Note that $(\mu,\nu)$ is a good edge if $\mu^{-1}\nu$
is one of the reflections in the set

$\\{(2,3)(-2,-3),(3,-9)(-3,9),(-7,-9)(7,9),(-8,-9)(8,9)\\},$

and a bad edge if $\mu^{-1}\nu$ is one of the reflections in the set

$\\{(2,-7)(-2,7),(2,-8)(-2,8),(2,-9)(-2,9),(3,-7)(-3,7),(3,-8)(-3,8),(-7,-8)(7,8)\\}.$

By Proposition 3.5, there are $\binom{k}{2}$ edges $(\mu,\nu)$ with reflection
$\mu^{-1}\nu\leq\delta$, where $\delta=(d_{1},\dots,d_{\ell}$,
$-d_{\ell+1},\dots,-d_{k})(-d_{1},\dots,-d_{\ell},d_{\ell+1},\dots,d_{k})$ is
a paired cycle of $\nu$. In the following result, these edges are partitioned
into $k-1$ sets with exactly one good edge in each set.

######  Lemma 3.7.

Suppose $(\mu,\nu)$ is an edge in ${\mathrm{NC}}(B_{n},c)$ with reflection
$t=\mu^{-1}\nu\leq\delta$, where
$\delta=(d_{1},\dots,d_{\ell},-d_{\ell+1},\dots,-d_{k})(-d_{1},\dots,-d_{\ell},d_{\ell+1},\dots,d_{k})$
is a paired cycle of $\nu$, for some integers $0<d_{1}<\cdots<d_{k}$ and
$1\leq\ell\leq k$. Write $\delta=(f_{1},\dots,f_{k})(-f_{1},\dots,-f_{k})$,
where

$f_{i}=\begin{cases}d_{\ell}&\mbox{if $i=1$}\\\ -d_{\ell+i-1}&\mbox{if $2\leq
i\leq k-\ell+1$}\\\ d_{i-k+\ell-1}&\mbox{if $k-\ell+2\leq i\leq
k$.}\end{cases}$ (3.6)

Let $F_{1},\dots,F_{k-1}$ be a partition of the edges $(\mu,\nu)$ with
$\mu^{-1}\nu\leq\delta$, defined by

$F_{j}:=\\{(\mu,\nu):\mu^{-1}\nu=(f_{i},f_{i+j})(-f_{i},-f_{i+j}),1\leq i\leq
k-j\\}.$ (3.7)

Then for $1\leq j\leq k-1$ the following properties hold.

  1. (i)

$|F_{j}|=k-j$.

  2. (ii)

Each $F_{j}$ contains exactly one good edge.

  3. (iii)

For any $(\mu,\nu)\in F_{j}$, the reflection $\mu^{-1}\nu$ splits $\delta$
into a paired cycle of size $k-j$ and a paired cycle of size $j$.

###### Proof.

(i) That $|F_{j}|=k-j$ is clear. (ii) By Proposition 3.5, the edge
$(\mu,\nu)\in F_{j}$ with

$\mu^{-1}\nu=\begin{cases}(f_{k-\ell+1-j},f_{k-\ell+1})(-f_{k-\ell+1-j},-f_{k-\ell+1})&\mbox{if
$1\leq j\leq k-\ell-1$};\\\ (f_{1},f_{j+1})(-f_{1},-f_{j+1})&\mbox{if
$k-\ell\leq j\leq k-1$}\end{cases}$ (3.8)

is the only good edge in $F_{j}$ since
$(f_{k-\ell+1-j},f_{k-\ell+1})=(-d_{k-j},-d_{k})$ for $1\leq j\leq k-\ell-1$,
$(f_{1},f_{k-\ell+1})=(d_{\ell},-d_{k})$, and
$(f_{1},f_{j+1})=(d_{\ell},d_{j-k+\ell})$ for $k-\ell+1\leq j\leq k-1$.

(iii) For any $(\mu,\nu)\in F_{j}$, say
$\mu^{-1}\nu=(f_{i},f_{i+j})(-f_{i},-f_{i+j})$, we observe that the cycle
$\delta$ is split by $\mu^{-1}\nu$ into a paired cycle
$(f_{1},\dots,f_{i},f_{i+j+1},\dots,f_{k})(-f_{1},\dots,-f_{i},-f_{i+j+1},\dots,-f_{k})$
and a paired cycle $(f_{i+1},\dots,f_{i+j})(-f_{i+1},\dots,-f_{i+j})$. ∎

###  3.2. The map $\varphi_{B}$

In what follows we shall establish a bijection $\varphi_{B}$ between the
parking functions in ${\mathrm{PF}}^{B}$ and the maximal chains in
${\mathrm{NC}}(B_{n},c)$.

Following Lemma 3.7, we assign an order for the edges in each set $F_{j}$ in
(3.7) such that the first edge is the good edge. This will be used in the
construction of the map $\varphi_{B}$.

Procedure C.1

By abuse of notation, for $1\leq j\leq k-\ell-1$, let $F_{j}$ denote the
sequence of reflections

$\displaystyle(-d_{k-j},-d_{k})(d_{k-j},d_{k}),(-d_{k-j+1},d_{1})(d_{k-j+1},-d_{1}),\dots,(d_{\ell-j-1},d_{\ell-1})(-d_{\ell-j-1},-d_{\ell-1}),$
$\displaystyle\quad(d_{\ell},-d_{\ell+j})(-d_{\ell},d_{\ell+j}),(-d_{\ell+1},-d_{\ell+j+1})(d_{\ell+1},d_{\ell+j+1}),\dots,(-d_{k-j-1},-d_{k-1})(d_{k-j-1},d_{k-1}).$

Moreover, for $k-\ell\leq j\leq k-1$, let $F_{j}$ denote the sequence of
reflections

$(f_{1},f_{j+1})(-f_{1},-f_{j+1}),(f_{2},f_{j+2})(-f_{2},-f_{j+2}),\dots,(f_{k-j},f_{k})(-f_{k-j},-f_{k});$

namely,

$\displaystyle F_{k-\ell}:\,$
$\displaystyle(d_{\ell},-d_{k})(-d_{\ell},d_{k}),(-d_{\ell+1},d_{1})(d_{\ell+1},-d_{1}),(-d_{\ell+2},d_{2})(d_{\ell+2},-d_{2}),\dots;$
$\displaystyle F_{k-\ell+1}:\,$
$\displaystyle(d_{\ell},d_{1})(-d_{\ell},-d_{1}),(-d_{\ell+1},d_{2})(d_{\ell+1},-d_{2}),\dots;$
$\displaystyle\vdots\,$ $\displaystyle F_{k-1}:\,$
$\displaystyle(d_{\ell},d_{\ell-1})(-d_{\ell},-d_{\ell-1}).$

######  Example 3.8.

Following Example 3.6, the reflections
$\mu^{-1}\nu\leq(2,3,-7,-8,-9)(-2,-3,7,8,9)$ are partitioned into the
following four sequences:

$\displaystyle F_{1}:\,$
$\displaystyle(-8,-9)(8,9),(-9,2)(9,-2),(3,-7)(-3,7),(-7,-8)(7,8);$
$\displaystyle F_{2}:\,$
$\displaystyle(-7,-9)(7,9),(-8,2)(8,-2),(3,-8)(-3,8);$ $\displaystyle
F_{3}:\,$ $\displaystyle(3,-9)(-3,9),(-7,2)(7,-2);$ $\displaystyle F_{4}:\,$
$\displaystyle(3,2)(-3,-2).$

Given a sequence $1=z_{1}<\cdots<z_{m}\leq n$ of integers, any
$\alpha=(a_{1},\dots,a_{m})\in\\{z_{1},\dots,z_{m}\\}^{m}$ can be regarded as
a parking function of type $B$, using $m$ parking spaces numbered by
$z_{1},\dots,z_{m}$. Let $\pi=(p_{1},\dots,p_{m})$ be the outcome of $\alpha$,
which is a permutation of $\\{z_{1},\dots,z_{m}\\}$. Next, we describe a
decomposition of $(a_{1},\dots,a_{m-1})$ into a parking function of type $B$
(possibly empty) and a parking function of type $A$ with respect to $p_{m}$.
To show this, we construct a specific set $Z_{0}$ from the prefix
$(p_{1},\dots,p_{m-1})$ of $\pi$ by the following procedure.

Procedure C.2

For $(p_{1},\dots,p_{m})$, if $p_{m}=1$ (i.e., $z_{1}$), let $Z_{0}$ be empty.
If $p_{m}\neq 1$, in the $(m-1)$-tuple $(p_{1},\dots,p_{m-1})$ find the
greatest integer $z_{g}$ such that all of $z_{1},z_{2},\dots,z_{g-1}$ occur to
the left of $z_{g}$, and then find the least integer $z_{m-h+1}$ such that all
of $z_{m},z_{m-1},\dots,z_{m-h+1}$ occur to the left of $z_{g}$ if any. Let
$Z_{0}$ denote the set $\\{z_{1},\dots,z_{g},z_{m-h+1},\dots,z_{m}\\}$. We
call $Z_{0}$ the _zeta-naught set_ of $(p_{1},\dots,p_{m-1})$. Let
$Z_{1}=\\{p_{1},\dots,p_{m-1}\\}\setminus Z_{0}$.

By a subword of $\alpha$ _induced_ on $Z_{0}$ ($Z_{1}$, respectively) we mean
the subword consisting of the entries $a_{i}$ such that $p_{i}\in Z_{0}$
($Z_{1}$, respectively). For example, consider a parking function
$\alpha=(3,8,8,7,8,5,5,7)$ in ${\mathrm{PF}}^{B}_{8}$ with outcome
$\pi=(p_{1},\dots,p_{8})=(3,8,1,7,2,5,6,4)$. The zeta-naught set of
$(p_{1},\dots,p_{7})$ is $Z_{0}=\\{1,2,7,8\\}$, and then $Z_{1}=\\{3,5,6\\}$.
The subword of $\alpha$ induced on $Z_{0}$ ($Z_{1}$, respectively) is
$(8,8,7,8)$ ($(3,5,5)$, respectively). The following result shows that the
subword of $\alpha$ induced on $Z_{0}$ ($Z_{1}$, respectively) is a parking
function of type $B$ ($A$, respectively).

######  Lemma 3.9.

For $1\leq j\leq m-1$, we have

  1. (i)

$p_{j}\in Z_{1}$ if and only if $a_{j}\in Z_{1}$. In this case, either
$a_{j}\leq p_{j}<p_{m}$ or $p_{m}<a_{j}\leq p_{j}$.

  2. (ii)

$p_{j}\in Z_{0}$ if and only if $a_{j}\in Z_{0}$.

###### Proof.

(i) If $p_{m}=1$ (i.e., $z_{1}$) then the space $1$ is last occupied. The set
$Z_{0}$ is empty and $Z_{1}$ is $\\{z_{2},\dots,z_{m}\\}$. Note that
$a_{j}\neq 1$ for each $j\in[m-1]$. Thus $a_{j}\in Z_{1}$, say
$a_{j}=z_{\ell}$. If $p_{j}<a_{j}$, the spaces
$z_{\ell},z_{\ell+1},\dots,z_{m}$ have been occupied when the $j$th car
arrives. Then the $j$th car will park at space $z_{1}$, a contradiction. Thus,
$p_{m}<a_{j}\leq p_{j}$. Let $p_{m}\neq 1$. Suppose the $k$th car parks at
space $z_{g}$, i.e., $z_{g}=p_{k}$ for some $k<m$.

($\Longrightarrow$) Suppose $p_{j}=z_{\ell^{\prime}}\in Z_{1}$. If $a_{j}\in
Z_{0}$, consider the following two cases.

  * •

$j>k$. The parking spaces $z_{g+1},\dots,z_{\ell^{\prime}-1}$ have been
occupied when the $j$th car arrives. It follows that the elements
$z_{1},z_{2},\dots,z_{\ell^{\prime}-1}$ occur to the left of
$z_{\ell^{\prime}}$ in $\pi$, which is against the choice of $z_{g}$.

  * •

$j<k$. The space $z_{g}$ is empty when the $j$th car has parked, and hence the
$j$th car parks at one of the spaces in $Z_{0}$, which is against $p_{j}\in
Z_{1}$.

Thus, we have $a_{j}\in Z_{1}$.

($\Longleftarrow$) Suppose $a_{j}=z_{\ell}\in Z_{1}$. If $p_{j}\in Z_{0}$, by
Procedure C.2 we have $j\leq k$. We observe that the parking spaces
$z_{\ell},z_{\ell+1}\dots,z_{m-h}$ have been occupied when the $j$th car
arrives. It follows that the elements $z_{\ell},z_{\ell+1}\dots,z_{m}$ occur
to the left of $z_{g}$ in $\pi$, which is against the choice of $z_{m-h+1}$.
Thus, we have $p_{j}\in Z_{1}$.

In the case of $a_{j},p_{j}\in Z_{1}$, if $a_{j}<p_{m}$ then the $j$th car
will park at a space before $p_{m}$ since the space $p_{m}$ is not occupied
until the last car arrives. Thus, $a_{j}\leq p_{j}<p_{m}$. Otherwise,
$a_{j}>p_{m}$ and the $j$th car will park at one of the spaces
$a_{j}=z_{\ell},z_{\ell+1},\dots,z_{m-h}$. Thus $p_{m}<a_{j}\leq p_{j}$. The
assertion (i) follows.

The assertion (ii) is proved by the same argument. ∎

We have a further observation about Lemma 3.9(i).

######  Lemma 3.10.

If $p_{m}\neq 1$ then the entries $p_{j}\in Z_{1}$ satisfying $p_{j}<p_{m}$
occur to the left of $z_{g}$ in $(p_{1},\dots,p_{m-1})$.

###### Proof.

By Procedure C.2, we observe that every element in $Z_{1}$ is greater than
$z_{g}$. Suppose $p_{j}=z_{\ell}\in Z_{1}$ is the least entry on the right of
$z_{g}$ in $(p_{1},\dots,p_{m-1})$. If $p_{j}<p_{m}$ then the elements
$z_{g+1},\dots,z_{\ell-1}$ occur to the left of $z_{g}$. It follows that all
of $z_{1},z_{2},\dots,z_{\ell-1}$ occur to the left of $z_{\ell}$, which is
against the choice of $z_{g}$. Hence $p_{j}>p_{m}$. The result follows. ∎

Now, we describe the map $\varphi_{B}$. Given
$\alpha=(a_{1},\dots,a_{n})\in{\mathrm{PF}}^{B}_{n}$ with outcome
$\pi=(p_{1},\dots,p_{n})$, let $\varphi_{B}(\alpha)={\mathbf{w}}$, where
${\mathbf{w}}:e=\omega_{0}<\omega_{1}<\cdots<\omega_{n}=c$ is a maximal chain
in ${\mathrm{NC}}(B_{n},c)$, and let $t_{1}t_{2}\cdots t_{n}$ be the
corresponding factorization of $c$, where $t_{i}=\omega^{-1}_{i-1}\omega_{i}$.
We shall construct the reflections $t_{1},t_{2},\dots,t_{n}$ in reverse order
by the following procedure. When working on $t_{i}$, the cycles of
$\omega_{i}$ have been ordered $\delta_{0}\delta_{1}\cdots\delta_{n-i}$, where
$\delta_{0}$ is the balanced cycle (possibly empty), and each $\delta_{j}$,
$j>0$, is a paired cycle. The cycle $\delta_{0}$ ($\delta_{j}$, respectively)
is associated with a tuple $\zeta_{0}$ ($\zeta_{j}$, respectively) of
integers, where $\zeta_{0},\zeta_{1},\dots,\zeta_{n-i}$ form a partition of
$[n]$. Initially, we associate $\omega_{n}=\delta_{0}$ with the $n$-tuple
$\zeta_{0}=(1,\dots,n)$. In the following, let $\overline{\ell}\pmod{m}$
denote the integer congruent to $\ell$ mod $m$ with $1\leq\overline{\ell}\leq
m$.

Algorithm C

For $i=n,\dots,1$, the reflection $t_{i}$ is determined by $a_{i}$ and $p_{i}$
as follows. Among the tuples $\zeta_{0},\dots,\zeta_{n-i}$, find the tuple
that contains the integer $p_{i}$. There are two cases.

Case 1. $p_{i}\in\zeta_{0}$. Suppose $\delta_{0}=(d_{1},\dots,d_{2m})$ for
some $m$, where $0<d_{1}<\cdots<d_{m}$ and $d_{m+i}=-d_{i}$ for all $i\in[m]$.
If $m=1$, we set $t_{i}=(d_{1},-d_{1})$.

Let $m>1$. Let $\zeta_{0}=(z_{1},\dots,z_{m})$, where $1=z_{1}<\cdots<z_{m}$,
say $p_{i}=z_{\ell}$ and $a_{i}=z_{\ell^{\prime}}$. Let
$j=\overline{\ell^{\prime}-\ell}\pmod{m}$.

If $p_{i}=1$, we set $t_{i}=(d_{m+j},d_{2m+j})$. Note that $\delta_{0}$ is
split by $t_{i}$ into a paired cycle $\delta^{\prime}_{1}$ of size $m$. We
associate $\delta^{\prime}_{1}$ with the $m$-tuple
$\zeta^{\prime}_{1}=(z_{2},\dots,z_{m},1^{*})$.

Otherwise, $p_{i}\neq 1$. Let $\pi_{0}$ be the subword of $\pi$ consisting of
the entries $p_{r}$ that occur in $\zeta_{0}$ and $r<i$. By Procedure C.2,
create the zeta-naught set $Z_{0}$ of $\pi_{0}$. Suppose $|Z_{0}|=m-k$ for
some $k\in[m-1]$, we set

$t_{i}=(d_{m-k+j},d_{m+j})(d_{2m-k+j},d_{2m+j}).$ (3.9)

Note that $\delta_{0}$ is split by $t_{i}$ into a balanced cycle
$\delta^{\prime}_{0}$ of size $2(m-k)$ and a paired cycle
$\delta^{\prime}_{1}$ of size $k$, written in the order
$\delta^{\prime}_{0}\delta^{\prime}_{1}$.

Let $\\{z_{1},\dots,z_{m}\\}\setminus Z_{0}=\\{z_{h+1},\dots,z_{h+k}\\}$ for
some integer $h$. Since $p_{i}\not\in Z_{0}$, $p_{i}=z_{h+b}$ for some $b$. We
associate $\delta^{\prime}_{0}$ with an $(m-k)$-tuple $\zeta^{\prime}_{0}$ and
associate $\delta^{\prime}_{1}$ with a $k$-tuple $\zeta^{\prime}_{1}$ by
setting

$\displaystyle\zeta^{\prime}_{0}$
$\displaystyle=(z_{1},\dots,z_{h},z_{h+k+1},\dots,z_{m});$ (3.10)
$\displaystyle\zeta^{\prime}_{1}$
$\displaystyle=(z_{h+b+1},\dots,z_{h+k},z_{h+1},\dots,z_{h+b-1},z_{h+b}^{*}).$
(3.11)

(The entry marked with a star, which equals $p_{i}$, in the tuple
$\zeta^{\prime}_{1}$ indicates that the corresponding parking space is not
occupied until the $i$th car arrives.)

Case 2. $p_{i}\in\zeta_{r}$ for some $r>0$. Suppose

$\delta_{r}=(d_{1},\dots,d_{\ell},-d_{\ell+1},\dots,-d_{k})(-d_{1},\dots,-d_{\ell},d_{\ell+1},\dots,d_{k})$

for some $k$, where $0<d_{1}<\cdots<d_{k}$ and $1\leq\ell\leq k$. Let
$\zeta_{r}=(y_{1},\dots,y_{k-1},y^{*}_{k})$, say $p_{i}=y_{j}$ and
$a_{i}=y_{j^{\prime}}$, for some $j^{\prime}\leq j\leq k-1$. (Currently, the
parking space $y_{k}$ is empty.)

Write $\delta_{r}=(f_{1},\dots,f_{k})(-f_{1},\dots,-f_{k})$ as defined in
(3.6). Using Procedure C.1, create a family $F_{1},\dots,F_{k-1}$ of sequences
of reflections from $\delta_{r}$, and then set $t_{i}$ to be the
$(j-j^{\prime}+1)$th reflection in the sequence $F_{k-j}$, say
$t_{i}=(f_{b},f_{b+k-j})(-f_{b},-f_{b+k-j})$ for some $b$. Note that
$\delta_{r}$ is split by $t_{i}$ into a paired cycle $\delta_{r,1}$ of size
$j$ and a paired cycle $\delta_{r,2}$ of size $k-j$, written in the order
$\delta_{r,1}\delta_{r,2}$, where

$\displaystyle\delta_{r,1}$
$\displaystyle=(f_{1},\dots,f_{b},f_{b+k-j+1},\dots,f_{k})(-f_{1},\dots,-f_{b},-f_{b+k-j+1},\dots,-f_{k});$
(3.12) $\displaystyle\delta_{r,2}$
$\displaystyle=(f_{b+1},\dots,f_{b+k-j})(-f_{b+1},\dots,-f_{b+k-j}).$

Their associated tuples $\zeta_{r,1},\zeta_{r,2}$ are obtained by cutting
$\zeta_{r}$ after the entry $p_{i}$, i.e.,

$\zeta_{r,1}=(y_{1},\dots,y_{j-1},y^{*}_{j});\qquad\zeta_{r,2}=(y_{j+1},\dots,y_{k-1},y_{k}).$
(3.13)

######  Example 3.11.

Let $\alpha=(3,8,8,7,8,5,5,7)\in{\mathrm{PF}}^{B}_{8}$ with outcome
$(3,8,1,7,2,5,6,4)$. Let $\varphi_{B}(\alpha)={\mathbf{w}}$, where
${\mathbf{w}}:\omega_{0}<\omega_{1}<\cdots<\omega_{8}$, and let
$t_{1}t_{2}\cdots t_{8}$ be the corresponding factorization of
$\omega_{8}=(1,\dots,8,-1,\dots,-8)$, where
$t_{i}=\omega_{i-1}^{-1}\omega_{i}$. The construction of $t_{1},\cdots,t_{8}$
is shown in Table 3. We use the abbreviation $[d_{1},\dots,d_{m}]$ for a
balanced cycle $(d_{1},\dots,d_{m},-d_{1},\dots,-d_{m})$, and the abbreviation
$(d_{1},\dots,d_{\ell},-d_{\ell+1},\dots,-d_{k})$ for a paired cycle in (3.2).
Moreover, the tuple $\zeta_{0}$ associated to a balanced cycle is underlined,
and the good and bad edges are indicated by $\circ$ and $\times$,
respectively. Some initial steps are described below.

(1) $a_{8}=7$ and $p_{8}=4$. Initially, $p_{8}$ occurs in
$\zeta_{0}=(1,\dots,8)$. We have $\overline{a_{8}-p_{8}}\equiv 3\pmod{8}$.
Creating the zeta-naught set of the sequence $(3,8,1,7,2,5,6)$, we have
$Z_{0}=\\{1,2,7,8\\}$ and hence $|Z_{0}|=4$. By (3.9), we set
$t_{8}=(7,-3)(-7,3)$. Then $\omega_{8}$ is split by $t_{8}$ into
$\delta^{\prime}_{0},\delta^{\prime}_{1}$, where
$\delta^{\prime}_{0}=(4,5,6,7,-4,-5,-6,-7)$ and
$\delta^{\prime}_{1}=(1,2,3,-8)(-1,-2,-3,8)$. For their associated tuples, we
set $\zeta^{\prime}_{0}=(1,2,7,8)$ and $\zeta^{\prime}_{1}=(5,6,3,4^{*})$.

(2) $a_{7}=5$ and $p_{7}=6$. Note that $p_{7}$ occurs in the tuple
$\zeta_{1}=(y_{1},y_{2},y_{3},y_{4})=(5,6,3,4^{*})$, which is associated to a
paired cycle $\delta_{1}=(1,2,3,-8)(-1,-2,-3,8)$. By Procedure C.1, create a
family $F_{1},F_{2},F_{3}$ of sequences of reflections from $\delta_{1}$:

$\displaystyle F_{1}:\,$
$\displaystyle(3,-8)(-3,8),(-8,1)(8,-1),(1,2)(-1,-2);$ $\displaystyle
F_{2}:\,$ $\displaystyle(3,1)(-3,-1),(-8,2)(8,-2);$ $\displaystyle F_{3}:\,$
$\displaystyle(3,2)(-3,-2).$

Since $a_{7}=y_{1}$ and $p_{7}=y_{2}$, we set $t_{7}=(-8,2)(8,-2)$, i.e., the
second reflection in $F_{2}$. Then $\delta_{1}$ is split by $t_{7}$ into
$\delta_{1,1},\delta_{1,2}$, where $\delta_{1,1}=(3,-8)(-3,8)$ and
$\delta_{1,2}=(1,2)(-1,-2)$. For their associated tuples, we set
$\zeta_{1,1}=(5,6^{*})$ and $\zeta_{1,2}=(3,4)$.

Table 3. The construction of the maximal chain $\varphi_{B}(\alpha)=t_{1}t_{2}\cdots t_{8}$ in Example 3.11. $i$ |  | $a_{i}$ | $p_{i}$ | $|Z_{0}|$ | $t_{i}$ | $\omega_{i}$ | $\zeta_{0}\zeta_{1}\cdots\zeta_{8-i}$ | $\circ\times$
---|---|---|---|---|---|---|---|---
8 |  | 7 | 4 | 4 |  | $[1,2,3,4,5,6,7,8]$ | $(\underline{1,2,3,4,5,6,7,8})$ |
|  |  |  |  | $(7,-3)(-7,3)$ |  |  | $\times$
7 |  | 5 | 6 |  |  | $[4,5,6,7](1,2,3,-8)$ | $(\underline{1,2,7,8})(5,6,3,4)$ |
|  |  |  |  | $(-8,2)(8,-2)$ |  |  | $\times$
6 |  | 5 | 5 |  |  | $[4,5,6,7](3,-8)(1,2)$ | $(\underline{1,2,7,8})(5,6)(3,4)$ |
|  |  |  |  | $(3,-8)(-3,8)$ |  |  | $\circ$
5 |  | 8 | 2 | 2 |  | $[4,5,6,7](3)(8)(1,2)$ | $(\underline{1,2,7,8})(5)(6)(3,4)$ |
|  |  |  |  | $(7,-5)(-7,5)$ |  |  | $\times$
4 |  | 7 | 7 |  |  | $[6,7](4,5)(3)(8)(1,2)$ | $(\underline{1,8})(7,2)(5)(6)(3,4)$ |
|  |  |  |  | $(4,5)(-4,-5)$ |  |  | $\circ$
3 |  | 8 | 1 | 0 |  | $[6,7](4)(5)(3)(8)(1,2)$ | $(\underline{1,8})(7)(2)(5)(6)(3,4)$ |
|  |  |  |  | $(6,-6)$ |  |  | $\times$
2 |  | 8 | 8 |  |  | $(6,-7)(4)(5)(3)(8)(1,2)$ | $(8,1)(7)(2)(5)(6)(3,4)$ |
|  |  |  |  | $(6,-7)(-6,7)$ |  |  | $\circ$
1 |  | 3 | 3 |  |  | $(6)(7)(4)(5)(3)(8)(1,2)$ | $(8)(1)(7)(2)(5)(6)(3,4)$ |
|  |  |  |  | $(1,2)(-1,-2)$ |  |  | $\circ$
0 |  |  |  |  |  | $(6)(7)(4)(5)(3)(8)(1)(2)$ | $(8)(1)(7)(2)(5)(6)(3)(4)$ |

######  Proposition 3.12.

We have

  1. (i)

The maximal chain $\varphi_{B}(\alpha)$ is well-defined.

  2. (ii)

For $1\leq i\leq n$, $(\omega_{i-1},\omega_{i})$ is a good edge in
$\varphi_{B}(\alpha)$ if and only if the $i$th car of $\alpha$ is lucky.

###### Proof.

(i) By Algorithm C, it suffices to prove that $a_{i}$ occurs in the same tuple
of integers as $p_{i}$ for each $i$.

In the initial step, $a_{n}$ and $p_{n}$ are in the $n$-tuple $(1,\dots,n)$,
$Z_{0}$ is the zeta-naught set of $(p_{1},\dots,p_{n-1})$, and
$Z_{1}=\\{p_{1},\dots,p_{n-1}\\}\setminus Z_{0}$. By Lemma 3.9, the subword of
$\alpha$ induced on $Z_{0}$ ($Z_{1}$, respectively) is a parking function of
type $B$ ($A$, respectively).

For $i\leq n-1$, suppose $p_{i}$ occurs in the tuple
$\zeta_{0}=(z_{1},\dots,z_{m})$ associated to a balanced cycle, the subword
$\alpha^{\prime}$ of $\alpha$ induced on $\\{z_{1},\dots,z_{m}\\}$ is a
parking function of type $B$. Hence $a_{i}$ occurs in $\zeta_{0}$. Moreover,
in Case 1 of the algorithm, we observe that $\alpha^{\prime}$ is decomposed
into a parking function of type $B$ ($A$, respectively) with parking spaces
$\zeta^{\prime}_{0}$ in (3.10) ($\zeta^{\prime}_{1}$ in (3.11), respectively).

On the other hand, suppose $p_{i}$ occur in the tuple
$\zeta_{r}=(y_{1},\dots,y_{k-1},y^{*}_{k})$ associated to a paired cycle, the
subword $\alpha^{\prime\prime}$ of $\alpha$ induced on
$\\{y_{1},\dots,y_{k-1}\\}$ is a parking function of type $A$. Hence
$a_{i}\in\\{y_{1},\dots,y_{k-1}\\}$. Moreover, in Case 2 of the algorithm,
$\alpha^{\prime\prime}$ is decomposed into two parking functions of type $A$
with parking spaces $\zeta_{r,1}$ and $\zeta_{r,2}$ in (3.13), respectively.

By induction, $a_{i-1}$ occurs in the same tuple as $p_{i-1}$. Hence
$\varphi_{B}(\alpha)$ is well-defined.

(ii) In Case 1, suppose $p_{i}$ occurs in the tuple
$\zeta_{0}=(z_{1},\dots,z_{m})$, say $p_{i}=z_{\ell}$. Then
$a_{i}=z_{\ell^{\prime}}$ for some $\ell^{\prime}\in[m]$. Let
$j=\overline{\ell^{\prime}-\ell}\pmod{m}$. We set

$t_{i}=\begin{cases}(d_{m+j},d_{2m+j})&\mbox{if $p_{i}=1$};\\\
(d_{m-k+j},d_{m+j})(d_{2m-k+j},_{2m+j})&\mbox{if $p_{i}\neq 1$}.\end{cases}$

By Proposition 3.2, $(\omega_{i-1},\omega_{i})$ is a good edge if and only if
$j=m$ (i.e., $a_{i}=p_{i}$), in which case the $i$th car of $\alpha$ is lucky.

In Case 2, suppose $p_{i}$ occurs in a tuple
$\zeta_{r}=(y_{1},\dots,y_{k-1},y_{k}^{*})$, say $p_{i}=y_{j}$, we have
$a_{i}=y_{j^{\prime}}$ for some $1\leq j^{\prime}\leq j\leq k-1$. Note that
there are $j$ reflections in the sequence $F_{k-j}$, and that we set $t_{i}$
to be the $(j-j^{\prime}+1)$th reflection in $F_{k-j}$. By Lemma 3.7 and
Procedure C.1, $(\omega_{i-1},\omega_{i})$ is a good edge if and only if
$j^{\prime}=j$, in which case the $i$th car of $\alpha$ is lucky. The result
follows. ∎

The injectivity of the map $\varphi_{B}$ from the parking functions in
${\mathrm{PF}}^{B}_{n}$ to the maximal chains in ${\mathrm{NC}}(B_{n},c)$ is
proved. By (1.6) and (1.7), these two statistics ${\mathsf{reluc}}$ and
${\mathsf{bad}}$ share the same distribution. Thus, Theorem 1.3 follows. In
what follows we do establish the inverse map $\varphi_{B}^{-1}$ to prove the
surjectivity.

###  3.3. The map $\varphi_{B}^{-1}$

Given a maximal chain
${\mathbf{w}}:e=\omega_{0}<\omega_{1}<\cdots<\omega_{n}=c$ in
${\mathrm{NC}}(B_{n},c)$, let $t_{1}t_{2}\cdots t_{n}$ be the corresponding
factorization of $c$, where $\omega^{-1}_{i-1}\omega_{i}=t_{i}$. Let
$\varphi_{B}^{-1}({\mathbf{w}})=\alpha=(a_{1},\dots,a_{n})\in{\mathrm{PF}}^{B}_{n}$
with outcome $\pi=(p_{1},\dots,p_{n})$. The construction of $\alpha$ is
described in two procedures. The first procedure is for constructing the
subword of $\alpha$ corresponding to a paired cycle, which is the reverse
operation in Case 2 of Algorithm C.

Procedure D.1

Given a subword $\delta=t_{i_{1}}t_{i_{2}}\cdots t_{i_{k-1}}$ of
${\mathbf{w}}$ and a $k$-tuple $\zeta=(z_{1},\dots,z_{k-1},z^{*}_{k})$
associated to $\delta$, where $\delta$ is a paired cycle of size $k$ and
$1\leq i_{1}<\dots<i_{k-1}<n$, we construct $\alpha^{\prime}$ and
$\pi^{\prime}$ such that
$\alpha^{\prime}=(a_{i_{1}},\dots,a_{i_{k-1}})\in\\{z_{1},\dots,z_{k-1}\\}^{k-1}$
and $\pi^{\prime}=(p_{i_{1}},\dots,p_{i_{k-1}})$ is a permutation of
$\\{z_{1},\dots,z_{k-1}\\}$ by the following procedure. Suppose

$\delta=(d_{1},\dots,d_{\ell},-d_{\ell+1},\dots,-d_{k})(-d_{1},\dots,-d_{\ell},d_{\ell+1},\dots,d_{k}),$
(3.14)

for some integers $0<d_{1}<\cdots<d_{k}$ and $1\leq\ell\leq k$.

(i) Write $\delta=(f_{1},\dots,f_{k})(-f_{1},\dots,-f_{k})$ as defined in
(3.6). Using Procedure C.1, create a family $F_{1},\dots,F_{k-1}$ of sequences
of reflections from $\delta$. Suppose $t_{i_{k-1}}$ is the $i$th reflection in
$F_{j}$, we set $a_{i_{k-1}}=z_{k-j+1-i}$ and $p_{i_{k-1}}=z_{k-j}$. Note that
$\delta$ is split by $t_{i_{k-1}}$ into a paired cycle $\delta_{1}$
($\delta_{2}$, respectively) of size $k-j$ ($j$, respectively), written in the
order $\delta_{1}\delta_{2}$. We associate $\delta_{1}$ and $\delta_{2}$ with
a $(k-j)$-tuple $\zeta_{1}$ and a $j$-tuple $\zeta_{2}$, respectively, by
setting

$\zeta_{1}=(z_{1},\dots,z_{k-j-1},z^{*}_{k-j});\qquad\zeta_{2}=(z_{k-j+1},\dots,z_{k-1},z^{*}_{k}).$

(ii) The rest of entries of $\alpha^{\prime}$ and $\pi^{\prime}$ can be
obtained from $\delta_{1}$ and $\delta_{2}$ by iteration of (i) inductively.

######  Example 3.13.

Suppose a paired cycle $\delta=(1,2,3,-8,-9,)(-1,-2,-3,8,9)$ is factorized as
$\delta=t_{i_{1}}t_{i_{2}}t_{i_{3}}t_{i_{4}}$, where $t_{i_{1}}=(2,-9)(-2,9)$,
$t_{i_{2}}=(3,-8)(-3,8)$, $t_{i_{3}}=(1,-9)(-1,9)$, and
$t_{i_{4}}=(2,-8)(-2,8)$. Let $\zeta=(z_{1},\dots,z^{*}_{5})=(6,7,3,4,5^{*})$
be the tuple associated to $\delta$. Using Procedure C.1, create a family
$F_{1},\dots,F_{4}$ of sequences of reflections from $\delta$:

$\displaystyle F_{1}:\,$
$\displaystyle(-8,-9)(8,9),(-9,1)(9,-1),(1,2)(-1,-2),(3,-8)(-3,8);$
$\displaystyle F_{2}:\,$
$\displaystyle(3,-9)(-3,9),(-8,1)(8,-1),(-9,2)(9,-2);$ $\displaystyle
F_{3}:\,$ $\displaystyle(3,1)(-3,-1),(-8,2)(8,-2);$ $\displaystyle F_{4}:\,$
$\displaystyle(3,2)(-3,-2).$

Note that $t_{i_{4}}=(-8,2)(8,-2)$ is the second reflection in $F_{3}$, we set
$a_{i_{4}}=z_{1}=6$ and $p_{i_{4}}=z_{2}=7$. Then $\delta$ is split into
$\delta_{1},\delta_{2}$, where $\delta_{1}=(3,-8)(-3,8)$ and
$\delta_{2}=(1,2,-9)(-1,-2,9)$ associated with the tuples
$\zeta_{1}=(6,7^{*})$ and $\zeta_{2}=(3,4,5^{*})$, respectively.

The construction of the corresponding words $\alpha^{\prime}=(3,6,3,6)$ and
$\pi^{\prime}=(3,6,4,7)$ is shown in Table 4, where the notation for paired
cycles is abbreviated and the working $\delta$ is underlined.

Table 4. The construction of $\alpha^{\prime}$ and $\pi^{\prime}$ in Example 3.13. $j$ |  | $t_{i_{j}}$ | $\delta$ | $\zeta$ | $a_{i_{j}}$ | $p_{i_{j}}$ |  | $\circ\times$
---|---|---|---|---|---|---|---|---
4 |  | $(-8,2)(8,-2)$ | $(\underline{1,2,3,-8,-9})$ | $(6,7,3,4,5^{*})$ | 6 | 7 |  | $\times$
3 |  | $(-9,1)(9,-1)$ | $(3,-8)(\underline{1,2,-9})$ | $(6,7^{*})(3,4,5^{*})$ | 3 | 4 |  | $\times$
2 |  | $(3,-8)(-3,8)$ | $(\underline{3,-8})(2,-9)(1)$ | $(6,7^{*})(3,4^{*})(5^{*})$ | 6 | 6 |  | $\circ$
1 |  | $(2,-9)(-2,9)$ | $(3)(8)(\underline{2,-9})(1)$ | $(6^{*})(7^{*})(3,4^{*})(5)$ | 3 | 3 |  | $\circ$
|  |  | $(3)(8)(2)(9)(1)$ | $(6^{*})(7^{*})(3^{*})(4^{*})(5^{*})$ |  |  |  |

Now, we present the map $\varphi_{B}^{-1}$, which is essentially constructed
by the reverse operation in Case 1 of Algorithm C. Given a maximal chain
${\mathbf{w}}:e=\omega_{0}<\omega_{1}<\cdots<\omega_{n}=c$, find the (unique)
chain $e=\omega_{j_{0}}<\omega_{j_{1}}<\cdots<\omega_{j_{b}}=\omega_{n}$
satisfying the following conditions.

  1. (D1)

For $1\leq i\leq b$, each $\omega_{j_{i}}$ contains a balanced cycle.

  2. (D2)

The integer $j_{1}$ is the least index such that $\omega_{j_{1}}$ contains a
balanced cycle.

  3. (D3)

For $2\leq i\leq b$, the integer $j_{i}$ is the least index such that the
balanced cycle of $\omega_{j_{i-1}}$ is properly contained in the balanced
cycle of $\omega_{j_{i}}$.

The map $\varphi_{B}^{-1}$ is described by an inductive procedure for
constructing the subword of $\alpha$ corresponding to the balanced cycle of
$\omega_{j_{i}}$ for $i=1,2,\dots,b$.

Algorithm D

(i) For the base step, suppose $\delta=t_{i_{1}}t_{i_{2}}\dots t_{i_{h}}$ is
the balanced cycle of $\omega_{j_{1}}$ for some integers $1\leq
i_{1}<i_{2}<\cdots<i_{h}=j_{1}$, we associate $\delta$ with the $h$-tuple
$\zeta=(1,n-h+2,n-h+3,\dots,n)$. The corresponding subword
$(a_{i_{1}},a_{i_{2}},\dots,a_{i_{h}})$ of $\alpha$ and the subword
$(p_{i_{1}},p_{i_{2}},\dots,p_{i_{h}})$ of $\pi$ are constructed as follows.

Suppose $\delta=(d_{1},\dots,d_{h},-d_{1},\dots,-d_{h})$ for some integers
$0<d_{1}<\cdots<d_{h}$. If $h=1$, set $a_{i_{h}}=p_{i_{h}}=1$ and we are done.
Let $h>1$. Since $\delta$ is split by $t_{i_{h}}$ into a paired cycle
$\delta_{1}$ of size $h$, note that $t_{i_{h}}=(d_{j},-d_{j})$ for some
$j\in[h]$. We set $p_{i_{h}}=1$ and set

$a_{i_{h}}=\begin{cases}1&\mbox{if $t_{i_{h}}=(d_{h},-d_{h})$;}\\\
n+1-h+j&\mbox{if $t_{i_{h}}=(d_{j},-d_{j})$ and $1\leq j\leq
h-1$.}\end{cases}$ (3.15)

We associate $\delta_{1}=t_{i_{1}}t_{i_{2}}\cdots t_{i_{h-1}}$ with the
$h$-tuple $\zeta_{1}=(n-h+2,n-h+3,\dots,n,1^{*})$. Using $\delta_{1}$,
$\zeta_{1}$ and Procedure D.1, we obtain the remaining entries
$a_{i_{1}},a_{i_{2}},\dots,a_{i_{h-1}}$ and
$p_{i_{1}},p_{i_{2}},\dots,p_{i_{h-1}}$.

(ii) For the inductive step, suppose $\delta=t_{u_{1}}t_{u_{2}}\cdots
t_{u_{m}}$ is the balanced cycle of $\omega_{j_{i}}$ ($i\geq 2$) for some
integers $1\leq u_{1}<u_{2}<\cdots<u_{m}=j_{i}$, we shall construct the
corresponding subword $(a_{u_{1}},a_{u_{2}},\dots,a_{u_{m}})$ of $\alpha$ and
the subword $(p_{u_{1}},p_{u_{2}},\dots,p_{u_{h}})$ of $\pi$.

Let $\delta_{0}=t_{v_{1}}t_{v_{2}}\cdots t_{v_{m^{\prime}}}$ be the balanced
cycle of $\omega_{j_{i-1}}$ for some integers $1\leq
v_{1}<v_{2}<\cdots<v_{m^{\prime}}=j_{i-1}$. By (D3),
$\\{v_{1},\dots,v_{m^{\prime}}\\}\subset\\{u_{1},\dots,u_{m}\\}$. Assume that
the words $(a_{v_{1}},\dots,a_{v_{m^{\prime}}})$ and
$(p_{v_{1}},\dots,p_{v_{m^{\prime}}})$ corresponding to $\delta_{0}$ have been
determined, where $p_{v_{m^{\prime}}}=\ell$ for some $\ell\geq 1$. Then the
$m^{\prime}$-tuple $\zeta_{0}$ associated to $\delta_{0}$ is

$\zeta_{0}=(1,2,\dots,\ell,n-m^{\prime}+\ell+1,n-m^{\prime}+\ell+2,\dots,n).$
(3.16)

The remaining entries of $(a_{u_{1}},a_{u_{2}},\dots,a_{u_{m}})$ and
$(p_{u_{1}},p_{u_{2}},\dots,p_{u_{m}})$ are constructed as follows.

Suppose $\delta=(d_{1},\dots,d_{m},-d_{1},\dots,-d_{m})$, where
$0<d_{1}<\cdots<d_{m}$. Note that $\delta$ is split by $t_{u_{m}}$ into the
balanced cycle $\delta_{0}$ of size $m^{\prime}$ and a paired cycle
$\delta_{1}$ of size $m-m^{\prime}$. We determine the integer $j\in[m]$ such
that $t_{u_{m}}$ is written as

$t_{u_{m}}=(d_{m^{\prime}+j},d_{m+j})(d_{m+m^{\prime}+j},d_{2m+j}).$ (3.17)

Moreover, $\delta_{1}$ consists of the reflections $t_{r}$ such that
$r\in\\{u_{1},\dots,u_{m-1}\\}\setminus\\{v_{1},\dots,v_{m^{\prime}}\\}$, say
$\delta_{1}=t_{u_{i_{1}}}t_{u_{i_{2}}}\cdots t_{u_{i_{m-m^{\prime}-1}}}$,
where $1\leq i_{1}<i_{2}<\cdots<i_{m-m^{\prime}-1}\leq m-1$. As an
intermediate stage, we associate $\delta_{1}$ with the $(m-m^{\prime})$-tuple
$\zeta^{\prime}_{1}=(1,\dots,m-m^{\prime}-1,(m-m^{\prime})^{*})$, and
construct a pair $(\alpha^{\prime},\pi^{\prime})$ from $\delta_{1}$ and
$\zeta^{\prime}_{1}$ by using Procedure D.1, where
$\alpha^{\prime}=\big{(}a_{u_{i_{1}}},a_{u_{i_{2}}}\dots,a_{u_{i_{m-m^{\prime}-1}}}\big{)}\in[m-m^{\prime}-1]^{m-m^{\prime}-1}$
and
$\pi^{\prime}=\big{(}p_{u_{i_{1}}},p_{u_{i_{2}}},\dots,p_{u_{i_{m-m^{\prime}-1}}}\big{)}$
is a permutation of $[m-m^{\prime}-1]$.

Among the entries of $\pi^{\prime}$, find the least integer $m-m^{\prime}-b$
such that all of $m-m^{\prime}-1,m-m^{\prime}-2,\dots,m-m^{\prime}-b$ occur to
the left of $p_{v_{m^{\prime}}}$, i.e.,
$p_{u_{i_{j}}}\in\\{m-m^{\prime}-1,m-m^{\prime}-2,\dots,m-m^{\prime}-b\\}$
implies $u_{i_{j}}<v_{m^{\prime}}$ (possibly all of the entries of
$\pi^{\prime}$ occur to the right of $p_{v_{m^{\prime}}}$, in which case
$b=0$). With this integer $b$, we obtain from (3.16) the $m$-tuple $\zeta$
associated to $\delta$ by setting

$\displaystyle\zeta$ $\displaystyle=(z_{1},\dots,z_{m})$ (3.18)
$\displaystyle=(1,2,\dots,\ell+b+1,n-m+\ell+b+2,n-m+\ell+b+3,\dots,n).$

Then we set $p_{u_{m}}=\ell+b+1$, say $p_{u_{m}}=z_{r}$. Using the integer $j$
from (3.17), we set $a_{u_{m}}=z_{r^{\prime}}$, where
$r^{\prime}=\overline{r+j}\pmod{m}$. From (3.16) and (3.18), we replace
$\zeta^{\prime}_{1}$ by the $(m-m^{\prime})$-tuple

$\zeta_{1}=(n-m+\ell+b+2,n-m+\ell+b+3,\dots,n-m^{\prime}+\ell,\ell+1,\dots,\ell+b,(\ell+b+1)^{*}).$
(3.19)

Using $\delta_{1}$, $\zeta_{1}$ and Procedure D.1, we obtain the requested
entries $a_{u_{i_{1}}},a_{u_{i_{2}}}\dots,a_{u_{i_{m-m^{\prime}-1}}}$ and
$p_{u_{i_{1}}},p_{u_{i_{2}}},\dots,p_{u_{i_{m-m^{\prime}-1}}}$.

######  Example 3.14.

Let ${\mathbf{w}}$ be a maximal chain in ${\mathrm{NC}}(B_{9},c)$ with the
corresponding factorization $t_{1}t_{2}\cdots t_{9}$ of $c$ given in Table 5,
where we find the chain $e=\omega_{0}<\omega_{4}<\omega_{7}<\omega_{9}$
satisfying the conditions (D1)-(D3). The construction of
$\varphi_{B}^{-1}({\mathbf{w}})=\alpha=(a_{1},\dots,a_{9})$ with outcome
$\pi=(p_{1},\dots,p_{9})$ is described below.

(1) For the initial step, we observe that the balanced cycle of $\omega_{4}$
is $\delta=t_{2}t_{4}=(4,7,-4,-7)$, and hence we associate $\delta$ with
$\zeta=(1,9)$. Since $t_{4}=(4,-4)$, by (3.15) we set $p_{4}=1$ and $a_{4}=9$.
Using $\delta_{1}=t_{2}$ and $\zeta_{1}=(9,1^{*})$, we obtain $a_{2}=9$ and
$p_{2}=9$ by Procedure D.1.

(2) The balanced cycle of $\omega_{7}$ is
$\delta=t_{2}t_{4}t_{5}t_{7}=(4,5,6,7,-4,-5,-6,-7)$, which is split by $t_{7}$
into $\delta_{0}=t_{2}t_{4}$ and $\delta_{1}=t_{5}$. Since
$t_{7}=(4,6)(-4,-6)$, by (3.17) we determine the integer $j=3$ (in this case,
$m^{\prime}=2$ and $m=4$). Note that $\pi^{\prime}=(p_{5})$ is on the right of
$p_{4}$. By (3.18), we determine the tuple
$\zeta=(z_{1},z_{2},z_{3},z_{4})=(1,2,8,9)$ (in this case, $b=0$). We set
$p_{7}=2=z_{2}$ and set $a_{7}=z_{1}=1$ (in this case, $r=2$ and $j=3$). By
(3.19), we have $\zeta_{1}=(8,2^{*})$. Using $\delta_{1}=t_{5}=(5,6)(-5,-6)$
and $\zeta_{1}$, we obtain the entries $a_{5}=8$ and $p_{5}=8$ by Procedure
D.1.

(3) The balanced cycle of $\omega_{9}$ is $\delta=t_{1}t_{2}\cdots
t_{9}=(1,\dots,9,-1,\dots,-9)$, which is split by $t_{9}$ splits into
$\delta_{0}=t_{2}t_{4}t_{5}t_{7}$ and
$\delta_{1}=t_{1}t_{3}t_{6}t_{8}t_{9}=(1,2,3,-8,-9)(-1,-2,-3,8,9)$. By
$t_{9}=(3,-7)(-3,7)$, we have $j=3$ (in this case, $m^{\prime}=4$ and $m=9$).
As an intermediate stage, we associate $\delta_{1}$ with
$\zeta^{\prime}_{1}=(1,2,3,4,5^{*})$. Using $\delta_{1}$ and
$\zeta^{\prime}_{1}$, we construct a pair $(\alpha^{\prime},\pi^{\prime})$ by
Procedure D.1, where $\alpha^{\prime}=(a_{1},a_{3},a_{6},a_{8})=(3,1,3,1)$ and
$\pi^{\prime}=(p_{1},p_{3},p_{6},p_{8})=(3,1,4,2)$. Note that
$\\{p_{1},p_{6}\\}=\\{3,4\\}$ is the requested maximal subset of
$\pi^{\prime}$ that occurs to the left of $p_{7}$. By (3.18), we determine the
tuple $\zeta=(z_{1},z_{2},\dots,z_{9})=(1,2,\dots,9)$ (in this case $b=2$). We
set $p_{9}=5=z_{5}$ and set $a_{9}=z_{8}=8$ (in this case $r=5$ and $j=3$). By
(3.19), replace $\zeta^{\prime}_{1}$ by $\zeta_{1}=(6,7,3,4,5^{*})$. Using
$\delta_{1}$ and $\zeta_{1}$, we construct the entries
$(a_{1},a_{3},a_{6},a_{8})=(3,6,3,6)$ and
$(p_{1},p_{3},p_{6},p_{8})=(3,6,4,7)$ by Algorithm D.1, as shown in Example
3.13. Thus, we obtain the corresponding parking function
$\alpha=(3,9,6,9,8,3,1,6,8)$ with outcome $\pi=(3,9,6,1,8,4,2,7,5)$.

Table 5. The construction of $\varphi_{B}^{-1}({\mathbf{w}})$ in Example 3.14. $i$ | $t_{i}$ | $\omega_{i}$ | $\zeta$ | $a_{i_{j}}$ | $p_{i_{j}}$ | $\circ\times$
---|---|---|---|---|---|---
0 |  | $(1)(2)(3)(4)(5)(6)(7)(8)(9)$ |  |  |  |
1 | $(2,-9)(-2,9)$ | $(1)(2,-9)(3)(4)(5)(6)(7)(8)$ |  | 3 | 3 | $\circ$
2 | $(4,-7)(-4,7)$ | $(1)(2,-9)(3)(4,-7)(5)(6)(8)$ |  | 9 | 9 | $\circ$
3 | $(3,-8)(-3,8)$ | $(1)(2,-9)(3,-8)(4,-7)(5)(6)$ |  | 6 | 6 | $\circ$
4 | $(4,-4)$ | $[4,7](1)(2,-9)(3,-8)(5)(6)$ | $(1,9)$ | 9 | 1 | $\times$
5 | $(5,6)(-5,-6)$ | $[4,7](1)(2,-9)(3,-8)(5,6)$ |  | 8 | 8 | $\circ$
6 | $(1,-9)(-1,9)$ | $[4,7](1,2,-9)(3,-8)(5,6)$ |  | 3 | 4 | $\times$
7 | $(4,6)(-4,-6)$ | $[4,5,6,7](1,2,-9)(3,-8)$ | $(1,2,8,9)$ | 1 | 2 | $\times$
8 | $(2,-8)(-2,8)$ | $[4,5,6,7](1,2,3,-8,-9)$ |  | 6 | 7 | $\times$
9 | $(3,-7)(-3,7)$ | $[1,2,3,4,5,6,7,8,9]$ | $(1,2,3,4,5,6,7,8,9)$ | 8 | 5 | $\times$

Remarks. We describe the strategy used in the inductive step of Algorithm D.
Note that $\\{p_{v_{1}},\dots,p_{v_{m^{\prime}}}\\}$ is in fact the zeta-
naught set $Z_{0}$ of $(p_{u_{1}},p_{u_{2}},\dots,p_{u_{m-1}})$ with
$Z_{1}=\\{p_{u_{i_{1}}},p_{u_{i_{2}}},\dots$, $p_{u_{i_{m-m^{\prime}-1}}}\\}$.
By Procedure C.2, every element in $Z_{1}$ is greater than
$p_{v_{m^{\prime}}}=\ell$. By Lemma 3.10, the entries $p_{j}\in Z_{1}$
satisfying $p_{j}<p_{u_{m}}$ occur to the left of $p_{v_{m^{\prime}}}$. Thus,
in order to determine $p_{u_{m}}$, we need the greatest integer $b$ such that
all of $\ell+1,\dots,\ell+b$ in the word
$(p_{u_{i_{1}}},p_{u_{i_{2}}},\dots,p_{u_{i_{m-m^{\prime}-1}}})$ occur to the
left of $p_{v_{m^{\prime}}}$ if any. By (3.11), these integers are the last
$b+1$ entries in the $(m-m^{\prime})$-tuple $\zeta_{1}$. Using the temporary
$(m-m^{\prime})$-tuple
$\zeta^{\prime}_{1}=(1,\dots,m-m^{\prime}-1,(m-m^{\prime})^{*})$ associated to
$\delta_{1}=t_{u_{i_{1}}}t_{u_{i_{2}}}\cdots t_{u_{i_{m-m^{\prime}-1}}}$, we
construct $(\alpha^{\prime},\pi^{\prime})$ by Procedure D.1 and find the
integer $b$ from the maximal number of entries
$m-m^{\prime}-1,m-m^{\prime}-2,\dots,m-m^{\prime}-b$ of $\pi^{\prime}$ that
occur to the left of $p_{v_{m^{\prime}}}$. Using this integer $b$, we set
$p_{u_{m}}=\ell+b+1$ and determine the $m$-tuple $\zeta$ in (3.18) and the
$(m-m^{\prime})$-tuple $\zeta_{1}$ in (3.19).

The proof of Theorem 1.3 is completed. The correspondence of the bijection
$\varphi_{B}$ for $n=3$ is listed in Table 6 for reference.

Table 6. The map $\varphi_{B}:\alpha\mapsto{\mathbf{w}}=t_{1}t_{2}t_{3}$ for all $\alpha\in{\mathrm{PF}}^{B}_{3}$. $\alpha$ |  | $\pi$ |  |  | ${\mathbf{w}}$ |  | $\circ\times$
---|---|---|---|---|---|---|---
123 |  | 123 |  |  | $[(1,-1)][(1,2)(-1,-2)][(2,3)(-2,-3)]$ |  | $\circ\circ\circ$
132 |  | 132 |  |  | $[(1,-1)][(2,3)(-2,-3)][(1,3)(-1,-3)]$ |
213 |  | 213 |  |  | $[(2,3)(-2,-3)][(1,-1)][(1,3)(-1,-3)]$ |
231 |  | 231 |  |  | $[(2,3)(-2,-3)][(1,3)(-1,-3)][(3,-3)]$ |
312 |  | 312 |  |  | $[(1,2)(-1,-2)][(2,-2)][(2,3)(-2,-3)]$ |
321 |  | 321 |  |  | $[(1,2)(-1,-2)][(2,3)(-2,-3)][(3,-3)]$ |
121 |  | 123 |  |  | $[(2,-2)][(2,3)(-2,-3)][(1,-3)(-1,3)]$ |  | $\circ\circ\times$
122 |  | 123 |  |  | $[(1,-1)][(1,3)(-1,-3)][(1,2)(-1,-2)]$ |
131 |  | 132 |  |  | $[(3,-3)][(1,2)(-1,-2)][(2,-3)(-2,3)]$ |
133 |  | 132 |  |  | $[(2,-2)][(1,-3)(-1,3)][(1,-2)(-1,2)]$ |
211 |  | 213 |  |  | $[(1,-3)(-1,3)][(2,-2)][(1,-2)(-1,2)]$ |
212 |  | 213 |  |  | $[(1,2)(-1,-2)][(3,-3)][(2,-3)(-2,3)]$ |
232 |  | 231 |  |  | $[(1,-2)(-1,2)][(2,3)(-2,-3)][(1,-1)]$ |
233 |  | 231 |  |  | $[(1,2)(-1,-2)][(2,-3)(-2,3)][(2,-2)]$ |
311 |  | 312 |  |  | $[(1,3)(-1,-3)][(3,-3)][(1,2)(-1,-2)]$ |
313 |  | 312 |  |  | $[(2,3)(-2,-3)][(3,-3)][(1,-3)(-1,3)]$ |
322 |  | 321 |  |  | $[(2,3)(-2,-3)][(1,-3)(-1,3)][(1,-1)]$ |
323 |  | 321 |  |  | $[(1,-3)(-1,3)][(1,2)(-1,-2)][(2,-2)]$ |
113 |  | 123 |  |  | $[(2,-2)][(1,-2)(-1,2)][(2,3)(-2,-3)]$ |  | $\circ\times\circ$
221 |  | 231 |  |  | $[(1,3)(-1,-3)][(1,2)(-1,-2)][(3,-3)]$ |
332 |  | 312 |  |  | $[(1,-2)(-1,2)][(1,-1)][(2,3)(-2,-3)]$ |
111 |  | 123 |  |  | $[(3,-3)][(2,-3)(-2,3)][(1,-3)(-1,3)]$ |  | $\circ\times\times$
112 |  | 123 |  |  | $[(3,-3)][(1,-3)(-1,3)][(1,2)(-1,-2)]$ |
222 |  | 231 |  |  | $[(1,-3)(-1,3)][(1,-2)(-1,2)][(1,-1)]$ |
223 |  | 231 |  |  | $[(2,-3)(-2,3)][(1,-3)(-1,3)][(2,-2)]$ |
333 |  | 312 |  |  | $[(2,-3)(-2,3)][(2,-2)][(1,-3)(-1,3)]$ |
331 |  | 312 |  |  | $[(1,-3)(-1,3)][(1,-1)][(1,2)(-1,-2)]$ |

Let $B_{n}(q):=M(B_{n},q)$. We observe that the polynomial $B_{n}(q)$
satisfies the following recurrence relation.

######  Proposition 3.15.

For $n\geq 1$, we have

$B_{n}(q)=\big{(}1+(n-1)q\big{)}\sum_{k=1}^{n}\binom{n-1}{n-k}B_{n-k}(q)A_{k-1}(q),$

with $B_{0}(q)=1$.

###### Proof.

We enumerate the factorizations $t_{1}t_{2}\cdots t_{n}$ of $c$ corresponding
to a maximal chain
${\mathbf{w}}:e=\omega_{0}\leq\omega_{1}\leq\cdots\leq\omega_{n}=c$, where
$t_{i}=\omega^{-1}_{i-1}\omega_{i}$. For congruence of integers modulo $2n$,
the notation $n+i$ ($2n+i$, respectively) is used to stand for $-i$ ($i$,
respectively) for $1\leq i\leq n$.

Let $T_{1},\dots,T_{n}$ be a family of sets of reflections given by

$\displaystyle T_{j}$ $\displaystyle:=\\{(i,i+j)(n+i,n+i+j):1\leq i\leq
n\\}\quad\mbox{if $1\leq j\leq n-1$;}$ (3.20) $\displaystyle T_{n}$
$\displaystyle:=\\{(i,i+n):1\leq i\leq n\\}.$

The reflection $t_{n}$ is in one of the sets $T_{1},\dots,T_{n}$, say
$t_{n}\in T_{k}$. By Lemma 3.3, among the $n$ reflections in $T_{k}$, there is
exactly one possibility for $t_{n}$ such that $(\omega_{n-1},\omega_{n})$ is a
good edge. Moreover, the reflection $t_{n}$ splits $\omega_{n}$ into a
balanced cycle $\delta_{0}$ of size $2(n-k)$ and a paired cycle $\delta_{1}$
of size $k$, and among $t_{1},t_{2},\dots,t_{n-1}$ there are $n-k$ ($k-1$,
respectively) reflections comparable with $\delta_{0}$ ($\delta_{1}$,
respectively). The generating $q$-polynomial for the maximal chains in the
$\delta_{0}$-noncrossing partition lattice ($\delta_{1}$-noncrossing partition
lattice, respectively) is $B_{n-k}(q)$ ($A_{k-1}(q)$, respectively). The
result follows. ∎

##  4\. Words of types $A$ and $B$

In this section we study a simple object in connection with parking functions
from the prospective of the polynomials $M(W,q)$. In the case of $W=B_{n}$,
this object will be used in the proof of the $\gamma$-positivity of
$M(B_{n},q)$ (Theorem 1.4).

###  4.1. Type-$A$ words

Let ${\mathcal{X}}^{A}_{n}$ denote the set of words
${\mathbf{x}}=x_{1}x_{2}\cdots x_{n-1}$ over the alphabet $\\{0,1,\dots,n\\}$.
Notice that a word ${\mathbf{x}}\in{\mathcal{X}}^{A}_{n}$ consists of $n-1$
letters. A letter $x_{i}$ is an _excedance_ of ${\mathbf{x}}$ if $x_{i}>i$.
Let ${\mathsf{exc}}({\mathbf{x}})$ denote the number of excedances of
${\mathbf{x}}$. By (1.4), it is easy to see that

$M(\mathfrak{S}_{n+1},q)=\sum_{{\mathbf{x}}\in{\mathcal{X}}^{A}_{n}}q^{{\mathsf{exc}}({\mathbf{x}})}.$
(4.1)

######  Theorem 4.1.

There is a bijection $\psi_{A}:\alpha\mapsto{\mathbf{x}}=x_{1}\cdots x_{n-1}$
of ${\mathrm{PF}}^{A}_{n}$ onto ${\mathcal{X}}^{A}_{n}$ such that for each
$i\in\\{2,\dots,n\\}$ the $i$th car of $\alpha$ is reluctant if and only if
$x_{n-i+1}$ is an excedance.

The map $\psi_{A}:{\mathrm{PF}}^{A}_{n}\rightarrow{\mathcal{X}}^{A}_{n}$ is
described below. We make use of a cycle with vertex set $V=\\{0,1,\dots,n\\}$
arranged in increasing order (clockwise). Given
$\alpha=(a_{1},\dots,a_{n})\in{\mathrm{PF}}^{A}_{n}$ with outcome
$(p_{1},\dots,p_{n})$, we construct the corresponding word
$\psi_{A}(\alpha)=x_{1}\cdots x_{n-1}$ from right to left by the following
procedure. When working on $x_{n-k+1}$, we first create a bijective labeling
$f:V\rightarrow\\{0,1,\dots,n\\}$ such that
$(f(p_{1}),f(p_{2}),\dots,f(p_{k-1}))=(n,n-1,\dots,n-k+2)$.

Algorithm E1

For $k=2,\dots,n$, the entry $x_{n-k+1}$ is determined as follows.

  1. (i)

Find the vertices $p_{1},\dots,p_{k-1}$ in the cycle, and create a vertex
labeling by setting $f(p_{i})=n-i+1$ for each $i\in[k-1]$. Then assign the
labels $0,1,\dots,n-k+1$ clockwise to the remaining vertices, staring from the
first unlabeled vertex after $p_{1}$.

  2. (ii)

Set $x_{n-k+1}$ to be the label that the vertex $a_{k}$ receives, i.e.,
$x_{n-k+1}=f(a_{k})$.

######  Example 4.2.

Consider the cars $C_{1},\dots,C_{6}$ with preference list
$\alpha=(2,4,2,3,5,1)\in{\mathrm{PF}}^{A}_{6}$. The outcome of $\alpha$ is
$(2,4,3,5,6,1)$. As shown in Table 7, we have $\psi_{A}(\alpha)=x_{1}\cdots
x_{5}=1\,3\,4\,6\,1$. Note that the excedances $x_{4}$, $x_{3}$ and $x_{2}$ of
$\psi_{A}(\alpha)$ correspond to the reluctant cars $C_{3}$, $C_{4}$ and
$C_{5}$, respectively. Some initial steps are described below.

(1) $k=2$. We set $f(2)=6$. Then assign the labels $0,1,2,3,4,5$ to the
vertices $3,4,5,6,0,1$, accordingly. By $a_{2}=4$, we set $x_{5}=f(4)=1$. Note
that $C_{2}$ is lucky and the letter $x_{5}$ is not an excedance of
$\psi_{A}(\alpha)$.

(2) $k=3$. We set $f(2)=6$ and $f(4)=5$. Then assign the labels $0,1,2,3,4$ to
the vertices $3,5,6,0,1$, accordingly. By $a_{3}=2$, we set $x_{4}=f(2)=6$.
Note that $C_{3}$ is reluctant and the letter $x_{4}$ is an excedance of
$\psi_{A}(\alpha)$.

Table 7. The construction of the word $\psi_{A}(\alpha)$ in Example 4.2. $k$ | $a_{k}$ | $p_{k}$ | $f(0)$ | $f(1)$ | $f(2)$ | $f(3)$ | $f(4)$ | $f(5)$ | $f(6)$ | $x_{7-k}$
---|---|---|---|---|---|---|---|---|---|---
1 | 2 | 2 |  |  |  |  |  |  |  |
2 | 4 | 4 | 4 | 5 | 6 | 0 | 1 | 2 | 3 | 1
3 | 2 | 3 | 3 | 4 | 6 | 0 | 5 | 1 | 2 | 6
4 | 3 | 5 | 2 | 3 | 6 | 4 | 5 | 0 | 1 | 4
5 | 5 | 6 | 1 | 2 | 6 | 4 | 5 | 3 | 0 | 3
6 | 1 | 1 | 0 | 1 | 6 | 4 | 5 | 3 | 2 | 1

######  Lemma 4.3.

For $2\leq k\leq n$, the letter $x_{n-k+1}$ is an excedance of
$\psi_{A}(\alpha)$ if and only if the $k$th car of $\alpha$ is reluctant.

###### Proof.

Note that the $k$th car of $\alpha$ is reluctant if and only if
$a_{k}\in\\{p_{1},\dots,p_{k-1}\\}$. By the vertex labeling in (i) of
Algorithm E1, we have $\\{f(p_{1}),\dots,f(p_{k-1})\\}=\\{n,\dots,n-k+2\\}$.
By setting $x_{n-k+1}=f(a_{k})$, we have $x_{n-k+1}>n-k+1$ if and only if
$a_{k}\in\\{p_{1},\dots,p_{k-1}\\}$. ∎

To find $\psi^{-1}_{A}$, given ${\mathbf{x}}=x_{1}\cdots
x_{n-1}\in{\mathcal{X}}^{A}_{n}$, we shall construct
$\psi^{-1}_{A}({\mathbf{x}})=(a_{1},\dots,a_{n})$ in two stages. We also make
use of the cycle with vertex set $V=\\{0,1,\dots,n\\}$. In the first stage,
using $n+1$ parking spaces numbered $0,1,\dots,n$ arranged in a circle, we
construct a parking function
$\alpha^{\prime}=(a^{\prime}_{1},\dots,a^{\prime}_{n})\in\\{0,1,\dots,n\\}^{n}$
with outcome $\pi^{\prime}=(p^{\prime}_{1},\dots,p^{\prime}_{n})$ such that
$a^{\prime}_{1}=p^{\prime}_{1}=0$. When working on $a^{\prime}_{k}$ and
$p^{\prime}_{k}$ for $k\geq 2$, a bijective labeling
$g:V\rightarrow\\{0,1,\dots,n\\}$ such that
$(g(n),g(n-1),\dots,g(n-k+2))=(p^{\prime}_{1},\dots,p^{\prime}_{k-1})$ has
been created. There will be a unique empty space. In the second stage, we make
an adjustment so that the parking space 0 is empty.

Algorithm E2

(i) Let $a^{\prime}_{1}=p^{\prime}_{1}=0$. The initial vertex labeling is
given by $g(i)=i+1\pmod{n+1}$ for all $0\leq i\leq n$. This gets
$g(n)=0=p^{\prime}_{1}$.

  * •

For $k\geq 2$, set $a^{\prime}_{k}=g(x_{n-k+1})$, say $g(x_{n-k+1})=t$. If
$x_{n-k+1}\leq n-k+1$ then set $p^{\prime}_{k}=t$. Otherwise,
$x_{n-k+1}>n-k+1$ and set $p^{\prime}_{k}$ to be the next available space,
i.e., find the least positive integer $s$ such that $\ell=t+s\pmod{n+1}$ and
$g^{-1}(\ell)\leq n-k+1$, and then set $p^{\prime}_{k}=\ell$.

  * •

Set $g(n-k+1)=p^{\prime}_{k}$ and relabel the vertices $0,1,\dots,n-k$ in
increasing order by the integers
$\\{0,1,\dots,n\\}\setminus\\{g(n-k+1),\dots,g(n)\\}$.

(ii) Find the unique element in
$\\{0,1,\dots,n\\}\setminus\\{p^{\prime}_{1},\dots,p^{\prime}_{n}\\}$, say
$b>0$. Then the corresponding parking function
$\psi^{-1}_{A}({\mathbf{x}})=(a_{1},\dots,a_{n})$ is obtained by setting
$a_{i}\equiv a^{\prime}_{i}+n+1-b\pmod{n+1}$.

######  Example 4.4.

Let ${\mathbf{x}}=1\,3\,4\,6\,1\in{\mathcal{X}}^{A}_{6}$. As shown in Table 8,
we obtain $\alpha^{\prime}=(0,2,0,1,3,6)$ with outcome
$\pi^{\prime}=(0,2,1,3,4,6)$, where the empty space is numbered by 5. Hence
the corresponding parking function of ${\mathbf{x}}$ is
$\psi^{-1}_{A}({\mathbf{x}})=(2,4,2,3,5,1)$.

Table 8. The construction of the first stage $\alpha^{\prime}$ in Example 4.4. $k$ | $x_{7-k}$ | $g(0)$ | $g(1)$ | $g(2)$ | $g(3)$ | $g(4)$ | $g(5)$ | $g(6)$ |  |  | $a^{\prime}_{k}$ | $p^{\prime}_{k}$
---|---|---|---|---|---|---|---|---|---|---|---|---
1 |  |  |  |  |  |  |  |  |  |  | 0 | 0
2 | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 0 |  |  | 2 | 2
3 | 6 | 1 | 3 | 4 | 5 | 6 | 2 | 0 |  |  | 0 | 1
4 | 4 | 3 | 4 | 5 | 6 | 1 | 2 | 0 |  |  | 1 | 3
5 | 3 | 4 | 5 | 6 | 3 | 1 | 2 | 0 |  |  | 3 | 4
6 | 1 | 5 | 6 | 4 | 3 | 1 | 2 | 0 |  |  | 6 | 6

The proof of Theorem 4.1 is completed.

###  4.2. Type-$B$ words

Let ${\mathcal{X}}^{B}_{n}$ denote the set of words
${\mathbf{x}}=x_{1}x_{2}\cdots x_{n}$ over the alphabet $\\{1,\dots,n\\}$.
Likewise, a letter $x_{i}$ is an excedance of ${\mathbf{x}}$ if $x_{i}>i$, and
the number of excedances of ${\mathbf{x}}$ is
${\mathsf{exc}}({\mathbf{x}})=\\#\\{x_{i}:x_{i}>i,1\leq i\leq n\\}$. By (1.6),
it is easy to see that

$M(B_{n},q)=\sum_{{\mathbf{x}}\in{\mathcal{X}}^{B}_{n}}q^{{\mathsf{exc}}({\mathbf{x}})}.$
(4.2)

######  Theorem 4.5.

There is a bijection $\psi_{B}:\alpha\mapsto{\mathbf{x}}=x_{1}\cdots x_{n}$ of
${\mathrm{PF}}^{B}_{n}$ onto ${\mathcal{X}}^{B}_{n}$ such that for each
$i\in\\{1,\dots,n\\}$ the $i$th car of $\alpha$ is reluctant if and only if
$x_{n-i+1}$ is an excedance.

We describe the map
$\psi_{B}:{\mathrm{PF}}^{B}_{n}\rightarrow{\mathcal{X}}^{B}_{n}$. Given
$\alpha=(a_{1},\dots,a_{n})\in{\mathrm{PF}}^{B}_{n}$ with outcome
$(p_{1},\dots,p_{n})$, the corresponding word
$\psi_{B}(\alpha)=x_{1}x_{2}\cdots x_{n}$ is constructed from right to left by
the following procedure.

Algorithm F1

  1. (i)

Set $x_{n}=a_{1}$.

  2. (ii)

For $k\geq 2$, if $a_{k}=p_{k}$ then set $x_{n-k+1}=j$, where $p_{k}$ is the
$j$th smallest element among $p_{k},p_{k+1},\dots,p_{n}$. Otherwise,
$a_{k}=p_{\ell}$ for some $\ell\in[k-1]$, and set $x_{n-k+1}=n-\ell+1$.

######  Example 4.6.

Consider the cars $C_{1},\dots,C_{6}$ with preference list
$\alpha=(2,2,5,5,6,6)\in{\mathrm{PF}}^{B}_{6}$. The outcome of $\alpha$ is
$(2,3,5,6,1,4)$. As shown in Table 9, the corresponding word is
$\psi_{B}(\alpha)=x_{1}\cdots x_{6}=3\,3\,4\,3\,6\,2$. Note that the
excedances $x_{5},x_{3},x_{2},x_{1}$ of $\psi_{B}(\alpha)$ correspond to the
reluctant cars $C_{2},C_{4},C_{5},C_{6}$, accordingly.

Table 9. The construction of the word $\psi_{B}(\alpha)$ in Example 4.6. $k$ |  | 1 | 2 | 3 | 4 | 5 | 6
---|---|---|---|---|---|---|---
$a_{k}$ |  | 2 | 2 | 5 | 5 | 6 | 6
$p_{k}$ |  | 2 | 3 | 5 | 6 | 1 | 4
$x_{7-k}$ |  | 2 | 6 | 3 | 4 | 3 | 3

######  Lemma 4.7.

For $1\leq k\leq n$, the letter $x_{n-k+1}$ is an excedance of
$\psi_{B}(\alpha)$ if and only if the $k$th car of $\alpha$ is reluctant.

###### Proof.

It is obvious that $x_{n}$ is not an excedance of ${\mathbf{x}}$, just as the
first car of $\alpha$ is always lucky. For $k\geq 2$, the $k$th car $C$ of
$\alpha$ is lucky if $a_{k}=p_{k}$. In this case, by (ii) of Algorithm F1,
$x_{n-k+1}\leq|\\{p_{k},\dots,p_{n}\\}|=n-k+1$. On the other hand, $C$ is
reluctant if $a_{k}=p_{\ell}$ for some $\ell\in[k-1]$. In this case,
$x_{n-k+1}=n-\ell+1>n-k+1$. Thus, the result follows. ∎

To find $\psi^{-1}_{B}$, given a word ${\mathbf{x}}=x_{1}\cdots
x_{n}\in{\mathcal{X}}^{B}_{n}$, we construct
$\psi^{-1}_{B}({\mathbf{x}})=(a_{1},\dots,a_{n})$ by the following procedure.
Recall that $\overline{j}\pmod{n}$ stands for the integer congruent to $j$ mod
$n$ with $1\leq\overline{j}\leq n$.

Algorithm F2

  1. (i)

Set $a_{1}=p_{1}=x_{n}$.

  2. (ii)

For $k\geq 2$, if $x_{n-k+1}$ is not an excedance of ${\mathbf{x}}$, say
$x_{n-k+1}=j\leq n-k+1$, we set $a_{k}$ to be the $j$th smallest element in
$\\{1,\dots,n\\}\setminus\\{p_{1},\dots,p_{k-1}\\}$, and set $p_{k}=a_{k}$.
Otherwise, $x_{n-k+1}$ is an excedance, say $x_{n-k+1}=\ell>n-k+1$. Then we
set $a_{k}=p_{n-\ell+1}$, say $p_{n-\ell+1}=t$, and set $p_{k}$ to be the next
available space, i.e., find the least integer $s$ such that
$r=\overline{t+s}\pmod{n}$ and
$r\in\\{1,\dots,n\\}\setminus\\{p_{1},\dots,p_{k-1}\\}$, and then set
$p_{k}=r$.

The proof of Theorem 4.5 is completed.

##  5\. Gamma-positivity of $M(B_{n},q)$

In this section we prove the $\gamma$-positivity of the polynomial
$M(B_{n},q)$ in terms of excedance number of the words in
${\mathcal{X}}^{B}_{n}$.

######  Theorem 5.1.

For all $n\geq 1$, we have

$M(B_{n},q)=\sum_{j=0}^{\lfloor(n-1)/2\rfloor}\gamma_{n,j}q^{j}(1+q)^{n-1-2j},$
(5.1)

where $\gamma_{n,j}$ is the number of words ${\mathbf{x}}=x_{1}\cdots
x_{n}\in{\mathcal{X}}^{B}_{n}$ with ${\mathsf{exc}}({\mathbf{x}})=j$ such that
$x_{1}=1$ and ${\mathbf{x}}$ contains no two consecutive excedances.

The generating function for the $\gamma$-coefficients $\gamma_{n,j}$ can be
expressed as follows.

######  Lemma 5.2.

We have

$\sum_{j=0}^{\lfloor(n-1)/2\rfloor}\gamma_{n,j}q^{j}=\begin{cases}{\displaystyle
n\cdot\prod_{k=1}^{\frac{n-1}{2}}\big{(}k(n-k)+(n-2k)^{2}q\big{)}}&\mbox{if
$n$ is odd;}\\\\[12.91663pt]
{\displaystyle\frac{n^{2}}{2}\cdot\prod_{k=1}^{\frac{n-2}{2}}\big{(}k(n-k)+(n-2k)^{2}q\big{)}}&\mbox{if
$n$ is even.}\end{cases}$ (5.2)

###### Proof.

Using (1.6), express $M(B_{n},q)$ as a product of the following factors

$\displaystyle\big{(}(n-k)+kq\big{)}\big{(}k+(n-k)q\big{)}$
$\displaystyle=k(n-k)+\big{(}k^{2}+(n-k)^{2}\big{)}q+k(n-k)q^{2}$
$\displaystyle=k(n-k)(1+q)^{2}+(n-2k)^{2}q.$

We have

$\displaystyle M(B_{n},q)$
$\displaystyle=\prod_{k=0}^{n-1}\big{(}(n-k)+kq\big{)}$
$\displaystyle=n\cdot\prod_{k=1}^{n-1}\big{(}(n-k)+kq\big{)}$
$\displaystyle=\begin{cases}{\displaystyle
n\cdot\prod_{k=1}^{\frac{n-1}{2}}\big{(}(n-k)+kq\big{)}\big{(}k+(n-k)q\big{)}}&\mbox{if
$n$ is odd;}\\\\[8.61108pt] {\displaystyle
n\left(\frac{n}{2}+\frac{nq}{2}\right)\prod_{k=1}^{\frac{n-2}{2}}\big{(}(n-k)+kq\big{)}\big{(}k+(n-k)q\big{)}}&\mbox{if
$n$ is even.}\end{cases}$ $\displaystyle=\begin{cases}{\displaystyle
n\cdot\prod_{k=1}^{\frac{n-1}{2}}\big{(}k(n-k)(1+q)^{2}+(n-2k)^{2}q\big{)}}&\mbox{if
$n$ is odd;}\\\\[8.61108pt]
{\displaystyle\frac{n^{2}}{2}(1+q)\prod_{k=1}^{\frac{n-2}{2}}\big{(}k(n-k)(1+q)^{2}+(n-2k)^{2}q\big{)}}&\mbox{if
$n$ is even.}\end{cases}$

Thus, the result follows from collecting the terms with $q^{j}(1+q)^{n-1-2j}$.
∎

Let ${\mathcal{F}}_{n}\subset{\mathcal{X}}^{B}_{n}$ be the set of words
${\mathbf{x}}=x_{1}\cdots x_{n}$ such that $x_{1}=1$ and ${\mathbf{x}}$
contains no two consecutive excedances. We present a determinantal expression
of the generating function for the words in ${\mathcal{X}}^{B}_{n}$
(${\mathcal{F}}_{n}$, respectively) with respect to excedance numbers, using a
method in [17, Eq. (12.4)].

######  Lemma 5.3.

For $1\leq j\leq n-1$, let $m_{j}=(n-j)q/j$. The following results hold.

  1. (i)

We have

$M(B_{n},q)=n!\cdot\det\begin{bmatrix}m_{1}&m_{2}&m_{3}&\cdots&m_{n-1}&1\\\
-1&m_{2}&m_{3}&\cdots&m_{n-1}&1\\\ &-1&m_{3}&\cdots&m_{n-1}&1\\\
&&\ddots&\ddots&\vdots&\vdots\\\ &&&-1&m_{n-1}&1\\\ &&&&-1&1\end{bmatrix}.$
(5.3)

  2. (ii)

We have

$\sum_{{\mathbf{x}}\in{\mathcal{F}}_{n}}q^{{\mathsf{exc}}({\mathbf{x}})}=n!\cdot\det\begin{bmatrix}0&m_{2}&m_{3}&\cdots&m_{n-1}&1\\\
-1&0&m_{3}&\cdots&m_{n-1}&1\\\ &-1&0&\cdots&m_{n-1}&1\\\
&&\ddots&\ddots&\vdots&\vdots\\\ &&&-1&0&1\\\ &&&&-1&1\end{bmatrix}.$ (5.4)

###### Proof.

(i) For any $A\subset[n-1]$, let $f(A)$ be the number of words
${\mathbf{x}}\in{\mathcal{X}}^{B}_{n}$ with excedance set $A$. If
$A=\\{b_{1}<b_{2}<\cdots<b_{\ell}\\}$, we observe that

$f(A)=n!\cdot\prod_{j=1}^{\ell}\left(\frac{n-b_{j}}{b_{j}}\right).$ (5.5)

Suppose that $M=(m_{ij})$ is an $n\times n$ matrix for which $m_{ij}=0$ if
$j<i-1$. By the permutation expansion for determinants, if
$\prod_{i=1}^{n}m_{i,\sigma(i)}\neq 0$ then every cycle of $\sigma$ is of the
form $(b,b-1,\dots,a+1,a)$. Moreover, if $m_{i,i-1}=1$ for $2\leq i\leq n$
then the contribution to $\det M$ from the permutation
$\sigma=(b_{1},b_{1}-1,\dots,2,1)(b_{2},\dots,b_{1}+1)\cdots(b_{\ell+1},\dots,b_{\ell}+1)$,
where $1\leq b_{1}<b_{2}<\cdots<b_{\ell+1}=n$, is
$(-1)^{n-\ell-1}m_{1,b_{1}}m_{b_{1}+1,b_{2}}\cdots m_{b_{\ell}+1,n}$. Thus, if
we set $m_{i,i-1}=-1$ for $2\leq i\leq n$, $m_{ij}=(n-j)q/j$ for $1\leq i\leq
j\leq n-1$ and $m_{i,n}=1$ for $1\leq i\leq n$, we derive

$\displaystyle n!\cdot\det M$ $\displaystyle=\sum_{A\subset[n-1]}f(A)q^{|A|}$
(5.6)
$\displaystyle=\sum_{{\mathbf{x}}\in{\mathcal{X}}^{B}_{n}}q^{{\mathsf{exc}}({\mathbf{x}})}.$

By (4.2) and (5.6), the assertion (i) follows.

(ii) If we set further $m_{i,i}=0$ for $1\leq i\leq n-1$ then the excedance
sets $A=\\{b_{1}<b_{2}<\cdots<b_{\ell}\\}\subset[n-1]$ that contribute
$m_{1,b_{1}}m_{b_{1}+1,b_{2}}\cdots m_{b_{\ell}+1,n}\neq 0$ to $\det M$
satisfy $b_{1}>1$ and $b_{j+1}-b_{j}>1$ for each $j\in[\ell-1]$. Thus, the
assertion (ii) follows. ∎

To evaluate the determinant in (5.4), we make use of Chu’s formula for the
determinants of a family of tridiagonal matrices [14].

######  Theorem 5.4 (Chu).

Let

$f_{n}(x,y;u,v):=\det\begin{bmatrix}x&u&0&0&\cdots&0&0&0\\\
nv&x+y&2u&0&\cdots&0&0&0\\\ 0&(n-1)v&x+2y&3u&\cdots&0&0&0\\\
\vdots&\vdots&\vdots&\ddots&\ddots&\ddots&\vdots&\vdots\\\
0&0&0&0&\cdots&2v&x+(n-1)y&nu\\\ 0&0&0&0&\cdots&0&v&x+ny\end{bmatrix}.$ (5.7)

We have

$f_{n}(x,y;u,v)=\prod_{k=0}^{n}\left(x+\frac{ny}{2}+\frac{n-2k}{2}\sqrt{y^{2}+4uv}\right).$
(5.8)

To prove Theorem 5.1, it suffices to show that the generating function for
$\gamma_{n,j}$ in Lemma 5.2 coincides with the polynomial in Lemma 5.3(ii).

_Proof of Theorem 5.1._ By Lemma 5.3(ii), we have

$\displaystyle\sum_{{\mathbf{x}}\in{\mathcal{F}}_{n}}q^{{\mathsf{exc}}({\mathbf{x}})}$
$\displaystyle=n!\cdot\det\begin{bmatrix}1&m_{2}&&&&\\\ -1&1&m_{3}&&&\\\
&-1&1&\ddots&&\\\ &&-1&\ddots&m_{n-2}&\\\ &&&\ddots&1&m_{n-1}\\\
&&&&-1&1\end{bmatrix}_{(n-1)\times(n-1)}$ (5.9)
$\displaystyle=n\cdot\det\begin{bmatrix}1&(n-2)q&&&&\\\ -1&2&(n-3)q&&&\\\
&-2&3&\ddots&&\\\ &&-3&\ddots&2q&\\\ &&&\ddots&n-2&q\\\
&&&&-(n-2)&n-1\end{bmatrix}.$ (5.10)

The matrix in (5.9) is obtained from the matrix in (5.4) by subtracting the
$(i+1)$th row from the $i$th row for each $i\in[n-1]$ and expanding the
determinant along the last column. The matrix in (5.10) is obtained from the
matrix in (5.9) by multiplying the $j$th column by $j$ for each $j\in[n-1]$.
Note that the transpose of the matrix in (5.10) coincides with the tridiagonal
matrix in (5.7), with determinant $f_{n-2}(x,y;u,v)$, specialized at $x=1$,
$y=1$, $u=-1$ and $v=q$. Thus, by Theorem 5.4, we have

$\displaystyle\sum_{\mathbf{x}\in{\mathcal{F}}_{n}}q^{{\mathsf{exc}}({\mathbf{x}})}$
$\displaystyle=n\cdot f_{n-2}(1,1;-1,q)$
$\displaystyle=n\cdot\prod_{k=0}^{n-2}\left(1+\frac{n-2}{2}+\frac{n-2-2k}{2}\sqrt{1-4q}\right)$
$\displaystyle=n\cdot\prod_{k=1}^{n-1}\left(\frac{n}{2}+\frac{n-2k}{2}\sqrt{1-4q}\right)$
$\displaystyle=\begin{cases}{\displaystyle
n\cdot\prod_{k=1}^{\frac{n-1}{2}}\left(\frac{n}{2}+\frac{n-2k}{2}\sqrt{1-4q}\right)\left(\frac{n}{2}-\frac{n-2k}{2}\sqrt{1-4q}\right)}&\mbox{if
$n$ is odd;}\\\\[12.91663pt]
{\displaystyle\frac{n^{2}}{2}\cdot\prod_{k=1}^{\frac{n-2}{2}}\left(\frac{n}{2}+\frac{n-2k}{2}\sqrt{1-4q}\right)\left(\frac{n}{2}-\frac{n-2k}{2}\sqrt{1-4q}\right)}&\mbox{if
$n$ is even.}\end{cases}$ $\displaystyle=\begin{cases}{\displaystyle
n\cdot\prod_{k=1}^{\frac{n-1}{2}}\big{(}k(n-k)+(n-2k)^{2}q\big{)}}&\mbox{if
$n$ is odd;}\\\\[12.91663pt]
{\displaystyle\frac{n^{2}}{2}\cdot\prod_{k=1}^{\frac{n-2}{2}}\big{(}k(n-k)+(n-2k)^{2}q\big{)}}&\mbox{if
$n$ is even.}\end{cases}$

By Lemma 5.2, we obtain the relation

$\sum_{\mathbf{x}\in{\mathcal{F}}_{n}}q^{{\mathsf{exc}}({\mathbf{x}})}=\sum_{j=0}^{\lfloor(n-1)/2\rfloor}\gamma_{n,j}q^{j}.$

It follows that $\gamma_{n,j}$ is the number of words
${\mathbf{x}}\in{\mathcal{F}}_{n}$ with ${\mathsf{exc}}({\mathbf{x}})=j$.
Thus, the proof of Theorem 5.1 is completed. ∎

By Theorems 1.3, 4.5 and 5.1, the proof of Theorem 1.4 is completed.

##  6\. Concluding Remarks

In this paper we establish a connection of parking functions of types $A$ and
$B$ with the maximal chains in the lattice of noncrossing partitions of $W$ by
the polynomials $M(\mathfrak{S}_{n+1},q)$ and $M(B_{n},q)$. Some potential
follow-up questions may arise. There are interesting bijections between the
regions of Shi arrangement and parking functions [1], and between the regions
and the maximal chains in the lattice of noncrossing partitions [22]. There
are other objects counted by the number $(n+1)^{n-1}$, such as Cayley trees
with $n+1$ vertices, the critical states of the abelian sandpile model on the
complete graph $K_{n+1}$, the regions in the Ish arrangement in
$\mathbb{R}^{n}$ [3], etc. It would be interesting to investigate the
interrelationship among these combinatorial structures from the perspective of
the polynomial $M(\mathfrak{S}_{n+1},q)$.

In a study of interval partitions, Biane and Josuat-Vergés [8] generalized the
polynomial $M(\mathfrak{S}_{n+1},q)$ to a multivariate generating function

$\sum_{{\mathbf{w}}}{\mathsf{wt}}({\mathbf{w}})=\prod_{k=1}^{n-1}\big{(}n-k+1+kX_{k}\big{)},$

summed over all maximal chains ${\mathbf{w}}$ in
${\mathrm{NC}}(\mathfrak{S}_{n+1},c)$, where the weight ${\mathsf{wt}}$ is a
monomial in the $X_{k}$. As quoted from [8], they said “it would be
interesting to investigate the existence of similar formulas for other types.”

## Acknowledgements.

We would like to thank an anonymous referee for reading the manuscript
carefully and providing helpful suggestions. This research was supported in
part by National Science and Technology Council, Taiwan, through grants
110-2115-M-003-011-MY3 (S.-P. Eu), 111-2115-M-153-004-MY2 (T.-S. Fu), and
postdoctoral fellowship 111-2811-M-A49-537-MY2 (Y.-J. Cheng).

## References

  * [1] C. A. Athanasiadis, S. Linusson, A simple bijection for the regions of the Shi arrangement of hyperplanes, Discrete Math. 204 (1999), 27–39.
  * [2] D. Armstrong, Generalized noncrossing partitions and combinatorics of Coxeter groups, Mem. Amer. Math. Soc. 202, 2009.
  * [3] D. Armstrong, B. Rhoades, The Shi arrangement and the Ish arrangement, Trans. Amer. Math. Soc. 364(3) (2012), 1509–1528.
  * [4] D. Bessis, The dual braid monoid, Ann. Sci. École Norm. Sup. 36(5) (2003), 647–683.
  * [5] P. Biane, Some properties of crossings and partitions, Discrete Math. 175(1-3) (1997), 41–53.
  * [6] P. Biane, Parking functions of types $A$ and $B$, Electron. J. Combin. 9 (2002), #N7.
  * [7] P. Biane, M. Josuat-Vergès, Noncrossing partitions, Bruhat order and the cluster complex, Annales de l’Institut Fourier 69(5) (2019), 2241–2289.
  * [8] P. Biane, M. Josuat-Vergès, Minimal factorizations of a cycle: a multivariate generating function, Discret. Math. Theor. Comput. Sci., DMTCS Proc. (FPSAC 2016), 2016, pp. 239–250.
  * [9] A. Björner, F. Brenti, Combinatorics of Coxeter Groups, Graduate Texts in Math., Vol. 231, Springer-Verlag, New York, 2005.
  * [10] T. Brady, C. Watt, $K(\pi,1)$’s for Artin groups of finite type, Geom. Dedicata 94(1) (2002), 225–250.
  * [11] T. Brady, C. Watt, Non-crossing partition lattices in finite real reflection groups, Trans. Amer. Math. Soc. 360(4) (2008), 1983–2005.
  * [12] F. Chapoton, Enumerative properties of generalized associahedra, Sémin. Lothar. Combin. 51 (2004), B51b.
  * [13] G. Chapuy, T. Douvropoulos, Counting chains in the noncrossing partition lattice via the $W$-Laplacian, J. Algebra 602 (2021), 381–404.
  * [14] W. Chu, Fibonacci polynomials and Sylvester determinant of tridiagonal matrix, Appl. Math. Comp. 216 (2010), 1018–1023.
  * [15] P. Deligne, Letter to E. Looijenga on March 9, 1974. Reprinted in the diploma thesis of P. Kluitmann, pp. 101–111.
  * [16] I. M. Gessel, S. Seo, A refinement of Cayley’s formula for trees, Electron. J. Combin. 11(2) (2004-6), R27.
  * [17] I. M. Gessel, R. Stanley, Algebraic enumeration, in: R. Graham, M. Grötschel, L. Lovász (Eds.), Handbook of Combinatorics, North-Holland, 1995, pp. 1021–1061.
  * [18] M. Josuat-Vergès, Refined enumeration of noncrossing chains and hook formulas, Ann. Combin. 19 (2015), 443–460.
  * [19] V. Reiner, Non-crossing partitions for classical reflection groups, Discrete Math. 177(1-3) (1997), 195–222.
  * [20] V. Reiner, V. Ripoll, C. Stump, On non-conjugate Coxeter elements in well-generated reflection groups, Math. Z. 285 (2017), 1041–1062.
  * [21] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published online at http://oeis.org.
  * [22] R. P. Stanley, Parking functions and noncrossing partitions, Electron. J. Combin. 4(2) (1997), R20.
  * [23] C.H. Yan, Parking functions, in: M. Bóna(ed.), Handbook of Enumerative Combinatorics, Discrete Math. Appl., CRC Press, Boca Raton, 2015, pp. 835–893.