# Defective parking functions and Young tableaux

Rebecca E. Garcia  Department of Mathematics and Computer Science, Colorado
Springs, CO 80903 United States<EMAIL_ADDRESS>,  Pamela E.
Harris  ,  Alex Moon  Department of Mathematical Sciences, University of
Wisconsin-Milwaukee, Milwaukee, WI 53211 United States<EMAIL_ADDRESS><EMAIL_ADDRESS>,  Aaron Ortiz  Department of Mathematics, The University of
Kansas, Lawrence, KS 66045 United States<EMAIL_ADDRESS>,  Lauren J. Quesada
Department of Statistics, Colorado State University, Fort Collins, CO
80523-1877 United States<EMAIL_ADDRESS>,  Cynthia Marie Rivera
Sánchez  Department of Mathematics, University of Puerto Rico - Río Piedras,
San Juan PR, 00925-2537 United States<EMAIL_ADDRESS>and  Dwight
Anderson Williams II  Department of Mathematics, Morgan State University,
Baltimore, MD 21251 United States<EMAIL_ADDRESS>
###### Abstract.

Recall that a defective $(m,n)$-parking function with defect $d$ is a parking
function with $m$ cars attempting to park on a street with $n$ parking spots
in which exactly $d$ cars fail to park. We establish a way to compute the
defect of a defective $(m,n)$-parking function and show that the defect of a
parking function is invariant under the action of $\mathfrak{S}_{m}$ the
symmetric group on $[m]=\\{1,2,\ldots,m\\}$. We also show that the set of
nondecreasing defective $(m,n)$-parking functions with defect $d$ are in
bijection with the set of standard Young tableaux of shape $(n+d,m-d)$. This
implies that the number of $\mathfrak{S}_{m}$-orbits of defective
$(m,n)$-parking functions with defect $d$ is given by
$\frac{n-m+2d+1}{n+d+1}\binom{m+n}{n+d}$. We also give a multinomial formula
for the size of an $\mathfrak{S}_{m}$-orbit of a nondecreasing $(m,n)$-parking
function with defect $d$. We conclude by using these results to give a new
formula for the number of defective parking functions.

###### Key words and phrases:

Parking function, Young tableau, Dyck path, Catalan number

###### 2020 Mathematics Subject Classification:

05A15, 05A19

##  1\. Introduction

Given $m,n\in\mathbb{N}\coloneqq\\{1,2,3,\ldots\\}$ with $m\leq n$, we recall
the classical combinatorial description of $(m,n)$-parking functions. Consider
$m$ cars in queue to enter a linear parking lot with $n$ sequentially numbered
parking spaces. A tuple $\mathbf{x}=(x_{1},x_{2},\ldots,x_{n})\in[n]^{m}$,
where $[n]=\\{1,2,\ldots,n\\}$, is called a _preference list_ and it encodes
that, for each $i\in[m]$, car $i$ prefers parking spot $x_{i}\in[n]$. Given a
parking list $\mathbf{x}$, we refer to an entry as a _parking preference_. The
following procedure for parking is what we refer to as the _classical parking
scheme_. Cars enter the street one at a time, proceed to their preferred
parking spot, and park there if their preference is unoccupied. Otherwise, the
car parks in the first space available after their preference. If no such spot
is available, then we say that car has failed to park. If the preference list
$\mathbf{x}$ allows all cars to park, then $\mathbf{x}$ is called an
$(m,n)$-parking function. Throughout we let $\mathrm{PF}_{m,n}$ denote the set
of $(m,n)$-parking functions of length $m$, and we recall that when $n=m$,
Konheim and Weiss showed $|\mathrm{PF}_{n,n}|=(n+1)^{n-1}$, while Cameron,
Johannsen, Prellberg, and Schweitzer showed
$|\mathrm{PF}_{m,n}|=(n+1-m)(n+1)^{m-1}$, see [7, 26] for proofs.

Parking functions have connections to many areas of mathematics including
representation theory, Coxeter groups, hyperplane arrangements, discrete
geometry, the quicksort algorithm, the Tower of Hanoi game, cooperative game
theory, and many others [3, 8, 14, 15, 23, 25]. Moreover, many have studied
generalizations of parking functions allowing for cars to move backwards when
finding their preferred parking spot occupied or bumping cars out of an
occupied parking spot, cars parking on a street with some parking spots
unavailable, allowing cars to have various lengths and colors, and cars having
multiple parking spot preferences [1, 2, 6, 9, 10, 11, 13, 17, 19, 24]. There
has also been substantial interest in the study of statistics of parking
functions. This includes statistics such as the number of lucky cars (those
cars that park in their preference), displacement (the difference between
where a car parks and its preference), and more classical statistics such as
ascents, descents, ties, peaks and valleys and flatness [12, 16, 21].

In our work, we study defective parking functions as introduced by [7].
Classically, a defective parking function of defect $d$ is a preference list
in $[n]^{m}$ in which exactly $d$ cars fail to park. We generalize this to
think of cars parking on an infinitely long road, where defect $d$ is the
difference between the true parking spot of the final car and $n$ whenever
there are cars failing to park. Here a car “fails to park” implies the car did
not park in the first $n$ spots so that $d$ is nonnegative and only parking
functions yield zero defect. We also allow preference lists to come from
$[n+1]^{m}$ to include defective parking functions where no cars park in the
$n$ parking spots. In this context, a parking function is a preference list
with zero defect. If $d\in\mathbb{Z}_{\geq 0}$, we let $\mathrm{DPF}_{m,n,d}$
denote the set of all defective parking functions with defect $d$, and as
usual $|\mathrm{DPF}_{m,n,d}|$ denotes the cardinality of the set. We refer
the reader to [7] for the enumeration of defective parking functions.

Our first contribution provides a quick way to determine the defect of a
preference list whose entries are nondecreasing.

######  Definition 1.1.

The defect of a parking preference $\mathbf{x}\in[n+1]^{m}$ is denoted
$\mathrm{dft}(\mathbf{x})$.

######  Proposition 1.2.

If $\mathbf{x}=(x_{1},x_{2},\ldots,x_{m})$ is a nondecreasing element of
$[n+1]^{m}$, then $\mathbf{x}\in\mathrm{DPF}_{m,n,d}$ where
$d=\mathrm{dft}(\mathbf{x})=\displaystyle\max_{i\in[m]}(x_{i}-i+(m-n),0)$.

######  Remark 1.3.

In the study of parking functions, most authors add the restriction that there
not be more cars than spots — indeed if $m>n$ then some amount of cars will
fail to park. In this case, however, we add no such restriction. In the case
where there are more cars than spots, we simply observe that defect $d$ is
positive and no less than $m-n$.

We recall that an important feature of parking functions is that they are
invariant under the action of $\mathfrak{S}_{m}$, the symmetric group on
$[m]$, see [20, §4 Example 1]. Namely, given
$\alpha=(a_{1},a_{2},\ldots,a_{m})\in\mathrm{PF}_{m,n}$ and any
$\pi\in\mathfrak{S}_{m}$, the tuple

$\pi\cdot\alpha=(a_{\pi^{-1}(1)},a_{\pi^{-1}(2)},\ldots,a_{\pi^{-1}(m)})\in\mathrm{PF}_{m,n}.$

It is a well-documented result (see [5] for a proof) that the
$\mathfrak{S}_{n}$-orbits of $\mathrm{PF}_{n,n}$ are enumerated by the Catalan
numbers, which are defined by [27, A000108]:

${\mathcal{C}}_{n}=\frac{1}{n+1}\binom{2n}{n}.$

There are multiple ways to consider parking functions with unequal number of
cars and spots. Armstrong, Loehr, and Warrington [4] consider the case where
$m$ and $n$ are coprime and in which case a car takes up a fraction of a spot.
In this paper, we allow for $m$ and $n$ to be any positive integers and for
each car to occupy exactly one spot. Our first result establishes that the
defect of a parking function is invariant under the action of
$\mathfrak{S}_{m}$, an analogous result to that in classical parking
functions.

######  Theorem 1.4.

If $m,n\in\mathbb{N}$ and $d\in\mathbb{Z}_{\geq 0}$, then the set
$\mathrm{DPF}_{m,n,d}$ is invariant under the action of $\mathfrak{S}_{m}$.

We then establish the following bijection.

######  Theorem 1.5.

The set of nondecreasing defective parking functions of defect
$d\in\mathbb{Z}_{\geq 0}$, denoted $\mathrm{DPF}_{m,n,d}^{\uparrow},$ is in
bijection with the set of standard Young tableaux of shape $(n+d,m-d)$.

As a consequence of Theorem 1.5 and the hook length formula (see [18] or [28,
Section 3.10]), we establish a formula for the number of
$\mathfrak{S}_{m}$-orbits of the set of defective parking functions with
defect $d$.

######  Corollary 1.6.

If $m,n\in\mathbb{N}$ and $d\in\mathbb{Z}_{\geq 0}$, then

$\displaystyle|\mathrm{DPF}^{\uparrow}_{m,n,d}|$
$\displaystyle=\frac{n-m+2d+1}{n+d+1}\binom{m+n}{n+d}.$ (1)

When $d=0$ all cars can park and equation (1) reduces to the Catalan numbers
when $n=m$.

In Theorem 4.1, we provide a multinomial formula for the size of the
$\mathfrak{S}_{m}$-orbit given a nondecreasing defective parking function. We
then use this result to give a new formula for the number of defective parking
functions as multiset permutations of nondecreasing defective parking
functions.

######  Theorem 1.7.

If $m,n,d\in\mathbb{N}$, then

