# On friendship and cyclic parking functions

Yujia Kang<EMAIL_ADDRESS>School of Mathematics and
Physics, Xi’an Jiaotong-Livepool University  Thomas Selig
<EMAIL_ADDRESS>School of Advanced Technology, Xi’an Jiaotong-
Livepool University  Guanyi Yang<EMAIL_ADDRESS>School of
Mathematics and Physics, Xi’an Jiaotong-Livepool University  Yanting Zhang
<EMAIL_ADDRESS>Mathematical Institute, University of Oxford
Haoyue Zhu<EMAIL_ADDRESS>School of Advanced Technology,
Xi’an Jiaotong-Livepool University

###### Abstract

In parking problems, a given number of cars enter a one-way street
sequentially, and try to park according to a specified preferred spot in the
street. Various models are possible depending on the chosen rule for
_collisions_ , when two cars have the same preferred spot. In classical
parking functions, if a car’s preferred spot is already occupied by a previous
car, it drives forward and looks for the first unoccupied spot to park.

In this work, we introduce a variant of classical parking functions, called
_friendship parking functions_ , which imposes additional restrictions on
where cars can park. Namely, a car can only end up parking next to cars which
are its friends (friendship will correspond to adjacency in an underlying
graph). We characterise and enumerate such friendship parking functions
according to their outcome permutation, which describes the final
configuration when all cars have parked. We apply this to the case where the
underlying friendship graph is the cycle graph. Finally, we consider a subset
of classical parking functions, called _cyclic parking functions_ , where cars
end up in an increasing cyclic order. We enumerate these cyclic parking
functions and exhibit a bijection to permutation components.

##  1 Introduction

In this section, we introduce parking functions and friendship parking
functions. Throughout the paper, $n$ represents a positive integer, and we
denote $[n]:=\\{1,\cdots,n\\}$. Permutations will play a key role in our
paper. We denote $S_{n}$ the set of permutations of the set $[n]$. For $\pi\in
S_{n}$, we write $\pi=\pi_{1}\cdots\pi_{n}$ using standard one-line notation.
We also denote $\pi^{-1}$ the inverse permutation of $\pi$. That is, for any
$i\in[n]$, $\pi^{-1}_{i}$ is the unique $j\in[n]$ such that $\pi_{j}=i$.

###  1.1 Parking functions and their variations

A _parking preference_ is a vector $p=(p_{1},\cdots,p_{n})\in[n]^{n}$. We will
regard $p_{i}$ as the preferred spot of car $i$ in a car park with spots
labelled $1,\cdots,n$. Given a parking preference $p$, the classical parking
process for $p$ is described as follows.

Cars enter the car park sequentially in order $1,\cdots,n$, and initially all
spots in the car park are unoccupied. When car $i$ enters, it will occupy
(park in) the first spot $k\geq p_{i}$ which is unoccupied at that point. If
no such spot exists, car $i$ exits the car park, having failed to park. We say
that $p$ is a _classical parking function_ if all $n$ cars are able to park
through this process. We denote $\mathrm{PF}_{n}$ the set of all classical
parking functions with $n$ cars/spots.

The _outcome map_ of classical parking functions is the map
$\mathcal{O}_{\mathrm{PF}_{n}}:\mathrm{PF}_{n}\rightarrow S_{n}$ which
associates a permutation
$\mathcal{O}_{\mathrm{PF}_{n}}\left(p\right)=\pi=\pi_{1}\cdots\pi_{n}$ of
$[n]$ to a classical parking function $p$ as follows. For any $i\in[n]$, we
set $\pi_{i}$ to be the label of the car ending up in spot $i$ after all cars
have parked in the classical parking process for $p$.

The _displacement vector_ of a classical parking function
$p\in\mathrm{PF}_{n}$ is defined by
$\mathrm{disp}\left(p\right)=(d_{1},d_{2},\cdots,d_{n})$, where
$d_{i}:=\pi^{-1}_{i}-p_{i}$ for all $i\in[n]$. Note that for $i\in[n]$,
$d_{i}$ measures the distance that car $i$ has travelled between its preferred
spot $p_{i}$ and the spot $\pi^{-1}_{i}$ where it finally parks. We say that
$d_{i}$ is the displacement of car $i$ in the parking function $p$. The total
displacement of $p$ is defined by
$|\mathrm{disp}\left(p\right)|:=\sum_{i=1}^{n}d_{i}$.

######  Example 1.1.

Consider the parking preference $p=(3,1,1,2)$, and let us illustrate the
classical parking process for $p$.

  * •

Car $1$ has preference $p_{1}=3$. Spot $3$ is unoccupied at that point, so car
$1$ parks in spot $3$ (in fact, car $1$ will always park in its preferred
spot), with displacement $d_{1}=0$.

  * •

Car $2$ has preference $p_{2}=1$. Spot $1$ is unoccupied at that point, so car
$2$ parks in spot $1$, with displacement $d_{2}=0$.

  * •

Car $3$ has preference $p_{3}=1$. However, spot $1$ is occupied at this point
(by car $2$), so car $3$ cannot park there. Instead, it continues to drive
forward and finds the first unoccupied spot after its preference, which is
spot $2$, and so car $3$ parks there. The displacement is given by
$d_{3}=2-1=1$.

  * •

Lastly, car $4$ has preference $p_{4}=2$. Again, spot $2$ is occupied (by car
$3$), as is spot $3$ (by car $1$). Thus, car $4$ will park in spot $4$, which
is in fact the only unoccupied spot at this point. The displacement is given
by $d_{4}=4-2=2$.

Finally, the cars are all able to park, so $p=(3,1,1,2)$ is a classical
parking function. We also get the outcome
$\mathcal{O}_{\mathrm{PF}_{n}}\left(p\right)=2314$, and the displacement
vector $\mathrm{disp}\left(p\right)=(0,0,1,2)$. The entire classical parking
process is illustrated in Figure 1 below.

carsspots$1$$2$$3$$4$$1$$\downarrow$$\Longrightarrow$$1$$2$$3$$4$$1$$2$$\downarrow$$\Longrightarrow$$1$$2$$3$$4$$1$$2$$3$$\curvearrowright$$\Longrightarrow$$1$$2$$3$$4$$1$$2$$3$$4$$\longrightarrow$$\searrow$$\Longrightarrow$$1$$2$$3$$4$$1$$2$$3$$4$
Figure 1: Illustrating the parking process for the classical parking function
$p=(3,1,1,2)$.

Parking functions were originally introduced by Konheim and Weiss [15] in
their study of _hashing functions_. Since then, they have been a popular
research topic in Mathematics and Computer Science, with rich connections to a
variety of fields such as graph theory, representation theory, hyperplane
arrangements, discrete geometry, and the Abelian sandpile model [4, 10, 21,
22]. We refer the interested reader to the excellent survey by Yan [25].

We may notice that in classical parking functions, the handling of
_collisions_ – when a car’s preferred spot is already occupied when it enters
the car park – appears quite flexible. Indeed, many variations of parking
functions with different parking rules have been discussed in the literature.
We list some of them briefly here. For a more detailed survey of
generalisations and open problems related to parking functions, see [3].

  * •

Defective parking functions [2]. This model follows classical parking rules,
with $m$ cars and $n$ spots, and $k$ cars being unable to park ($k$ is called
the _defect_ of the parking function).

  * •

Naples parking functions [6, 8, 24]. This model allows for some backward
movement of cars from their preferred spot if it is already occupied.

  * •

Parking assortments and parking sequences [1, 5, 12, 13]. These models involve
cars of different sizes, with the car park having just enough space for all
cars to park.

  * •

Subset parking functions [20]. In this model, cars have a preferred ordered
subset of spots in which they can park. See also [7] for an in-depth treatment
of interval parking functions, where each preference subset is a sub-interval
of $[n]$.

  * •

Vector parking functions, or $\mathbf{u}$-parking functions [19, 26]. For a
vector $u=(u_{1},\cdots,u_{n})$, we say that a parking preference
$p=(p_{1},p_{2},\ldots,p_{n})$ is a $u$-parking function if the non-decreasing
rearrangement $a=(a_{1},\cdots,a_{n})$ of $p$ satisfies $a_{i}\leq u_{i}$ for
all $i\in[n]$. These correspond to classical parking functions when
$u=(1,2,\ldots,n)$ (see e.g. [25, Section 1.1] for this characterisation of
classical parking functions).

  * •

Graphical parking functions on some graph $G$, or $G$-parking functions [16].
In this model, cars park on the vertices of the graph $G$ instead of in a one-
way street.

  * •

Higher-dimensional parking functions. There are several relevant models in
this area, such as the $(p,q)$-parking functions of Cori and Poulalhon [9], or
the tiered parking functions of Dukes [11]. Both of these models involve cars
of different colours or tiers, with extra conditions on where a car can park
depending on its tier/colour. Snider and Yan [18, 19] then defined a concept
of multidimensional $U$-parking functions, where $U$ is a collection of
multidimensional vectors. These generalise the $(p,q)$-parking functions of
Cori and Poulalhon and the (one-dimensional) vector parking functions, and
also connect to the graphical parking functions discussed above.

  * •

MVP parking functions [14, 17]. In this model, priority is given to cars which
enter later in the parking process. That is, when a car enters the car park,
if its preferred spot is occupied by a previous car, it will “bump” the
earlier car out of that spot, forcing it to drive on and find a new spot to
park in.

In this paper, we consider a new variation on parking functions, which we call
_friendship parking functions_. Informally, cars follow the classical parking
process, but can only park next to cars which they are “friends” with
(friendship will be determined by adjacency in an underlying graph).

###  1.2 Friendship parking functions

In this section we formally define the concept of friendship parking
functions. Let $G$ be a graph with vertex set $[n]$. We say that two vertices
$i$ and $j$ are _adjacent_ in the graph $G$ if $\\{i,j\\}$ is an edge of $G$.
As in the classical case, we consider a parking preference
$p=(p_{1},\cdots,p_{n})\in[n]^{n}$. The _friendship parking process_ is
described as follows.