$\displaystyle|\mathrm{DPF}_{m,n,d}|$
$\displaystyle=\sum_{\mathbf{x}\in\mathrm{DPF}^{\uparrow}_{m,n,d}}\binom{m}{\ell_{1}(\mathbf{x}),\ell_{2}(\mathbf{x}),\ldots,\ell_{n}(\mathbf{x})},$
(2)

where, for $1\leq i\leq n$, $\ell_{i}(\mathbf{x})$ denotes the number of
elements of $\mathbf{x}$ whose value is $i$.

The paper is organized as follows. In Section 2 we give a way to determine the
defect of a preference list and use this result to prove Theorem 1.4. In
Section 3 we prove Theorem 1.5 by establishing a set of bijections from which
the result follows. Section 4 contains proofs of the enumerative results in
Corollary 1.6, Theorem 4.1, and Theorem 1.7. We conclude with directions for
future research.

##  2\. Defect is an $\mathfrak{S}_{m}$-invariant

Prominent literature defines parking functions as elements of $[n]^{m}$, see
[26] or [29, Exercise 5.29. a.]. As we are concerned with defective parking
functions where not all cars may manage to park, we include the possible
preference $n+1$ to indicate the possibility of a car preferring none of the
available spots. Considering parking functions as elements of $[n+1]^{m}$
facilitates clarity when we introduce the conjugate of a parking function
(Definition 3.13). Moreover, it creates the possibility of a defective parking
function where no cars manage to park, in which all cars simply enter and exit
the parking lot without desiring to park. A preference list that includes
$n+1$ is not a parking function, so in the study of standard parking functions
this difference in convention is immaterial. Thus we employ the following
definitions.

######  Notation 2.1.

Throughout the article we use the following notation.

  * •

We use bold font to denote that $\mathbf{x}$ is a preference list and we let
$x_{i}$ denotes the $i$th element of $\mathbf{x}$.

  * •

Given a set of preference lists $S$ and a condition $P$ on $S$, we let $S(P)$
denote the subset of elements of $S$ that satisfy $P$.

######  Definition 2.2.

A preference list is an element $\mathbf{x}\in[n+1]^{m}$ in which $m$ cars
attempt to park in the first $n$ parking spots along a one-way street with
infinite spots. Cars park according to the classical parking scheme, where car
$i$ will attempt to park in the $x_{i}$th spot, continuing along the street to
park in the next available open spot if it finds the $x_{i}$th spot occupied.
A parking function is a preference list in which no car parks beyond the $n$th
spot in the classical parking scheme.

The set of parking functions with $m$ cars and $n$ spots is denoted
$\mathrm{PF}_{m,n}$ and the subset consisting of nondecreasing parking
functions is denoted by $\mathrm{PF}^{\uparrow}_{m,n}$.

######  Definition 2.3.

A defective parking function with defect $d$ is a preference list in which
exactly $d$ cars fail to park under the classical parking scheme. The set of
defective parking functions with $m$ cars, $n$ spots, and defect $d$ is
denoted by $\mathrm{DPF}_{m,n,d}$. The subset of $\mathrm{DPF}_{m,n,d}$ whose
elements are nondecreasing is denoted by $\mathrm{DPF}^{\uparrow}_{m,n,d}$.

######  Example 2.4.

Let $m=7$ and $n=9$. Consider the nondecreasing preference list
$(3,5,5,6,9,9,10)\in[10]^{7}$. Cars park/fail to park as illustrated in Figure
1. Since the preference list was nondecreasing, the cars parked (on an
infinitely long parking lot) in the order they arrived. The two cars that park
in a spot numbered $j\geq n+1=10$ failed to park in the parking lot. Hence,
the defect of $(3,5,5,6,9,9,10)$ is two.

$1$$2$$3$$4$$5$67cars that failed to park$1$$2$$3$$4$$5$$6$$7$$8$$9$end of lot
Figure 1. Parking position of cars with preference list
$(3,5,5,6,9,9,10)\in\mathrm{DPF}^{\uparrow}_{7,9,2}$.

######  Definition 2.5.

If $\mathbf{x}\in\mathrm{DPF}^{\uparrow}_{m,n,d}$, let

$\delta(\mathbf{x})=(x_{1}-1+(m-n),x_{2}-2+(m-n),\ldots,x_{m}-m+(m-n)).$

For $i\in[m]$, the $i$th entry of $\delta(\mathbf{x})$ is called the defect at
$i$ which we denote by

$\delta(\mathbf{x})_{i}\coloneqq x_{i}-i+(m-n).$

######  Remark 2.6.

In the case that $m=n$ and $d=0$, $f:\mathbf{x}\mapsto-\delta(\mathbf{x})$
gives a bijection between $\mathrm{PF}^{\uparrow}_{n,n}$ and Catalan words.
For more on Catalan words we refer the interested reader to [29, exercise
6.19.u, p. 222].

######  Example 2.7 (Example 2.4 continued).

Consider $\mathbf{x}=(3,5,5,6,9,9,10)\in\mathrm{DPF}^{\uparrow}_{7,9,2}$,
which satisfies $\delta(\mathbf{x})=(0,1,0,0,2,1,1)$. The maximum value in
$\delta(\mathbf{x})$ is two, which happens to be $\mathrm{dft}(\mathbf{x})$,
the defect of $\mathbf{x}$.

######  Lemma 2.8.

If $\mathbf{x}\in\mathrm{DPF}^{\uparrow}_{m,n,d}$, then
$\max(m-n,0)\leq\mathrm{dft}(\mathbf{x})\leq m$.

###### Proof.

There are $n-m$ more parking spots than cars. The minimum possible defect for
any preference list in $[n+1]^{m}$ is $\max(m-n,0)$, which is achieved
whenever all of the cars park in the first $m$ parking spots.

The maximum possible defect for any preference list in $[n+1]^{m}$ is $m$,
which is achieved whenever all of the cars prefer the $(n+1)$st parking spot
and all fail to park in the first $n$ parking spots. Hence
$\max(m-n,0)\leq\mathrm{dft}(\mathbf{x})\leq m$. ∎

Next we prove that in fact the defect of a nondecreasing parking list
$\mathbf{x}$ is always the maximum entry in $\delta(\mathbf{x})$. This allows
us to determine the defect of a preference list without having to employ the
parking scheme.

######  Proposition 2.9 (Restatement of Proposition 1.2).

If $\mathbf{x}$ is a nondecreasing element of $[n+1]^{m}$, then
$\mathrm{dft}(\mathbf{x})=\displaystyle\max_{i\in[m]}(\delta(\mathbf{x})_{i},0)$.

###### Proof.

We proceed by induction on $m$. A preference list with $m=1$ car is simply an
element $\mathbf{x}=(x_{1})\in[n+1]^{1}$. If $x_{1}\leq n$, the car parks and
$\mathrm{dft}(\mathbf{x})=0$. If $x_{1}=n+1$ then
$\mathrm{dft}(\mathbf{x})=1$, matching $\delta(\mathbf{x})_{1}=n+1-1+(1-n)=1$.

Now assume for the purpose of induction that $m>1$ and that for any
nondecreasing preference list $\mathbf{x}^{\prime}\in[n+1]^{m-1}$ that
$\mathrm{dft}(\mathbf{x}^{\prime})=\max_{j\in[m-1]}(\delta(\mathbf{x})_{i},0)$.
Consider some nondecreasing preference list $\mathbf{x}\in[n+1]^{m}$. For each
$i\in[m]$, let $p_{i}$ denote the parking position of car $i$ with preference
$x_{i}$. Recall that since $\mathbf{x}$ is nondecreasing, $p_{i}<p_{i+1}$ for
all $i\in[m-1]$. The restriction
$\mathbf{x}^{\prime}=(x_{1},x_{2},\ldots,x_{m-1})$ of $\mathbf{x}$ to its
first $m-1$ indices is a nondecreasing element of $[n+1]^{m-1}$, so

$\mathrm{dft}(\mathbf{x}^{\prime})=\max_{j\in[m-1]}\\{\delta(\mathbf{x}^{\prime})_{i},0\\},$

where $\mathbf{x}^{\prime}\in\mathrm{DPF}^{\uparrow}_{m-1,n,d^{\prime}}$ for
some $d^{\prime}\geq 0$.

The rest of the argument depends on whether
$\mathrm{dft}(\mathbf{x}^{\prime})=0$ or if
$\mathrm{dft}(\mathbf{x}^{\prime})>0$. We consider each case separately.

  1. (1)

If $\mathrm{dft}(\mathbf{x}^{\prime})=0$, there are two cases.

     * •

If $p_{m-1}\leq n-1$, then in $\mathbf{x}$ when the $m$th car goes to park,
the $n$th position is empty. Then we can regard $\mathbf{x}^{\prime}$ not as
an element of $\mathrm{DPF}^{\uparrow}_{m-1,n,0}$ but as an element of
$\mathrm{DPF}^{\uparrow}_{m-1,n-1,0}$. Then

$\max_{j\in[m-1]}\\{x_{j}-j+((m-1)-(n-1))\\}=\max_{j\in[m-1]}\\{x_{j}-j+(m-n)\\}\leq
0$

by the inductive hypothesis. If $x_{m}\leq n$ then
$\delta(\mathbf{x})_{m}=x_{m}-m+(m-n)=x_{m}-n\leq 0$, so

$\max_{j\in[m]}\\{x_{j}-j+(m-n),0\\}=0.$

Moreover, $p_{m}\leq n$, so $\mathrm{dft}(\mathbf{x})=0$. If $x_{m}=n+1$, then
$\delta(\mathbf{x})_{m}=1$, so

$\max_{j\in[m]}\\{x_{j}-j+(m-n),0\\}=1,$

corresponding to the fact that $\mathrm{dft}(\mathbf{x})=1$ because only the
last car fails to park.

     * •

If $p_{m-1}=n$, then $p_{m}>n$. The $m$th car is the unique car that fails to
park, so $\mathrm{dft}(\mathbf{x})=1$. In this case we regard
$\mathbf{x}^{\prime}$ as an element of $\mathrm{DPF}^{\uparrow}_{m-1,n-1,1}$
and see that

$\mathrm{dft}(\mathbf{x}^{\prime})=\max_{j\in[m-1]}\\{x_{j}-j+((m-1)-(n-1))\\}=\max_{j\in[m-1]}\\{x_{j}-j+(m-n)\\}=1.$

Because $x_{m}\leq n+1$, we have $\delta(\mathbf{x})_{m}=x_{m}-m+(m-n)\leq 1$.
Then

$\max_{j\in[m]}\\{x_{j}-j+(m-n)\\}=1=\mathrm{dft}(\mathbf{x})$

as desired.

  2. (2)

Now suppose that $\mathrm{dft}(\mathbf{x}^{\prime})>0$. We now solely consider
$\mathbf{x}^{\prime}$ as an element of
$\mathrm{DPF}^{\uparrow}_{m-1,n,d^{\prime}}$ for some $d^{\prime}>0$. Observe
that for $j\in[m-1]$,

$\delta(\mathbf{x})_{j}=x_{j}-j+(m-n)=x_{j}-j+((m-1)-n)+1=\delta(\mathbf{x}^{\prime})_{j}+1$

and that $\mathrm{dft}(\mathbf{x}^{\prime})$ measures the difference between
the true position of the $(m-1)$th car of $\mathbf{x}$ and the $n$th parking
spot. Namely, $\mathrm{dft}(\mathbf{x}^{\prime})=p_{m-1}-n$ and, hence,
$\mathrm{dft}(\mathbf{x}^{\prime})+n=p_{m-1}$.

     * •

Suppose that

$\delta(\mathbf{x})_{m}\geq\max_{j\in[m-1]}\delta(\mathbf{x})_{j}=\mathrm{dft}(\mathbf{x}^{\prime})+1.$

Hence, $x_{m}-m+(m-n)=x_{m}-n\geq p_{m-1}-n+1$. Hence $x_{m}>p_{m-1}$. In
other words, after $m-1$ cars have parked, the $x_{m}$th spot remains
available. Thus car $m$ parks in the $x_{m}$th spot (the $m$th car is lucky).
Then $\delta(\mathbf{x})_{m}=x_{m}-n$, and so

$\mathrm{dft}(\mathbf{x})=x_{m}-n=\max_{j\in[m]}\delta(\mathbf{x})_{j}.$

     * •

Suppose that

$\delta(\mathbf{x})_{m}<\max_{j\in[m-1]}\delta(\mathbf{x})_{j}=\mathrm{dft}(\mathbf{x}^{\prime})+1.$

Then following similar logic to the previous case, there is some $j\in[m-1]$
where car $j$ parks in spot $x_{m}$ (the $m$th car is unlucky). Because
$\mathbf{x}$ is nondecreasing and cars in a nondecreasing preferences list
park in order, car $m$ must park in the spot directly following where car
${m-1}$ parked. Namely $p_{m}=p_{m-1}+1$. Then $\mathrm{dft}(\mathbf{x})$ is
exactly one more than $\mathrm{dft}(\mathbf{x}^{\prime})$, so

$\mathrm{dft}(\mathbf{x})=\mathrm{dft}(\mathbf{x}^{\prime})+1=\max_{j\in[m]}\delta(\mathbf{x})_{j}.\qed$

We can now give a proof that the defect is invariant under the action of the
symmetric group.

###### Proof of Theorem 1.4.

Stanley and Pitman [30] introduced the following definition: For an integer
tuple $\textbf{u}=(u_{1},u_{2},\ldots,u_{k})$ with $k\in\mathbb{N}$, the set
of u-parking functions consist of the sequences $(a_{1},a_{2},\ldots,a_{k})$
whose rearrangement into nondecreasing order $(b_{1},b_{2},\ldots,b_{k})$
satisfy $b_{i}\leq u_{1}+\cdots+u_{i}$ for all $1\leq i\leq k$. In this way
when $\textbf{u}=(1,1,\ldots,1)\in[n]^{m}$, the set of u-parking functions is
precisely the set of $(m,n)$-parking functions. Moreover, Cameron et. al [7,
p. 3] give a characterization of defective parking functions with $m$ cars,
$n$ parking spots, and defect $d$ as

$(n-(m-d)+1\;,\;\underbrace{1,\;1,\;\ldots\;,1}_{\begin{matrix}2m-n-d\\\
\mbox{copies}\end{matrix}}\;,\;\underbrace{0,\;0,\;\ldots\;,0}_{\begin{matrix}d+(n-m)\\\
\mbox{copies}\end{matrix}})\mbox{-parking functions}$

that are not

$(n-(m-d)\;,\;\underbrace{1,\;1,\;\ldots\;,1}_{\begin{matrix}2m-n-d\\\
\mbox{copies}\end{matrix}}\;,\;\underbrace{0,\;0,\;\ldots\;,0}_{\begin{matrix}d+(n-m)\\\
\mbox{copies}\end{matrix}})\mbox{-parking functions.}$

As this holds for any initial parking function with defect $d$, this implies
that the defect only depends on the content of the parking function and not on
the order of the entries. Thus, in combination with Proposition 2.9, defective
parking functions are permutation invariant. ∎

##  3\. Main Bijection

In this section, we prove Theorem 1.5 and Corollary 1.6 through a chain of
bijective arguments. To begin we consider the case where there are the same
number of cars as numbered parking spots on the street.

###  3.1. Equal number of cars and spots

Throughout this section we let $m=n$, in which case $d\geq n-m=0$. Before
proceeding we point the reader to Figure 2 which provides a visual of the
bijections we will prove in this section.

Establishing the bijections illustrated via solid lines, we then establish a
bijection between the set of nondecreasing defective $(m,n)$-parking functions
with defect $d$ whose last entry is less than or equal to $k\in[n]$, which we
denote by $\mathrm{DPF}^{\uparrow}_{n,n,d}(x_{n}\leq k)$, and the set of
nondecreasing parking functions of length $n+d$ whose last entry is less than
or equal to $k-d$, which we denote by
$\mathrm{PF}^{\uparrow}_{n+d,n+d}(x_{n+d}\leq k-d)$.

${{\mathrm{DPF}^{\uparrow}_{n,n,d}(x_{n}\leq
k)}}$${{\mathrm{PF}^{\uparrow}_{n+d,n+d}(x_{n+d}\leq
k-d)}}$${{N_{n,d-1}}(x_{n}\leq k-1)}$${{M_{n+d-1}(x^{\prime}_{n+d-1}\leq
k-d)}}$Lemma 3.5Lemma 3.9$\scriptstyle{\text{Induction (Theorem
}\ref{thm:main-bij})}$Theorem 3.10 Figure 2. Illustration depicting the
bijections presented in this section in order to establish Theorem 3.10.

We begin by introducing some additional definitions and notation that will
assist in brevity.

######  Definition 3.1.

Given a defective parking function
$\mathbf{x}\in\mathrm{DPF}^{\uparrow}_{n,n,d}$, the decrement set of
$\mathbf{x}$, denoted $D(\mathbf{x})\subseteq[n]$, is the set of indices
$i\in[n]$ where $\delta(\mathbf{x})_{i}\geq 0$ and there does not exists an
integer $j<i$ with $\delta(\mathbf{x})_{j}>0$.

######  Example 3.2.

The defective parking function
$\mathbf{x}=(1,1,3,6,6,6)\in\mathrm{DPF}^{\uparrow}_{6,6,2}$ satisfies
$\delta(\mathbf{x})=(0,-1,0,2,1,0)$ and the corresponding decrement set is
$D(\mathbf{x})=\\{1,3,4\\}$.

The decrement set of a preference list will be helpful in establishing some
needed bijections. Part of these bijections will involve decrementing parking
functions at certain indices - the decrement set will be all of the indices
which could have been decremented to arrive at the current parking function. A
key component of our argument will be showing that the decrement set of a
defective parking function corresponds to the fixed point set of a non-
defective parking function.

######  Definition 3.3.

Given $n\geq 1$ and $d\geq 0$, the _decrement pair set_ $N_{n,d}$ is defined
by

$N_{n,d}=\\{(\mathbf{x},i)\mid\mathbf{x}\in\mathrm{DPF}^{\uparrow}_{n,n,d}\mbox{
and }i\in D(\mathbf{x})\\}.$

######  Example 3.4.

The pair set $N_{3,2}$ consists of six tuples $(\mathbf{x},i)$ with
$\mathbf{x}\in\mathrm{DPF}^{\uparrow}_{3,3,2}$ and $i\in D(\mathbf{x})$. Table
1 provides the elements of $\mathrm{DPF}^{\uparrow}_{3,3,2}$,
$\delta(\mathbf{x})$, and the decrement sets $D(\mathbf{x})$.