Cars enter sequentially in order $1,\cdots,n$ into a car park with spots
labelled $1,\cdots,n$. All spots are initially unoccupied. For $i\geq 1$, we
say that a spot $k$ is _available_ for car $i$ if it is unoccupied when car
$i$ enters the car park, and each of the two neighbouring spots $k-1$ and
$k+1$ are either unoccupied, or occupied by a car $j$ (necessarily $j<i$)
which is adjacent to $i$ in the graph $G$. Here we consider spots $0$ and
$n+1$ to be unoccupied by convention when handling the cases $k=1$ or $k=n$.
When car $i$ enters the car park, it occupies (parks in) the first spot $k\geq
p_{i}$ which is available for $i$. If no such spot exists, the car exits the
car park, having failed to park.

We say that $p$ is a _friendship parking function_ for $G$, or $G$-friendship
parking function, if all $n$ cars are able to park following this process. We
denote $\mathrm{FPF}\left(G\right)$ the set of all $G$-friendship parking
functions. As in the classical case, we can define the outcome map
$\mathcal{O}_{\mathrm{FPF}\left(G\right)}:\mathrm{FPF}\left(G\right)\rightarrow
S_{n}$. For a $G$-friendship parking function $p$, we let
$\pi=\pi_{1}\cdots\pi_{n}=\mathcal{O}_{\mathrm{PF}_{G}}\left(p\right)$ be the
permutation such that for any $i\in[n]$, $\pi_{i}$ is the label of the car
ending up in spot $i$ when running the friendship parking process for $p$.

Note that if $G$ is the complete graph on $n$ vertices (with edges between any
pair of distinct vertices), the notions of classical and friendship parking
functions are identical. Indeed, in this case, a spot is available for $i$ if,
and only if, it is unoccupied when $i$ enters the car park.

######  Example 1.2.

Let $G$ be the cycle on $n=4$ vertices, with edges
$\\{1,2\\},\\{2,3\\},\\{3,4\\},\\{4,1\\}$. Consider the parking preference
$p=(2,1,2,2)$, and let us illustrate the $G$-friendship parking process for
$p$.

  * •

Car $1$ has preference $p_{1}=2$. Spot $2$ is available for car $1$ since both
adjacent spots are both unoccupied (this will always be the case for car $1$’s
preferred spot). Therefore car $1$ parks in spot $2$.

  * •

Car $2$ has preference $p_{2}=1$. The neighbouring spot $2$ is occupied by car
$1$ at this point, but vertices $1$ and $2$ are adjacent in the graph $G$, so
spot $1$ is available for car $2$, allowing it to park there.

  * •

Car $3$ has preference $p_{3}=2$. However, spot $2$ is occupied at this point
(by car $1$), so is not available for $3$. Spot $3$ is unoccupied, but the
adjacent spot $2$ is occupied by car $1$, and $1$ and $3$ are not adjacent in
$G$. Therefore spot $3$ is not available for car $3$. Finally, spot $4$ is
also unoccupied, as is its neighbouring spot $3$, which implies that it is
available, and thus car $3$ parks in spot $4$.

  * •

Lastly, car $4$ has preference $p_{4}=2$. Spot $2$ is occupied, so car $4$
can’t park there. But spot $3$ is unoccupied, and the cars occupying its
neighbouring spots $2$ (car $1$) and $4$ (car $3$) are both adjacent to $4$ in
$G$, which means spot $3$ is available for car $4$, so it parks there.

Finally, the cars are all able to park, so $p=(2,1,2,2)$ is a $G$-friendship
parking function, and we get the outcome
$\mathcal{O}_{\mathrm{FPF}\left(G\right)}\left(p\right)=2143$. The entire
friendship parking process is illustrated in Figure 2 below.

carsspots$1$$2$$3$$4$$1$$\Longrightarrow$$1$$2$$3$$4$$1$$2$$\Longrightarrow$$1$$2$$3$$4$$1$$2$$3$$\times$$\Longrightarrow$$1$$2$$3$$4$$1$$2$$3$$4$$\Longrightarrow$$1$$2$$3$$4$$1$$2$$3$$4$
Figure 2: Illustrating the parking process for the friendship parking function
$p=(2,1,2,2)$.

######  Example 1.3.

Let $G$ again be the cycle graph on $4$ vertices, as in Example 1.2, and
consider the parking preference $p=(4,2,2,1)$. Car $1$ parks in spot $4$, and
car $2$ parks in spot $2$ (both neighbouring spots are unoccupied). However,
car $3$ cannot park. Indeed, the preference of car $3$ is $p_{3}=2$. At this
point, the only unoccupied spot $k\geq 2$ is $k=3$, but the neighbouring spot
$4$ is occupied by car $1$, which is not adjacent to $3$ in $G$. Therefore
spot $3$ is not available for car $3$, and so there are no available spots on
or after car $3$’s preference for it to park in. Thus $p$ is _not_ a
$G$-friendship parking function. This parking process is illustrated on Figure
3 below.

carsspots$1$$2$$3$$4$$1$$\Longrightarrow$$1$$2$$3$$4$$1$$2$$\Longrightarrow$$1$$2$$3$$4$$1$$2$$3$$\times$$\times$
Figure 3: Illustrating the friendship parking process for the parking
preference $p=(4,2,2,1)$. Here, car $3$ is unable to park, so $p$ is not a
friendship parking function.

It is worth noting that in the previous example, $p=(4,2,2,1)$ is a classical
parking function (we get the outcome
$\mathcal{O}_{\mathrm{PF}_{4}}\left(p\right)=4231$). This shows that our new
notion of friendship parking functions is a meaningful variant of classical
parking functions.

###  1.3 Contents of the paper

Our paper is organised as follows. In Section 2 we study this new friendship
parking process. We begin in Section 2.1 by showing a link between
$G$-friendship parking functions and _Hamiltonian paths_ of the graph $G$
(Proposition 2.1), and by giving some results connecting friendship and
classical parking functions (Propositions 2.2 and 2.3). Section 2.2 then gives
a characterisation and enumeration formula for friendship parking functions on
general graphs (Theorem 2.7 and Corollary 2.9). In Section 2.3 we apply these
results to the case where $G$ is the cycle graph on $n$ vertices, yielding the
enumeration formula from Theorem 2.13.

In Section 3 we return to the study of classical parking functions,
considering those whose outcome is an increasing cycle of the form
$\mathrm{IncCyc}^{i,n}:=i(i+1)\cdots n12\cdots(i-1)$ for some $i\in[n]$. We
call such parking functions _cyclic parking functions_ , and count them
(Proposition 3.1 and Corollary 3.3). We then describe a bijection between
cyclic parking functions and _permutation components_ , which maps the
displacement of cars to inversions in the corresponding permutation (Theorem
3.10). Finally, Section 4 gives a brief summary of our results, and outlines
some possible future research directions on friendship parking functions.

##  2 Characterising and counting friendship parking functions

In this section, we give characterisations and enumeration formulas for
friendship parking functions on general graphs $G$. We then apply these to the
case where $G$ is the cycle graph on $n$ vertices.

###  2.1 Friendship parking functions and Hamiltonian paths

We begin by exhibiting a connection between $G$-friendship parking functions
and _Hamiltonian paths_ of the graph $G$. To do this, we first recall some
relevant concepts. Given a graph $G$, with vertex set $[n]$, a _path_ of $G$
is a sequence of distinct vertices
$\mathcal{P}=(v_{1},v_{2},\cdots,v_{k})\in[n]^{k}$ such that
$\\{v_{i},v_{i+1}\\}$ is an edge of $E$ for each $i\in\\{1,\cdots,k-1\\}$.
Moreover, $\mathcal{P}$ is called a _Hamiltonian_ path if $k=n$, i.e. every
vertex of $G$ appears in $\mathcal{P}$.

Recall that for a $G$-friendship parking function
$p\in\mathrm{FPF}\left(G\right)$, we can define its outcome
$\pi=\mathcal{O}_{\mathrm{FPF}\left(G\right)}\left(p\right)=\pi_{1}\cdots\pi_{n}$,
which is a permutation of all the cars (for $i\in[n]$, car $\pi_{i}$ is the
car that ends up in spot $i$). In friendship parking functions, the
relationship among cars is indicated by a graph $G$ and the permutation
reflects that cars (vertices) that can park next to each other must be
“friends” (adjacent in the graph $G$). We can therefore obtain the following
fact.

######  Proposition 2.1.

Let $G=(V,E)$ be a graph. Then the set of $G$-friendship parking functions is
non-empty if, and only if, $G$ contains a Hamiltonian path.

###### Proof.

Suppose there exists some $p\in\mathrm{FPF}\left(G\right)$, and consider its
outcome
$\mathcal{O}_{\mathrm{FPF}\left(G\right)}\left(p\right)=\pi_{1}\cdots\pi_{n}$.
We claim that $\mathcal{P}:=(\pi_{1},\cdots,\pi_{n})$ is a Hamiltonian path of
$G$. Indeed, consider a car $i=\pi_{k}$ which parks in some spot $k\leq n-1$
in the friendship parking process. We wish to show that $j:=\pi_{k+1}$ is
adjacent to $i$ in $G$. If $j<i$, then car $j$ has already parked in spot
$k+1$ when car $i$ arrives. This means that for $i$ to park in spot $k$,
vertices $i$ and $j$ must be adjacent in $G$ (since spot $k$ must be available
for car $i$ when it arrives). The same applies if $j>i$: when car $j$ arrives,
car $i$ has already parked in spot $k$, so $j$ can only park in spot $k+1$ if
$i$ and $j$ are adjacent in $G$. Therefore $\mathcal{P}$ is a Hamiltonian
path, as desired.