$\mathbf{x}\in\mathrm{DPF}^{\uparrow}_{3,3,2}$ | $(1,4,4)$ | $(2,4,4)$ | $(3,3,3)$ | $(3,3,4)$ | $(3,4,4)$
---|---|---|---|---|---
$\delta(\mathbf{x})$ | $(0,2,1)$ | $(1,2,1)$ | $(2,1,0)$ | $(2,1,1)$ | $(2,2,1)$
$D(\mathbf{x})$ | $\\{1,2\\}$ | $\\{1\\}$ | $\\{1\\}$ | $\\{1\\}$ | $\\{1\\}$
Table 1. Elements of $\mathrm{DPF}^{\uparrow}_{3,3,2}$, $\delta(\mathbf{x})$,
and the decrement sets $D(\mathbf{x})$.

From Remark 2.1, we recall that whenever we write $S(P)$, we are considering
the restriction of the set $S$ with condition described by $P$. In this way,
the set $\mathrm{DPF}^{\uparrow}_{n,n,d}(x_{n}\leq k)$ denotes the set of
elements
$\mathbf{x}=(x_{1},x_{2},\ldots,x_{n})\in\mathrm{DPF}^{\uparrow}_{n,n,d}$ with
last entry less than or equal to $k$, and the set
$N_{n,d-1}(x^{\prime}_{n}\leq k-1)$ denotes the set of pairs
$(\mathbf{x}^{\prime},i)=((x_{1}^{\prime},x_{2}^{\prime},\ldots,x_{n}^{\prime}),i)\in
N_{n,d-1}$ with $x_{n}^{\prime}$ less than or equal to $k-1$.

We now establish some preliminary bijections.

######  Lemma 3.5.

Let $k\in[n+1]$, $d>0$, and
$\mathbf{x}=(x_{1},x_{2},\ldots,x_{n})\in\mathrm{DPF}^{\uparrow}_{n,n,d}(x_{n}\leq
k)$. Define the map

$\varphi:\mathrm{DPF}^{\uparrow}_{n,n,d}(x_{n}\leq k)\to
N_{n,d-1}(x^{\prime}_{n}\leq k-1)$

by

$\varphi(\mathbf{x})=(\mathbf{x}^{\prime},i),$

where
$\mathbf{x}^{\prime}=(x_{1},x_{2},\ldots,x_{i-1},x_{i}-1,x_{i+1}-1,\ldots,x_{n}-1)$
and $i\in[n]$ denotes the first index such that $\delta(\mathbf{x})_{i}>0$.
Then $\varphi$ is a bijection. Moreover, $D(\mathbf{x})=\\{j\in
D(\mathbf{x}^{\prime})\mid j\leq i\\}$.

###### Proof.

Given
$\mathbf{x}=(x_{1},x_{2},\ldots,x_{n})\in\mathrm{DPF}^{\uparrow}_{n,n,d}$, let
$i$ denote $\max(D(\mathbf{x}))$, the first index such that
$\delta(\mathbf{x})_{i}>0$. Such an index existing follows from Proposition
1.2 and the fact that $\mathbf{x}$ has positive defect. Then choose the map
$\varphi$ with

$\varphi:\mathbf{x}\mapsto((x_{1},x_{2},\ldots,x_{i-1},x_{i}-1,x_{i+1}-1,\ldots,x_{n}-1),i).$

Let
$\mathbf{x}^{\prime}=(x^{\prime}_{1},x^{\prime}_{2},\dots,x^{\prime}_{n})=(x_{1},x_{2},\ldots,x_{i-1},x_{i}-1,x_{i+1}-1,\ldots,x_{n}-1)$,
be the first component of $\varphi(\mathbf{x})$.

  * •

Well-defined: Since $i$ is the smallest index such that
$\delta(\mathbf{x})_{i}>0$, this implies that $x_{i}-i>0$ and
$x_{i-1}-(i-1)\leq 0$. Hence $x_{i}-1>i-1$ and $x_{i-1}\leq i-1$. Thus
$\mathbf{x}^{\prime}$ is still nondecreasing. Also, every index $j$ with
$\delta(\mathbf{x})_{j}>0$ has $j\geq i$ by definition, so the $j$th entry of
$\mathbf{x}^{\prime}$ satisfies $x^{\prime}_{j}=x_{j}-1$. Therefore, by
Proposition 1.2 the defect of $\mathbf{x}^{\prime}$ satisfies

$\max_{1\leq j\leq n}(\delta(\mathbf{x}^{\prime})_{j})=\max_{1\leq j\leq
n}(\delta(\mathbf{x})_{j})-1=d-1.$

This establishes that $\varphi$ is well-defined on the first component. Also,
because $\delta(\mathbf{x})_{i}>0$ and $x^{\prime}_{i}=x_{i}-1$, we know
$\delta(\mathbf{x}^{\prime})_{i}\geq 0$. If there were some $j<i$ with
$\delta(\mathbf{x}^{\prime})_{j}>0$, then we would also have
$\delta(\mathbf{x})_{j}>0$, as $x^{\prime}_{j}=x_{j}$ for all $j\in[i-1]$.
Contradicting the definition of $i$. Hence $i\in D(\mathbf{x}^{\prime})$ and
$\varphi$ is well-defined on the second component.

  * •

Injective: Suppose
$\mathbf{x}=(x_{1},x_{2},\ldots,x_{n}),\mathbf{y}=(y_{1},y_{2},\ldots,y_{n})\in\mathrm{DPF}^{\uparrow}_{n,n,d}$
and assume that $\varphi(\mathbf{x})=\varphi(\mathbf{y})$. Then the first
coordinates are equal, i.e. $\mathbf{x}^{\prime}=\mathbf{y}^{\prime}$. This
implies that $x^{\prime}_{j}=y^{\prime}_{j}$ for all $1\leq j\leq n$. This
together with the definition of $\varphi$ implies that

    * –

if $j<i$, then $y_{j}^{\prime}=x^{\prime}_{j}=x_{j}$, and

    * –

if $j\geq i$, then $y_{j}^{\prime}=x^{\prime}_{j}=x_{j}+1$.

This implies that $\mathbf{x}=\mathbf{y}$.

  * •

Surjective: Suppose $(\mathbf{x}^{\prime},i)\in N_{n,d-1}$. Let

$\mathbf{x}=(x^{\prime}_{1},x^{\prime}_{2},\ldots,x^{\prime}_{i-1},x^{\prime}_{i}+1,x^{\prime}_{i+1}+1,\ldots,x^{\prime}_{n}+1).$

Then from the definition of $\varphi$,
$\varphi(\mathbf{x})=(\mathbf{x}^{\prime},i)$. By proposition 1.2
$d-1=\max_{j\in[m]}(\delta(\mathbf{x}^{\prime})_{j})$. Let $j$ denote an index
where $\delta(\mathbf{x}^{\prime})_{j}=d-1$. From the definition of
$D(\mathbf{x}^{\prime})$, $i\leq j$. Then $\delta(\mathbf{x})_{j}=d$ and this
is maximal, so $\mathbf{x}$ has defect $d$. Finally, because
$x^{\prime}_{n}\leq k-1$, $x_{n}\leq k$, so
$\mathbf{x}\in\mathrm{DPF}^{\uparrow}_{n,n,d}(x_{n}\leq k)$ as desired.

Therefore, $\varphi$ is a bijection.

To conclude we prove that $D(\mathbf{x})=\\{j\in D(\mathbf{x}^{\prime})\mid
j\leq i\\}$ by establishing two set containments:

  * •

$D(\mathbf{x})\subseteq\\{j\in D(\mathbf{x}^{\prime})\mid j\leq i\\}$: Suppose
$j\in D(\mathbf{x})$. Because $i=\max(D(\mathbf{x}))$, $j\leq i$. Hence, for
all $\ell<j$ we know $x_{\ell}=x^{\prime}_{\ell}$, so
$\delta(\mathbf{x}^{\prime})_{\ell}\leq 0$.

    * –

If $j<i$, then $x^{\prime}_{j}=x_{j}$, so $\delta(\mathbf{x}^{\prime})_{j}=0$.

    * –

If $j=i$, then $\delta(\mathbf{x})_{j}>0$, so
$\delta(\mathbf{x}^{\prime})_{j}\geq 0$. Then $j\in D(\mathbf{x}^{\prime})$
and $j\leq i$. Thus $j\in\\{j\in D(\mathbf{x}^{\prime})\mid j\leq i\\}$, as
desired.

  * •

$\\{j\in D(\mathbf{x}^{\prime})\mid j\leq i\\}\subseteq D(\mathbf{x})$:
Suppose $j\in\\{j\in D(\mathbf{x}^{\prime})\mid j\leq i\\}$. Again, because
$j\leq i$ we know that $x_{\ell}=x^{\prime}_{\ell}$ for all $\ell<j$. Then
$\delta(\mathbf{x})_{\ell}\leq 0$.

    * –

If $j<i$, then $x_{j}=x^{\prime}_{j}$. Hence,
$\delta(\mathbf{x}^{\prime})_{j}=0$.

    * –

If $j=i$, then $\delta(\mathbf{x}^{\prime})_{j}\geq 0$, so
$\delta(\mathbf{x})_{j}>0$.

Thus $j\in D(\mathbf{x})$, as desired.∎

We now introduce the following definitions in order to establish our next
bijection.

######  Definition 3.6.

Given $\mathbf{x}\in\mathrm{PF}^{\uparrow}_{n,n}$, the fixed set of
$\mathbf{x}$ is

$F(\mathbf{x})=\\{i\in[n]\mid\delta(\mathbf{x})_{i}=0\\}.$

Since $m=n$, $i\in F(\mathbf{x})$ is equivalent to saying $x_{i}=i$.

######  Example 3.7.

The fixed set of the parking function
$\mathbf{x}=(1,1,2,3,5)\in\mathrm{PF}^{\uparrow}_{5,5}$ satisfies
$\delta(\mathbf{x})=(0,-1,-1,-1,0)$. Hence, $F(\mathbf{x})=\\{1,5\\}$.

######  Definition 3.8.

The _fixed pair set_ is defined by

$M_{n}=\\{(\mathbf{x},i)\mid\mathbf{x}\in\mathrm{PF}^{\uparrow}_{n,n}\mbox{
and }i\in F(\mathbf{x})\\}.$

######  Lemma 3.9.

Let $k\in[n]$ and
$\mathbf{x}=(x_{1},x_{2},\ldots,x_{n+1})\in\mathrm{PF}^{\uparrow}_{n+1,n+1}(x_{n}\leq
k)$. Define the map

$\psi:\mathrm{PF}^{\uparrow}_{n+1,n+1}(x_{n+1}\leq k)\to M_{n}(x_{n}\leq k)$

by

$\psi(\mathbf{x})=(\mathbf{x}^{\prime},i),$

where $i=\max(F(\mathbf{x}))$ and

$\mathbf{x}^{\prime}=(x_{1},x_{2},\ldots,x_{i-1},x_{i+1},x_{i+2},\ldots,x_{n+1}).$

Then $\psi$ is a bijection. Moreover, $F(\mathbf{x}^{\prime})=\\{j\in
F(\mathbf{x})\mid j\leq i\\}$.

###### Proof.

Fix
$\mathbf{x}=(x_{1},x_{2},\ldots,x_{n+1})\in\mathrm{PF}^{\uparrow}_{n+1,n+1}(x_{n+1}\leq
k)$ and let $i=\max(F(\mathbf{x}))$. Let

$\mathbf{x}^{\prime}=(x^{\prime}_{1},x^{\prime}_{2},\dots,x^{\prime}_{n})=(x_{1},x_{2},\ldots,x_{i-1},x_{i+1},x_{i+2},\ldots,x_{n+1}),$

be the first component of $\psi(\mathbf{x})$.

  * •

Well-defined: Since $\mathbf{x}$ is a nondecreasing parking function, we know
that $x_{i}\leq i$ for all $i\in[n+1]$. Moreover, since
$i=\max(F(\mathbf{x}))$, we know that $x_{\ell}-\ell<0$ whenever $i<\ell\leq
n+1$. Hence $x_{\ell}<\ell$ for all $i<\ell\leq n+1$. Now removing $x_{i}$
from $\mathbf{x}$ to construct $\mathbf{x}^{\prime}$ ensures that
$\mathbf{x}^{\prime}$ satisfies the following:

    * –

If $1\leq j<i$, then $x^{\prime}_{j}=x_{j}\leq j$, and

    * –

if $i\leq j\leq n$, then $x^{\prime}_{j}=x_{j+1}<j+1$. This condition implies
that $x_{j}^{\prime}\leq j$.

Together the above two condition ensure that $x^{\prime}$ satisfies
$x_{\ell}\leq\ell$ for all $\ell\in[n]$. Therefore,
$\mathbf{x}\in\mathrm{PF}^{\uparrow}_{n,n}$. By assumption $x_{n+1}\leq k$ and
$x^{\prime}_{n}=x_{n+1}$. Thus $x_{n}^{\prime}\leq k$, which implies that
$\mathbf{x}^{\prime}\in\mathrm{PF}^{\uparrow}_{n,n}(x_{n}^{\prime}\leq k)$, as
desired. Then $\psi$ is well-defined on the first component.

Because $k\leq n$, $x_{n+1}<n+1$ so $i<n+1$. As $i=\max(F(\mathbf{x}))$, then
$i+1$ is not the index of a fixed point of $\mathbf{x}$, so $x_{i+1}<i$. Then

$i=x_{i}\leq x_{i+1}<i+1,$ (3)

so $x^{\prime}_{i}=x_{i+1}=i$. This implies that $i$ is in
$F(\mathbf{x}^{\prime})$, so $\psi$ is well-defined on the second component.

  * •

Surjective: Suppose $(\mathbf{x}^{\prime},i)\in M_{n}$, where
$\mathbf{x}^{\prime}=(x_{1}^{\prime},x_{2}^{\prime},\ldots,x_{n}^{\prime})\in\mathrm{PF}^{\uparrow}_{n,n}$
with $x_{n}^{\prime}\leq k$. Then let

$\mathbf{x}=(x_{1},x_{2},\ldots,x_{n+1})=(x^{\prime}_{1},x^{\prime}_{2},\ldots,x^{\prime}_{i-1},i,x^{\prime}_{i},x^{\prime}_{i+1},\ldots,x^{\prime}_{n}).$

Namely,

$x_{j}=\begin{cases}x^{\prime}_{j}&\mbox{if }1\leq j<i\\\ i&\mbox{if }j=i\\\
x^{\prime}_{j-1}&\mbox{if }i<j\leq n+1.\par\end{cases}$

We claim that $\mathbf{x}\in\mathrm{PF}^{\uparrow}_{n+1,n+1}(x_{n+1}\leq k)$
and $\psi(\mathbf{x})=(\mathbf{x}^{\prime},i)$.

We will show that $x_{j}\leq j$ for all $j\in[n+1]$, which will establish that
$\mathbf{x}\in\mathrm{PF}^{\uparrow}_{n+1,n+1}$. In the case that $1\leq j<i$
we have $x_{j}=x^{\prime}_{j}\leq j$. When $j=i$ we have $x_{i}=i$. When
$i<j\leq n+1$ we have $x_{j}=x^{\prime}_{j-1}\leq j-1\leq j$. Thus $x_{j}\leq
j$ for all $j\in[n+1]$ and so $\mathbf{x}$ is a parking function. Because
$x^{\prime}_{i}=i$, we have

$x_{i-1}<x_{i}=x_{i+1},$

so $\mathbf{x}$ is nondecreasing. Then
$\mathbf{x}\in\mathrm{PF}^{\uparrow}_{n+1,n+1}$. Also, because
$x_{j}=x^{\prime}_{j-1}\leq j-1<j$, $i$ must be the index of the last fixed
point of $\mathbf{x}$, so $\psi(\mathbf{x})=(\mathbf{x}^{\prime},i)$ as
desired.

  * •

Injective: Suppose
$\mathbf{x}=(x_{1},x_{2},\ldots,x_{n+1}),\mathbf{y}=(y_{1},y_{2},\ldots,y_{n+1})\in\mathrm{PF}^{\uparrow}_{n+1,n+1}$
and assume that $\psi(\mathbf{x})=\psi(\mathbf{y})$. This implies that
$\max(F(\mathbf{x}))=\max(F(\mathbf{y}))$, which we denote by $i$. Moreover,
the first coordinates are equal, i.e.
$\mathbf{x}^{\prime}=\mathbf{y}^{\prime}$, which implies that
$x^{\prime}_{j}=y^{\prime}_{j}$ for all $j\in[n+1]\setminus\\{i\\}$. By the
definition of $\psi$, this implies that $x_{j}=y_{j}$ for all
$j\in[n+1]\setminus\\{i\\}$. Then as
$i=\max(F(\mathbf{x}))=\max(F(\mathbf{y}))$, we have that $x_{i}=i=y_{i}$.
Thus $\mathbf{x}=\mathbf{y}$, and $\psi$ is injective.

This establishes that $\psi$ is a bijection.

To conclude we prove that $F(\mathbf{x})=\\{j\in F(\mathbf{x}^{\prime})\mid
j\leq i\\}$ by establishing two set containments:

  * •

$F(\mathbf{x})\subseteq\\{j\in F(\mathbf{x}^{\prime})\mid j\leq i\\}$: Suppose
$j\in F(\mathbf{x})$. Recall $i=\max(F(\mathbf{x}))$. Hence,

$x^{\prime}_{j}=\begin{cases}x_{j}&\mbox{if }1\leq j<i\\\ x_{j+1}&\mbox{if
}j=i.\end{cases}$

If $1\leq j<i$, then $x^{\prime}_{j}=x_{j}<j$. If $j=i$, then from equation
(3) we know that $x_{j+1}=j$, so $j\in F(\mathbf{x}^{\prime})$. Thus
$j\in\\{F(\mathbf{x}^{\prime})\mid j\leq i\\}$.

  * •

$\\{j\in F(\mathbf{x}^{\prime})\mid j\leq i\\}\subseteq F(\mathbf{x})$:
Suppose $j\in F(\mathbf{x}^{\prime})$ and $1\leq j\leq i$. Then we have

$x_{j}=\begin{cases}x^{\prime}_{j}&\mbox{if }1\leq j<i\\\ i&\mbox{if
}j=i.\end{cases}$

Hence, if $1\leq j<i$, then
$\delta(\mathbf{x})_{j}=x_{j}-j=x^{\prime}_{j}-j=0$ and $j\in F(\mathbf{x})$.
If $j=i$, then $\delta(\mathbf{x})_{j}=x_{j}-j=i-i=0$ and so $j\in
F(\mathbf{x})$. In both cases we get that $j\in F(\mathbf{x})$, as desired.∎

######  Theorem 3.10.

For fixed $k\in[n+1]$, there is a bijection

$\rho:\mathrm{DPF}^{\uparrow}_{n,n,d}(x_{n}\leq
k)\to\mathrm{PF}^{\uparrow}_{n+d,n+d}(x_{n+d}\leq k-d)$

such that $\mathbf{x}\in\mathrm{DPF}^{\uparrow}_{n,n,d}(x_{n}\leq k)$
satisfies $D(\mathbf{x})=F(\rho(\mathbf{x}))$.