Conversely, suppose that $G$ contains a Hamiltonian path, say
$\mathcal{P}=(v_{1},v_{2},\cdots,v_{n})\in[n]^{n}$ where the $v_{i}$ are
distinct. By construction, $\pi:=v_{1}\cdots v_{n}$ is a permutation of $[n]$.
Define a parking preference $p=(p_{1},\cdots,p_{n})$ by $p_{i}=\pi^{-1}_{i}$
for all $i\in[n]$. Then it is straightforward to check that
$p\in\mathrm{FPF}\left(G\right)$ and
$\mathcal{O}_{\mathrm{FPF}\left(G\right)}\left(p\right)=\pi$. Indeed, in the
friendship parking process for $p$, each car can simply park in its preferred
spot (since $\mathcal{P}$ is a Hamiltonian path, these are always available).
∎

Proposition 2.1 establishes a connection between the outcomes of
$G$-friendship parking functions and Hamiltonian paths of $G$. With a slight
abuse of notation, we will henceforth consider a Hamiltonian path of $G$ to be
a permutation $\pi=\pi_{1}\cdots\pi_{n}$ of $[n]$ such that
$\\{\pi_{i},\pi_{i+1}\\}$ is an edge of $G$ for all $i\in[n-1]$. We denote
$\mathcal{H}\left(G\right)$ the set of Hamiltonian paths of $G$. We end this
section by stating two fairly straightforward propositions that connect
classical and friendship parking functions.

######  Proposition 2.2.

We have $\mathrm{FPF}\left(G\right)\subseteq\mathrm{PF}_{n}$.

###### Proof.

We first recall a well-known characterisation of classical parking functions.
For a parking preference $p=(p_{1},\cdots,p_{n})$, we denote
$\tilde{p}=(\tilde{p}_{1},\cdots,\tilde{p}_{n})$ the _non-decreasing
rearrangement_ of $p$. Then $p\in\mathrm{PF}_{n}$ if, and only if, we have
$\tilde{p}_{i}\leq i$ for all $i\in[n]$ (see e.g. [25, Section 1.1]).

Now let $p\in\mathrm{FPF}\left(G\right)$ be a $G$-friendship parking function,
and denote $\tilde{p}$ its non-decreasing rearrangement. Seeking
contradiction, suppose there is some $i\in[n]$ such that $\tilde{p}_{i}>i$. By
construction, this means that $\left|\\{j\in[n];\,p_{j}\leq i\\}\right|\leq
i-1$. But in the friendship (or indeed classical) parking process, each car
necessarily ends up parking on or after its preferred spot. In particular, for
any $i\in[n]$, there must be at least $i$ cars whose preference is one of the
first $i$ spots (since exactly $i$ cars must end up in these spots). This
yields the desired contradiction with the above inequality. ∎

######  Proposition 2.3.

Let $p\in\mathrm{PF}_{n}$ be a parking function such that its outcome
$\mathcal{O}_{\mathrm{PF}_{n}}\left(p\right)$ is a Hamiltonian path of the
graph $G$. Then we have $p\in\mathrm{FPF}\left(G\right)$, and
$\mathcal{O}_{\mathrm{FPF}\left(G\right)}\left(p\right)=\mathcal{O}_{\mathrm{PF}_{n}}\left(p\right)$.

###### Proof.

In fact, in this case the friendship and classical parking processes are
identical. Indeed, when a car $i$ parks in some spot $k$ in the classical
parking process, it will never move from spot $k$ thereafter. As such, since
$\pi:=\mathcal{O}_{\mathrm{PF}_{n}}\left(p\right)\in\mathcal{H}\left(G\right)$,
this implies that the spot $k$ is available at that time for car $i$ in the
friendship parking process. Since by definition $k$ is the first value greater
than or equal to $p_{i}$ which is unoccupied when $i$ enters the car park, car
$i$ also parks in $k$ for the friendship parking process. This completes the
proof. ∎

######  Remark 2.4.

Propositions 2.2 and 2.3 are not quite converse to each other. Indeed, there
exist friendship parking functions (which are thus also classical parking
functions) whose classical outcome is not a Hamiltonian path. Example 1.2
gives an example of such a parking function given by $p=(2,1,2,2)$. This is a
friendship parking function for the $4$-cycle, but its classical outcome is
$\mathcal{O}_{\mathrm{PF}_{4}}\left(p\right)=2134$, which is not a Hamiltonian
path of the $4$-cycle (vertices $1$ and $3$ are not adjacent). As such,
friendship parking functions are not just classical parking functions whose
outcome is a Hamiltonian path.

###  2.2 Characterising friendship parking functions according to their
outcomes

In this section, we give a general characterisation and enumeration of
friendship parking functions according to their outcome permutations. For
$\pi\in S_{n}$, the _outcome fibre_ of $\pi$ is the set
$\mathcal{O}^{-1}_{\mathrm{FPF}\left(G\right)}\left(\pi\right):=\\{p\in\mathrm{FPF}\left(G\right);\,\mathcal{O}_{\mathrm{FPF}\left(G\right)}\left(p\right)=\pi\\}$
of $G$-parking functions whose (friendship) outcome is $\pi$. We begin by
giving the definitions of _blocker_ and _blocking sequence_ , which will be
used in the subsequent results.

######  Definition 2.5.

Let $\pi\in\mathcal{H}\left(G\right)$ be a Hamiltonian path of the graph $G$,
and $i\in[n]$. We say that $j=\pi_{k}$ is a _blocker_ for $i$ in $\pi$, or
equivalently that $i$ is blocked by $j$ in $\pi$, if either of the two
following conditions holds:

  1. 1.

We have $j\leq i$; or

  2. 2.

We have $j>i$, but there is a neighbour $\ell$ of $j$ in $\pi$, i.e.
$\ell\in\\{\pi_{k-1},\pi_{k+1}\\}$ such that $\ell<i$ and $\ell$ is _not_
adjacent to $i$ in $G$.

The _blocking sequence_ for $i$ in $\pi$ is the longest sub-sequence of $\pi$,
ending at $i$, whose elements are all blockers for $i$. We denote $B(i,\pi,G)$
the blocking sequence for $i$, and $b(i,\pi,G):=|B(i,\pi,G)|$ its length.

######  Example 2.6.

Let $G$ be the graph in Figure 4, with Hamiltonian path $\pi=87152463$ (drawn
in red). Then $i=4$ is blocked by: $1,2,3,4$ (all $\leq 4$), as well as $5$
and $7$. For $5$ and $7$, note that they are both neighbours of $\ell=1$ in
$\pi$, which satisfies $\ell=1<4=i$, and $1$ is not adjacent to $4$ in $G$, so
Condition (2) of Definition 2.5 applies.

However, $j=8$ is not a blocker, since its only neighbour $\ell=7$ in $\pi$ is
not strictly less than $i=4$. Neither is $j=6$ a blocker. Indeed, its
neighbours in $\pi$ are $3$ and $4$. Among these, the only value which is
strictly less than $i=4$ is $\ell=3$, and there is an edge between $\ell=3$
and $i=4$ in $G$, so Condition (2) of Definition 2.5 does not apply here. The
blocking sequence for $4$ is then $B(4,\pi,G)=71524$, with length
$b(4,\pi,G)=5$.

$1$$2$$3$$4$$5$$6$$7$$8$ Figure 4: The graph $G$ with Hamiltonian path
$\pi=87152463$ (red)

We now state the main result of this section, which gives a complete
characterisation of the outcome fibres of friendship parking functions in
terms of blocking sequences.

######  Theorem 2.7.

Let $\pi\in\mathcal{H}\left(G\right)$ be a Hamiltonian path of $G$, and
$p=(p_{1},\cdots,p_{n})\in[n]^{n}$ a parking preference. Then we have
$p\in\mathcal{O}^{-1}_{\mathrm{FPF}\left(G\right)}\left(\pi\right)$ if, and
only if, for all $i\in[n]$, we have $p_{i}\in S_{i}$, where
$S_{i}:=\\{s\in[n];\,\pi_{s}\in B(i,\pi,G)\\}$ is the set of spots that are
occupied in the outcome $\pi$ by an element in the blocking sequence for $i$
in $\pi$.

######  Example 2.8.

Consider the graph $G$ from Figure 4 with corresponding Hamiltonian path
$\pi=87152463$ as in Example 2.6. We wish to calculate the fibre set
$\mathcal{O}^{-1}_{\mathrm{FPF}\left(G\right)}\left(\pi\right)$ by applying
Theorem 2.7. For this we calculate the blocking sequences $B(i,\pi,G)$ for
each element $i\in[8]$, and their corresponding index sets
$S_{i}:=\\{s\in[n];\,\pi_{s}\in B(i,\pi,G)\\}$.

  * •

For $i=1$, $B(1,\pi,G)=1=\pi_{3}$, so $S_{1}=\\{3\\}$.

  * •

For $i=2$, $B(2,\pi,G)=7152=\pi_{2}\pi_{3}\pi_{4}\pi_{5}$, so
$S_{2}=\\{2,3,4,5\\}$.

  * •

For $i=3$, $B(3,\pi,G)=3=\pi_{8}$, so $S_{3}=\\{8\\}$.

  * •

For $i=4$, $B(4,\pi,G)=71524=\pi_{2}\cdots\pi_{6}$, so $S_{4}=[2,6]$.

  * •

For $i=5$, $B(5,\pi,G)=15=\pi_{3}\pi_{4}$, so $S_{5}=\\{3,4\\}$.

  * •

For $i=6$, $B(6,\pi,G)=715246=\pi_{2}\cdots\pi_{7}$, so $S_{6}=[2,7]$.

  * •

For $i=7$, $B(7,\pi,G)=7=\pi_{2}$, so $S_{7}=\\{2\\}$.

  * •

For $i=8$, $B(8,\pi,G)=8=\pi_{1}$, so $S_{8}=\\{1\\}$.

Finally, we get the fibre set
$\mathcal{O}^{-1}_{\mathrm{FPF}\left(G\right)}\left(\pi\right)=\prod\limits_{i=1}^{8}S_{i}=\\{3\\}\times[2,5]\times\cdots\times\\{2\\}\times\\{1\\}$,
and the fibre size
$\left|\mathcal{O}^{-1}_{\mathrm{FPF}\left(G\right)}\left(\pi\right)\right|=\prod\limits_{i=1}^{8}\left|S_{i}\right|=1*4*1*5*2*6*1*1=240.$