###### Proof.

We induct on $d\geq 0$. For the base case $d=0$, note that
$\mathrm{DPF}^{\uparrow}_{n,n,0}=\mathrm{PF}^{\uparrow}_{n,n}$. Then, when
$d=0$, we are tasked with finding a bijection

$\rho:\mathrm{PF}^{\uparrow}_{n,n}(x_{n}\leq
k)\longleftrightarrow\mathrm{PF}^{\uparrow}_{n,n}(x_{n}\leq k)$

that sends elements of the decrement set of the input $\mathbf{x}$ to elements
of the fixed point set of $\rho(\mathbf{x})$. The elements of the decrement
set of a parking function $\mathbf{x}$ with no defect are precisely the
elements of the fixed point set of $\mathbf{x}$. Thus the desired bijection
$\rho$ is simply the identity.

Now for the purpose of induction suppose there is a bijection

$\rho:\mathrm{DPF}^{\uparrow}_{n,n,d-1}(x_{n}\leq
k)\longleftrightarrow\mathrm{PF}^{\uparrow}_{n+d-1,n+d-1}(x_{n+d-1}\leq
k-d+1)$

such that $D(\mathbf{x})=F(\rho(\mathbf{x}))$.

For the induction step, first, from Lemmas 3.5 and 3.9, we have bijections

$\displaystyle\varphi$
$\displaystyle:\mathrm{DPF}^{\uparrow}_{n,n,d}(x_{n}\leq k)\to
N_{n,d-1}(x_{n}\leq k-1),\mbox{ and}$ $\displaystyle\psi$
$\displaystyle:\mathrm{PF}^{\uparrow}_{n+d,n+d}(x_{n+d}\leq k-d)\to
M_{n+d-1}(x_{n+d-1}\leq k-d)$

that map

$\displaystyle\varphi$
$\displaystyle:\mathbf{x}\mapsto(\mathbf{x}^{\prime},i),\mbox{ and }$
$\displaystyle\psi$ $\displaystyle:\mathbf{y}\mapsto(\mathbf{y}^{\prime},i)$

with

$\displaystyle D(\mathbf{x})$ $\displaystyle=\\{j\in
D(\mathbf{x}^{\prime})\mid j\leq i\\},\mbox{ and }$ $\displaystyle
F(\mathbf{y})$ $\displaystyle=\\{j\in F(\mathbf{y}^{\prime})\mid j\leq i\\}.$

Thus, it is sufficient to find a bijection

$\rho^{\prime}:N_{n,d-1}(x_{n}\leq k-1)\to M_{n+d-1}(x_{n+d-1}\leq k-d)$

that maps

$\rho^{\prime}:(\mathbf{x}^{\prime},i)\mapsto(\mathbf{y}^{\prime},i)$

such that $D(\mathbf{x}^{\prime})=F(\mathbf{y}^{\prime})$. We simply choose
$\mathbf{y}^{\prime}=\rho(\mathbf{x}^{\prime})$ using the inductive
hypothesis. ∎

Setting $k=n+1$ in Theorem 3.10 implies the following result.

######  Corollary 3.11.

For any $n\in\mathbb{N}$ and nonnegative integer $d$, there is a bijection
between the sets $\mathrm{DPF}^{\uparrow}_{n,n,d}$ and
$\mathrm{PF}^{\uparrow}_{n+d,n+d}(x_{n+d}\leq n+1-d)$.

###  3.2. Different numbers of cars and spots

We now consider the more general case where there are $m\in\mathbb{N}$ cars
and $n\in\mathbb{N}$ parking spots. We begin by establishing an analogous
result to Corollary 3.11 in the case when $m>n$.

######  Proposition 3.12.

For $m>n$ and $k\in[m+1]$, there exists a bijection

$\theta:\mathrm{DPF}^{\uparrow}_{m,n,d}\longleftrightarrow\mathrm{PF}^{\uparrow}_{n+d,n+d}(x_{n+d}\leq
m+1-d).$

###### Proof.

Consider $\mathbf{x}\in\mathrm{DPF}^{\uparrow}_{m,n,d}$. Because $x_{1}\geq
1$, we have that

$d=\max_{i\in[m]}(\delta(\mathbf{x})_{i})\geq\delta(\mathbf{x})_{1}\geq m-n.$

Introducing $k$ new spots at the end of the street will reduce defect of
$\mathbf{x}$ by $k$. So in particular, by adding $m-n$ spots we have a
bijection

$\theta_{1}:\mathrm{DPF}^{\uparrow}_{m,n,d}\longleftrightarrow\mathrm{DPF}^{\uparrow}_{m,m,d-(m-n)}(x_{m}\leq
n+1).$

Theorem 3.10 yields a bijection

$\rho:\mathrm{DPF}^{\uparrow}_{m,m,d-(m-n)}(x_{m}\leq
n+1)\longleftrightarrow\mathrm{PF}^{\uparrow}_{n+d,n+d}(x_{n+d}\leq m+1-d).$

The desired result comes from the composition $\theta=\rho\circ\theta_{1}$. ∎

######  Definition 3.13.

The conjugate of
$\mathbf{x}=(x_{1},x_{2},\ldots,x_{m})\in\mathrm{DPF}^{\uparrow}_{m,n,d}$,
denoted $\bar{\mathbf{x}}=(\bar{x}_{1},\bar{x}_{2},\ldots,\bar{x}_{n})$, is
defined by

$\bar{x}_{i}=1+\left|\\{j\in[m]\mid x_{j}>n-i+1\\}\right|$

for $1\leq i\leq n$.

######  Example 3.14.

Consider $\mathbf{x}=(1,1,2,3,5,5,6)\in\mathrm{DPF}^{\uparrow}_{7,5,2}$.
Observe that $\mathbf{x}$ has one entry greater than 5, three entries greater
than 4, three entries greater than 3, four entries greater than 2, and five
entries greater than 1. Then incrementing each of these counts yields

$\bar{\mathbf{x}}=(2,4,4,5,6).$

Conjugation is most easily interpreted in terms of reversal of lattice paths.
We recall that an $(m,n)$ lattice path is a path from $(0,0)$ to $(m,n)$
consisting of $(0,1)$ steps (called north steps and denoted by $N$) and
$(1,0)$ steps (called east steps and denoted by $E$). Such a path is typically
denoted by a word with $n$ $N$’s and $m$ $E$’s. Given a lattice path
$\mathbf{w}$, we let $n_{i}$ denote the position of the $i$th $N$ step in
$\mathbf{w}$. The preference list $\mathbf{x}$ corresponding to $\mathbf{w}$
is defined by

$x_{i}=1+\left|\\{j\in[m+n]\mid w_{j}=E,j<n_{i}\\}\right|.$

In other words, for each $i\in[m]$, the entry $x_{i}$ is one more than the
number of east steps before the $i$th north step. If $n=m$ and we specify that
a lattice path must lie above the $y=x$ line, then the lattice path is called
a Dyck path of semilength $n$. We let $\mathcal{D}_{n}$ denote the set of Dyck
paths of semilength $n$.

######  Definition 3.15.

The conjugate lattice path of $\mathbf{w}$, which we denote by
$\bar{\mathbf{w}}$, is obtained by reversing $\mathbf{w}$ and then switching
$E$’s to $N$’s and $N$’s to $E$’s. The _conjugate of a nondecreasing
preference list_ $\mathbf{x}$, denoted by $\bar{\mathbf{x}}$, is obtained by
conjugating its corresponding lattice path, then turning the result back into
a parking function.

The key intuition in Definition 3.15 is that conjugating the lattice path
corresponds to “flipping” the path along the line $y=-x$ in a process similar
to conjugating a Young diagram.

######  Example 3.16.

Consider $\mathbf{x}=(1,1,2,3,5,5,6)$. In this way the $(5,7)$ lattice path
corresponding to $\mathbf{x}$ is given by $\mathbf{w}=NNENENEENNEN$, Then the
corresponding conjugate path to $\mathbf{w}$ is
$\bar{\mathbf{w}}=ENEENNENENEE$. Both $\mathbf{w}$ and $\bar{\mathbf{w}}$ are
illustrate in Figure 3. We conclude by noting that based on
$\bar{\mathbf{w}}$, one can readily confirm that
$\bar{\mathbf{x}}=(2,4,4,5,6)$. .

$\mathbf{w}=NNENENEENNEN$

$\bar{\mathbf{w}}=ENEENNENENEE$

Figure 3. The lattice path $\mathbf{w}$ corresponding to
$\mathbf{x}=(1,1,2,3,5,5,6)$ as well as its conjugate lattice path
$\bar{\mathbf{w}}$ corresponding to $\bar{\mathbf{x}}=(2,4,4,5,6)$.

######  Proposition 3.17.

If
$c:\mathrm{DPF}^{\uparrow}_{m,n,d}\longleftrightarrow\mathrm{DPF}^{\uparrow}_{n,m,d-(m-n)}$
is defined by $c(\mathbf{x})=\bar{\mathbf{x}}$, then $c$ is an involution.

###### Proof.

Suppose $\mathbf{x}\in\mathrm{DPF}^{\uparrow}_{m,n,d}$. By Definition 3.13,
for any $j\in[n]$,

$\bar{x}_{n-j+1}=1+|\\{i\in[m]:x_{i}>j\\}|,$

which is one plus the number of elements of $\mathbf{x}$ greater than $j$. We
focus on an individual index $i\in[m]$. Suppose $x_{i}=k$ for some
$k\in[n+1]$. First we prove that the $i$th entry of
$c(c(\mathbf{x}))=\bar{\bar{\mathbf{x}}}$ satisfies $\bar{\bar{x}}_{i}=k$.

  * •

Since $\mathbf{x}$ is nondecreasing any value in $\mathbf{x}$ that is greater
than $k$ is to the right of $x_{i}$, so the number of values in $\mathbf{x}$
greater than $k$ is at most $m-i$. In other words, $\bar{x}_{n-k+1}\leq
m-i+1$. Then the number of values in $\bar{\mathbf{x}}$ greater than $m-i+1$
must be strictly less than $n-(n-k+1)+1=k$. Then

$\bar{\bar{x}}_{m-(m-i+1)+1}=\bar{\bar{x}}_{i}<1+k.$ (4)

  * •

Since $\mathbf{x}$ is nondecreasing any value in $\mathbf{x}$ from $x_{i}$
onwards is greater than $k-1$, so the number of values in $\mathbf{x}$ that
are greater than $k-1$ is at least $m-i+1$. In other words
$\bar{x}_{n-k+2}\geq m-i+1$. Then the number of values of $\bar{\mathbf{x}}$
that are greater than $m-i+1$ must be at least $m-(m-k+2)+1=k-1$. Then

$\bar{\bar{x}}_{m-(m-i+1)+1}=\bar{\bar{x}}_{i}\geq 1+(k-1)=k.$ (5)

Equations (4) and (5) establish that the only possibility is for
$\bar{\bar{x}}_{i}=k$.

Now all that remains to show is that conjugation maps
$\mathrm{DPF}^{\uparrow}_{m,n,d}\to\mathrm{DPF}^{\uparrow}_{n,m,d-(m-n)}$. If
$\mathbf{x}\in\mathrm{DPF}^{\uparrow}_{m,n,d}$, then certainly the total
length of $\bar{\mathbf{x}}$ is equal to $n$, its elements are positive and
cannot exceed $m+1$, and the conjugation process creates a nondecreasing
tuple. Then $\bar{\mathbf{x}}\in\mathrm{DPF}^{\uparrow}_{n,m,d^{\prime}}$ for
some defect $d^{\prime}\geq 0$.

We proceed with a case-by-case investigation:

  * •

Suppose $d=0$. Then, by the pigeonhole principle, $d\geq m-n$. So $m\leq n$.
Then because $\bar{\mathbf{x}}$ is a parking function with $n$ cars and $m$
spots, $d^{\prime}\geq n-m$. Hence, it is sufficient to show that
$d^{\prime}\leq m-n$.

If $d=0$, then, by Proposition 1.2, we know

$\displaystyle x_{j}-j+(m-n)\leq 0$ (6)

for all $j\in[m]$. Suppose for the sake of contradiction that
$d^{\prime}>m-n$. Then there is some $i\in[n]$ such that
$\bar{x}_{n-i+1}-(n-i+1)+(n-m)>n-m$. In other words, there is some $i\in[n]$
with $\bar{x}_{n-i+1}>n-i+1$. Then the number of elements of $\mathbf{x}$
exceeding $i$ is strictly greater than $n-i$, so $x_{m-(n-i)}>i$. Note that
the entry $x_{m-n+1}$ is in $\mathbf{x}$ as the index $m-n+i$ with $i\in[n]$,
ensures that $m-n+i\leq m$. As there are only $m$ cars attempting to park, we
know $n-i\leq m-1$ so $m-n+i\geq 1$. Then
$x_{m-n+i}-(m-n+i)+(m-n)=x_{m-n+i}-i>0$, a contradiction to (6). Hence
$d^{\prime}\leq m-n$.

  * •

Suppose $d>0$. Then, by Proposition 1.2, we know
$d=\max_{j\in[m]}\\{\delta(\mathbf{x})_{j}\\}=\max_{j\in[m]}\\{x_{j}-j+(m-n)\\}$.
We will show that $d^{\prime}=d-(m-n)$ by showing that

$\max_{i\in[n]}\\{\bar{x}_{i}-i\\}=d.$

Suppose for the sake of contradiction that there is some index $i\in[n]$ such
that $\bar{x}_{n-i+1}-(n-i+1)>d$. Then $\bar{x}_{n-i+1}>(n-i+d)+1$. This
implies that the number of elements of $\mathbf{x}$ exceeding $i$ is strictly
greater than $n-i+d$. Then because $\bar{\bar{\mathbf{x}}}=\mathbf{x}$, we
know

$\displaystyle x_{m-(n-i+d)}>i.\ $ (7)

There are only $m$ cars, so $m-(n-i+d)\geq 1$. Likewise, $m-(n-i+d)\leq m$
(i.e. $i\leq n+d$) because $d$ is nonnegative. Then $m-(n-i+d)\in[m]$, so
$x_{m-(n-i+d)}$ is an entry in $\mathbf{x}$ and

$\displaystyle\delta(\mathbf{x})_{m-(n-i+d)}$
$\displaystyle=x_{m-(n-i+d)}-(m-(n-i+d))+(m-n)$
$\displaystyle=x_{m-(n-i+d)}-i+d$ $\displaystyle>i-i+d\qquad\qquad\mbox{(by
Equation~{}\eqref{eq:needed})}$ $\displaystyle>d,$

which contradicts that $d$ was the defect of $\mathbf{x}$. Then
$\max_{i\in[n]}\\{\bar{x}_{i}-i\\}\leq d$. In other words, $d^{\prime}\geq
d-(m-n)$.

We now exploit the involutive nature of conjugation (and the previous case, if
$d^{\prime}=0$) to say that $d\geq d^{\prime}-(n-m)$, so $d^{\prime}\leq
d-(m-n)$. Then $d^{\prime}=d-(m-n)$.

∎

######  Proposition 3.18.

If $m<n$, there is a bijection

$\gamma:\mathrm{DPF}^{\uparrow}_{m,n,d}\longleftrightarrow\mathrm{PF}^{\uparrow}_{n+d,n+d}(x_{n+d}\leq
m+1-d).$

###### Proof.

Proposition 3.17 gives a bijection

$\gamma_{1}:\mathrm{DPF}^{\uparrow}_{m,n,d}\longleftrightarrow\mathrm{DPF}^{\uparrow}_{n,m,d-(m-n)}.$

Proposition 3.12 gives a bijection

$\theta:\mathrm{DPF}^{\uparrow}_{n,m,d-(m-n)}\longleftrightarrow\mathrm{PF}^{\uparrow}_{n+d,n+d}(x_{n+d}\leq
m+1-d).$

The desired result comes from the composition $\gamma=\theta\circ\gamma_{1}$.
∎

######  Corollary 3.19.

For all $m,n\in\mathbb{N}$ and integer $d$ satisfying $n-m\leq d\leq n$, the
sets $\mathrm{DPF}^{\uparrow}_{m,n,d}$ and
$\mathrm{PF}^{\uparrow}_{n+d,n+d}(x_{n+d}\leq m+1-d)$ are in bijection.

###### Proof.

Either $m=n$, $m>n$, or $m<n$. The cases are covered by Corollary 3.11,
Proposition 3.12, and Proposition 3.18, respectively. ∎

Next we establish a bijection between nondecreasing parking functions with
restricted maximal values and two-row standard Young tableaux. This connection
is widely accepted as fact, however after a literature search we were unable
to find the original proof. Thus, for sake of completion, we include an
independent proof below.

######  Proposition 3.20.

For any positive integers $a\geq b$, let $\mathrm{SYT}(a,b)$ denote the set of
standard Young tableaux of shape $(a,b)$. For positive integers $n,k$ with
$k\leq n$, there is a bijection

$\sigma:\mathrm{PF}^{\uparrow}_{n,n}(x_{n}\leq k)\to\mathrm{SYT}(n,k-1).$

###### Proof.

Let $\mathbf{z}$ be an element of $\mathcal{D}_{n}$. There is a bijection
$\sigma_{1}:\mathrm{PF}^{\uparrow}_{n,n}\to\mathcal{D}_{n}$ such that if
$\mathbf{x}\in\mathrm{PF}^{\uparrow}_{n,n}$, the $i$th North step in
$\sigma_{1}(\mathbf{x})$ is preceded by exactly $x_{i}-1$ East steps. East
steps are appended to the end of the Dyck path to ensure proper length. This
is well defined because $x_{i}\leq i$, so the $i$th East step always comes
after the $i$th North step. It’s injective because two parking functions that
map to the same Dyck path must be equal in every index, and it’s surjective
because reversing the process yields a valid parking function.

A bijection $\sigma_{2}:\mathcal{D}_{n}\to\mathrm{SYT}(n,n)$ is given in [22,
Page 1] where for a Dyck path $\mathbf{z}$ of semilength $n$, they define the
tableau $\sigma_{2}(\mathbf{z})$ by putting $i$ in the first row if $z_{i}=N$
and in the second row if $z_{i}=E$.

Restricting $\sigma_{1}$ to $\mathrm{PF}^{\uparrow}_{n,n}(x_{n}\leq k)$ yields
a bijection to the set of Dyck paths of semilength $n$ that end with $n-k+1$
East steps. Restricting $\sigma_{2}$ yields a bijection to the set of Young
tableaux of shape $(n,n)$ such that the numbers $\\{n+k+1,\ldots,2n\\}$ all
lie in the second row. Then because we know that the last $n-k+1$ entries of
the second row are always the same, we can remove those entries without losing
bijectivity. This gives the desired result. ∎

We are now ready to prove Theorem 1.5, which we recall states that the set of
nondecreasing defective parking functions of defect $d$, denoted
$\mathrm{DPF}_{m,n,d}^{\uparrow},$ and the set of standard Young tableaux of
shape $(n+d,m-d)$ are in bijection.