Theorem 2.7 immediately implies enumeration formulas for the fibres and total
number of friendship parking functions.

######  Corollary 2.9.

For any Hamiltonian path $\pi\in\mathcal{H}\left(G\right)$ of $G$, we have
$\left|\mathcal{O}^{-1}_{\mathrm{FPF}\left(G\right)}\left(\pi\right)\right|=\prod\limits_{i\in[n]}b(i,\pi,G)$.
In particular, this implies that the total number of $G$-friendship parking
functions is equal to
$\sum\limits_{\pi\in\mathcal{H}\left(G\right)}\left(\prod\limits_{i\in[n]}b(i,\pi,G)\right)$.

###### Proof of Theorem 2.7.

Fix $\pi\in\mathcal{H}\left(G\right)$ a Hamiltonian path of $G$. For
$i\in[n]$, denote $S_{i}:=\\{s\in[n];\,\pi_{s}\in B(i,\pi,G)\\}$ the set of
spots occupied in $\pi$ by cars in the blocking sequence of $i$, and
$s_{i}:=\min S_{i}$ the first such spot. Note that by definition of the
blocking sequence, we have $S_{i}=\left[s_{i},\pi^{-1}_{i}\right]$.

We first assume that
$p=(p_{1},\cdots,p_{n})\in\mathcal{O}^{-1}_{\mathrm{FPF}\left(G\right)}\left(\pi\right)$
is a friendship parking function whose outcome is the Hamiltonian path $\pi$.
We wish to show that for all $i\in[n]$, we have $p_{i}\in S_{i}$. Seeking
contradiction, suppose that is not the case. Let $i\in[n]$ be such that
$p_{i}\notin S_{i}$, and define $j:=\pi^{-1}_{i}$ to be the spot where car $i$
ends up. Since $S_{i}=\left[s_{i},\pi^{-1}_{i}\right]=[s_{i},j]$, we have two
cases to consider.

  1. 1.

Case 1: $p_{i}>j$. That is, car $i$ prefers a spot (strictly) to the right of
spot $j$. But by definition, we have $j=\pi_{i}$, so car $i$ should end up in
spot $j$, which is impossible given the parking process (cars necessarily end
up parking on or to the right of their preference).

  2. 2.

Case 2: $p_{i}<s_{i}$. Consider the spot $k:=s_{i}-1$, and the corresponding
car $\pi_{k}$. Note that we have $p_{i}\leq k<j$. By definition of the
blocking sequence, $\pi_{k}$ is not a blocker for $i$ in $\pi$. In particular,
we must have $\pi_{k}>i$, so spot $k$ is unoccupied when car $i$ arrives.
Moreover, none of the neighbouring spots $k-1,k+1$ can be occupied by cars
arriving before $i$ which are not adjacent to $i$ in $G$. This means exactly
that spot $k$ is available for $i$ in the $G$-friendship parking process for
$p$. But since $p_{i}\leq k$, this means that car $i$ will end up either in
spot $k$ or to its left. In particular, it is impossible for car $i$ to end up
in spot $j$, since $j>k$. This gives the desired contradiction.

We now show the converse. That is, suppose that $p=(p_{1},\cdots,p_{n})$ is a
parking preference such that $p_{i}\in S_{i}$ for all $i\in[n]$. We wish to
show that $p\in\mathcal{O}^{-1}_{\mathrm{FPF}\left(G\right)}\left(\pi\right)$.
Consider the friendship parking process for $p$. We show by induction on
$i\geq 1$ that car $i$ always ends up in spot $\pi^{-1}_{i}$.

For $i=1$, we note that $1$ has no blockers other than itself, since it is the
minimal element of $[n]$, and the condition for $j>i$ to be a blocker
(Condition (2) of Definition 2.5) relies on the existence of an element $\ell$
satisfying $\ell<i$. That is, $B(1,\pi,G)=1$, so $S_{1}=\\{\pi^{-1}_{1}\\}$ by
definition. Therefore, since $p_{1}\in S_{1}$ by assumption, we have
$p_{1}=\pi^{-1}_{1}$. Finally, since car $1$ always parks in its preferred
spot, we have that car $1$ ends up in spot $\pi^{-1}_{1}$, as desired.

Now suppose that, for some $i\geq 2$, we have shown that car $j$ parks in spot
$\pi^{-1}_{j}$ for all $j\leq i-1$. Consider how car $i$ parks. By assumption,
we have $p_{i}\in S_{i}=\left[s_{i},\pi^{-1}_{i}\right]$. Consider a spot
$k\in S_{i}\setminus\\{\pi^{-1}_{i}\\}$, and $j:=\pi_{k}$ the corresponding
car. We wish to show that $i$ cannot park in spot $k$. By definition, $j$ is a
blocker for $i$, and $j\neq i$ (since $k=\pi^{-1}_{j}<\pi^{-1}_{i}$). We
distinguish two cases.

  1. 1.

Case 1: $j<i$. By the induction hypothesis, $j$ occupies spot
$\pi^{-1}_{j}=k$, so car $i$ cannot park in spot $k$.

  2. 2.

Case 2: $j>i$. In this case, by definition of blockers, for at least one of
the values $\ell\in\\{k-1,k+1\\}$, we must have that $\pi_{\ell}<i$ and
$\pi_{\ell}$ is not adjacent to $i$ in $G$. By the induction hypothesis, car
$\pi_{\ell}$ occupies spot $\ell$, which neighbours spot $k$ in $\pi$, and
since $\pi_{\ell}$ and $i$ are not adjacent in $G$, this prevents car $i$ from
parking in spot $k$ in the friendship parking process.

As such, car $i$ cannot park in any of the spots
$s_{i},s_{i}+1,\cdots,\pi^{-1}_{i}-1$. It therefore remains to show that it is
allowed to park in spot $\pi^{-1}_{i}$ in the friendship parking process, i.e.
that spot $\pi^{-1}_{i}$ is available for $i$. First, note that by the
induction hypothesis, cars $1,\cdots i-1$ occupy spots
$\pi^{-1}_{1},\cdots,\pi^{-1}_{i-1}$. Therefore, when car $i$ enters the car
park, spot $\pi^{-1}_{i}$ is unoccupied. Now consider
$N(i):=\\{\pi^{-1}_{i}-1,\pi^{-1}_{i}+1\\}$ the two neighbouring spots to
$\pi^{-1}_{i}$. By definition, if $s\in N(i)$, then $\pi_{s}$ is a neighbour
of $i$ in the Hamiltonian path $\pi$, and therefore is adjacent to $i$ in the
graph $G$. Moreover, by the induction hypothesis, when $i$ enters the car
park, such a spot $s$ is either occupied by $\pi_{s}$ (if $\pi_{s}<i$), or
unoccupied (if $\pi_{s}>i$). Finally, we have shown that when car $i$ enters
the car park, spot $\pi^{-1}_{i}$ is unoccupied (see above), and each of its
two neighbouring spots is either unoccupied, or is occupied by a car adjacent
to $i$ in $G$. This means exactly that spot $\pi^{-1}_{i}$ is available for
$i$ in the friendship parking process, as desired. ∎

###  2.3 Application: the cycle graph case

In this section, we are interested in the specific case where $G$ is a cycle
graph. For $n\geq 3$, we denote $C_{n}$ the cycle graph on $n$ vertices. This
is the graph with vertex set $[n]$ and edge set
$\\{(i,i+1)\\}_{i\in[n-1]}\cup\\{(n,1)\\}$ (see Figure 5).

$1$$2$$3$$4$$5$$6$ Figure 5: The cycle graph $C_{6}$ on six vertices.

We wish to apply Theorem 2.7 and Corollary 2.9 to the cycle graph case. First,
note that Hamiltonian paths of the cycle graph are of one of the following two
types:

  1. 1.

_Increasing cycles_ , which are of the form
$\mathrm{IncCyc}^{i,n}:=i(i+1)\cdots n12\cdots(i-1)$ for some $i\in[n]$;

  2. 2.

_Decreasing cycles_ , which are of the form
$\mathrm{DecCyc}^{i,n}:=i(i-1)\cdots 1n(n-1)\cdots(i+1)$ for some $i\in[n]$.

We characterise the blocking sequences for both types of outcome. We begin
with the decreasing cycle case. For technical reasons (see Remark 2.11) we
assume that $n\geq 4$.

######  Proposition 2.10.

Decreasing cycle case, $n\geq 4$.

  1. 1.

Case $i\leq n-2$. Let $i\leq n-2$. For any $j\in[n]$, we have:

$B\left(j,\mathrm{DecCyc}^{i,n},C_{n}\right)=\left\\{\begin{array}[]{ll}j&\text{
if }j\leq n-2,\\\ i(i-1)\cdots 1n(n-1)&\text{ if }j=n-1,\\\ i(i-1)\cdots
1n&\text{ if }j=n.\end{array}\right.$

In particular, this implies that
$\left|\mathcal{O}^{-1}_{\mathrm{FPF}\left(C_{n}\right)}\left(\mathrm{DecCyc}^{i,n}\right)\right|=(i+1)(i+2)$.

  2. 2.

Case $i=n-1$. For any $j\in[n-1]$, we have
$B\left(j,\mathrm{DecCyc}^{n-1,n},C_{n}\right)=j$. Moreover, we have
$B\left(n,\mathrm{DecCyc}^{n-1,n},C_{n}\right)=(n-1)\cdots
1n=\mathrm{DecCyc}^{n-1,n}$. In particular, this implies that
$\left|\mathcal{O}^{-1}_{\mathrm{FPF}\left(C_{n}\right)}\left(\mathrm{DecCyc}^{n-1,n}\right)\right|=n$.

  3. 3.

Case $i=n$. For any $j\in[n]$, we have
$B\left(j,\mathrm{DecCyc}^{n,n},C_{n}\right)=j$. In particular, this implies
that
$\left|\mathcal{O}^{-1}_{\mathrm{FPF}\left(C_{n}\right)}\left(\mathrm{DecCyc}^{n,n}\right)\right|=1$.

###### Proof.

Fix some $i,j\in[n]$, and consider the blocking sequence for $j$ in the
decreasing cycle $\mathrm{DecCyc}^{i,n}=i(i-1)\cdots 1n(n-1)\cdots(i+1)$. We
first note that if $j\leq n-2$, then
$\mathrm{DecCyc}^{i,n}=\cdots(j+2)(j+1)j\cdots$ (assuming $j$ doesn’t appear
in position $1$ or $2$). This implies that $j+1$ is not a blocker for $j$,
since it is strictly greater than $j$ and both of its neighbours in
$\mathrm{DecCyc}^{i,n}$ are greater than or equal to $j$. This shows that
$B\left(j,\mathrm{DecCyc}^{i,n},C_{n}\right)=j$, as desired.

Now consider $j=n-1$. If $i\leq n-2$, then we have
$\mathrm{DecCyc}^{i,n}=i\cdots 1n(n-1)\cdots$. As the vertices $1$ and $n-1$
are not adjacent in $C_{n}$ (since $n\geq 4$), and $1<n-1$, this implies that
$n$ is a blocker for $n-1$. Moreover, all values $i,i-1,\cdots,1$ are strictly
less than $n-1$, so are all blockers. Thus, we have
$B\left(n-1,\mathrm{DecCyc}^{i,n},C_{n}\right)=i(i-1)\cdots 1n(n-1)$, as
desired. However, this relies on $1$ (immediately) preceding $n$ in
$\mathrm{DecCyc}^{i,n}$, which only occurs if $i\leq n-2$. Otherwise, $n-1$
appears in first or second position, and is at most preceded by $n$, which is
not a blocker in that case, so
$B\left(n-1,\mathrm{DecCyc}^{i,n},C_{n}\right)=n-1$ if $i\in\\{n-1,n\\}$, as
desired.

Finally, consider $j=n$. If $i\leq n-1$, then we have
$\mathrm{DecCyc}^{i,n}=i\cdots 1n\cdots$. All elements in $i,i-1,\cdots,1$ are
strictly less than $n$, so are blockers in this case. This gives
$B\left(n,\mathrm{DecCyc}^{i,n},C_{n}\right)=i(i-1)\cdots 1n$ as desired. If
$i=n$, then $n$ appears in first position in
$\mathrm{DecCyc}^{n,n}=n(n-1)\cdots 1$, so
$B\left(n,\mathrm{DecCyc}^{i,n},C_{n}\right)=n$. This completes the proof. ∎

######  Remark 2.11.

The above proof in the case $j=n-1$ shows why we assumed that $n\geq 4$.
Otherwise, for $n=3$, in the outcome $132$, the blocking sequence for
$j=n-1=2$ is just $2$. Indeed, in this case $3$ is not a blocker for $2$,
since $1$ and $2$ are adjacent in $C_{3}$. We therefore get
$\left|\mathcal{O}^{-1}_{\mathrm{FPF}\left(C_{3}\right)}\left(132\right)\right|=1*1*b(3,132,C_{3})=2$,
instead of the value $2*3=6$ as would be given by Case (1) of Proposition
2.10.

######  Proposition 2.12.

Increasing cycle case.

  1. 1.

Case $i\geq 4$. Let $i\geq 4$. For any $j\in[n]$, we have:

$B\left(j,\mathrm{IncCyc}^{i,n},C_{n}\right)=\left\\{\begin{array}[]{ll}i(i+1)\cdots
j&\text{ if }j\geq i,\\\ n12\cdots j&\text{ if }3\leq j\leq i-1,\\\ 12&\text{
if }j=2,\\\ 1&\text{ if }j=1.\end{array}\right.$

In particular, this implies that
$\left|\mathcal{O}^{-1}_{\mathrm{FPF}\left(C_{n}\right)}\left(\mathrm{IncCyc}^{i,n}\right)\right|=(n-i+1)!i!/3$.

  2. 2.

Case $i\leq 3$. Let $i\leq 3$. For any $j\in[n]$, we have:

$B\left(j,\mathrm{IncCyc}^{i,n},C_{n}\right)=\left\\{\begin{array}[]{ll}i\cdots
j&\text{ if }j\geq i,\\\ 1\cdots j&\text{ if }j\leq i-1.\end{array}\right.$

In particular, this implies that
$\left|\mathcal{O}^{-1}_{\mathrm{FPF}\left(C_{n}\right)}\left(\mathrm{IncCyc}^{i,n}\right)\right|=(n+1-i)!(i-1)!$.

###### Proof.

Fix $i,j\in[n]$. If $j\geq i$, we have
$B\left(j,\mathrm{IncCyc}^{i,n},C_{n}\right)=i(i+1)\cdots j$. Indeed, all
elements to the left of $j$ in $\mathrm{IncCyc}^{i,n}$ are less than or equal
to $j$, so they are all blockers for $j$. Moreover, it is straightforward to
check that $B\left(1,\mathrm{IncCyc}^{i,n},C_{n}\right)=1$ (true in fact for
any graph $G$ and Hamiltonian path $\pi\in\mathcal{H}\left(G\right)$, see
proof of Theorem 2.7).

Now consider the case $j=2$ where $j\leq i-1$, i.e. $2$ is not in first
position in $\mathrm{IncCyc}^{i,n}$. In this case, $2$ immediately follows $1$
in $\mathrm{IncCyc}^{i,n}$, and therefore $1$ is in the blocking sequence for
$2$. Moreover, $n$ is not a blocker for $2$, since its neighbours in
$\mathrm{IncCyc}^{i,n}$ are $n-1$ (which is greater than or equal to $2$), and
$1$ (which is adjacent to $2$ in $C_{n}$). Therefore if $i\geq 3$ we have
$B\left(2,\mathrm{IncCyc}^{i,n},C_{n}\right)=12=1\cdots j$, as desired.

It therefore remains to consider the case $3\leq j\leq i-1$. Necessarily we
have $i\geq 4$, so that $\mathrm{IncCyc}^{i,n}=\cdots n12\cdots j\cdots$. By
definition, $1,2,\cdots,j$ are all blockers for $j$, since they are less than
or equal to $j$. Moreover, since $3\leq j\leq i-1\leq n-1$, the elements $j$
and $1$ are not adjacent in $C_{n}$ ($n$ and $2$ are the vertices adjacent to
$1$). Since $n$ is followed by $1$ in $\mathrm{IncCyc}^{i,n}$, this implies
that $n$ is a blocker for $j$. Finally, $n-1$ is not a blocker for $j$, since
both its neighbours in $\mathrm{IncCyc}^{i,n}$ are greater than or equal to
$j$. Therefore, we get $B\left(2,\mathrm{IncCyc}^{i,n},C_{n}\right)=n12\cdots
j$, as desired. This completes the proof. ∎

Combining Propositions 2.10 and 2.12, we get the following enumeration for the
total number of $C_{n}$-friendship parking functions.

######  Theorem 2.13.

Let $n\geq 4$. The total number of friendship parking functions for the cycle
graph $C_{n}$ is given by

$\big{|}\mathrm{FPF}\left(C_{n}\right)\big{|}=n+1+\sum\limits_{i=1}^{n-2}(i+1)(i+2)+\sum\limits_{i=1}^{3}(n+1-i)!(i-1)!+\sum\limits_{i=4}^{n}(n-i+1)!i!/3.$

For the case $n=3$, the enumeration is given by the same formula, except that
we replace the product $(i+1)(i+2)$ in the left-most sum with just $(i+1)$, as
per Remark 2.11.

##  3 Cyclic parking functions and permutation components

In this part we consider classical parking functions whose outcome is an
increasing cycle, i.e. of the form $\mathrm{IncCyc}^{i,n}:=i(i+1)\cdots
n12\cdots(i-1)$ for some $i\in[n]$. This is a slight variant on the
$C_{n}$-friendship parking functions from Section 2.3. We say that
$p=(p_{1},\cdots,p_{n})$ is a _cyclic parking function_ if we have
$\mathcal{O}_{\mathrm{PF}_{n}}\left(p\right)=\mathrm{IncCyc}^{i,n}$, for some
$i\in[n]$. We denote
$\mathrm{CycPF}_{n}:=\bigcup\limits_{i\in[n]}\mathcal{O}^{-1}_{\mathrm{PF}_{n}}\left(\mathrm{IncCyc}^{i,n}\right)$
the set of cyclic parking functions of length $n$.

######  Proposition 3.1.

For any $i\in[n]$, we have
$\left|\mathcal{O}^{-1}_{\mathrm{PF}_{n}}\left(\mathrm{IncCyc}^{i,n}\right)\right|=(n+1-i)!(i-1)!$.

###### Proof.

The proof is similar to that of Theorem 2.7 and Proposition 2.12, so we allow
ourselves to be briefer here. Let $i\in[n]$, and consider how a parking
preference $p=(p_{1},\cdots,p_{n})$ can yield the outcome permutation
$\mathrm{IncCyc}^{i,n}=i(i+1)\cdots n12\cdots(i-1)$ (for the classical parking
process). Car $1$ ends up in spot $j:=n+2-i$ (with the convention that $j=1$
if $i=1$). Since car $1$ always ends up in its preferred spot in the classical
parking process, we must have $p_{1}=j$. Then car $2$ ends up in spot $j+1$.
This occurs if, and only if, we have $p_{2}\in\\{j,j+1\\}$ (since car $1$
occupies $j$).

We repeat this reasoning on the first $i-1$ cars, and see that each car
$k\in\\{1,\cdots,i-1\\}$ has exactly $k$ possibilities for its parking
preference. This gives the $(i-1)!$ factor in the formula. The $(n+1-i)!$
factor comes from an analogous reasoning on cars $i,i+1,\cdots,n$. Car $i$
ends up in spot $1$, so must prefer that spot. Car $(i+1)$ ends up in spot
$2$, so must prefer spot $1$ (occupied by car $i$) or spot $2$, and so on.
This completes the proof. ∎

######  Remark 3.2.

The formula in Proposition 3.1 is quite similar to that of friendship parking
functions on the cycle graph $C_{n}$ whose outcome is an increasing cycle (see
Proposition 2.12). The key difference lies in the role of the car/vertex $n$.
In $C_{n}$-friendship parking functions, this vertex plays the role of a
blocker for cars $j\geq 3$ which park to its right, whereas in classical
parking functions it is never a “blocker” (if car $j$ wanted to park in the
corresponding spot, it could).

As an example, consider the parking function $p=(2,3,1,1)$. In the friendship
parking process for $C_{4}$, car $3$ cannot park in spot $1$, since spot $2$
is occupied by car $1$, and there is no edge $(1,3)$ in $C_{4}$. Therefore we
get the outcome
$\mathcal{O}_{\mathrm{FPF}\left(4\right)}\left(p\right)=4123=\mathrm{IncCyc}^{4,4}$,
and $p$ is a $C_{4}$-friendship parking function. However, in the classical
parking process, car $3$ can park in spot $1$, and so car $4$ will end up in
spot $4$, yielding the outcome
$\mathcal{O}_{\mathrm{PF}_{4}}\left(p\right)=3124$, so $p$ is not a cyclic
parking function in the sense of this section.

Summing the right-hand side of the enumeration in Proposition 3.1 over values
of $i$ from $1$ to $n$, combined with the change of variable $i\rightarrow
n+1-i$, immediately yields the following.

######  Corollary 3.3.

We have $\left|\mathrm{CycPF}_{n}\right|=\sum\limits_{i=0}^{n-1}i!(n-i)!$.

Calculating these numbers for the first few values of $n$, we get the sequence
$1,3,10,40,192,\cdots$, which corresponds to Sequence A136128 in the OEIS
[23]. The entry for this sequence states “Number of components in all
permutations of $[n]$”, and the goal of this section is to give a bijective
proof of this fact by exhibiting a bijection between cyclic parking functions
and permutation components. As such, cyclic parking functions provide a new
combinatorial interpretation for this Sequence A136128. Before defining our
bijection, we first need to introduce some terminology relating to
permutations.

Given a permutation $\pi=\pi_{1}\cdots\pi_{n}$, a _component_ of $\pi$ is a
sub-sequence $\pi_{i}\pi_{i+1}\cdots\pi_{j}$ for some $1\leq i\leq j\leq n$
such that $\\{\pi_{i},\pi_{i+1},\cdots\pi_{j}\\}=\\{i,i+1,\cdots,j\\}$, which
is minimal for inclusion (i.e. it does not contain any smaller such sub-
sequence). It is straightforward to see that every permutation can be uniquely
decomposed into its components. For example, the permutation $31248657$ has
three components: $312$, $4$, $8657$. We will use a slash to separate the
components of a permutation, for example $312/4/8657$. The set of components
of a permutation $\pi$ is denoted $\mathrm{comp}\left(\pi\right)$.

Note that the same sub-sequence can be a component of more than one
permutation. For example, $1$ is a component of both $1/32$ or $1/2/3$. In
this section, we consider the set of all components of permutations of length
$n$, $\mathrm{Comp}_{n}:=\bigsqcup\limits_{\pi\in
S_{n}}\mathrm{comp}\left(\pi\right)$, where $\bigsqcup$ denotes the disjoint
union. That is, we distinguish between the component $1$ in the permutation
$1/32$ and the component $1$ in the permutation $1/2/3$. For
$c\in\mathrm{Comp}_{n}$, we will denote $\mathrm{Perm}\left(c\right)\in S_{n}$
the underlying permutation, i.e.
$c\in\mathrm{comp}\left(\mathrm{Perm}\left(c\right)\right)$).

In our bijection between cyclic parking functions and permutation components,
permutation inversions will play a key role. Given a permutation
$\pi=\pi_{1}\cdots\pi_{n}\in S_{n}$, we say that an ordered pair $(i,j)$ is an
_inversion_ of $\pi$ if $i>j$ and $i$ appears before $j$ in the permutation
$\pi$. The _inversion number_ of $i$ in $\pi$, denoted
$\mathrm{inv}_{i}\left(\pi\right)$, is the number of $j<i$ such that $(i,j)$
is an inversion of $\pi$. In words, the inversion number of $i$ counts how
many letters less than $i$ appear after $i$ in $\pi$. For example, the
permutation $\pi=3152476$ has the following inversions:
$(3,1),(3,2),(5,2),(5,4),(7,6)$. We have
$\mathrm{inv}_{1}\left(\pi\right)=\mathrm{inv}_{2}\left(\pi\right)=\mathrm{inv}_{4}\left(\pi\right)=\mathrm{inv}_{6}\left(\pi\right)=0$,
$\mathrm{inv}_{3}\left(\pi\right)=\mathrm{inv}_{5}\left(\pi\right)=2$, and
$\mathrm{inv}_{7}\left(\pi\right)=1$. Note that any inversion of $\pi$ is
necessarily contained in a component of $\pi$.

######  Definition 3.4.

Let $a=(a_{1},\cdots,a_{n})$ be a sequence of non-negative integers. We say
that $a$ is an _inversion sequence_ if $a_{i}<i$ for all $i\in[n]$.

The terminology _inversion sequence_ comes from the following classical
result, of which we give a brief proof for completeness.

######  Theorem 3.5.

The map
$\mathrm{InvSeq}:\pi=\pi_{1}\cdots\pi_{n}\mapsto\mathrm{InvSeq\left(\pi\right)}:=\left(\mathrm{inv}_{1}\left(\pi\right),\cdots,\mathrm{inv}_{n}\left(\pi\right)\right)$
is a bijection from the set of $n$-permutations to the set of inversion
sequences of length $n$.

###### Proof.

Let $\pi=\pi_{1}\cdots\pi_{n}\in S_{n}$, and
$\mathrm{InvSeq\left(\pi\right)}:=\left(\mathrm{inv}_{1}\left(\pi\right),\cdots,\mathrm{inv}_{n}\left(\pi\right)\right)$.
By definition, for any $i\in[n]$, $\mathrm{inv}_{i}\left(\pi\right)$ is the
number of $j<i$ such that $(i,j)$ is an inversion of $\pi$, which immediately
implies that $\mathrm{inv}_{i}\left(\pi\right)<i$, i.e. that
$\mathrm{InvSeq\left(\pi\right)}$ is an inversion sequence. Moreover, it is
straightforward to see that there are $n!$ inversion sequences of length $n$.
Indeed, we have $1$ choice ($0$) for the entry $a_{1}$, $2$ choices ($0$ and
$1$) for the entry $a_{2}$, and so on.

To show that the map $\mathrm{InvSeq}$ is a bijection, it is therefore
sufficient to show that it is surjective. Let $a=(a_{1},\cdots,a_{n})$ be an
inversion sequence. We construct a permutation $\pi$ as follows. Start with
$i=0$ and the empty word $\pi^{0}=\emptyset$. Suppose that after $i$ steps we
have constructed a word $\pi^{i}=\pi^{i}_{1}\cdots\pi^{i}_{i}\in S_{i}$ such
that $\mathrm{inv}_{j}\left(\pi^{i}\right)=a_{j}$ for all $j\in[i]$. Then at
step $i+1$, we define $\pi^{i+1}=\pi^{i+1}_{1}\cdots\pi^{i+1}_{i+1}$ by simply
inserting $(i+1)$ in the permutation $\pi^{i}$ at index $i+1-a_{i+1}$ (i.e.
$a_{i+1}$ spots starting from the right). By construction, we get a
permutation $\pi^{i+1}\in S_{i+1}$ such that
$\mathrm{inv}_{j}\left(\pi^{i+1}\right)=a_{j}$ for all $j\in[i+1]$. Therefore,
the final permutation $\pi^{n}\in S_{n}$ obtained satisfies
$\mathrm{InvSeq\left(\pi^{n}\right)}=a$, as desired. ∎

######  Example 3.6.

Consider the inversion sequence $a=(0,0,1,3,2)$. We start with the empty word
$\pi^{0}=\emptyset$. At step $1$, we insert the letter $1$ in the empty word
so that there are $a_{1}=0$ letters to its right, i.e. we get $\pi^{1}=1$ (we
will always have this step). At step $2$, we have $a_{2}=0$, so we insert $2$
into the permutation $\pi^{1}=1$, so that there are $0$ letters to its right,
yielding $\pi^{2}=12$. Then at step $3$, we have $a_{3}=1$. As such, we insert
$3$ into the permutation $12$ so that it has $1$ letter to its right, yielding
$\pi^{3}=132$. At step $4$, we insert $4$ into $132$ so that it has $a_{4}=3$
letters to its right, yielding $\pi^{4}=4132$. Finally, at step $5$, we insert
$5$ so that it has $a_{5}=2$ letters to its right, yielding the permutation
$\pi=\pi^{5}=41532$. We can then check that
$\mathrm{InvSeq\left(\pi\right)}=(0,0,1,3,2)=a$, as desired.

Inversion sequences are linked to the displacement vector of parking functions
by the following result.

######  Proposition 3.7.

Let $p\in\mathrm{PF}_{n}$ be a parking function. Then its displacement vector
$\mathrm{disp}\left(p\right)$ is an inversion sequence.

###### Proof.

Let $p\in\mathrm{PF}_{n}$, and write
$\mathrm{disp}\left(p\right)=(d_{1},\cdots,d_{n})$ for its displacement
vector. Fix $i\in[n]$. By definition, $d_{i}$ is the distance car $i$ travels
from its preferred spot to its final parking spot. In the classical parking
process, this means that spots $p_{i},p_{i}+1,\cdots,p_{i}+d_{i}-1$ must all
be occupied when car $i$ enters the car park. Since there are $i-1$ cars
entering before car $i$, and each of these occupies at most one of those
spots, this implies that $d_{i}\leq i-1<i$, as desired. ∎

We are now equipped to define the bijection from cyclic parking functions to
permutation components. Given a cyclic parking function $p$, whose outcome is
$\mathrm{IncCyc}^{i,n}$ for some $i\in[n]$, we define $\Psi(p)$ to be the
component of $\pi$ containing $i$, where $\pi\in S_{n}$ is the unique
permutation such that
$\mathrm{InvSeq\left(\pi\right)}=\mathrm{disp}\left(p\right)$.

######  Example 3.8.

Consider the parking function $p=(4,4,6,6,7,9,7,1,2,1)$. By running the
parking process, we get
$\mathcal{O}_{\mathrm{PF}_{10}}\left(p\right)=89(10)1234567=\mathrm{IncCyc}^{8,10}$.
The displacement vector of $p$ is
$\mathrm{disp}\left(p\right)=(0,1,0,1,1,0,3,0,0,2)$. The corresponding
permutation $\pi$ such that
$\mathrm{disp}\left(p\right)=\mathrm{InvSeq\left(\pi\right)}$ is
$\pi=21/47536/(10)89$, and we map this to the component containing car $i=8$,
so $\Psi(p)=(10)89$.

######  Example 3.9.

Here we fix $n=3$, and consider the images of all cyclic parking functions of
length $n$ under the map $\Psi$. These are illustrated in Table 1 below. We
have partitioned cyclic parking functions (listed in Column 2) according to
their outcome (in Column 1). Column 3 then gives the displacement vector of
each parking function, with Column 4 listing the permutation whose inversion
sequence is the displacement vector. Finally, in the component column (Column
5), we have copied in this permutation for clarity, with the corresponding
component $\Psi(p)$ in bold.

Outcome | Parking function $p$ | $\mathrm{disp}\left(p\right)$ | Permutation $\pi$ | Component $c=\Psi(p)$
---|---|---|---|---
$123$ | $(1,1,1)$ | $(0,1,2)$ | $321$ | $\mathbf{321}$
$(1,1,2)$ | $(0,1,1)$ | $231$ | $\mathbf{231}$
$(1,1,3)$ | $(0,1,0)$ | $213$ | $\mathbf{21}/3$
$(1,2,1)$ | $(0,0,2)$ | $312$ | $\mathbf{312}$
$(1,2,2)$ | $(0,0,1)$ | $132$ | $\mathbf{1}/32$
$(1,2,3)$ | $(0,0,0)$ | $123$ | $\mathbf{1}/2/3$
$231$ | $(3,1,1)$ | $(0,0,1)$ | $132$ | $1/\mathbf{32}$
$(3,1,2)$ | $(0,0,0)$ | $123$ | $1/\mathbf{2}/3$
$312$ | $(2,2,1)$ | $(0,1,0)$ | $213$ | $21/\mathbf{3}$
$(2,3,1)$ | $(0,0,0)$ | $123$ | $1/2/\mathbf{3}$
Table 1: All cyclic parking functions of length $n=3$, with their
corresponding permutation components.

######  Theorem 3.10.

The map $\Psi:\mathrm{CycPF}_{n}\rightarrow\mathrm{Comp}_{n}$ is a bijection
from cyclic parking functions to permutation components. Moreover, for any
cyclic parking function $p$ and any $i\in[n]$, the displacement of car $i$ in
$p$ is equal to the inversion number of $i$ in the underlying permutation
$\mathrm{Perm}\left(\Psi(p)\right)$.

######  Lemma 3.11.

Let $p\in\mathrm{CycPF}_{n}$ be a cyclic parking function with outcome
$\mathcal{O}_{\mathrm{FPF}\left(C_{n}\right)}\left(p\right)=\mathrm{IncCyc}^{i,n}$,
i.e. car $i$ ends up in spot $1$. Then we have $i=\min\Psi(p)$.

###### Proof.

Let $p\in\mathrm{CycPF}_{n}$ be a cyclic parking function, and
$\mathrm{disp}\left(p\right)=(d_{1},\cdots,d_{n})$ its displacement vector.
Define $\pi\in S_{n}$ to be the unique permutation such that
$\mathrm{InvSeq\left(\pi\right)}=\mathrm{disp}\left(p\right)$. Denote
$c:=\Psi(p)$ the component of the permutation $\pi$ corresponding to the
parking function $p$, and let $i^{\prime}:=\min c$ and $k=|c|$ be its minimal
element and size respectively. By definition, the component $c$ is a
permutation of the set $\\{i^{\prime},\cdots,i^{\prime}+k-1\\}$. Moreover, by
construction we have
$d_{j}=\mathrm{inv}_{j}\left(\pi\right)=\mathrm{inv}_{j}\left(c\right)$ for
any $j\in c$, since all inversions of the permutation $\pi$ are necessarily
contained in its components.

Seeking contradiction, suppose that $i^{\prime}<i$. We consider cars
$i^{\prime},i^{\prime}+1,\cdots,i-1$ in the parking process, which are the
$i-i^{\prime}$ smallest elements of the component $c$. By the remarks above,
we have $d_{i^{\prime}+j-1}<j$ for all $j\in[i-i^{\prime}]$. Now consider cars
$i,i+1,\cdots,i^{\prime}+k-1$. By definition of $i$, these occupy spots
$1,\cdots,k+i^{\prime}-i$. In particular, we must have
$\mathrm{disp}\left(i+j-1\right)<j$ for all $j\in[k+i^{\prime}-i]$. These
inequalities summarise as below.

$\begin{array}[]{rcccccc}\text{cars:}&i^{\prime}&\cdots&i-1&i&\cdots&i^{\prime}+k-1\\\
\hline\cr&d_{i^{\prime}}&\cdots&d_{i-1}&d_{i}&\cdots&d_{i^{\prime}+k-1}\\\
\text{displacement:}&\wedge&\cdots&\wedge&\wedge&\cdots&\wedge\\\
&1&\cdots&i-i^{\prime}&1&\cdots&k+i^{\prime}-i\\\ \end{array}$

Now recall that $\mathrm{disp}\left(p\right)=\mathrm{InvSeq\left(\pi\right)}$,
and that $c$ is a sub-sequence in $\pi$ which is a permutation of the set
$\\{i^{\prime}\cdots,i^{\prime}+k-1\\}$. It is straightforward, using the
inverse construction from Theorem 3.5, to check that the inequalities above
imply that $c$ can be written as $c=c^{1}\\!\cdot\\!c^{2}$, where $c^{1}$,
resp. $c^{2}$, is a permutation of the set $\\{i^{\prime},\cdots,i-1\\}$,
resp. of the set $\\{i,\cdots,i^{\prime}+k-1\\}$. This contradicts the
minimality of the component $c$. ∎

###### Proof of Theorem 3.10.

We first show that $\Psi$ is injective. For this, let $p,p^{\prime}$ be two
cyclic parking functions such that $c:=\Psi(p)=\Psi(p^{\prime})$. Let $i:=\min
c$. By Lemma 3.11, we have that
$\mathcal{O}_{\mathrm{FPF}\left(n\right)}\left(p\right)=\mathcal{O}_{\mathrm{FPF}\left(n\right)}\left(p^{\prime}\right)=\mathrm{IncCyc}^{i,n}$.
Moreover, by construction, we have
$\mathrm{disp}\left(p\right)=\mathrm{disp}\left(p^{\prime}\right)=\mathrm{Perm}\left(c\right)$.
We claim that two parking functions which share the same outcome and
displacement vector are necessarily equal. Indeed, the preference of any car
is equal to its index in the outcome permutation minus its displacement (this
is the definition of the displacement vector).

It remains to show that $\Psi$ is surjective, which we do by constructing its
inverse. Let $c\in\mathrm{comp}\left(\pi\right)$ be a component of some
permutation $\pi\in S_{n}$. Define $i:=\min c$ to be its minimal element. Let
$s=(s_{1},\cdots,s_{n}):=\mathrm{InvSeq\left(\pi\right)}$ be the inversion
sequence of $\pi$. For $j\in[n]$, denote $\overline{j}$ the index of $j$ in
the cyclic permutation $\mathrm{IncCyc}^{i,n}$. That is, $\bar{j}=n+j+1-i$ if
$j\leq i-1$, and $\bar{j}=j+1-i$ if $j\geq i$.

We claim that $s_{j}<\bar{j}$ for all $j\in[n]$. If $j\leq i-1$, this simply
follows from the fact that $s$ is an inversion sequence: we have $\bar{j}\geq
j+1$ and $s_{j}<j$. Now note that since $i$ is the minimal element in a
component of the permutation $\pi$, this means in particular that $\pi$ can be
decomposed as $\pi^{<i}\\!\cdot\\!\pi^{\geq i}$, where $\pi^{<i}$, resp.
$\pi^{\geq i}$, is a permutation of the set $\\{1,\cdots,i-1\\}$, resp.
$\\{i,\cdots,n\\}$. In particular, if $j\geq i$, all inversions
$(j,j^{\prime})$ of $\pi$ must be in the right-hand permutation $\pi^{\geq
i}$. This implies in particular that $s_{j}<j-(i-1)=\bar{j}$, as desired.

We can then define $p=(p_{1},\cdots,p_{n})$ by setting $p_{j}=\bar{j}-s_{j}$
for all $j\in[n]$. By the above claim, we have $p_{j}>0$ for all $j$, so $p$
is a parking preference. Moreover, by construction, we have
$\mathcal{O}_{\mathrm{FPF}\left(n\right)}\left(p\right)=\mathrm{IncCyc}^{i,n}$,
and $\Psi(p)=c$. This shows that $\Psi$ is surjective, and thus a bijection,
as desired. The fact that $\Psi$ maps the displacement of a car to its
inversion number in the underlying permutation is by construction: the
permutation $\mathrm{Perm}\left(\Psi(p)\right)$ is defined so that
$\mathrm{InvSeq\left(\mathrm{Perm}\left(\Psi(p)\right)\right)}=\mathrm{disp}\left(p\right)$.
∎

######  Example 3.12.

We show an example of the construction of $\Psi^{-1}$ in the previous proof.
Consider the permutation $\pi=3412/\mathbf{7865}/9$, with component $c=7865$.
We first calculate the inversion sequence of $\pi$, yielding
$\mathrm{InvSeq\left(\pi\right)}=(0,0,2,2;0,1,2,2;0)$ where we have used a
semi-colon to separate the permutation components for clarity. The minimal
element of $c$ is $i=5$. This indicates that car $5$ must end up in spot $1$,
cars $6$ to $9$ end up in spots $2$ to $5$, and cars $1$ to $4$ end up in
spots $6$ to $9$. For each car $i$, we determine its parking preference
$p_{i}$ by subtracting its inversion number (which will be equal to its
displacement) from its final spot. For example, car $8$ ends up in spot $4$,
and $8$ has inversion number $2$ in $\pi$, corresponding to the inversions
$(8,6)$ and $(8,5)$, so we set $p_{8}=4-2=2$. We do this for each car, and
finally get the parking preference $p=(6,7,6,7,1,1,1,2,5)$. We can check that
$\mathcal{O}_{\mathrm{FPF}\left(9\right)}\left(p\right)=567891234$, and that
$\mathrm{disp}\left(p\right)=\mathrm{InvSeq\left(\pi\right)}$, as desired.

######  Remark 3.13.

Theorem 3.10 implies a converse for Proposition 3.7. Namely, if
$a=(a_{1},\cdots,a_{n})$ is an inversion sequence, then there exists a cyclic
parking function $p$ such that $\mathrm{disp}\left(p\right)=a$. In fact, the
number of such cyclic parking functions is equal to the number of components
of the permutation $\pi$ such that $a=\mathrm{InvSeq\left(\pi\right)}$.
Indeed, given an inversion sequence $a$ with corresponding permutation $\pi$
(i.e. $\mathrm{InvSeq\left(\pi\right)}=a$), then the set of cyclic parking
functions $p$ satisfying $\mathrm{disp}\left(p\right)=a$ is exactly the set
$\Psi^{-1}\left(\mathrm{comp}\left(\pi\right)\right)$.

##  4 Conclusion and future work

In this paper, we introduced a new variation on classical parking functions,
called _friendship parking functions_. These essentially follow classical
parking rules, with the added restriction that a car can only park next to its
“friends” (adjacent vertices in an underlying graph $G$). We gave a full
characterisation of $G$-friendship parking functions according to their
outcome, or equivalently Hamiltonian paths of $G$ (Theorem 2.7). We then
applied this result and its enumerative consequence to the case where $G$ is
the cycle graph on $n$ vertices (Section 2.3). Finally, in Section 3 we
returned to classical parking functions, considering _cyclic parking
functions_ whose (classical) outcome is an increasing cycle of the form
$i(i+1)\cdots n12\cdots(i-1)$. We exhibited (Theorem 3.10) a bijection between
cyclic parking functions of _permutation components_ , which maps the
_displacement_ of each car to its _inversion_ number in the corresponding
permutation.

One natural question from this last work is to ask whether other families of
permutations have natural combinatorial interpretations of their outcome
fibres (whether for classical parking functions or one of the variations
thereon). For example, in [17] it was shown that the outcome fibre of a
permutation $\pi$ can be interpreted in terms of certain subgraphs of the
corresponding permutation graph $G_{\pi}$, and various families of
permutations were studied under that representation. It would be interesting
to ask similar questions of classical parking functions.

Regarding friendship parking functions, a first question to consider would be
to pursue the study of graph families. In this paper we studied the case of
cycle graphs. We could also investigate other families such as cycle graphs
with a different labelling, wheel graphs, complete graphs with one edge
removed, and so on. We should look for both closed enumeration formulas and
combinatorial interpretations of friendship parking functions in those cases.

Finally, we could also consider the case where the underlying graph $G$ does
not have a Hamiltonian path. In this case, there will be no friendship parking
functions allowing all cars to park, but we could consider _defective_ parking
functions, as in the classical case [2]. In other words, for some fixed $k>0$,
how many friendship parking functions are there where exactly $k$ cars fail to
park? What are the minimal/maximal values of such a $k$? Of particular
interest could be the case where $G$ is a disjoint union of cliques, i.e.
where the friendship relationship is transitive. In other words, we partition
the set $[n]$ into subsets $F_{1},\cdots,F_{j}$ where any pair of elements in
$F_{\ell}$ are friends, but there is no friendship between elements of
distinct $F_{\ell}$ and $F_{\ell^{\prime}}$. What can be said about friendship
parking functions under this model?

## Acknowledgments

The research leading to these results was supported by the Summer
Undergraduate Research Fellowship programme at Xi’an Jiaotong-Liverpool
University. The authors would like to thank Xiaoyi Zhang for helpful initial
discussions. The authors have no competing interests to declare that are
relevant to the content of this article.

## References

  * [1] Ayomikun Adeniran and Catherine Yan.  On increasing and invariant parking sequences.  Australas. J. Comb., 79:167–182, 2021.
  * [2] Peter Jephson Cameron, Daniel Johannsen, Thomas Prellberg, and Pascal Schweitzer.  Counting defective parking functions.  Electron. J. Comb., 15(1):research paper R92, 378–388, 2008.
  * [3] Joshua Carlson, Alex Christensen, Pamela E. Harris, Zakiya Jones, and Andrés Ramos Rodríguez.  Parking functions: Choose your own adventure.  The College Mathematics Journal, 52(4):254–264, 2021.
  * [4] Denis Chebikin and Pavlo Pylyavskyy.  A family of bijections between $G$-parking functions and spanning trees.  J. Comb. Theory, Ser. A, 110(1):31–41, 2005.
  * [5] Douglas Chen, Pamela E. Harris, Juan Carlos Martínez Mori, Eric Pabón-Cancel, and Gabriel Sargent.  Permutation invariant parking assortments.  Enumer. Comb. Appl., 4(1):Paper No. S2R4, 2021.
  * [6] Alex Christensen, Pamela E. Harris, Zakiya Jones, Marissa Loving, Andrés Ramos Rodríguez, Joseph Rennie, and Gordon Rojas Kirby.  A generalization of parking functions allowing backward movement.  Electron. J. Comb., 27(1):research paper p1.33, 18, 2020.
  * [7] Emma Colaric, Ryan DeMuse, Jeremy L. Martin, and Mei Yin.  Interval parking functions.  Adv. Appl. Math., 123:102129, 2021.
  * [8] Laura Colmenarejo, Pamela E. Harris, Zakiya Jones, and Christo Keller.  Counting k-Naples parking functions through permutations and the k-Naples area statistic.  Enumer. Comb. Appl., 1(2):Paper No. S2R11, 2021.
  * [9] Robert Cori and Dominique Poulalhon.  Enumeration of (p,q)-parking functions.  Discrete Math., 256(3):609–623, 2002.  LaCIM 2000 Conference on Combinatorics, Computer Science and Applications.
  * [10] Robert Cori and Dominique Rossin.  On the sandpile group of dual graphs.  Eur. J. Comb., 21(4):447–459, 2000.
  * [11] Mark Dukes.  The sandpile model on the complete split graph, Motzkin words, and tiered parking functions.  J. Comb. Theory, Ser. A, 180:105418, 2021.
  * [12] Richard Ehrenborg and Alex Happ.  Parking cars of different sizes.  Am. Math. Mon., 123(10):1045–1048, 2016.
  * [13] Spencer Franks, Pamela E. Harris, Kimberly Harry, Jan Kretschmann, and Megan Vance.  Counting parking sequences and parking assortments through permutations.  Enumer. Comb. Appl., 4(1):Paper No. S2R2, 2021.
  * [14] Pamela E. Harris, Brian M. Kamau, J. Carlos Martínez Mori, and Roger Tian.  On the outcome map of MVP parking functions: permutations avoiding 321 and 3412, and Motzkin paths.  Enumer. Comb. Appl., 3(2):Paper No. S2R11, 16, 2023.
  * [15] Alan G. Konheim and Benjamin Weiss.  An occupancy discipline and applications.  SIAM J. Appl. Math., 14(6):1266–1274, 1966.
  * [16] Alexander Postnikov and Boris Shapiro.  Trees, parking functions, syzygies, and deformations of monomial ideals.  T. Am. Math. Soc., 356:3109–3142, 2004.
  * [17] Thomas Selig and Haoyue Zhu.  New combinatorial perspectives on MVP parking functions and their outcome map, 2023.
  * [18] Lauren Snider and Catherine Yan.  U-parking functions and (p,q)-parking functions.  Adv. Appl. Math., 134:102309, 2022.
  * [19] Lauren Snider and Catherine Yan.  ($\mathfrak{S}_{p}\times\mathfrak{S}_{q}$)-invariant graphical parking functions, 2023.
  * [20] Sam Spiro.  Subset parking functions.  J. Integer Seq., 22(7):article 19.7.3, 16, 2019.
  * [21] Richard P. Stanley.  Hyperplane arrangements, interval orders, and trees.  Proc. Natl. Acad. Sci. USA, 93(6):2620–2625, 1996.
  * [22] Richard P. Stanley and Jim Pitman.  A polytope related to empirical distributions, plane trees, parking functions, and the associahedron.  Discrete Comput. Geom., 27(4):603–634, 2002.
  * [23] The OEIS Foundation Inc.  The On-line Encyclopedia of Integer Sequences, 2023.
  * [24] Roger Tian.  Connecting $k$-Naples parking functions and obstructed parking functions via involutions.  Electron. J. Comb., 29(3):research paper p3.8, 24, 2022.
  * [25] Catherine H. Yan.  Parking Functions, chapter 13.  CRC Press, 2015.
  * [26] Mei Yin.  Parking functions, multi-shuffle, and asymptotic phenomena.  La Matematica, pages 1–25, 2023.