###### Proof of Theorem 1.5.

The result follows from the composition of the bijections in Corollary 3.19
and Proposition 3.20. ∎

##  4\. Enumerative Results

We are now ready to establish a count for the number of $\mathfrak{S}_{n}$
orbits of defective parking functions. Given the bijection in Theorem 1.5, it
suffices to use the hook length formula to establish the count of Corollary
1.6.

###### Proof of Corollary 1.6.

From Corollary 3.19, there is a bijection

$\mathrm{DPF}^{\uparrow}_{m,n,d}\longleftrightarrow\mathrm{PF}^{\uparrow}_{n+d,n+d}(x_{n+d}\leq
m+1-d).$

By Proposition 3.20, $\mathrm{PF}^{\uparrow}_{n+d,n+d}(x_{n+d}\leq m+1-d)$ is
in bijection with standard Young tableaux of shape $(n+d,m-d)$. The hook
length formula implies

$|\mathrm{DPF}^{\uparrow}_{m,n,d}|=\frac{n-m+2d+1}{n+d+1}\binom{m+n}{n+d}.\qed$

We conclude by providing a formula for the size of each orbit.

######  Theorem 4.1.

Given a nondecreasing defective parking function
$\mathbf{x}\in\mathrm{DPF}^{\uparrow}_{m,n,d}$, let $\ell_{i}$ denote the
number of elements of $\mathbf{x}$ equal to $i$. Then the size of the orbit of
defective parking functions with representative $\mathbf{x}$ is

$\binom{m}{\ell_{1},\ell_{2},\ldots,\ell_{n}}=\frac{m!}{\ell_{1}!\ell_{2}!\cdots\ell_{n}!}.$

###### Proof.

The size of the orbit is equal to the number of multiset permutations of
$\mathbf{x}$, which is given by the multinomial coefficient. ∎

Using our previous results, we establish Theorem 1.7, thereby giving a new
formula for the number of defective parking functions.

###### Proof of Theorem 1.7.

The formula in equation (2) follows directly from summing Theorem 4.1 over
$\mathrm{DPF}^{\uparrow}_{m,n,d}$. ∎

##  5\. Future work

We conclude with the following direction for future research. Our proof of
Theorem 1.5 relied on a chain of bijective arguments. We wonder if a more
direct bijection can be established. Moreover, there have been numerous works
generalizing parking functions and studying discrete statistics on these sets.
We pose the following problems.

  1. (1)

Consider cars of varying lengths (such as parking assortments and sequences
[9, 13]). Give counts for the number of defective parking assortments and
sequences.

  2. (2)

Consider the case where cars have an interval of parking preferences, as in
[2]). Give counts for the number of defective $\ell$-interval parking
functions.

  3. (3)

Enumerate defective parking functions based on the number of lucky cars, those
cars which park in their preference. When the defect is $d=0$, and $m=n$,
there are known product formulas for their enumeration [21].

## Acknowledgements

The authors acknowledge funding support from National Science Foundation Grant
No. DMS-1659138 and Sloan Grant No. G-2020-12592. P. E. Harris was partially
supported through a Karen Uhlenbeck EDGE Fellowship.

## References

  * [1] Adeniran, A., Butler, S., Dorpalen-Barry, G., Harris, P. E., Hettle, C., Liang, Q., Martin, J. L., and Nam, H. Enumerating parking completions using join and split.  Electron. J. Combin. 27, 2 (2020), Paper No. 2.44, 19.
  * [2] Aguilar-Fraga, T., Elder, J., Garcia, R. E., Hadaway, K. P., Harris, P. E., Harry, K. J., Hogan, I. B., Johnson, J., Kretschmann, J., Lawson-Chavanu, K., Martínez Mori, J. C., Monroe, C. D., Quiñonez, D., Tolson III, D., and Williams II, D. A. Interval and $\ell$-interval rational parking functions, 2023.
  * [3] Aguillon, Y., Alvarenga, D., Harris, P. E., Kotapati, S., Martínez, J. C. M., Monroe, C. D., Saylor, Z., Tieu, C., and Williams II, D. A. On parking functions and the tower of Hanoi.  Amer. Math. Monthly (2023), 1–7.
  * [4] Armstrong, D., Loehr, N. A., and Warrington, G. S. Rational parking functions and Catalan numbers.  Ann. Comb. 20, 1 (2016), 21–58.
  * [5] Armstrong, D., Reiner, V., and Rhoades, B. Parking spaces.  Advances in Mathematics 269 (2015), 647–706.
  * [6] Bradt, S. A., Elder, J., Harris, P. E., Rojas Kirby, G., Reutercrona, E., Wang, Y. S., and Whidden, J. Unit-interval parking functions and the $r$-Fubini numbers, 2023.  Submitted.
  * [7] Cameron, P. J., Johannsen, D., Prellberg, T., and Schweitzer, P. Counting defective parking functions.  Electron. J. Combin. 15, 1 (2008), Research Paper 92, 15.
  * [8] Chaves Meyles, L., Harris, P. E., Jordaan, R., Rojas Kirby, G., Sehayek, S., and Spingarn, E. Unit-interval parking functions and the permutohedron, 2023.
  * [9] Chen, D. M., Harris, P. E., Martínez Mori, J. C., Pabón-Cancel, E. J., and Sargent, G. Permutation invariant parking assortments.  Enumer. Comb. Appl. 4, 1 (2024), Paper No. S2R4, 25.
  * [10] Christensen, A., Harris, P. E., Jones, Z., Loving, M., Ramos Rodríguez, A., Rennie, J., and Kirby, G. R. A generalization of parking functions allowing backward movement.  Electron. J. Combin. 27, 1 (2020), Paper No. 1.33, 18.
  * [11] Colmenarejo, L., Harris, P. E., Jones, Z., Keller, C., Ramos Rodríguez, A., Sukarto, E., and Vindas-Meléndez, A. R. Counting $k$-Naples parking functions through permutations and the $k$-Naples area statistic.  Enumer. Comb. Appl. 1, 2 (2021), Paper No. S2R11, 16.
  * [12] Cruz, A., Harris, P. E., Harry, K. J., Kretschmann, J., McClinton, M., Moon, A., Museus, J. O., and Redmon, E. On some discrete statistics of parking functions, 2024.
  * [13] Ehrenborg, R., and Happ, A. Parking cars after a trailer.  Australas. J. Combin. 70 (2018), 402–406.
  * [14] Elder, J., Harris, P. E., Kretschmann, J., and Martínez Mori, J. C. Boolean intervals in the weak order of $\mathfrak{S}_{n}$, 2023.
  * [15] Elder, J., Harris, P. E., Kretschmann, J., and Martínez Mori, J. C. Cost-sharing in Parking Games, 2023.
  * [16] Elder, J., Harris, P. E., Markman, Z., Tahir, I., and Verga, A. On flattened parking functions.  J. Integer Seq. 26, 5 (2023), Art. 23.5.8, 34.
  * [17] Fang, B., Harris, P. E., Kamau, B. M., and Wang, D. Vacillating parking functions, 2024.
  * [18] Frame, J. S., Robinson, G. d. B., and Thrall, R. M. The hook graphs of the symmetric groups.  Canad. J. Math. 6 (1954), 316–324.
  * [19] Franks, S. J., Harris, P. E., Harry, K. J., Kretschmann, J., and Vance, M. Counting parking sequences and parking assortments through permutations.  Enumer. Comb. Appl. 4, 1 (2024), Paper No. S2R2, 10.
  * [20] Françon, J. Acyclic and parking functions.  Journal of Combinatorial Theory, Series A 18, 1 (1975), 27–35.
  * [21] Gessel, I. M., and Seo, S. A refinement of Cayley’s formula for trees.  Electron. J. Combin. 11, 2 (2004/06), Research Paper 27, 23.
  * [22] Gil, J. B., McNamara, P. R. W., Tirrell, J. O., and Weiner, M. D. From dyck paths to standard young tableaux.  Ann. Comb. 24, 1 (mar 2020), 69–93.
  * [23] Haiman, M. D. Conjectures on the quotient ring by diagonal invariants.  J. Alg. Combin. 3, 1 (1994), 17–76.
  * [24] Harris, P. E., Kamau, B. M., Martínez Mori, J. C., and Tian, R. On the outcome map of MVP parking functions: permutations avoiding 321 and 3412, and Motzkin paths.  Enumer. Comb. Appl. 3, 2 (2023), Paper No. S2R11, 16.
  * [25] Harris, P. E., Kretschmann, J., and Martinez Mori, J. C. Lucky Cars and the Quicksort Algorithm.  Amer. Math. Monthly (2024).
  * [26] Konheim, A. G., and Weiss, B. An occupancy discipline and applications.  SIAM J. Appl. Math. 14, 6 (1966), 1266–1274.
  * [27] OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences, 2023.  Published electronically at http://oeis.org.
  * [28] Sagan, B. E. The symmetric group, second ed., vol. 203 of Graduate Texts in Mathematics.  Springer-Verlag, New York, 2001.  Representations, combinatorial algorithms, and symmetric functions.
  * [29] Stanley, R. P. Enumerative combinatorics. Vol. 2, second ed., vol. 208 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, Cambridge, [2024] ©2024.  With an appendix by Sergey Fomin.
  * [30] Stanley, R. P., and Pitman, J. A polytope related to empirical distributions, plane trees, parking functions, and the associahedron.  Discrete Comput. Geom. 27, 4 (2002), 603–634.