#  On the Structure of Permutation Invariant Parking

Douglas M. Chen  Department of Mathematics, Johns Hopkins University,
Baltimore, MD 21218<EMAIL_ADDRESS>
###### Abstract.

We continue the study of parking assortments, a generalization of parking
functions introduced by Chen, Harris, Martínez, Pabón-Cancel, and Sargent.
Given $n\in\mathbb{N}$ cars of lengths
$\mathbf{y}=(y_{1},y_{2},\dots,y_{n})\in\mathbb{N}^{n}$, our focuses are the
sets $\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$ and
$\mathsf{PA}^{\mathrm{inv},\uparrow}_{n}(\mathbf{y})$ of permutation invariant
(resp. nondecreasing) parking assortments for $\mathbf{y}$. For
$\mathbf{x}=(x_{1},x_{2},\dots,x_{n})\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$,
we introduce the _degree_ of $\mathbf{x}$, the number of non-$1$ entries of
$\mathbf{x}$, and the _characteristic_ $\chi(\mathbf{y})$ of $\mathbf{y}$, the
greatest degree across all
$\mathbf{z}\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$. We establish direct
necessary conditions for $\mathbf{y}$ with $\chi(\mathbf{y})=0$ and a simple
characterization for $\mathbf{y}$ with $\chi(\mathbf{y})=n-1$. In the process,
we derive a closed form for $\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$ and
an enumeration of $|\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})|$ using
properties of the Pitman-Stanley polytope, where $\chi(\mathbf{y})=n-1$. Next,
for any $\mathbf{y}\in\mathbb{N}^{n}$, we prove that
$\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$ is closed under the replacement
of any of its elements’ entries by a $1$, and given
$\mathbf{y}^{+}\in\mathbb{N}^{n+1}$, where $\mathbf{y}$ is the prefix of
$\mathbf{y}^{+}$, there is an embedding of
$\mathsf{PA}^{\mathrm{inv},\uparrow}_{n}(\mathbf{y})$ into
$\mathsf{PA}^{\mathrm{inv},\uparrow}_{n+1}(\mathbf{y}^{+})$. We apply these
results to study the degree as a function and the characteristic under
sequences of successive prefix length vectors. We then examine the _invariant
solution set_
$\mathcal{W}(\mathbf{y})\coloneqq\\{w\in\mathbb{N}:(1^{n-1},w)\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})\\}$.
We obtain tight upper bounds of $\mathcal{W}(\mathbf{y})$ and prove that for
any $n\in\mathbb{N}$, we have $|\mathcal{W}(\mathbf{y})|\leq 2^{n-1}$,
providing constraints on the subsequence sums of $\mathbf{y}$ for equality to
hold. Finally, we show that if
$\mathbf{x}\in\mathsf{PA}^{\mathrm{inv},\uparrow}_{n}(\mathbf{y})$, then
$\mathbf{x}\in\\{1\\}^{n-\chi(\mathbf{y})}\times\mathcal{W}(\mathbf{y})^{\chi(\mathbf{y})}$,
which implies a new upper bound on
$|\mathsf{PA}^{\mathrm{inv},\uparrow}_{n}(\mathbf{y})|$. Our results
generalize several theorems by Chen, Harris, Martínez, Pabón-Cancel, and
Sargent.

##  1\. Introduction

Parking assortments were introduced recently in [4] as a generalization of
parking functions, classic combinatorial objects that arose in the 1960s from
the study of hash functions and linear probing [11]. There are two well-known
equivalent definitions of parking functions. The first can be described via a
“parking experiment.”

######  Definition 1.1.

Consider a one-way street with $n\in\mathbb{N}\coloneqq\\{1,2,3,\dots\\}$
parking spots. There are $n\in\mathbb{N}$ cars of unit length waiting to enter
the street. For each $i\in[n]\coloneqq\\{1,2,\dots,n\\}$, car $i$ prefers a
spot $x_{i}\in[n]$ of the parking lot, so it drives up to $x_{i}$ and parks if
$x_{i}$ is unoccupied; otherwise, it parks in the next available spot (if it
exists). We say that $\mathbf{x}\coloneqq(x_{1},x_{2},\dots,x_{n})\in[n]^{n}$
is a _parking function of length $n$_ if every car can park following their
respective preference in $\mathbf{x}$.

The second is via a property of $(x_{(1)},x_{(2)},\dots,x_{(n)})$, which is
the nondecreasing rearrangement of the entries of $\mathbf{x}$.

######  Definition 1.2.

We say that $\mathbf{x}=(x_{1},x_{2},\dots,x_{n})\in[n]^{n}$ is a _parking
function of length $n$_ if $x_{(i)}\leq i$ for all $i\in[n]$.

Perhaps the most celebrated result concerning parking functions is the fact
that

$|\mathsf{PF}_{n}|=(n+1)^{n-1},$

where $\mathsf{PF}_{n}$ denotes the set of parking functions of length $n$
(cf. Lemma 1 in [11]). Such a count allows one to see that parking functions
are in bijection with several notable combinatorial objects including labeled
trees and the Shi hyperplane arrangement [14]. Explicitly constructing and
investigating these bijections reveals many illuminating combinatorial
properties of parking functions. As an example, the sequence

$(c_{1},c_{2},\dots,c_{n-1}),\quad\text{where}\quad
c_{i}\coloneqq(x_{i+1}-x_{i})\pmod{n+1}\quad\forall i\in[n-1],$

of successive differences modulo $n+1$ of an $\mathbf{x}\in\mathsf{PF}_{n}$
yields the Prüfer code of a unique labeled tree on $n+1$ vertices [14].
Moreover, let $\mathbf{u}=(u_{1},u_{2},\dots,u_{n})\in\mathbb{N}^{n}$ be
nondecreasing, and consider the _Pitman-Stanley polytope_

$\Pi_{n}(\mathbf{u})\coloneqq\left\\{(p_{1},p_{2},\dots,p_{n})\in\mathbb{R}_{\geq
0}^{n}:\sum_{i=1}^{j}p_{i}\leq\sum_{i=1}^{j}u_{i}\quad\forall
j\in[n]\right\\}.$

With $\mathbf{u}=(1,2,\dots,n)$, we have
$n!V_{n}(\mathbf{u})=|\mathsf{PF}_{n}|$, where $V_{n}(\mathbf{u})$ denotes the
$n$-dimensional volume of $\Pi_{n}(\mathbf{u})$. More generally,
$n!V_{n}(\mathbf{u})$ is the number of
$\mathbf{x}=(x_{1},x_{2},\dots,x_{n})\in\mathbb{N}^{n}$ such that $x_{(i)}\leq
u_{i}$ for all $i\in[n]$ (cf. Theorem 11 in [12]); such $\mathbf{x}$
generalize Definition 1.2 and are aptly known as _$\mathbf{u}$ -parking
functions of length $n$_. For a detailed treatment on the combinatorial theory
of parking functions, see Yan [14].

Given these connections and results, parking functions have been an active
research topic, appearing in a diverse array of contexts such as pattern
avoidance in permutations [8], convex geometry [1], polyhedral combinatorics
[3], partially ordered sets [6], impartial games [10], and of course, the
combinatorics of its variations and generalizations [5, 7].

Now, we define the combinatorial object of interest in this work: parking
assortments. This will involve a natural extension to the parking experiment
described in Definition 1.1.

######  Definition 1.3.

Consider a one-way street with $m\in\mathbb{N}$ parking spots. There are
$n\in\mathbb{N}$ cars waiting to enter the street, and they have lengths
$\mathbf{y}\coloneqq(y_{1},y_{2},\dots,y_{n})\in\mathbb{N}^{n}$, where
$m=\sum_{i=1}^{n}y_{i}$. For each $i\in[n]$, car $i$ (with length $y_{i}$)
prefers a spot $x_{i}\in[m]$ of the parking lot, so it drives up to $x_{i}$
and parks if spots $x_{i},x_{i}+1,\dots,x_{i}+y_{i}-1$ are unoccupied;
otherwise, it parks in the next $y_{i}$ contiguously available spots (if they
exist). We say that $\mathbf{x}\coloneqq(x_{1},x_{2},\dots,x_{n})\in[m]^{n}$
is a _parking assortment_ for $\mathbf{y}$ if every car can park following
their respective preference in $\mathbf{x}$.

######  Example 1.4.

See Figure 1, where $\mathbf{y}=(3,4,2)$ and $\mathbf{x}=(5,1,6)$. The parking
experiment proceeds as follows. First, car $1$, with length $3$ and preference
$5$, occupies spots $5$, $6$, and $7$. Then, car $2$, with length $4$ and
preference $1$, occupies spots $1$, $2$, $3$, and $4$ because they are all
still available. Lastly, car $3$, with length $2$ and preference $6$, occupies
spots $8$ and $9$ because spots $6$ and $7$ have been occupied (namely by car
$1$), and spots $8$ and $9$ are the next $2$ contiguously available spots.

Figure 1. If $\mathbf{y}=(3,4,2)$, then
$\mathbf{x}\in\mathsf{PA}_{3}(\mathbf{y})$.

Note that if $\mathbf{y}=(1^{n})\coloneqq(1,1,\dots,1)\in\mathbb{N}^{n}$, then
the set $\mathsf{PA}_{n}(\mathbf{y})$ of parking assortments for $\mathbf{y}$
is precisely $\mathsf{PF}_{n}$. From Definition 1.2, we see that this set has
the peculiar property that for any
$\mathbf{x}=(x_{1},x_{2},\dots,x_{n})\in\mathsf{PA}_{n}(\mathbf{y})$, any
permutation of its entries
$\mathbf{x}^{\prime}=(x_{\sigma(1)},x_{\sigma(2)},\dots,x_{\sigma(n)})$, where
$\sigma\in\mathfrak{S}_{n}$, is also in $\mathsf{PA}_{n}(\mathbf{y})$. This
permutation invariance of parking functions is a crucial property used to
study $\mathsf{PF}_{n}$ (cf. §1.1 in [14]). However, this is not true for
general $\mathbf{y}$; if $\mathbf{y}=(1,2,2)$, then
$\mathbf{x}=(1,1,2)\notin\mathsf{PA}^{\mathrm{inv}}_{3}(\mathbf{y})$ since
$(2,1,1)\notin\mathsf{PA}_{3}(\mathbf{y})$, as detailed in [4]. This motivates
the problem of determining what $\mathbf{x}\in\mathsf{PA}_{n}(\mathbf{y})$
have this property and hence the definition below.

######  Definition 1.5.

Let $\mathbf{y}\in\mathbb{N}^{n}$. We say
$\mathbf{x}\in\mathsf{PA}_{n}(\mathbf{y})$ is a _(permutation) invariant
parking assortment for_ $\mathbf{y}$ if any permutation of its entries is also
in $\mathsf{PA}_{n}(\mathbf{y})$.

In this work, we are interested in the set
$\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$ of invariant parking assortments
for $\mathbf{y}$. Alternatively, we may study the set
$\mathsf{PA}^{\mathrm{inv},\uparrow}_{n}(\mathbf{y})$ of nondecreasing
invariant parking assortments for $\mathbf{y}$, as it is equivalent to
$\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$ up to permutation.

######  Example 1.6.

Let $\mathbf{y}=(7,4,6)\in\mathbb{N}^{3}$. Then
$\mathsf{PA}^{\mathrm{inv},\uparrow}_{3}(\mathbf{y})=\\{(1^{3}),(1^{2},5)\\}$.
Indeed, $(1^{3})\in\mathsf{PA}_{3}(\mathbf{y})$, and
$(1^{2},5),(1,5,1),(5,1^{2})\in\mathsf{PA}_{3}(\mathbf{y})$; in other words,
all permutations of the entries of $(1^{3})$ and $(1^{2},5)$ are also parking
assortments, so
$\\{(1^{3}),(1^{2},5)\\}\subseteq\mathsf{PA}^{\mathrm{inv},\uparrow}_{3}(\mathbf{y})$.
One can also check that no other elements of $[7+4+6]^{3}=[17]^{3}$ have this
property, which yields the reverse inclusion.

Determining $\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$ is generally an
arduous task due to the problem of checking each of the elements of $[m]^{n}$
for invariance. The main motivator behind the notions introduced in this work
is to attempt to reduce this search space considerably.

A basic approach to narrowing the possibilities is to “decrease the exponent”
by noticing that by definition, parking assortments have at least one entry
that is equal to $1$; otherwise, parking spot $1$ is never occupied by any
car. This reduces the search space to a size of $m^{n-1}$. We can take this
idea a step further and specifically study the number of entries of invariant
parking assortments that are not equal to $1$, a fundamental property we will
refer to as their _degree_. Heuristically, one can expect that most of the
entries of an $\mathbf{x}\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$ are
$1$, and so many of the results presented here will concern and analyze the
maximum degree across all
$\mathbf{z}\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$, which we call the
_characteristic_ of $\mathbf{y}$. If there is a straightforward way to bound
the characteristic, then this can reduce our search space by more factors of
$m$.

######  Definition 1.7.

Let $\mathbf{y}\in\mathbb{N}^{n}$. For any
$\mathbf{x}=(x_{1},x_{2},\dots,x_{n})\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$,
the _degree_ of $\mathbf{x}$ is given by

$\deg\mathbf{x}\coloneqq|\\{i\in[n]:x_{i}\neq 1\\}|.$

Moreover, the _characteristic_ of $\mathbf{y}$ is given by

$\chi(\mathbf{y})\coloneqq\max_{\mathbf{z}\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})}\deg\mathbf{z}.$

As a special case, note that $\chi(\mathbf{y})=0$ is equivalent to
$\mathbf{y}$ being _minimally invariant_ , which is when
$\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})=\\{(1^{n})\\}$ [4]. Furthermore,
we always have $\chi(\mathbf{y})\in[n-1]_{0}\coloneqq[n-1]\cup\\{0\\}$.

In Section 2, we study $\mathbf{y}$ of minimal and maximal characteristic. We
first establish a direct necessary condition for $\mathbf{y}$ to have minimal
characteristic.

######  Theorem A.

Let $\mathbf{y}=(y_{1},y_{2},\dots,y_{n})\in\mathbb{N}^{n}$. If $\mathbf{y}$
is minimally invariant, then

$y_{1}<\min(y_{2},y_{3},\dots,y_{n})\quad\text{and}\quad
y_{2}\neq\sum_{j\in[n]\setminus\\{2\\}}y_{j}.$

Moreover, we work on decreasing the exponent by considering
$\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$ for $\mathbf{y}=(b,a^{n-1})$ and
$n\geq 2$. In particular, we obtain a simple necessary and sufficient
condition for $\mathbf{y}\in\mathbb{N}^{n}$ to have maximal characteristic,
which provides an easy way to reduce the search space by at least one more
factor of $m$, as we need only check for invariant parking assortments of
degree $n-1$ when this condition is satisfied.

######  Theorem B.

Let $\mathbf{y}=(y_{1},y_{2},\dots,y_{n})\in\mathbb{N}^{n}$. Then
$\chi(\mathbf{y})=n-1$ if and only if

$y_{1}\geq y_{2}\quad\text{and}\quad y_{2}=y_{3}=\cdots=y_{n}.$ (1)

Additionally, we obtain an explicit description of
$\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$ and corresponding enumerative
results. The enumerative formulas for C(b) are deduced via two results: an
enumerative result related to the theory of the Pitman-Stanley polytope and
empirical distributions [12] and a recursive formula for Catalan’s triangle
[2].

######  Theorem C.

Let $\mathbf{y}=(b,a^{n-1})\in\mathbb{N}^{n}$, where $n\geq 2$.

  1. (a)

If $a\mid b$ or $b>(n-1)a$, then
$\mathbf{x}\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$ if and only if

$x_{(i)}\in\\{1+(k-1)a:k\in[i]\\}\quad\forall i\in[n].$

Moreover,

$|\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})|=(n+1)^{n-1}\quad\text{and}\quad|\mathsf{PA}^{\mathrm{inv},\uparrow}_{n}(\mathbf{y})|=\frac{1}{n+1}\binom{2n}{n}.$

  2. (b)

Otherwise, if $a\nmid b$ and $b<(n-1)a$, then
$\mathbf{x}\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$ if and only if

$x_{(i)}\in\begin{cases}\\{1+(k-1)a:k\in[i]\\}&\forall
i\in\left[\left\lfloor\frac{b}{a}\right\rfloor+1\right]\\\
\left\\{1+(k-1)a:k\in\left[\left\lfloor\frac{b}{a}\right\rfloor+1\right]\right\\}&\text{otherwise}.\end{cases}$

Moreover,

$\displaystyle|\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})|$
$\displaystyle=\sum_{j=0}^{n-\left\lfloor
b/a\right\rfloor-1}(-1)^{j}\binom{n}{j}\left(n-\left\lfloor\frac{b}{a}\right\rfloor-1\right)^{j}(n-j+1)^{n-j-1}\quad\text{and}$
$\displaystyle|\mathsf{PA}^{\mathrm{inv},\uparrow}_{n}(\mathbf{y})|$
$\displaystyle=\frac{n-\left\lfloor
b/a\right\rfloor+1}{n+1}\binom{n+\left\lfloor b/a\right\rfloor}{\left\lfloor
b/a\right\rfloor}.$

In Section 3, we study the structure of
$\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$ for any
$\mathbf{y}\in\mathbb{N}^{n}$, which implies special properties of the degree
and characteristic. Namely, we prove that
$\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$ is closed under the operation of
replacing any of its elements’ entries with a $1$. We may use this property to
compute the image of the degree as a function, reveal an embedding property of
the set of invariant parking assortments, and obtain a bound for
$\chi(\mathbf{y}^{+})$ in terms of $\chi(\mathbf{y})$, where $\mathbf{y}$ is
the prefix of $\mathbf{y}^{+}\in\mathbb{N}^{n+1}$.

To state these results precisely, we need the following list operations: for
$\mathbf{v}=(v_{1},v_{2},\dots,v_{n})\in\mathbb{N}^{n}$, $k\in\mathbb{N}$, and
$i\in[n]$, let
$\mathbf{v}_{\widehat{i}}\coloneqq(v_{1},v_{2},\dots,v_{i-1},v_{i+1},\dots,v_{n})\in\mathbb{N}^{n-1}$,
$\mathbf{v}_{|_{i}}\coloneqq(v_{1},v_{2},\dots,v_{i})\in\mathbb{N}^{i}$, and
$(1^{k},\mathbf{v})\coloneqq(1^{k},v_{1},v_{2},\dots,v_{n})\in\mathbb{N}^{n+k}$.

The inspiration for Theorem D(a) is due to [9]; we present an independent
proof in Section 3.

######  Theorem D.

Let $\mathbf{y}=(y_{1},y_{2},\dots,y_{n})\in\mathbb{N}^{n}$ and
$\mathbf{y}^{+}=(\mathbf{y},y_{n+1})\in\mathbb{N}^{n+1}$.

  1. (a)

If $(1^{n-d},\mathbf{w})\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$, where
$\mathbf{w}\in\mathbb{N}^{d}_{>1}$, then
$(1^{n-d+1},\mathbf{w}_{\widehat{i}})\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$
for all $i\in[d]$.

  2. (b)

The image of $\deg:\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})\to[n-1]_{0}$ is
$[\chi(\mathbf{y})]_{0}$. In other words, for each
$d\in[\chi(\mathbf{y})]_{0}$, there exists
$\mathbf{x}\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$ with
$\deg\mathbf{x}=d$.

  3. (c)

If $\mathbf{x}\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$, then
$(1,\mathbf{x})\in\mathsf{PA}^{\mathrm{inv}}_{n+1}(\mathbf{y}^{+})$. In
particular, we have the embedding 111That is,
$\mathsf{PA}^{\mathrm{inv},\uparrow}_{n}(\mathbf{y})$ is included in
$\mathsf{PA}^{\mathrm{inv},\uparrow}_{n+1}(\mathbf{y}^{+})$ up to inserting a
$1$ at the start of each of its elements.

$\eta:\begin{cases}\mathsf{PA}^{\mathrm{inv},\uparrow}_{n}(\mathbf{y})&\hookrightarrow\mathsf{PA}^{\mathrm{inv},\uparrow}_{n+1}(\mathbf{y}^{+})\\\
\mathbf{x}&\mapsto(1,\mathbf{x}).\end{cases}$

  4. (d)

If $\chi(\mathbf{y})=\alpha$, then
$\chi(\mathbf{y}^{+})\in\\{\alpha,\alpha+1\\}$.

Note that applying Theorem D(d) repeatedly implies that if
$\chi(\mathbf{y}_{|_{k}})=\alpha$ for some $k<n$, then
$\chi(\mathbf{y})\in[\alpha,\alpha+n-k]$, which helps decrease the exponent,
as discussed previously. Moreover, the characteristic is monotonically
increasing with respect to sequences $\\{\mathbf{y}^{(j)}\\}_{j\in\mathbb{N}}$
of length vectors, where each $\mathbf{y}^{(j)}$ is the prefix of
$\mathbf{y}^{(j+1)}$.

On the flip side, Theorem D(b) implies that if the characteristic is known,
then for every $d\in[\chi(\mathbf{y})]_{0}$, each set
$\\{1\\}^{n-d}\times[m]^{d}$, which consists of candidates for
$\mathbf{x}\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$ with
$\deg\mathbf{x}=d$, indeed contains at least one such $\mathbf{x}$.
Consequently, we must check each degree in $[\chi(\mathbf{y})]_{0}$ to find
invariant parking assortments. Thus, we cannot take the approach of decreasing
the exponent further. This motivates the need to consider the analogous
approach of “decreasing the base,” where we eliminate elements of $[m]$ that
cannot be an entry of an invariant parking assortment for $\mathbf{y}$.
Intuitively, such elements are either too large or not compatible with partial
sums of the entries of $\mathbf{y}$. The former intuition is made precise in
Proposition 2.2 in [4]. The latter intuition is the basis for Section 4, where
we also sharpen the former intuition.

######  Theorem E.

Let $\mathbf{y}=(y_{1},y_{2},\dots,y_{n})\in\mathbb{N}^{n}$, and define
$\mathcal{W}(\mathbf{y})\coloneqq\\{w\in\mathbb{N}:(1^{n-1},w)\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})\\}$.

  1. (a)

If $\mathbf{y}$ is non-constant and $w\in\mathcal{W}(\mathbf{y})$, then
$w\leq\sum_{j=1}^{n-1}y_{j}$.

  2. (b)

We have

$\mathcal{W}(\mathbf{y})\subseteq\\{1+\mathbf{b}^{\top}\mathbf{y}:\mathbf{b}\in\\{0\\}\times\\{0,1\\}^{n-1}\\}\quad\text{and}\quad|\mathcal{W}(\mathbf{y})|\leq
2^{n-1}.$

  3. (c)

If

$y_{j}>\sum_{i=j+1}^{n}y_{i}\quad\forall j\in[n-1],$ (2)

then equality is achieved in (b). Moreover,

$|\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})|=2^{n-1}n-n+1\quad\text{and}\quad|\mathsf{PA}^{\mathrm{inv},\uparrow}_{n}(\mathbf{y})|=2^{n-1}.$

  4. (d)

If equality is achieved in (b), then

$y_{1}\geq y_{2}\quad\text{and}\quad y_{j}>\sum_{i=j+1}^{n}y_{i}\quad\forall
j\in[n-1]\setminus\\{1\\}.$ (3)

Lastly, we combine the approaches of decreasing the exponent and decreasing
the base to show the following inclusion and upper bound.

######  Theorem F.

Let $\mathbf{y}\in\mathbb{N}^{n}$. Then
$\mathsf{PA}^{\mathrm{inv},\uparrow}_{n}(\mathbf{y})\subseteq\\{1\\}^{n-\chi(\mathbf{y})}\times\mathcal{W}(\mathbf{y})^{\chi(\mathbf{y})}$.
In particular,

$|\mathsf{PA}^{\mathrm{inv},\uparrow}_{n}(\mathbf{y})|\leq\binom{2^{n-1}+n-2}{n-1}.$

We conclude in Section 5 with several open problems to spur future study.

##  2\. Length Vectors of Minimal and Maximal Characteristic

In this section, we study the inverse problem of determining
$\mathbf{y}\in\mathbb{N}^{n}$ of a given characteristic $\alpha$. Doing so can
still allow us to recover $\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$;
notably, this is immediate for $\alpha=0$, and it turns out that if
$\alpha=n-1$, then we can explicitly compute
$\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$. In §2.1, we obtain a direct
necessary condition for $\mathbf{y}$ to be of minimal characteristic, thereby
establishing Theorem A. In contrast, §2.2 proves a simple equivalent condition
for $\mathbf{y}$ to be of maximal characteristic and provides a closed form of
$\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$ for all such $\mathbf{y}$. By
establishing a bijection between certain $\mathbf{u}$-parking functions and
elements of $\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$, we utilize a result
of Pitman and Stanley to enumerate
$|\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})|$; we deduce a recursive formula
to enumerate $|\mathsf{PA}^{\mathrm{inv},\uparrow}_{n}(\mathbf{y})|$.
Altogether, §2.2 proves Theorems B and C.

###  2.1. Minimal Characteristic

Recall the following result for minimally invariant
$\mathbf{y}\in\mathbb{N}^{3}$.

######  Theorem 2.1 (Theorem 5.3 in [4]).

Let $\mathbf{y}=(y_{1},y_{2},y_{3})\in\mathbb{N}^{3}$. Then, $\mathbf{y}$ is
minimally invariant if and only if $y_{1}<\min(y_{2},y_{3})$ and $y_{2}\neq
y_{1}+y_{3}$.

Thus, one might ask whether this can be generalized for $n>3$. It turns out
that the natural extension of this result is necessary for all
$n\in\mathbb{N}$ but not sufficient. We will first prove the necessity, which
is Theorem A. The failure of the sufficiency will be easily established after
we prove Theorem D(a) in Section 3.

###### Proof of Theorem A.

We consider the contrapositive.

Assume first that $y_{1}\geq\min(y_{2},y_{3},\dots,y_{n})$. We claim
$(1^{n-1},1+\min\mathbf{y})\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$. As
$y_{1}\geq\min\mathbf{y}$, we have $1+\min\mathbf{y}\leq
1+\sum_{j=1}^{i}y_{j}$ for all $i\in[n-1]$, so
$(1^{i},1+\min\mathbf{y})\in\mathsf{PA}_{n}(\mathbf{y}_{|_{i+1}})$ by Lemma
3.1. It follows that
$(1^{i},1+\min\mathbf{y},1^{n-i-1})\in\mathsf{PA}_{n}(\mathbf{y})$. Indeed,
under its parking experiment, the last $n-i-1$ cars, all with preference $1$,
are forced to successively fill $[1+\sum_{j=1}^{i+1}y_{j},m]$, as the first
$i+1$ cars already occupy $[1,\sum_{j=1}^{i+1}y_{j}]$ since
$(1^{i},1+\min\mathbf{y})\in\mathsf{PA}_{n}(\mathbf{y}_{|_{i+1}})$. Lastly, to
show that $(1+\min\mathbf{y},1^{n-1})\in\mathsf{PA}_{n}(\mathbf{y})$, note
that under its parking experiment, the first car leaves $[1,\min\mathbf{y}]$
unoccupied, and these spots can only be filled by one car. The remaining cars,
all with preference $1$, either park starting at the first empty spot after
$[1,\min\mathbf{y}]$ (if its length exceeds $\min\mathbf{y}$) or fill
$[1,\min\mathbf{y}]$ (if its length is precisely $\min\mathbf{y}$ and no other
cars with length $\min\mathbf{y}$ have attempted to park). For the latter
possibility, there must exist a smallest index $j>1$ such that
$j=\operatorname*{arg\,min}\mathbf{y}$ by assumption. Thus,
$[1,\min\mathbf{y}]$ will be filled by car $j$, after which point $[1,s]$ is
occupied for some $s\in\mathbb{N}$, so cars $j+1,j+2,\dots,n$ will
successively fill $[s+1,m]$. Hence,
$(1^{n-1},1+\min\mathbf{y})\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$, as
needed.

Now, assume $y_{2}=\sum_{j\in[n]\setminus\\{2\\}}y_{j}$. We claim that
$\mathbf{x}=(1^{n-1},1+y_{2})\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$.
To see this, note first that
$(1+y_{2},1^{n-1})\in\mathsf{PA}_{n}(\mathbf{y})$, as under its parking
experiment, the first two cars will occupy $[1,y_{1}+y_{2}]$, and the
remaining cars all have preference $1$, so they will park successively in
$[1+y_{1}+y_{2},m]$. Moreover,
$(1,1+y_{2},1^{n-2})\in\mathsf{PA}_{n}(\mathbf{y})$ because under its parking
experiment, the first car parks in $[1,y_{1}]$, while the second car parks in
$[1+y_{2},2y_{2}]=[m-y_{2}+1,m]$ since $m=\sum_{i=1}^{n}y_{i}=2y_{2}$. Since
$\sum_{j=3}^{n}y_{j}=m-y_{1}-y_{2}=y_{2}-y_{1}$ and the remaining cars all
have preference $1$, they will park successively in $[1+y_{1},m-y_{2}]$.
Otherwise, let
$\mathbf{x}^{\prime}=(x_{1}^{\prime},x_{2}^{\prime},\dots,x_{n}^{\prime})$ be
a permutation of $\mathbf{x}$ such that $x_{j}^{\prime}=1+y_{2}$, where $j>2$,
and consider the parking experiment for $\mathbf{x}^{\prime}$. Cars
$1,2,\dots,j-1$ all have preference $1$, so they will occupy
$[1,\sum_{i=1}^{j-1}y_{i}]$, where $|[1,\sum_{i=1}^{j-1}y_{i}]|>y_{2}$. As car
$j$ has preference $1+y_{2}$, it will occupy
$[1+\sum_{i=1}^{j-1}y_{i},\sum_{i=1}^{j}y_{i}]$. Lastly, any remaining cars
again all have preference $1$, so they will park successively in
$[1+\sum_{i=1}^{j}y_{i},m]$. Hence,
$(1^{n-1},1+y_{2})\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$, as needed.

Therefore, if $y_{1}\geq\min(y_{2},y_{3},\dots,y_{n})$ or
$y_{2}=\sum_{j\in[n]\setminus\\{2\\}}y_{j}$, then $\chi(\mathbf{y})\geq 1$, as
desired. ∎

###  2.2. Maximal Characteristic

Recall the following theorem on $\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$
for constant $\mathbf{y}$.

######  Theorem 2.2 (Theorem 3.1 in [4]).

Let $\mathbf{y}=(a^{n})\in\mathbb{N}^{n}$ and
$\mathbf{x}=(x_{1},x_{2},\ldots,x_{n})\in[m]^{n}=[\sum_{i=1}^{n}y_{i}]^{n}$.
We have $\mathbf{x}\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$ if and only
if

$x_{(i)}\in\\{1+(k-1)a:k\in[i]\\}\quad\forall i\in[n].$ (4)

We now perturb $\mathbf{y}$ and study length vectors of the form
$(b,a^{n-1})$, where $a,b\in\mathbb{N}$ and $n\geq 2$. We will refer to such
$\mathbf{y}$ as “almost constant” (note that constant $\mathbf{y}$ also fall
into this classification).

As seen in the statement of Theorem C, it turns out that even when $a\neq b$,
under certain conditions, this perturbation of $\mathbf{y}$ does not affect
$\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$.

First, we prove two intermediate steps for the proof of the closed forms of
$\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$ as described in Theorem C. For
brevity, for parking spots $S,E\in\mathbb{N}$, let the interval
$[S,E]\coloneqq\\{S,S+1,\dots,E-1,E\\}$ denote the set of parking spots
numbered between $S$ and $E$, inclusive; define its length to be
$|[S,E]|\coloneqq|\\{S,S+1,\dots,E-1,E\\}|=E-S+1$.

######  Lemma 2.3.

Let $\mathbf{y}=(b,a^{n-1})\in\mathbb{N}^{n}$, where $n\geq 2$, and
$\mathbf{x}=(x_{1},x_{2},\dots,x_{n})\in[m]^{n}$. If
$\mathbf{x}\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$, then

$x_{i}\equiv 1\pmod{a}\quad\forall i\in[n].$

###### Proof.

We will prove the contrapositive. Assume that $x_{j}\not\equiv 1\pmod{a}$ for
some $j\in[n]$.

By Euclidean division, we may write $x_{j}=aq+r$, where
$q\in\mathbb{N}_{0}\coloneqq\mathbb{N}\cup\\{0\\}$, and $r\neq 1$ is a
remainder (i.e. $r\in[a-1]_{0}\setminus\\{1\\}$). Let
$\mathbf{x}^{\prime}=(x_{1}^{\prime},x_{2}^{\prime},\dots,x_{n}^{\prime})$ be
any permutation of $\mathbf{x}$ such that $x_{1}^{\prime}=x_{j}$. Under the
parking experiment for $\mathbf{x}^{\prime}$, the first car will occupy the
$b$ spots $[aq+r,aq+r+b-1]$, which leaves $[1,aq+r-1]$ empty. As $r\neq 1$,
$|[1,aq+r-1]|$ is not an integral multiple of $a$. In particular, none of the
remaining cars, which all have length $a$, can precisely fill $[1,aq+r-1]$.
Thus, we have $\mathbf{x}^{\prime}\notin\mathsf{PA}_{n}(\mathbf{y})$ and
$\mathbf{x}\notin\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$. ∎

######  Lemma 2.4.

Let $\mathbf{y}=(b,a^{n-1})\in\mathbb{N}^{n}$, where $n\geq 2$, and
$\mathbf{x}=(x_{1},x_{2},\dots,x_{n})\in[m]^{n}$. If
$\mathbf{x}\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$, then

$x_{(i)}\leq 1+(i-1)a\quad\forall i\in[n].$

###### Proof.

Again, we argue using the contrapositive. Assume that $x_{(j)}>1+(j-1)a$ for
some $j\in[n]$. Then $x_{(j)}=1+qa$ for some $q\in[n-1]$ by Lemma 2.3. Let
$\mathbf{x}^{\prime}=(x_{1}^{\prime},x_{2}^{\prime},\dots,x_{n}^{\prime})$ be
any permutation of $\mathbf{x}$ such that $x_{1}^{\prime}=x_{(j)}$. Under the
parking experiment for $\mathbf{x}^{\prime}$, since
$x_{1}^{\prime}=x_{(j)}\leq x_{(j+1)}\leq\cdots\leq x_{(n)}$, there are at
least $n-j+1$ cars, including the first car with length $b$, preferring to
park in $[1+qa,m]$. The total length of these cars is then at least
$b+(n-j)a$, so to ensure that they all can park, $|[1+qa,m]|\geq b+(n-j)a$
must hold. However,

$|[1+qa,m]|=|[1+qa,b+(n-1)a]|=b+(n-q-1)a<b+(n-j)a.$

Hence, $\mathbf{x}^{\prime}\notin\mathsf{PA}_{n}(\mathbf{y})$, so
$\mathbf{x}\notin\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$, as desired. ∎

We are now ready to prove the closed form of
$\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$.

######  Theorem 2.5.

Let $\mathbf{y}=(b,a^{n-1})\in\mathbb{N}^{n}$, where $n\geq 2$, and
$\mathbf{x}=(x_{1},x_{2},\ldots,x_{n})\in[m]^{n}$. If $a\mid b$, then
$\mathbf{x}\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$ if and only if

$x_{(i)}\in\\{1+(k-1)a:k\in[i]\\}\quad\forall i\in[n].$ (5)

###### Proof.

Let $\mathbf{x}\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$. Combining
Lemmas 2.3 and 2.4, it follows that $\mathbf{x}$ satisfies (5).

We now prove the converse. Assume that (5) holds. In other words, for all
$i\in[n]$, $x_{(i)}\leq 1+(i-1)a$ and $x_{i}=1+t_{i}a$ for some
$t_{i}\in[n-1]_{0}$. We will show inductively that parking succeeds under
$\mathbf{x}$.

Under the parking experiment for $\mathbf{x}$, the first car, with length
$b=ha$ and preference $x_{1}$, will park in spots $[x_{1},x_{1}+ha-1]$, where
$x_{1}=1+t_{1}a$ for some $t_{1}\in[n-1]_{0}$; that is,
$[1+t_{1}a,(t_{1}+h)a]$ is occupied by car 1. Next, the second car, with
length $a$ and preference $x_{2}$, will attempt to park in
$[x_{2},x_{2}+a-1]$, where $x_{2}=1+t_{2}a$ for some $t_{2}\in[n-1]_{0}$. Note
that (5) stipulates that at most one entry of $\mathbf{x}$ can be $1+(n-1)a$,
so if $t_{1}=n-1$, then $t_{2}<t_{1}$, so that car 2 successfully parks in
$[x_{2},x_{2}+a-1]=[1+t_{2}a,(t_{2}+1)a]$. Now, assume $t_{1}<n-1$. If
$t_{1}+h\leq n-1$, then we have

$t_{2}\in[t_{1}-1]_{0}\cup\\{t_{1}+h,t_{1}+h+1,\dots,n-1\\}\quad\text{or}\quad
t_{2}\in\\{t_{1},t_{1}+1,\dots,t_{1}+h-1\\}.$

In the former, car 2 successfully parks in
$[x_{2},x_{2}+a-1]=[1+t_{2}a,(t_{2}+1)a]$. In the latter, car 2 fails to park
in $[x_{2},x_{2}+a-1]=[1+t_{2}a,(t_{2}+1)a]$ since car 1 occupies
$[1+t_{1}a,(t_{1}+h)a]\supseteq[1+t_{2}a,(t_{2}+1)a]$. Thus, car 2 must park
in $[1+(t_{1}+h)a,(t_{1}+h+1)a]$. If $t_{1}+h>n-1$, then we have

$t_{2}\in[t_{1}-1]_{0}\quad\text{or}\quad
t_{2}\in\\{t_{1},t_{1}+1,\dots,n-1\\}.$

In the former, car 2 successfully parks in
$[x_{2},x_{2}+a-1]=[1+t_{2}a,(t_{2}+1)a]$. In the latter, car 2 again fails to
park in $[x_{2},x_{2}+a-1]$ for the same reason, so it must park in
$[1+(t_{1}+h)a,(t_{1}+h+1)a]$. This proves that car $2$ will occupy
$[S_{2},S_{2}+a-1]$, where $S_{2}\equiv 1\pmod{a}$, which will serve as our
base case.

Assume now that the first $k\in[n-1]$ cars are parked, and each car $j$, where
$j\in[k]\setminus\\{1\\}$, occupies $[S_{j},S_{j}+a-1]$ for some $S_{j}\equiv
1\pmod{a}$. Moreover, for $S_{1}=1+t_{1}a$, car 1 occupies
$[S_{1},S_{1}+ha-1]$. Thus, all the terms of the sequence
$(S_{1},S_{2},\dots,S_{k})\in\mathbb{N}^{k}$ are distinct, so that its
nondecreasing rearrangement $(S_{(1)},S_{(2)},\dots,S_{(k)})$ is strictly
increasing. Now, for any $j\in[k]$, define

$\ell(j)\coloneqq\begin{cases}ha&\text{if }S_{(j)}=S_{1}\\\
a&\text{otherwise}.\end{cases}$

Then at this stage of the parking experiment, the set of unoccupied parking
spots is

$\mathcal{U}\coloneqq[m]\setminus\bigcup_{j=1}^{k}[S_{(j)},S_{(j)}+\ell(j)-1]=\bigcup_{j=0}^{k}\mathcal{U}_{j},\quad\text{where}\quad\mathcal{U}_{j}\coloneqq\begin{cases}[1,S_{(1)}-1]&\text{if
}j=0\\\ [S_{(j)}+\ell(j),S_{(j+1)}-1]&\text{if }j\in[k-1]\\\
[S_{(k)}+\ell(k),m]&\text{if }j=k.\end{cases}$ (6)

We note that the $\mathcal{U}_{j}$ are pairwise disjoint and possibly empty,
and there should be a total of $(n+h-1)a-(h+k-1)a=(n-k)a$ unoccupied spots, so
that $|\mathcal{U}|\coloneqq\sum_{j=0}^{k}|\mathcal{U}_{j}|=(n-k)a$. In
particular, as the inductive hypothesis gives $S_{(j)}\equiv 1\pmod{a}$, (6)
implies that any $\mathcal{U}_{j}$ has a left endpoint congruent to
$1\pmod{a}$, and $|\mathcal{U}_{j}|$ is an integral multiple of $a$.

We now show that the $(k+1)$th car can park. If $x_{k+1}=1$, then (6) implies
that car $k+1$ can find some interval of $a$ unoccupied spots to park in. If
$x_{k+1}=1+t_{k+1}a$ for some $t_{k+1}\in[n-1]$, then we have the following
three distinct possibilities.

######  Case 2.5.1.

$t_{1}=n-1$ and $x_{k+1}=1+t_{k+1}a<1+t_{1}a$.

###### Proof.

Here, the first car occupies $[1+(n-1)a,(n+h-1)a]$. If spot $1+t_{k+1}a$ is
empty, then car $k+1$ will park in
$\mathcal{P}\coloneqq[1+t_{k+1}a,(t_{k+1}+1)a]$ by (6). Otherwise, we claim
that car $k+1$ must be able to find and park in an interval of $a$ unoccupied
spots in $\mathcal{A}\coloneqq[1+(t_{k+1}+1)a,(n-1)a]$.

Figure 2.  Illustration of Case 2.5.1. Car 1 takes the last $b$ spots in blue.
Next, car $k+1$ either parks according to its preference in the red, or it
must be able to find an alternative spot in the green, which is located
between the red and blue regions.

Assume the contrary, so that $\mathcal{A}$ is completely occupied. Let

$S_{\text{max}}=\max\\{s\in[m]:s\text{ is unoccupied when car $k+1$ attempts
to park}\\}.$ (7)

Since $S_{\text{max}}$ is the right endpoint of an interval of unoccupied
spots, by (6), $S_{\text{max}}=ta$ for some $t\in[t_{k+1}]$. Then
$[1+S_{\text{max}},(n+h-1)a]$, where
$|[1+S_{\text{max}},(n+h-1)a]|=(n+h-t-1)a$, is occupied by $n-t$ cars, one of
which is car 1 (with length $ha$) and $n-t-1$ of which are cars with length
$a$. Moreover, by assumption,
$[1+S_{\text{max}},(n+h-1)a]\supseteq\mathcal{P}$. Thus, including car $k+1$,
at least $n-t+1$ cars have preference at least $1+S_{\text{max}}$ since
$S_{\text{max}}$ is unoccupied. In other words, at most $t-1$ cars have
preference strictly less than $1+S_{\text{max}}$, forcing $x_{(t)}\geq
1+S_{\text{max}}=1+ta$. This contradicts $x_{(t)}\leq 1+(t-1)a$. ∎

######  Case 2.5.2.

$t_{1}\neq n-1$ and $x_{k+1}=1+t_{k+1}a<1+t_{1}a$.

###### Proof.

Now, the first car no longer occupies spot $m$. Note again by (6) that if spot
$1+t_{k+1}a$ is empty, then car $k+1$ will park in
$\mathcal{P}\coloneqq[1+t_{k+1}a,(t_{k+1}+1)a]$. Otherwise, car $k+1$ searches
for an interval of $a$ unoccupied spots in
$\mathcal{A}_{1}\coloneqq[1+(t_{k+1}+1)a,t_{1}a]$. If it finds one, then it
will occupy it. If it does not, then we claim that it must be able to find and
park in such an interval in $\mathcal{A}_{2}\coloneqq[1+(h+t_{1})a,(n+h-1)a]$.

Figure 3.  Illustration of Case 2.5.2. Car 1 takes the $b$ spots in blue.
Next, car $k+1$ either parks according to its preference in the red, or it
must be able to find an alternative spot in one of the green regions, which
surround car 1.

Assume the contrary, so that $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$ are
completely occupied. Let $S_{\text{max}}$ be as in (7), so that again,
$S_{\text{max}}=ta$ for some $t\in[t_{k+1}]$. Repeating the argument for Case
2.5.1 allows us to arrive at the same contradiction.

∎

######  Case 2.5.3.

$x_{k+1}=1+t_{k+1}a\geq 1+t_{1}a$.

###### Proof.

Note first that $t_{1}<n-1$ due to (5). Here, we claim that car $k+1$ will
find and park in an interval of $a$ unoccupied spots in
$\mathcal{I}\coloneqq[1+(h+t_{1})a,(n+h-1)a]$.

Figure 4.  Illustration of Case 2.5.3. Car 1 takes the $b$ spots in blue.
Next, car $k+1$ will find parking in the yellow, which is located to the right
of car 1.

Assume now that car $k+1$ cannot find such an interval, and let
$S_{\text{max}}$ be as in (7).

Note that we may take $h+t_{1}<n-1$. Otherwise, $h+t_{1}\geq n-1$, and since
car 1 occupies $[1+t_{1}a,(h+t_{1})a]$, any car with preference at least
$1+t_{1}a$ is forced to park in an interval of $a$ unoccupied spots in
$\mathcal{I}$. Then our assumption implies that $\mathcal{I}$ is completely
occupied when car $k+1$ attempts to park, so that $S_{\text{max}}=ta$ for some
$t\in[t_{k+1}]$. Repeating the argument for Case 2.5.1 then completes the
proof. For similar reasons, we may assume $S_{\text{max}}\geq 1+(h+t_{1})a$.

Given these additional assumptions, we have

$S_{\text{max}}=ta\quad\text{for some}\quad
t\in\\{h+t_{1}+1,h+t_{1}+2,\dots,t_{k+1}\\}.$

Thus, $[1+S_{\text{max}},(n+h-1)a]$, where
$|[1+S_{\text{max}},(n+h-1)a]|=(n+h-t-1)a$, is occupied by $n+h-t-1$ cars, all
of which must have length $a$ since $S_{\text{max}}\geq 1+(h+t_{1})a$. Thus,
including car $k+1$, at least $n+h-t$ cars have preference at least
$1+S_{\text{max}}$ since $S_{\text{max}}$ is unoccupied, so at most $t-h$ cars
have preference strictly less than $1+S_{\text{max}}$. Thus, $x_{(t-h+1)}\geq
1+S_{\text{max}}=1+ta$. Since $h$ is a positive integer, this contradicts
$x_{(t-h+1)}\leq 1+(t-h)a$. ∎

This covers all cases and completes the induction. Hence,
$\mathbf{x}\in\mathsf{PA}_{n}(\mathbf{y})$. Note that (5) does not depend on
how the entries of $\mathbf{x}$ are permuted, so parking succeeds under any
permutation of $\mathbf{x}$. Therefore, if $\mathbf{x}$ satisfies (5), then
$\mathbf{x}\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$, concluding the
proof. ∎

######  Theorem 2.6.

Let $\mathbf{y}=(b,a^{n-1})\in\mathbb{N}^{n}$, where $n\geq 2$, and
$\mathbf{x}=(x_{1},x_{2},\ldots,x_{n})\in[m]^{n}$. If $b>(n-1)a$, then
$\mathbf{x}\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$ if and only if

$x_{(i)}\in\\{1+(k-1)a:k\in[i]\\}\quad\forall i\in[n].$ (8)

###### Proof.

Let $\mathbf{x}\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$. Lemmas 2.3 and
2.4 again show that $\mathbf{x}$ satisfies (8).

We now prove the converse. Assume that (8) holds. In other words, for all
$i\in[n]$, $x_{(i)}\leq 1+(i-1)a$ and $x_{i}=1+t_{i}a$ for some
$t_{i}\in[n-1]_{0}$. We will show inductively that parking succeeds under
$\mathbf{x}$.

Under the parking experiment for $\mathbf{x}$, the first car, with length $b$
and preference $x_{1}$, will park in $[x_{1},x_{1}+b-1]$, where
$x_{1}=1+t_{1}a$ for some $t_{1}\in[n-1]_{0}$. Thus, $[1+t_{1}a,b+t_{1}a]$ is
now occupied. Next, the second car, with length $a$ and preference $x_{2}$,
will attempt to park in $[x_{2},x_{2}+a-1]$, where $x_{2}=1+t_{2}a$ for some
$t_{2}\in[n-1]_{0}$. Due to (8), if $t_{1}=n-1$, then $t_{2}<t_{1}$, so that
car $2$ successfully parks in $[x_{2},x_{2}+a-1]=[1+t_{2}a,(t_{2}+1)a]$. If
$t_{1}<n-1$, then we have

$t_{2}\in[t_{1}-1]_{0}\quad\text{or}\quad
t_{2}\in\\{t_{1},t_{1}+1,\dots,n-1\\}.$

In the former, car 2 successfully parks in
$[x_{2},x_{2}+a-1]=[1+t_{2}a,(t_{2}+1)a]$. In the latter, car 2 fails to park
in $[x_{2},x_{2}+a-1]=[1+t_{2}a,(t_{2}+1)a]$ since car 1 occupies
$[1+t_{1}a,b+t_{1}a]$, where $b+t_{1}a>(n+t_{1}-1)a\geq(n-1)a$, so
$b+t_{1}a\geq 1+(n-1)a$ and $b+t_{1}a\geq 1+t_{2}a$. Thus, car 2 must park in
$[1+b+t_{1}a,b+(t_{1}+1)a]$. This proves that car 2 will occupy
$[S_{2},S_{2}+a-1]$, where

$S_{2}\equiv\begin{cases}1\pmod{a}&\text{if }S_{2}<1+t_{1}a\\\
1+b\pmod{a}&\text{if }S_{2}>b+t_{1}a,\end{cases}$

which will serve as our base case.

Assume now that the first $k\in[n-1]$ cars are parked, and each car $j$, where
$j\in[k]\setminus\\{1\\}$, occupies $[S_{j},S_{j}+a-1]$ for some

$S_{j}\equiv\begin{cases}1\pmod{a}&\text{if }S_{j}<1+t_{1}a\\\
1+b\pmod{a}&\text{if }S_{j}>b+t_{1}a.\end{cases}$

In other words, $S_{j}\equiv 1\pmod{a}$ if it is located to the left of
$[1+t_{1}a,b+t_{1}a]$ (where car 1 is parked), and $S_{j}\equiv 1+b\pmod{a}$
otherwise. Moreover, for $S_{1}=1+t_{1}a$, car 1 occupies $[S_{1},S_{1}+b-1]$.
Now, for any $j\in[k]$, define

$\ell(j)\coloneqq\begin{cases}b&\text{if $S_{(j)}=S_{1}$}\\\
a&\text{otherwise}.\end{cases}$ (9)

At this stage of the parking experiment, the set of unoccupied spots is again
$\bigcup_{j=0}^{k}\mathcal{U}_{j}$, where the $\mathcal{U}_{j}$ are defined as
in (6) with $\ell(j)$ as in (9). Furthermore, from (6), any $\mathcal{U}_{j}$
has a left endpoint congruent to either $1\pmod{a}$ or $1+b\pmod{a}$ (when
$\mathcal{U}_{j}$ is located to the left and right, respectively, of where car
1 is parked), and $|\mathcal{U}_{j}|$ is an integral multiple of $a$.

We now show that the $(k+1)$th car can park. If $x_{k+1}=1$, then (6) implies
that car $k+1$ can find some interval of $a$ unoccupied spots to park in. If
$x_{k+1}=1+t_{k+1}a$ for $t_{k+1}\in[n-1]$, then we have the following three
distinct possibilities.

######  Case 2.6.1.

$t_{1}=n-1$ and $x_{k+1}=1+t_{k+1}a<1+t_{1}a$.

###### Proof.

Here, the first car occupies $[1+(n-1)a,b+(n-1)a]$. If spot $1+t_{k+1}a$ is
empty, then car $k+1$ will park in $[1+t_{k+1}a,(t_{k+1}+1)a]$ by (6).
Otherwise, we claim that car $k+1$ must be able to find and park in an
interval of $a$ unoccupied spots in $[1+(t_{k+1}+1)a,(n-1)a]$. Assume not, so
that $[1+(t_{k+1}+1)a,(n-1)a]$ is completely occupied. Define $S_{\text{max}}$
as in (7). Since $S_{\text{max}}$ is the right endpoint of an interval of
unoccupied spots located to the left of where car 1 is parked, by (6),
$S_{\text{max}}=ta$ for some $t\in[t_{k+1}]$. Then
$[1+S_{\text{max}},b+(n-1)a]$, where
$|[1+S_{\text{max}},b+(n-1)a]|=(n-t-1)a+b$, are occupied by $n-t$ cars, one of
which is car 1 (with length $b$) and $n-t-1$ of which are cars with length
$a$. Thus, including car $k+1$, at least $n-t+1$ cars have preference at least
$1+S_{\text{max}}$. Hence, at most $t-1$ cars have preference strictly less
than $1+S_{\text{max}}$, forcing $x_{(t)}\geq 1+S_{\text{max}}=1+ta$, which
contradicts $x_{(t)}\leq 1+(t-1)a$. ∎

######  Case 2.6.2.

$t_{1}\neq n-1$ and $x_{k+1}=1+t_{k+1}a<1+t_{1}a$.

###### Proof.

Note again that (6) implies that if spot $1+t_{k+1}a$ is empty, then car $k+1$
will park in $[1+t_{k+1}a,(t_{k+1}+1)a]$. Otherwise, car $k+1$ searches for an
interval of $a$ unoccupied spots in $[1+(t_{k+1}+1)a,t_{1}a]$. If it finds
one, then it will occupy it. If it does not, then we claim that it must be
able to find and park in such an interval in $[1+b+t_{1}a,b+(n-1)a]$. Assume
not, so that both $[1+(t_{k+1}+1)a,t_{1}a]$ and $[1+b+t_{1}a,b+(n-1)a]$ are
completely occupied. Let $S_{\text{max}}$ be as in (7), so that by (6) again,
$S_{\text{max}}=ta$ for some $t\in[t_{k+1}]$. Repeating the argument for Case
2.6.1 yields the same contradiction. ∎

######  Case 2.6.3.

$x_{k+1}=1+t_{k+1}a\geq 1+t_{1}a$.

###### Proof.

Here, we claim that car $k+1$ will be able to find and park in an interval of
$a$ unoccupied spots in $[1+b+t_{1}a,b+(n-1)a]$. Assume not, and let
$S_{\text{max}}$ be as in (7). Note that $b+t_{1}a\geq 1+(n-1)a$, so any car
with preference at least $1+t_{1}a$ is forced to park in an interval of $a$
unoccupied spots in $[1+b+t_{1}a,b+(n-1)a]$. Then our assumption implies that
$[1+b+t_{1}a,b+(n-1)a]$ is completely occupied when car $k+1$ attempts to
park, so that $S_{\text{max}}=ta$ for some $t\in[t_{k+1}]$. Repeating the
argument for Case 2.6.1 yields another contradiction. ∎

This covers all cases and completes the induction, so
$\mathbf{x}\in\mathsf{PA}_{n}(\mathbf{y})$. Again, (8) is preserved under any
permutation of $\mathbf{x}$. Therefore, if $\mathbf{x}$ satisfies (8), then
$\mathbf{x}\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$, concluding the
proof. ∎

From Theorems 2.5 and 2.6, we see that the conditions (4), (5), and (8) are
identical, and hence the equality
$\mathsf{PA}^{\mathrm{inv}}_{n}((a^{n}))=\mathsf{PA}^{\mathrm{inv}}_{n}((b,a^{n-1}))$
holds whenever $a\mid b$ or $b>(n-1)a$.

It remains to study the possibility of $b\nmid a$ and $b<(n-1)a$. For this
case, we will see that the order statistic bounds provided by Lemma 2.4 are
not strong enough to guarantee that
$\mathbf{x}\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$. Thus, sharpening
some of these bounds is needed to obtain such a result.

######  Theorem 2.7.

Let $\mathbf{y}=(b,a^{n-1})\in\mathbb{N}^{n}$, where $n\geq 2$, and
$\mathbf{x}=(x_{1},x_{2},\ldots,x_{n})\in[m]^{n}$. If $a\nmid b$ and
$b<(n-1)a$, then $\mathbf{x}\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$ if
and only if

$x_{(i)}\in\begin{cases}\\{1+(k-1)a:k\in[i]\\}&\forall
i\in\left[\left\lfloor\frac{b}{a}\right\rfloor+1\right]\\\
\left\\{1+(k-1)a:k\in\left[\left\lfloor\frac{b}{a}\right\rfloor+1\right]\right\\}&\text{otherwise}.\end{cases}$
(10)

###### Proof.

First, assume that $\mathbf{x}$ does not satisfy (10). That is, there exists
$j\in[n]$ for which at least one of the following is true:

$\displaystyle x_{(j)}$ $\displaystyle\not\equiv 1\pmod{a}$ $\displaystyle
x_{(j)}$ $\displaystyle>1+(j-1)a\text{ if
}j\leq\left\lfloor\frac{b}{a}\right\rfloor+1$ $\displaystyle x_{(j)}$
$\displaystyle>1+\left\lfloor\frac{b}{a}\right\rfloor a\text{ if
}j>\left\lfloor\frac{b}{a}\right\rfloor+1.$

Lemma 2.3 allows us to assume that any entry of $\mathbf{x}$ is congruent to
$1\pmod{a}$. Similarly, Lemma 2.4 allows us to assume that $x_{(j)}\leq
1+(j-1)a$ if $j\leq\left\lfloor\frac{b}{a}\right\rfloor+1$.

If $x_{(j)}>1+\left\lfloor\frac{b}{a}\right\rfloor a$, where
$j>\left\lfloor\frac{b}{a}\right\rfloor+1$, then write $x_{(j)}=1+qa$, where
$q\geq\left\lfloor\frac{b}{a}\right\rfloor+1$. Let
$\mathbf{x}^{\prime}=(x_{1}^{\prime},x_{2}^{\prime},\dots,x_{n}^{\prime})$ be
any permutation of $\mathbf{x}$ such that $x_{1}^{\prime}=x_{(1)}$ and
$x_{2}^{\prime}=x_{(j)}$. Under the parking experiment for
$\mathbf{x}^{\prime}$, the first car will occupy the $b$ spots $[1,b]$, and
the second car will occupy the $a$ spots
$[x_{(j)},x_{(j)}+a-1]=[1+qa,(q+1)a]$. This leaves the $qa-b$ spots $[b+1,qa]$
empty. Note that as $a\nmid b$, we have
$\frac{b}{a}-1<\left\lfloor\frac{b}{a}\right\rfloor<\frac{b}{a}$, so

$qa-b\geq\left(\left\lfloor\frac{b}{a}\right\rfloor+1\right)a-b>\frac{ab}{a}-b=0;$

thus, $[b+1,qa]\neq\emptyset$. Similarly,
$\left\lfloor\frac{b}{a}\right\rfloor<\frac{b}{a}<\left\lfloor\frac{b}{a}\right\rfloor+1$,
which yields

$\left(q-\left\lfloor\frac{b}{a}\right\rfloor-1\right)a<qa-b<\left(q-\left\lfloor\frac{b}{a}\right\rfloor\right)a,$

so $qa-b$ is strictly bounded between consecutive multiples of $a$. Hence,
none of the remaining cars, which all have length $a$, can fill $[b+1,qa]$.
Thus, we have $\mathbf{x}^{\prime}\in\mathsf{PA}_{n}(\mathbf{y})$ and
$\mathbf{x}\notin\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$.

Thus, if $\mathbf{x}\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$, then
$\mathbf{x}$ satisfies (10).

We now prove the converse. Assume that (10) holds. In other words, for all
$i\in\left[\left\lfloor\frac{b}{a}\right\rfloor+1\right]$, $x_{(i)}\leq
1+(i-1)a$, for all $\left\lfloor\frac{b}{a}\right\rfloor+1<i\leq n$,
$x_{(i)}\leq 1+\left\lfloor\frac{b}{a}\right\rfloor a$, and $x_{i}=1+t_{i}a$
for some $t_{i}\in\left[\left\lfloor\frac{b}{a}\right\rfloor\right]_{0}$. We
will show inductively that parking succeeds under $\mathbf{x}$.

Under the parking experiment for $\mathbf{x}$, the first car, with length $b$
and preference $x_{1}$, will park in $[x_{1},x_{1}+b-1]$, where
$x_{1}=1+t_{1}a$ for some
$t_{1}\in\left[\left\lfloor\frac{b}{a}\right\rfloor\right]_{0}$. Then, the
second car, with length $a$ and preference $x_{2}$, will attempt to park in
$[x_{2},x_{2}+a-1]$, where $x_{2}=1+t_{2}a$ for some
$t_{2}\in\left[\left\lfloor\frac{b}{a}\right\rfloor\right]_{0}$. We have

$t_{2}\in[t_{1}-1]_{0}\quad\text{or}\quad
t_{2}\in\left\\{t_{1},t_{1}+1,\dots,\left\lfloor\frac{b}{a}\right\rfloor\right\\}.$

In the former, car 2 successfully parks in
$[x_{2},x_{2}+a-1]=[1+t_{2}a,(t_{2}+1)a]$. In the latter, car 2 fails to park
in $[x_{2},x_{2}+a-1]=[1+t_{2}a,(t_{2}+1)a]$ since car 1 occupies
$[1+t_{1}a,b+t_{1}a]$, where $b+t_{1}a\geq
b>\left\lfloor\frac{b}{a}\right\rfloor a$, so $b+t_{1}a\geq
1+\left\lfloor\frac{b}{a}\right\rfloor a$ and $b+t_{1}a\geq 1+t_{2}a$. Thus,
car 2 must park in $[1+b+t_{1}a,b+(t_{1}+1)a]$. This proves that car 2 will
occupy $[S_{2},S_{2}+a-1]$, where

$S_{2}\equiv\begin{cases}1\pmod{a}&\text{if }S_{2}<1+t_{1}a\\\
1+b\pmod{a}&\text{if }S_{2}>b+t_{1}a,\end{cases}$

which will serve as our base case. Assume now that the first $k\in[n-1]$ cars
are parked, and each car $j$, where $j\in[k]\setminus\\{1\\}$, occupies
$[S_{j},S_{j}+a-1]$ for some

$S_{j}\equiv\begin{cases}1\pmod{a}&\text{if }S_{j}<1+t_{1}a\\\
1+b\pmod{a}&\text{if }S_{j}>b+t_{1}a.\end{cases}$

Moreover, for $S_{1}=1+t_{1}a$, car 1 occupies $[S_{1},S_{1}+b-1]$. At this
stage of the parking experiment, the set of unoccupied spots is again
$\bigcup_{j=0}^{k}\mathcal{U}_{j}$, where the $\mathcal{U}_{j}$ are defined as
in (6) with $\ell(j)$ as in (9). Furthermore, from (6), any $\mathcal{U}_{j}$
has a left endpoint congruent to either $1\pmod{a}$ or $1+b\pmod{a}$, and
$|\mathcal{U}_{j}|$ is an integral multiple of $a$.

We now show that the $(k+1)$th car can park. If $x_{k+1}=1$, then (6) implies
that car $k+1$ can find some interval of $a$ unoccupied spots to park in. If
$x_{k+1}=1+t_{k+1}a$ for $t_{k+1}\geq 1$, then we have the following two
distinct possibilities.

######  Case 2.7.1.

$x_{k+1}=1+t_{k+1}a<1+t_{1}a$.

###### Proof.

Note first that car 1 cannot occupy $[1+(n-1)a,b+(n-1)a]$ since $x_{1}\leq
1+\left\lfloor\frac{b}{a}\right\rfloor a<1+(n-1)a$. In particular, as
$\left\lfloor\frac{b}{a}\right\rfloor\leq n-2$, we have
$|[x_{1}+b,b+(n-1)a]|=(n-1)a-\left\lfloor\frac{b}{a}\right\rfloor a\geq a$; in
other words, the first car will park at least $a$ spots away from the end of
the parking lot.

Now, note that if spot $1+t_{k+1}a$ is empty, then car $k+1$ will park in
$[1+t_{k+1}a,(t_{k+1}+1)a]$ by (6). Otherwise, it searches for an interval of
$a$ unoccupied spots in $[1+(t_{k+1}+1)a,t_{1}a]$. If it finds one, then it
will occupy it. If it does not, then we claim it must be able to find and park
in such an interval in $[1+t_{1}a+b,b+(n-1)a]$.

Assume not, so that all of these spots are occupied. Let $S_{\text{max}}$ be
as in (7). Since it is the right endpoint of an interval of unoccupied spots
located to the left of where car 1 is parked, by (6), $S_{\text{max}}=ta$ for
some $t\in[t_{k+1}]$. Repeating the argument for Case 2.6.1 yields the same
contradiction. ∎

######  Case 2.7.2.

$x_{k+1}=1+t_{k+1}a\geq 1+t_{1}a$.

###### Proof.

Here, we claim that car $k+1$ will be able to find and park in an interval of
$a$ unoccupied spots in $[1+t_{k+1}a,b+(n-1)a]$. Assume not, and let
$S_{\text{max}}$ be as in (7). Since it is the right endpoint of an interval
of unoccupied spots located to the right of where car 1 is parked, by (6),
$S_{\text{max}}=ta+b$ for some $t_{1}<t<t_{k+1}$. We have

$\left(t+\left\lfloor\frac{b}{a}\right\rfloor\right)a<S_{\text{max}}=ta+b<\left(t+\left\lfloor\frac{b}{a}\right\rfloor+1\right)a.$

Thus, as $S_{\text{max}}$ is unoccupied, there are cars that have preference
at least
$1+\left(t+\left\lfloor\frac{b}{a}\right\rfloor+1\right)a>S_{\text{max}}$. But
by (10), no car can have preference greater than
$1+\left\lfloor\frac{b}{a}\right\rfloor a$, and
$1+\left(t+\left\lfloor\frac{b}{a}\right\rfloor+1\right)a>1+\left\lfloor\frac{b}{a}\right\rfloor
a$, so we have a contradiction. ∎

This covers all cases and completes the induction, so
$\mathbf{x}\in\mathsf{PA}_{n}(\mathbf{y})$. Again, (10) is preserved under any
permutation of $\mathbf{x}$. Therefore, if $\mathbf{x}$ satisfies (10), then
$\mathbf{x}\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$, concluding the
proof. ∎

Theorems 2.5, 2.6, and 2.7 illustrate that for almost constant $\mathbf{y}$,
$\chi(\mathbf{y})$ is maximal when $y_{1}\geq y_{2}$ and minimal otherwise. We
now prove a surprising partial converse: the almost constant condition on
length vectors is necessary for their characteristic to be maximal. Recall the
following results.

######  Lemma 2.8 (Lemma 2.3 in [4]).

Let $\mathbf{y}\in\mathbb{N}^{n}$ and
$\mathbf{x}=(x_{1},x_{2},\dots,x_{n})\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$.
If $k=\operatorname*{arg\,max}_{i\in[n]}x_{i}$, then
$\mathbf{x}_{\widehat{k}}\in\mathsf{PA}^{\mathrm{inv}}_{n-1}(\mathbf{y}_{|_{n-1}})$.
In particular, if $\chi(\mathbf{y})=\alpha$, then
$\chi(\mathbf{y}_{|_{n-1}})\geq\alpha-1$.

######  Lemma 2.9 (Theorem 5.1 in [4]).

Let $\mathbf{y}=(y_{1},y_{2})\in\mathbb{N}^{2}$. Then $\chi(\mathbf{y})=1$ if
and only if $y_{1}\geq y_{2}$.

######  Lemma 2.10 (Theorem 5.4 in [4]).

Let $\mathbf{y}=(y_{1},y_{2},y_{3})\in\mathbb{N}^{3}$. If
$\chi(\mathbf{y})=2$, then $y_{2}=y_{3}$.

Now, we will present the partial converse, which implies one direction of
Theorem B. Its proof will be via induction on $n$, so the above results will
be instrumental in setting up the base cases and proving the inductive step.

######  Theorem 2.11.

Let $\mathbf{y}=(y_{1},y_{2},\dots,y_{n})\in\mathbb{N}^{n}$, where $n\geq 2$.
If $\chi(\mathbf{y})=n-1$, then

$y_{2}=y_{3}=\cdots=y_{n}.$

###### Proof.

We will proceed via induction on $n$. Note that $\chi(\mathbf{y})=n-1$ implies
that there exists $\mathbf{w}\in\mathbb{N}_{>1}^{n-1}$ such that
$(1,\mathbf{w})\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$. For $n=2$, if
$(1,w)\in\mathsf{PA}^{\mathrm{inv}}_{2}(\mathbf{y})$, where $w>1$, then the
conclusion follows vacuously by Lemma 2.9. For $n=3$, the conclusion follows
by Lemma 2.10.

Thus, we have verified the base cases, so assume that the statement is true up
to some $n=k\geq 3$. That is, for any $\mathbf{y}\in\mathbb{N}^{k}$ such that
$\chi(\mathbf{y})=k-1$, we have $y_{2}=y_{3}=\cdots=y_{k}$. We now show that
this is true for $n=k+1$. Let
$\mathbf{y}^{\prime}=(y_{1}^{\prime},y_{2}^{\prime},\dots,y_{k+1}^{\prime})\in\mathbb{N}^{k+1}$
such that $\chi(\mathbf{y}^{\prime})=k$. Then there exists
$\mathbf{x}=(1,\mathbf{w}^{\prime})\in\mathsf{PA}^{\mathrm{inv}}_{k+1}(\mathbf{y}^{\prime})$,
where $\mathbf{w}^{\prime}\in\mathbb{N}_{>1}^{k}$. Assume without loss of
generality that $\mathbf{w}^{\prime}$ is nondecreasing. As
$w^{\prime}_{k}=\max\mathbf{x}$, by Lemma 2.8, we have
$(1,\mathbf{w}^{\prime}_{|{k-1}})\in\mathsf{PA}^{\mathrm{inv}}_{k}(\mathbf{y}^{\prime}_{|_{k}})$.
Thus, $\chi(\mathbf{y}^{\prime}_{|_{k}})\leq k-1$, and we have equality since
$k-1$ is the maximal characteristic. Hence, by the inductive hypothesis,
$\mathbf{y}^{\prime}_{|_{k}}$ is of the form $(b,a^{k-1})\in\mathbb{N}^{k}$,
which shows that $y^{\prime}_{2}=y^{\prime}_{3}=\cdots=y^{\prime}_{k}$.
Consequently, $\mathbf{y}^{\prime}$ is of the form $(b,a^{k-1},c)$ for some
$c\in\mathbb{N}$, and it remains to show that $c=a$.

To do this, we prove the contrapositive: if $c\neq a$, then
$\mathbf{x}=(1,\mathbf{w}^{\prime})\not\in\mathsf{PA}^{\mathrm{inv}}_{k+1}(\mathbf{y}^{\prime})$.
We claim that parking fails for the permutation
$\mathbf{x}^{\prime}=(\mathbf{w}^{\prime},1)$. This can be rewritten as

$\mathbf{x}^{\prime}=(w^{\prime}_{1},w^{\prime}_{2},\dots,w^{\prime}_{k-1},w^{\prime}_{k},1)=(\mathbf{w}^{\prime}_{|_{k-1}},w^{\prime}_{k},1).$

Since
$(1,\mathbf{w}^{\prime}_{|{k-1}})\in\mathsf{PA}^{\mathrm{inv}}_{k}(\mathbf{y}^{\prime}_{|_{k}})$,
we have
$(\mathbf{w}^{\prime}_{|_{k-1}},1)\in\mathsf{PA}_{k}(\mathbf{y}^{\prime}_{|_{k}})$.
Thus, consider the parking experiment for $(\mathbf{w}^{\prime}_{|_{k-1}},1)$
with length vector $\mathbf{y}^{\prime}_{|_{k}}$. As all cars park
successfully and $\mathbf{w}^{\prime}\in\mathbb{N}_{>1}^{k}$, car $k$, with
preference $1$, must occupy $[1,a]$, while the remaining cars completely
occupy $[1+a,m-c]$. This means that in the parking experiment for
$\mathbf{x}^{\prime}=(\mathbf{w}^{\prime}_{|_{k-1}},w^{\prime}_{k},1)$ (with
length vector $\mathbf{y}^{\prime}$), the first $k-1$ cars will completely
occupy $[1+a,m-c]$, so they leave $[1,a]$ and $[m-c+1,m]$ unoccupied. By
assumption, $w^{\prime}_{k}=\max\mathbf{x}^{\prime}>1$, so car $k$, with
length $a$, must occupy a subset of $[m-c+1,m]$ (otherwise, parking fails, and
the proof is complete).

We now consider the following two distinct cases.

######  Case 2.11.1.

$\mathbf{y}^{\prime}=(b,a^{k-1},c)$ with $a<c$.

###### Proof.

Here, car $k$ will take $a$ spots in $[m-c+1,m]$; thus, $c-a$ spots in this
interval are still left unoccupied. Then, car $k+1$, with preference $1$ and
length $c>a$, cannot park in $[1,a]$, and $c-a<c$, so it cannot park in
$[m-c+1,m]$ either. Hence, parking fails. ∎

######  Case 2.11.2.

$\mathbf{y}^{\prime}=(b,a^{k-1},c)$ with $a>c$.

###### Proof.

Here, car $k$, with length $a>c$, cannot park in $[m-c+1,m]$, so parking
fails. ∎

Therefore, $c=a$, and $\mathbf{y}^{\prime}=(b,a^{k})$, so
$y_{1}^{\prime}=y_{2}^{\prime}=\cdots=y_{k+1}^{\prime}$, completing the
induction. ∎

######  Remark 2.12.

The contrapositive proof strategy displayed above in the inductive step can be
used to provide an alternate proof of Lemma 2.10. Thus, Theorem 2.11 can be
proven without the use of Theorem 5.4 in [4]; it can then be utilized to
provide a quicker proof of that theorem since we have a necessary condition
for the characteristic to be maximal.

Putting everything together, we arrive at Theorem B.

###### Proof of Theorem B.

If (1) holds, then $\chi(\mathbf{y})=n-1$ by Theorems 2.5, 2.6, and 2.7. If
$\chi(\mathbf{y})=n-1$, then Theorem 2.11 yields $y_{2}=y_{3}=\cdots=y_{n}$.
Given this, Theorems 2.5, 2.6, and 2.7 imply $y_{1}\geq y_{2}$, as desired. ∎

To conclude this section, we present the enumerative results on
$|\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})|$ and
$|\mathsf{PA}^{\mathrm{inv},\uparrow}_{n}(\mathbf{y})|$ when $\mathbf{y}$ is
almost constant. For constant $\mathbf{y}$, recall the following.

######  Theorem 2.13 (Corollary 3.3 and Corollary 3.4 in [4]).

Let $\mathbf{y}=(a^{n})\in\mathbb{N}^{n}$. Then

$|\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})|=(n+1)^{n-1}\quad\text{and}\quad|\mathsf{PA}^{\mathrm{inv},\uparrow}_{n}(\mathbf{y})|=C_{n},$

where $C_{n}=\frac{1}{n+1}\binom{2n}{n}$ is the $n$th Catalan number 222OEIS
A000108..

As discussed, the exact same is true for certain almost constant $\mathbf{y}$.

######  Corollary 2.14.

Let $\mathbf{y}=(b,a^{n-1})\in\mathbb{N}^{n}$, where $n\geq 2$. If $a\mid b$
or $b>(n-1)a$, then

$|\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})|=(n+1)^{n-1}\quad\text{and}\quad|\mathsf{PA}^{\mathrm{inv},\uparrow}_{n}(\mathbf{y})|=C_{n}.$

###### Proof.

By Theorems 2.2, 2.5, and 2.6, we have
$\mathsf{PA}^{\mathrm{inv}}_{n}((b,a^{n-1}))=\mathsf{PA}^{\mathrm{inv}}_{n}((a^{n}))$.
Thus, the result follows by Theorem 2.13. ∎

We now readily obtain a proof of Theorem C(a).

###### Proof of Theorem C(a).

This is Theorems 2.5 and 2.6 and Corollary 2.14. ∎

To prove the next corollary, we will appeal to the following classical
counting lemma due to Pitman and Stanley [12]. For a nondecreasing
$\mathbf{u}=(u_{1},u_{2},\dots,u_{n})\in\mathbb{N}^{n}$ with successive
differences
$\Delta(\mathbf{u})\coloneqq(u_{1},u_{2}-u_{1},\dots,u_{n}-u_{n-1})\in\mathbb{N}_{0}^{n}$,
let $\mathsf{PF}_{n}(\mathbf{u})$ denote the set of $\mathbf{u}$-parking
functions of length $n$, and let
$\mathsf{PF}^{\uparrow}_{n}(\mathbf{u})\subseteq\mathsf{PF}_{n}(\mathbf{u})$
denote its subset of nondecreasing elements.

######  Lemma 2.15 ((8) in [12]).

Let $\mathbf{u}=(u_{1},u_{2},\dots,u_{n})\in\mathbb{N}^{n}$ be nondecreasing
and $k\in[n-1]$. Assume that $\Delta(\mathbf{u})=(a,b^{n-k-1},c,0^{k-1})$.
Then

$|\mathsf{PF}_{n}(\mathbf{u})|=a\sum_{j=0}^{k}\binom{n}{j}(c-(k+1-j)b)^{j}(a+(n-j)b)^{n-j-1}.$

Lemma 2.15 arose from the study of empirical distributions and order
statistics. It was generalized by Yan in [13] via two combinatorial proofs:
one involved a strategic decomposition of a $\mathbf{u}$-parking function into
subsequences, and the other was a recursive argument.

Armed with this result, we proceed to present and prove the second set of
counting results.

######  Corollary 2.16.

Let $\mathbf{y}=(b,a^{n-1})\in\mathbb{N}^{n}$, where $n\geq 2$. If $a\nmid b$
and $b<(n-1)a$, then

$|\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})|=\sum_{j=0}^{n-\left\lfloor
b/a\right\rfloor-1}(-1)^{j}\binom{n}{j}\left(n-\left\lfloor\frac{b}{a}\right\rfloor-j\right)^{j}(n-j+1)^{n-j-1}$

and

$|\mathsf{PA}^{\mathrm{inv},\uparrow}_{n}(\mathbf{y})|=\displaystyle\frac{n-\left\lfloor
b/a\right\rfloor+1}{n+1}\binom{n+\left\lfloor b/a\right\rfloor}{\left\lfloor
b/a\right\rfloor}.$

###### Proof.

Let
$\mathbf{x}=(x_{1},x_{2},\dots,x_{n})\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$.
We first compute $|\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})|$. The main
claim is the following, which states that, for an appropriate choice of
$\mathbf{u}$, such (resp. nondecreasing) invariant parking assortments are
(resp. nondecreasing) $\mathbf{u}$-parking functions up to scaling.

######  Claim 2.16.1.

Let
$\mathbf{u}=\left(1,2,\dots,\left\lfloor\frac{b}{a}\right\rfloor,\left(\left\lfloor\frac{b}{a}\right\rfloor+1\right)^{n-\left\lfloor
b/a\right\rfloor}\right)$. Then $\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$
and $\mathsf{PF}_{n}(\mathbf{u})$ are in bijection, and
$\mathsf{PA}^{\mathrm{inv},\uparrow}_{n}(\mathbf{y})$ and
$\mathsf{PF}^{\uparrow}_{n}(\mathbf{u})$ are in bijection.

###### Proof.

We construct a bijection between the sets in question. Define
$\varphi:\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})\to\mathsf{PF}_{n}(\mathbf{u})$
by

$\varphi(\mathbf{x})=\left(1+\frac{x_{1}-1}{a},1+\frac{x_{2}-1}{a},\dots,1+\frac{x_{n}-1}{a}\right)\coloneqq(\varphi(\mathbf{x})_{1},\varphi(\mathbf{x})_{2},\dots,\varphi(\mathbf{x})_{n}).$

By Theorem 2.7, $x_{(i)}\leq 1+(i-1)a$ for all
$i\in\left[\left\lfloor\frac{b}{a}\right\rfloor+1\right]$, so
$\varphi(\mathbf{x})_{(i)}\leq i$ for all
$i\in\left[\left\lfloor\frac{b}{a}\right\rfloor+1\right]$. For the same
reason, $x_{(i)}\leq 1+\left\lfloor\frac{b}{a}\right\rfloor a$ for all
$i\in\left\\{\left\lfloor\frac{b}{a}\right\rfloor+1,\left\lfloor\frac{b}{a}\right\rfloor+2,\dots,n\right\\}$,
so $\varphi(\mathbf{x})_{(i)}\leq\left\lfloor\frac{b}{a}\right\rfloor+1$ for
all
$i\in\left\\{\left\lfloor\frac{b}{a}\right\rfloor+1,\left\lfloor\frac{b}{a}\right\rfloor+2,\dots,n\right\\}$.
Hence, $\varphi(\mathbf{x})\in\mathsf{PF}_{n}(\mathbf{u})$. Furthermore, for
all $i\in[n]$, we have $x_{i}\equiv 1\pmod{a}$, so
$\frac{x_{i}-1}{a}\in\mathbb{Z}$ for all $i\in[n]$, which implies that
$\varphi(\mathbf{x})_{i}\in\mathbb{Z}$. Putting everything together, since
$1\leq x_{i}\leq 1+(n-1)a$, we have $1\leq\varphi(\mathbf{x})_{i}\leq n$, so
$\varphi(\mathbf{x})\in\mathsf{PF}_{n}(\mathbf{u})$.

We now construct the inverse of $\varphi$ to show that it is a bijection.
Given $\mathbf{p}=(p_{1},p_{2},\dots,p_{n})\in\mathsf{PF}_{n}(\mathbf{u})$,
define
$\psi:\mathsf{PF}_{n}(\mathbf{u})\to\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$
by

$\psi(\mathbf{p})=(1+(p_{1}-1)a,1+(p_{2}-1)a,\dots,1+(p_{n}-1)a)\coloneqq\\{\psi(\mathbf{p})_{1},\psi(\mathbf{p})_{2},\dots,\psi(\mathbf{p})_{n}\\}.$

Since $p_{(i)}\leq i$ for all
$i\in\left[\left\lfloor\frac{b}{a}\right\rfloor+1\right]$, we have
$\psi(\mathbf{x})_{(i)}\in\\{1,1+a,\dots,1+(i-1)a\\}$ for all
$i\in\left[\left\lfloor\frac{b}{a}\right\rfloor+1\right]$, and as
$p_{(i)}\leq\left\lfloor\frac{b}{a}\right\rfloor+1$ for all
$i\in\left\\{\left\lfloor\frac{b}{a}\right\rfloor+1,\left\lfloor\frac{b}{a}\right\rfloor+2,\dots,n\right\\}$,
we have
$\psi(\mathbf{x})_{(i)}\in\left\\{1,1+a,\dots,1+\left\lfloor\frac{b}{a}\right\rfloor
a\right\\}$ for all
$i\in\left\\{\left\lfloor\frac{b}{a}\right\rfloor+1,\left\lfloor\frac{b}{a}\right\rfloor+2,\dots,n\right\\}$.
Thus, $\psi(\mathbf{p})\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$ by
Theorem 2.7. Note that $\psi\circ\varphi(\mathbf{x})=\mathbf{x}$ and
$\varphi\circ\psi(\mathbf{p})=\mathbf{p}$, so we indeed have
$\varphi^{-1}=\psi$.

Lastly, we show that
$\varphi:\mathsf{PA}^{\mathrm{inv},\uparrow}_{n}(\mathbf{y})\to\mathsf{PF}^{\uparrow}_{n}(\mathbf{u})$
is also a bijection. It suffices to prove that $\varphi$ and $\psi$ map
nondecreasing elements to nondecreasing elements. Note that if
$\mathbf{x}=(x_{1},x_{2},\dots,x_{n})\in\mathsf{PA}^{\mathrm{inv},\uparrow}_{n}(\mathbf{y})$,
then for all $i,j\in[n]$ with $i\leq j$, $x_{i}\leq x_{j}$ implies
$1+\frac{x_{i}-1}{a}\leq 1+\frac{x_{j}-1}{a}$ since $a>0$, so
$\varphi(\mathbf{x})\in\mathsf{PF}^{\uparrow}_{n}(\mathbf{u})$. Similarly, if
$\mathbf{p}=(p_{1},p_{2},\dots,p_{n})\in\mathsf{PF}^{\uparrow}_{n}(\mathbf{u})$,
then for all $i,j\in[n]$ with $i\leq j$, $p_{i}\leq p_{j}$ implies
$1+(p_{i}-1)a\leq 1+(p_{j}-1)a$ since $a>0$, so
$\psi(\mathbf{p})\in\mathsf{PA}^{\mathrm{inv},\uparrow}_{n}(\mathbf{y})$. ∎

Claim 2.16.1 establishes that it suffices to compute
$|\mathsf{PF}_{n}(\mathbf{u})|$. To do so, we compute
$\Delta(\mathbf{u})=(1^{\left\lfloor b/a\right\rfloor+1},0^{n-\left\lfloor
b/a\right\rfloor-1})=(1,1^{\left\lfloor b/a\right\rfloor},0,0^{n-\left\lfloor
b/a\right\rfloor-2})$. The result then follows by Lemma 2.15.

Now, we turn our attention to computing
$|\mathsf{PA}^{\mathrm{inv},\uparrow}_{n}(\mathbf{y})|$. For
$n,k\in\mathbb{N}_{0}$ such that $n\geq k$, let

$f(n,k)\coloneqq|\mathsf{PF}^{\uparrow}_{n}((1,2,\dots,k,(k+1)^{n-k}))|.$

By Claim 2.16.1,
$|\mathsf{PA}^{\mathrm{inv},\uparrow}_{n}(\mathbf{y})|=f\left(n,\left\lfloor\frac{b}{a}\right\rfloor\right)$,
where $n>\left\lfloor\frac{b}{a}\right\rfloor+1$, so it suffices to compute
$f(n,k)$. To do so, we will make use of the following recursion.

######  Claim 2.16.2.

We have $f(n,0)=1$ for all $n\in\mathbb{N}_{0}$, $f(n,1)=n$ and
$f(n+1,n+1)=f(n+1,n)$ for all $n\in\mathbb{N}$, and
$f(n+1,k)=f(n+1,k-1)+f(n,k)$ for all $n,k\in\mathbb{N}$ such that $1<k<n+1$.

###### Proof.

We have $f(n,0)=|\mathsf{PF}^{\uparrow}_{n}((1^{n}))|=|\\{(1^{n})\\}|=1$ by
definition 333for $n=0$, the empty tuple is the unique element in this set,
but this will be immaterial for our purposes..

Similarly,
$\mathsf{PF}^{\uparrow}_{n}((1,2^{n-1}))=\\{(1^{j},2^{n-j}):j\in[n]\\}$
because if
$\mathbf{p}=(p_{1},p_{2},\dots,p_{n})\in\mathsf{PF}^{\uparrow}_{n}((1,2^{n-1}))$,
then there exists $j=\max\\{i\in[n]:p_{i}=1\\}$, and for
$i\in[n]\setminus[j]$, we must have $p_{i}=2$, showing that
$\mathbf{p}=(1^{j},2^{n-j})$; the reverse inclusion is immediate. Thus,
$f(n,1)=|\mathsf{PF}^{\uparrow}_{n}((1,2^{n-1}))|=n$. Moreover,
$f(n+1,n+1)=f(n+1,n)$ since

$(1,2,\dots,n+1,((n+1)+1)^{(n+1)-(n+1)})=(1,2,\dots,n+1)=(1,2,\dots,n,(n+1)^{(n+1)-n}).$

Now, for $n,k\in\mathbb{N}$ such that $1<k<n+1$, let
$\mathbf{v}=(1,2,\dots,k,(k+1)^{n+1-k})$, so that
$f(n+1,k)=|\mathsf{PF}^{\uparrow}_{n+1}(\mathbf{v})|$, and let
$\mathbf{v}^{\prime}=(1,2,\dots,k-1,k^{n-k+2})$. Notice that

$\mathsf{PF}^{\uparrow}_{n+1}(\mathbf{v})=\mathsf{PF}^{\uparrow}_{n+1}(\mathbf{v}^{\prime})\cup\\{\mathbf{p}=(p_{1},p_{2},\dots,p_{n+1})\in\mathsf{PF}^{\uparrow}_{n+1}(\mathbf{v}):p_{n+1}=k+1\\}.$

It is immediate that the above is a disjoint union since if
$\mathbf{p}=(p_{1},p_{2},\dots,p_{n+1})\in\mathsf{PF}^{\uparrow}_{n+1}(\mathbf{v}^{\prime})$,
then $p_{n+1}\leq k$. Next, let
$\mathbf{p}=(p_{1},p_{2},\dots,p_{n+1})\in\mathsf{PF}^{\uparrow}_{n+1}(\mathbf{v})$.
If $p_{n+1}<k+1$, then $\max\mathbf{p}\leq k$, so it must satisfy $p_{i}\leq
i$ for all $i\in[k]$, and $p_{i}\leq k$ otherwise, meaning
$\mathbf{p}\in\mathsf{PF}^{\uparrow}_{n+1}(\mathbf{v}^{\prime})$. The reverse
inclusion follows by definition. Therefore,

$\displaystyle f(n+1,k)$
$\displaystyle=|\mathsf{PF}^{\uparrow}_{n+1}(\mathbf{v})|$
$\displaystyle=|\mathsf{PF}^{\uparrow}_{n+1}(\mathbf{v}^{\prime})|+|\\{\mathbf{p}=(p_{1},p_{2},\dots,p_{n+1})\in\mathsf{PF}^{\uparrow}_{n+1}(\mathbf{v}):p_{n+1}=k+1\\}|$
$\displaystyle=|\mathsf{PF}^{\uparrow}_{n+1}(\mathbf{v}^{\prime})|+|\\{\mathbf{p}\in\mathsf{PF}^{\uparrow}_{n}(\mathbf{v^{\prime\prime}}):\mathbf{v}^{\prime\prime}=(1,2,\dots,k,(k+1)^{n-k})\\}|$
$\displaystyle=f(n+1,k-1)+f(n,k).$

∎

Claim 2.16.2 establishes that $f(n,k)$ satisfies the same recurrence as
Catalan’s triangle 444OEIS A009766., which has closed form
$\frac{n-k+1}{n+1}\binom{n+k}{k}$ (cf. Lemma 1 and Theorem in [2]). Therefore,
the result follows by setting $k=\left\lfloor\frac{b}{a}\right\rfloor$. ∎

######  Remark 2.17.

For $\left\lfloor\frac{b}{a}\right\rfloor=0,1,2$, one can show using Corollary
2.16 that we have
$|\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})|=1,2^{n}-1,3^{n}-2^{n}-n$,
respectively. As detailed by Yan in [13], closed forms of the sum in Lemma
2.15 do not exist for general $n$. However, one fact worth noting is that when
$\left\lfloor\frac{b}{a}\right\rfloor=2$, it turns out that
$|\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})|$ is also the number of regions
in the $G$-Shi arrangement when $G$ is the cycle graph with $n$ vertices
555OEIS A355645.

To finish, we may now easily prove the rest of Theorem C.

###### Proof of Theorem C(b).

This is Theorem 2.7 and Corollary 2.16. ∎

##  3\. Properties of $\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$ in Relation
to the Degree and Characteristic

Given the intricacies of the set $\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$
for $\mathbf{y}$ of maximal characteristic, our aim in this section is to
study the structure of the set given any $\mathbf{y}$. As we will see,
deriving certain structural results can allow us to recover general
information about the degree and characteristic; this will comprise Theorem D.

Throughout this section, the following result will be helpful.

######  Lemma 3.1 (Proposition 2.2 in [4]).

Let $\mathbf{y}=(y_{1},y_{2},\ldots,y_{n})\in\mathbb{N}^{n}$. Assume
$\mathbf{x}=(x_{1},x_{2},\ldots,x_{n})\in[m]^{n}$ is nondecreasing. Then,
$\mathbf{x}\in\mathsf{PA}_{n}(\mathbf{y})$ if and only if $x_{i}\leq
1+\sum_{j=1}^{i-1}y_{j}$ for all $i\in[n]$.

For proof of Theorem D specifically, the three lemmas below will be crucial
ingredients; Lemma 3.3 is due to [9], and we provide an independent proof. In
particular, Lemma 3.4 will allow us to morph an invariant parking assortment
into a more convenient parking assortment, which yields a useful technique to
help prove Theorem D(a).

######  Lemma 3.2.

Let $\mathbf{y}=(y_{1},y_{2},\dots,y_{n})\in\mathbb{N}^{n}$ and
$\mathbf{y}^{+}=(\mathbf{y},y_{n+1})\in\mathbb{N}^{n}$. If
$\mathbf{x}\in\mathsf{PA}_{n}(\mathbf{y})$, then
$\mathbf{x}^{+}=(\mathbf{x},x_{n+1})\in\mathsf{PA}_{n+1}(\mathbf{y}^{+})$ if
and only if $x_{n+1}\leq 1+\sum_{j=1}^{n}y_{j}$.

###### Proof.

Consider the parking experiment under $\mathbf{x}^{+}$. Because
$\mathbf{x}\in\mathsf{PA}_{n}(\mathbf{y})$, the first $n$ cars occupy
$[1,\sum_{j=1}^{n}y_{j}]$. This leaves only spots
$[1+\sum_{j=1}^{n}y_{j},\sum_{j=1}^{n+1}y_{j}]$ empty. If
$x_{n+1}>1+\sum_{j=1}^{n}y_{j}$, then the last car, with length $y_{n+1}$,
must park in $[x_{n+1},\sum_{j=1}^{n+1}y_{j}]$, but
$|[x_{n+1},\sum_{j=1}^{n+1}y_{j}]|<y_{n+1}$, so parking fails. If $x_{n+1}\leq
1+\sum_{j=1}^{n}y_{j}$, then since $[1,\sum_{j=1}^{n}y_{j}]$ is occupied, the
last car occupies $[1+\sum_{j=1}^{n}y_{j},\sum_{j=1}^{n+1}y_{j}]$, so parking
succeeds. ∎

######  Lemma 3.3.

Let $\mathbf{y}=(y_{1},y_{2},\dots,y_{n})\in\mathbb{N}^{n}$. Then if
$\mathbf{x}=(x_{1},x_{2},\dots,x_{n})\in\mathsf{PA}_{n}(\mathbf{y})$, and
there exists $i\in[n]$ such that $x_{i}=\min(x_{i},x_{i+1},\dots,x_{n})$, then
$\mathbf{r}=(x_{1},\dots,x_{i-1},r,x_{i+1},\dots,x_{n})\in\mathsf{PA}_{n}(\mathbf{y})$
for any $r\in[x_{i}]$. In particular,
$(\mathbf{x}_{|_{n-1}},1)\in\mathsf{PA}_{n}(\mathbf{y})$.

###### Proof.

Consider the parking experiment under $\mathbf{x}$. The key observation is
that $[1,x_{i}-1]$ is occupied when car $i$ attempts to park. To see this,
assume the contrary; i.e. there exists an $s\in[1,x_{i}-1]$ that is
unoccupied. Then because $x_{i}=\min(x_{i},x_{i+1},\dots,x_{n})$, cars
$i,i+1,\dots,n$ all drive past $s$, leaving $s$ unoccupied after all cars have
parked, contradicting $\mathbf{x}\in\mathsf{PA}_{n}(\mathbf{y})$.

Thus, if car $i$ instead had preference less than $x_{i}$ (and all other
preferences are unchanged), then since $[1,x_{i}-1]$ is occupied, its choice
of parking spots remains the same, implying that all cars can still park.
Therefore, $\mathbf{r}\in\mathsf{PA}_{n}(\mathbf{y})$. ∎

######  Lemma 3.4.

Let $\mathbf{a}=(a_{1},a_{2},\dots,a_{n})\in\mathbb{N}^{n}$ and
$S=\\{i\in[n]:a_{1}>a_{i}\\}$. Then there is a permutation
$\mathbf{b}=(b_{1},b_{2},\dots,b_{n})$ of the entries of $\mathbf{a}$ such
that

  1. (i)

$b_{1}=\min\mathbf{b}$.

  2. (ii)

$b_{i}\geq a_{i}$ for all $i\in S$ and $b_{i}=a_{i}$ for all $i\notin
S\cup\\{1\\}$.

  3. (iii)

$b_{i}=\min(b_{i},b_{i+1},\dots,b_{n})$ for all $i\in S$ such that
$b_{i}>a_{i}$.

###### Proof.

We will describe an algorithm that sequentially swaps certain entries of
$\mathbf{a}$ to construct $\mathbf{b}$. Set $\mathbf{a}^{(0)}=\mathbf{a}$ and
$S^{(0)}=S$. For $k\in\mathbb{N}_{0}$, first check if
$\mathbf{a}^{(k)}=(a_{1}^{(k)},a_{2}^{(k)},\dots,a_{n}^{(k)})$ satisfies
$a_{1}^{(k)}=\min\mathbf{a}^{(k)}$. If so, we claim
$\mathbf{b}=\mathbf{a}^{(k)}$ and stop. Otherwise, construct the index set
$S^{(k)}=\\{i\in[n]:a_{1}^{(k)}>a_{i}^{(k)}\\}$, and let $j_{k}=\max S^{(k)}$.
Then, swap the positions of $a_{1}^{(k)}$ and $a_{j_{k}}^{(k)}$ to obtain the
next iterate

$\mathbf{a}^{(k+1)}=(a_{1}^{(k+1)},a_{2}^{(k+1)},\dots,a_{n}^{(k+1)})\coloneqq(a_{j_{k}}^{(k)},a_{2}^{(k)},\dots,a_{j_{k}-1}^{(k)},a_{1}^{(k)},a_{j_{k}+1}^{(k)},\dots,a_{n}^{(k)}),$

and repeat the process.

To prove the correctness of this algorithm, we will first show that it
terminates; this gives property (i) in the process.

######  Claim 3.4.1.

The sequence of index sets $\\{S^{(k)}\\}$ is nested and strictly decreasing.

###### Proof.

Let $k$ be any nonnegative integer, and assume $S^{(k)}\neq\emptyset$. Because
$a_{1}^{(k+1)}=a_{j_{k}}^{(k)}$, where $j_{k}=\max
S^{(k)}=\max\\{i\in[n]:a_{1}^{(k)}>a_{i}^{(k)}\\}$, we have
$a_{1}^{(k)}>a_{1}^{(k+1)}$ (i.e. the sequence consisting of the first entries
$a_{1}^{(k)}$ of the iterates is strictly decreasing). Moreover, by
construction, $a_{i}^{(k)}=a_{i}^{(k+1)}$ if and only if $i\neq 1,j_{k}$. It
is clear that $1\notin S^{(k)}\cup S^{(k+1)}$. We also have
$a_{j_{k}}^{(k+1)}=a_{1}^{(k)}>a_{1}^{(k+1)}$, so $j_{k}\notin S^{(k+1)}$.
Thus,

$S^{(k+1)}=\\{i\in[n]:a_{1}^{(k+1)}>a_{i}^{(k+1)}\\}=\\{i\in[n]:a_{1}^{(k+1)}>a_{i}^{(k)}\\}\subsetneq\\{i\in[n]:a_{1}^{(k)}>a_{i}^{(k)}\\}=S^{(k)},$

as $a_{1}^{(k)}>a_{1}^{(k+1)}$ and $j_{k}\in S^{(k)}$, while $j_{k}\notin
S^{(k+1)}$, implying our claim. ∎

######  Claim 3.4.2.

We have

$\operatorname*{arg\,min}\mathbf{a}\notin S^{(k)}\iff\mathbf{a}^{(k)}\text{
satisfies }a_{1}^{(k)}=\min\mathbf{a}\iff S^{(k)}=\emptyset.$

###### Proof.

Note that $\min\mathbf{a}=\min\mathbf{a}^{(k)}$ since each iterate is a
permutation of the entries of $\mathbf{a}$ by construction. If
$\operatorname*{arg\,min}\mathbf{a}\notin S^{(k)}$, then all $i\in[n]$ such
that $a_{1}^{(k)}>a_{i}^{(k)}$ satisfy $a_{i}^{(k)}>\min\mathbf{a}$. But this
means $\min\mathbf{a}\neq a_{i}^{(k)}$ for all $i\in[n]\setminus\\{1\\}$, so
$a_{1}^{(k)}=\min\mathbf{a}$. Next, if $\mathbf{a}^{(k)}$ satisfies
$a_{1}^{(k)}=\min\mathbf{a}$, then no $i\in[n]$ can satisfy
$a_{1}^{(k)}>a_{i}^{(k)}$, so $S^{(k)}=\emptyset$. Lastly, if
$S^{(k)}=\emptyset$, then it is clear
$\operatorname*{arg\,min}\mathbf{a}\notin S^{(k)}$, proving the equivalence. ∎

Combining Claims 3.4.1 and 3.4.2, the algorithm must terminate because the
index sets are nested and strictly decreasing, so there exists $L$ for which
$S^{(L)}=\emptyset$, which is equivalent to $\mathbf{a}^{(L)}$ satisfying
$a_{1}^{(L)}=\min\mathbf{a}$, or property (i). It now suffices to show that
$\mathbf{a}^{(L)}$ satisfies properties (ii) and (iii).

Now, we note that by Claim 3.4.1, if $i\notin S^{(k)}$, then $i\notin
S^{(\ell)}$ for all $\ell>k$. In particular, as $a_{i}^{(k)}=a_{i}^{(k+1)}$ if
and only if $i\neq 1,j_{k}$, it follows that if $i\notin S\cup\\{1\\}$, then
$a_{i}^{(k)}=a_{i}^{(k+1)}$ for all $k$, which shows $a_{i}^{(L)}=a_{i}$.
Moreover, if $i\notin S^{(k)}\cup\\{1\\}$, then
$a_{i}^{(k)}=a_{i}^{(k+1)}=\cdots=a_{i}^{(L)}$.

Similarly, if $i\in S$, then there exists $k$ such that $i\in S^{(k)}$ but
$i\notin S^{(k+1)}$. Note that $i\in S^{(k)}\subsetneq
S^{(k-1)}\subsetneq\cdots\subsetneq S^{(0)}$. Then $i\neq
j_{0},j_{1},\dots,j_{k-1}$; if not, then $i=j_{\ell}$ for some $0\leq\ell\leq
k-1$, and $j_{\ell}\notin S^{(\ell+1)}$, which implies $j_{\ell}\notin
S^{(k)}$. Hence, $a_{i}^{(0)}=a_{i}^{(1)}=\cdots=a_{i}^{(k)}$. At this stage
of the algorithm, we have two possibilities: either $i=j_{k}=\max S^{(k)}$ or
$i<j_{k}$ with $a_{i}^{(k)}\geq a_{j_{k}}^{(k)}=a_{1}^{(k+1)}$. For the
former, as $i=j_{k}\notin S^{(k+1)}\cup\\{1\\}$, we have
$a_{1}^{(k)}=a_{j_{k}}^{(k+1)}=\cdots=a_{j_{k}}^{(L)}$, where
$a_{1}^{(k)}>a_{j_{k}}^{(k)}$; hence, $a_{j_{k}}^{(L)}>a_{j_{k}}^{(0)}$. For
the latter, $i\neq j_{0},j_{1},\dots,j_{L-1}$, as $i\notin S^{(k+1)}$ and
hence $i\notin S^{(\ell)}$ for any $\ell>k$, so
$a_{i}^{(0)}=a_{i}^{(1)}=\cdots=a_{i}^{(L)}$. Thus, $a_{i}^{(L)}\geq a_{i}$
for all $i\in S$. Altogether, we obtain property (ii).

Lastly, assume that $i\in S$ satisfies $a_{i}^{(L)}>a_{i}$. We showed above
that if $i\neq j_{k}$ for any $k$, then $a_{i}^{(L)}=a_{i}$. Thus, we must
have $i=j_{k}\notin S^{(k+1)}$ for some $k$, so
$a_{1}^{(k)}=a_{j_{k}}^{(k+1)}=a_{j_{k}}^{(L)}$. By the definition of $j_{k}$
and $\mathbf{a}^{(k+1)}$, we have

$a_{1}^{(k+1)}=a_{j_{k}}^{(k)}<a_{1}^{(k)}\leq
a_{j_{k}+1}^{(k)},\dots,a_{n}^{(k)}=a_{j_{k}+1}^{(k+1)},\dots,a_{n}^{(k+1)},$

which yields $j_{k}+1,\dots,n\notin S^{(k+1)}$, so
$(a_{j_{k}}^{(k+1)},a_{j_{k}+1}^{(k+1)},\dots,a_{n}^{(k+1)})=(a_{j_{k}}^{(L)},a_{j_{k}+1}^{(L)},\dots,a_{n}^{(L)})$.
Consequently,
$a_{j_{k}}^{(L)}=a_{1}^{(k)}=\min(a_{j_{k}}^{(L)},a_{j_{k}+1}^{(L)},\dots,a_{n}^{(L)})$,
which proves property (iii).

Therefore, we may take $\mathbf{b}=\mathbf{a}^{(L)}$, as desired. ∎

We can now leverage these lemmas to prove Theorem D successively (in order, we
prove the closure property, image of the degree, embedding property, and
monotonicity).

###### Proof of Theorem D(a).

For any $i\in[d]$, the main idea is to start with a permutation
$\mathbf{p}=(p_{1},p_{2},\dots,p_{n})$ of
$(1^{n-d+1},\mathbf{w}_{\widehat{i}})$, construct a specific permutation
$\mathbf{x}$ of
$(1^{n-d},\mathbf{w})\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$, and use
Lemmas 3.3 and 3.4 to progressively morph $\mathbf{x}$ into $\mathbf{p}$ while
ensuring that each change preserves membership in
$\mathsf{PA}_{n}(\mathbf{y})$.

Note first that if $p_{n}=1$, then $\mathbf{p}_{|_{n-1}}$ is a permutation of
$(1^{n-d},\mathbf{w}_{\widehat{i}})$, so
$(\mathbf{p}_{|_{n-1}},w_{i})\in\mathsf{PA}_{n}(\mathbf{y})$. Applying Lemma
3.3, we obtain
$(\mathbf{p}_{|_{n-1}},1)=\mathbf{p}\in\mathsf{PA}_{n}(\mathbf{y})$.

Now, we suppose $p_{n}=v\in\mathbf{w}_{\widehat{i}}$. Assume first that $v\leq
w_{i}$. Let $k=\max\\{j\in[n]:p_{j}=1\\}$. Consider the following permutation
of $(1^{n-d},\mathbf{w})$:

$\mathbf{x}=(p_{1},\dots,p_{k-1},v,p_{k+1},\dots,p_{n-1},w_{i})\in\mathsf{PA}_{n}(\mathbf{y}).$

Let
$\mathbf{q}=(q_{1},q_{2},\dots,q_{n-k+1})\coloneqq(v,p_{k+1},\dots,p_{n-1},w_{i})$
and $S=\\{j\in[n-k+1]:q_{1}>q_{j}\\}$. By Lemma 3.4, there is a permutation
$\mathbf{q}^{\prime}=(q_{1}^{\prime},q_{2}^{\prime},\dots,q_{n-k+1}^{\prime})$
of the entries of $\mathbf{q}$ such that
$q_{1}^{\prime}=\min\mathbf{q}^{\prime}$, $q_{j}^{\prime}\geq q_{j}$ for all
$j\in S$, $q_{j}^{\prime}=q_{j}$ for all $j\notin S\cup\\{1\\}$, and
$q_{j}^{\prime}=\min(q_{j}^{\prime},q_{j+1}^{\prime},\dots,q_{n-k+1}^{\prime})$
for all $j\in S$ such that $q_{j}^{\prime}>q_{j}$. Then
$\mathbf{x}^{\prime}=(\mathbf{x}_{|_{k-1}},\mathbf{q}^{\prime})=(\mathbf{p}_{|_{k-1}},\mathbf{q}^{\prime})\in\mathsf{PA}_{n}(\mathbf{y})$
is a permutation of $\mathbf{x}$.

From here, we aim to transform $\mathbf{q}^{\prime}$ into
$(p_{k},p_{k+1}\dots,p_{n})$ by way of Lemma 3.3. Since
$q_{1}^{\prime}=\min\mathbf{q}^{\prime}$, Lemma 3.3 yields
$(\mathbf{p}_{|_{k-1}},1,q_{2}^{\prime},\dots,q_{n-k+1}^{\prime})\in\mathsf{PA}_{n}(\mathbf{y})$.
For $2\leq j<n-k+1$, if $j\notin S$, then $q_{j}^{\prime}=q_{j}=p_{j+k-1}$. If
$j\in S$, then we have $q_{j}^{\prime}\geq q_{j}=p_{j+k-1}$. Consider the
sequence

$(h_{1},h_{2},\dots,h_{\ell})\coloneqq(j\in S:q_{j}^{\prime}>q_{j}),$

where $h_{1}<h_{2}<\cdots<h_{\ell}$. For any $t\in[\ell]$, inductively
assuming that we have already replaced $q_{h_{1}},\dots,q_{h_{t-1}}$, we have
$q_{h_{t}}^{\prime}>q_{h_{t}}$, and
$q_{h_{t}}^{\prime}=\min(q_{h_{t}}^{\prime},q_{h_{t}+1}^{\prime},\dots,q_{n-k+1}^{\prime})$,
so applying Lemma 3.3, $q_{h_{t}}^{\prime}$ may be replaced with
$q_{h_{t}}=p_{h_{t}+k-1}$ to obtain a parking assortment 666the first such
replacement is justified for the same reason.. Lastly, as $n-k+1\notin S$, we
have $q_{n-k+1}^{\prime}=q_{n-k+1}=w_{i}$. Consequently,
$(\mathbf{p}_{|_{n-1}},w_{i})\in\mathsf{PA}_{n}(\mathbf{y})$. Applying Lemma
3.3 a final time, as $v\leq w_{i}$, we have
$(\mathbf{p}_{|_{n-1}},v)=\mathbf{p}\in\mathsf{PA}_{n}(\mathbf{y})$. Now,
assume that $v>w_{i}$. We will instead consider the following permutation of
$(1^{n-d},\mathbf{w})$:

$\mathbf{x}=(p_{1},\dots,p_{k-1},w_{i},p_{k+1},\dots,p_{n-1},v)\in\mathsf{PA}_{n}(\mathbf{y}).$

Repeating the same argument as in the case of $v\leq w_{i}$ yields
$\mathbf{p}\in\mathsf{PA}_{n}(\mathbf{y})$.

This covers all permutations of $(1^{n-d+1},w_{\widehat{i}})$, so therefore,
as $i\in[d]$ was arbitrary, we have
$(1^{n-d+1},w_{\widehat{i}})\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$ for
all $i\in[d]$, as desired. ∎

###### Proof of Theorem D(b).

We repeatedly apply Theorem D(a). ∎

###### Proof of Theorem D(c).

Assume that $\deg\mathbf{x}=d$. Let $\mathbf{p}=(p_{1},p_{2},\dots,p_{n+1})$
be any permutation of $(1,\mathbf{x})$. First, if $p_{n+1}=1$, then
$\mathbf{p}_{|_{n}}$ is a permutation of
$\mathbf{x}\in\mathsf{PA}_{n}(\mathbf{y})$, so as $p_{n+1}\leq
1+\sum_{j=1}^{n}y_{j}$, we have
$\mathbf{p}\in\mathsf{PA}_{n+1}(\mathbf{y}^{+})$ by Lemma 3.2. Next, without
loss of generality, $\mathbf{x}=(1^{n-d},\mathbf{w})$, where
$\mathbf{w}\in\mathbb{N}_{>1}^{d}$. If $p_{n+1}=w_{i}$ for some $i\in[d]$,
then $\mathbf{p}_{|_{n}}$ is a permutation of
$(1^{n-d+1},\mathbf{w}_{\widehat{i}})\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$
by Theorem D(a). Because $w_{i}\leq\max\mathbf{w}\leq
1+\sum_{j=1}^{n-1}y_{j}\leq 1+\sum_{j=1}^{n}y_{j}$ by Lemma 3.1, we have
$\mathbf{p}\in\mathsf{PA}_{n+1}(\mathbf{y}^{+})$ by Lemma 3.2. This covers all
permutations of $(1,\mathbf{x})$; therefore,
$(1,\mathbf{x})\in\mathsf{PA}^{\mathrm{inv}}_{n+1}(\mathbf{y}^{+})$. ∎

######  Remark 3.5.

This result immediately implies that the converse of Theorem A does not hold.
For instance, if $\mathbf{y}=(1,3,2,2)$, then one can check that
$(1^{3},4)\in\mathsf{PA}^{\mathrm{inv}}_{4}(\mathbf{y})$, so
$(1^{k+3},4)\in\mathsf{PA}^{\mathrm{inv}}_{k+4}(\mathbf{y}^{+})$ for any
extension $\mathbf{y}^{+}=(\mathbf{y},y_{5},\dots,y_{k+4})$ of $\mathbf{y}$.

###### Proof of Theorem D(d).

We first deal with the upper bound. It is attainable, as if
$\mathbf{y}=(c^{n})$ and $\mathbf{y}^{+}=(c^{n+1})$, then
$\chi(\mathbf{y})=n-1$ and $\chi(\mathbf{y}^{+})=n$. To see that the upper
bound is valid, suppose $\chi(\mathbf{y}^{+})>\alpha+1$. By Lemma 2.8,
$\chi(\mathbf{y})>\alpha$. But by assumption, $\chi(\mathbf{y})=\alpha$, a
contradiction. Thus, $\chi(\mathbf{y}^{+})\leq\alpha+1$.

The lower bound is attainable, as if $\mathbf{y}$ is strictly increasing, and
$\mathbf{y}^{+}=(\mathbf{y},y_{n+1})$, where $y_{n+1}>y_{n}$, then
$\chi(\mathbf{y})=\chi(\mathbf{y}^{+})=0$ (cf. Theorem 4.9 in [4]). By
assumption, as $\chi(\mathbf{y})=\alpha$, there exists
$\mathbf{x}\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$ such that
$\deg\mathbf{x}=\alpha$. Then by Theorem D(c), we have
$(1,\mathbf{x})\in\mathsf{PA}^{\mathrm{inv}}_{n+1}(\mathbf{y}^{+})$, and
$\deg((1,\mathbf{x}))=\alpha$, which means that
$\chi(\mathbf{y}^{+})\geq\alpha$. ∎

######  Remark 3.6.

This result generalizes Corollary 4.3 in [4], which is the case $\alpha=0$.

##  4\. The Invariant Solution Set, Sum Avoidance, and Extremality

In this section, we introduce the invariant solution set of
$\mathbf{y}\in\mathbb{N}^{n}$ and relate it to
$\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$ and consider a family of strictly
decreasing length vectors. This in turn will lead us to proofs of Theorems E
and F. We define the invariant solution set as follows.

######  Definition 4.1.

Let $\mathbf{y}\in\mathbb{N}^{n}$. The _invariant solution set of
$\mathbf{y}$_ is given by

$\mathcal{W}(\mathbf{y})\coloneqq\\{w\in\mathbb{N}:(1^{n-1},w)\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})\\}.$

To illustrate why this set is useful to study, we have the following result,
which is a consequence of Theorem D(a).

######  Lemma 4.2.

If $\mathbf{x}\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$, then
$\mathbf{x}\in\mathcal{W}(\mathbf{y})^{n}$.

###### Proof.

It is clear that $1\in\mathcal{W}(\mathbf{y})$ for any $\mathbf{y}$, so
consider any $i\in[n]$ such that $x_{i}\neq 1$. Repeatedly applying Theorem
D(a), we have $(1^{n-1},x_{i})\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$,
so $x_{i}\in\mathcal{W}(\mathbf{y})$, as needed. ∎

Given this, we now examine the elements of $\mathcal{W}(\mathbf{y})$. Observe
that Lemma 3.1 implies that if $w\in\mathcal{W}(\mathbf{y})$, then $w\leq
1+\sum_{i=1}^{n-1}y_{i}$. Interestingly, this bound can only be improved
slightly if $\mathbf{y}$ is non-constant, which is Theorem E(a).

###### Proof of Theorem E(a).

Again, we prove the contrapositive: if $w=1+\sum_{i=1}^{n-1}y_{i}$ satisfies
$(1^{n-1},w)\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$, then $\mathbf{y}$
is constant.

By assumption, $(1^{n-p-1},w,1^{p})$ for all $p\in[n-1]_{0}$. Fix $p$, and
consider the parking experiment under $(1^{n-1},w)$. Then
$[1,\sum_{i=1}^{n-p-1}y_{i}]$ is occupied before the $(n-p)$th car parks.
After this car parks, note that
$\mathcal{U}_{1}\coloneqq[1+\sum_{i=1}^{n-p-1}y_{i},w-1]$ is unoccupied. Once
the $(n-p)$th car parks, it fills
$[1+\sum_{i=1}^{n-1}y_{i},y_{n-p}+\sum_{i=1}^{n-1}y_{i}]$. Then
$\mathcal{U}_{2}\coloneqq[1+y_{n-p}+\sum_{i=1}^{n-1}y_{i},m]=[w+y_{n-p},m]$,
where $|\mathcal{U}_{2}|=y_{n}-y_{n-p}\geq 0$, is unoccupied. Cars
$n-p+1,n-p+2\dots,n-1$, all with preference $1$, will then park in
$\mathcal{U}_{1}$, so that $\mathcal{U}_{1}^{\prime}=[w-y_{n-p},w-1]$, where
$|\mathcal{U}_{1}^{\prime}|=y_{n-p}>0$, is still unoccupied. Since
$w-1<w+y_{n-p}$, the intervals $\mathcal{U}_{1}^{\prime}$ and
$\mathcal{U}_{2}$ are not contiguous, and the $n$th car must fill these
intervals of lengths $y_{n-p}$ and $y_{n}-y_{n-p}$, which can only happen if
$y_{n}=y_{n-p}$. Therefore, because $p$ was arbitrary, $y_{n}=y_{n-p}$ for any
$p\in[n-1]_{0}$, which implies that $\mathbf{y}$ is constant. ∎

######  Remark 4.3.

Theorem E(a) also yields an alternate characterization of constant length
vectors: $\mathbf{y}$ is constant if and only if
$(1^{n-1},1+\sum_{i=1}^{n-1}y_{i})\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$.

For an example of the equality case for $w$ when $\mathbf{y}$ is non-constant,
consider $\mathbf{y}=(1,3,3,2)$. One can check that
$(1^{3},7)=(1,y_{1}+y_{2}+y_{3})\in\mathsf{PA}^{\mathrm{inv}}_{4}(\mathbf{y})$.
More generally, one also can show that if
$\mathbf{y}=(1,3^{n-2},2)\in\mathbb{N}^{n}$, then
$(1^{n-1},3n-5)\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$.

Moreover, the following result guarantees that any invariant solution can be
written as a binary combination of the last $n-1$ entries of $\mathbf{y}$,
which will allow us to prove Theorem E(b).

######  Lemma 4.4.

Let $\mathbf{y}\in\mathbb{N}^{n}$ and $w\in\mathcal{W}(\mathbf{y})$. Then
$w=1+\mathbf{b}^{\top}\mathbf{y}$ for some
$\mathbf{b}\in\\{0\\}\times\\{0,1\\}^{n-1}$.

###### Proof.

The result is immediate for $w=1$, so assume $w>1$. We first show that there
exists a $\mathbf{b}\in\\{0,1\\}^{n}$ for which
$w=1+\mathbf{b}^{\top}\mathbf{y}$. Assume not. Then
$(w,1^{n-1})\notin\mathsf{PA}_{n}(\mathbf{y})$. Indeed, $w-1$ is not a sum of
entries of $\mathbf{y}$, meaning that no subset of the cars can precisely fill
$[1,w-1]$, so $(1^{n-1},w)\notin\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$.
Thus, such a $\mathbf{b}\in\\{0,1\\}^{n}$ must exist.

Now, if $w=1+\mathbf{b}^{\top}\mathbf{y}$, where
$\mathbf{b}\in\\{1\\}\times\\{0,1\\}^{n-1}$, then we claim there exists
$\mathbf{c}\in\\{0\\}\times\\{0,1\\}^{n-1}$ such that
$\mathbf{b}^{\top}\mathbf{y}=\mathbf{c}^{\top}\mathbf{y}$. Indeed, as
$(w,1^{n-1})\in\mathsf{PA}_{n}(\mathbf{y})$, under its parking experiment, the
first car leaves $[1,w-1]$ empty, and this must be completely occupied by the
end of the experiment. Thus, there is a subset of cars $2,3,\dots,n$ that can
precisely fill $[1,w-1]$, which implies the existence of
$\mathbf{c}\in\\{0\\}\times\\{0,1\\}^{n-1}$ such that
$\mathbf{c}^{\top}\mathbf{y}=w-1=\mathbf{b}^{\top}\mathbf{y}$, as claimed.

Therefore, for any $w\in\mathcal{W}(\mathbf{y})$, we can always find
$\mathbf{b}\in\\{0\\}\times\\{0,1\\}^{n-1}$ such that
$w=1+\mathbf{b}^{\top}\mathbf{y}$. ∎

###### Proof of E(b).

To prove the set inclusion, apply Lemma 4.4. Then note that
$|\mathcal{W}(\mathbf{y})|\leq|\\{1+\mathbf{b}^{\top}\mathbf{y}:\mathbf{b}\in\\{0\\}\times\\{0,1\\}^{n-1}\\}|=2^{n-1}$.
∎

######  Remark 4.5.

Theorem E(b) generalizes consequences of Theorems 5.1 and 5.4 in [4], which
prove the result for $n=2,3$.

For brevity, write
$\mathcal{S}(\mathbf{y})\coloneqq\\{\mathbf{b}^{\top}\mathbf{y}:\mathbf{b}\in\\{0\\}\times\\{0,1\\}^{n-1}\\}$,
so that $\mathcal{W}(\mathbf{y})\subseteq 1+\mathcal{S}(\mathbf{y})$. Recall
that $\mathcal{W}(\mathbf{y})$ has the largest size for certain strictly
decreasing (or nonincreasing) $\mathbf{y}$ when $n=3$ (Theorem 5.4 in [4]).
Thus, a natural question to ask is whether this still holds for large $n$. The
answer is yes; however, we must note that not all strictly decreasing
$\mathbf{y}$ yield an optimal $|\mathcal{W}(\mathbf{y})|$; one must impose a
sum avoidance condition to avoid multiple
$\mathbf{b}\in\\{0\\}\times\\{0,1\\}^{n-1}$ yielding the same element of
$\mathcal{S}(\mathbf{y})$. One possible condition is for $\mathbf{y}$ to be
“superdecreasing,” which is condition (2) in Theorem E(c), which states that
such $\mathbf{y}$ indeed yield an optimal $|\mathcal{W}(\mathbf{y})|$. We now
prove Theorem E(c).

###### Proof of Theorem E(c).

We first prove that equality is achieved. The case for $n=1$ is immediate, so
assume $n\geq 2$. To begin, we will first prove a convenient uniqueness
property for binary combinations given $\mathbf{y}$ satisfying (2).

######  Claim 4.5.1.

If $s\in\mathcal{S}(\mathbf{y})$, then there is a unique
$\mathbf{b}\in\\{0\\}\times\\{0,1\\}^{n-1}$ such that
$s=\mathbf{b}^{\top}\mathbf{y}$.

###### Proof.

Assume for the sake of contradiction that there exist
$\mathbf{b},\mathbf{c}\in\\{0\\}\times\\{0,1\\}^{n-1}$ such that
$s=\mathbf{b}^{\top}\mathbf{y}=\mathbf{c}^{\top}\mathbf{y}$ and
$\mathbf{b}\neq\mathbf{c}$. Write $\mathbf{b}=(b_{1},b_{2},\dots,b_{n})$ and
$\mathbf{c}=(c_{1},c_{2},\dots,c_{n})$, and let

$k=\min\\{i\in[n]:b_{i}\neq c_{i}\\}.$

Without loss of generality, assume that $b_{k}=1$, so that $c_{k}=0$ (the same
argument holds otherwise). Then by definition,

$\mathbf{b}^{\top}\mathbf{y}=\left(\sum_{j=1}^{k-1}b_{j}y_{j}\right)+y_{k}+\left(\sum_{j=k+1}^{n}b_{j}y_{j}\right)=\left(\sum_{j=1}^{k-1}c_{j}y_{j}\right)+\left(\sum_{j=k+1}^{n}c_{j}y_{j}\right)=\mathbf{c}^{\top}\mathbf{y},$

so $y_{k}+\sum_{j=k+1}^{n}b_{j}y_{j}=\sum_{j=k+1}^{n}c_{j}y_{j}$. But by (2),
we have

$\sum_{j=k+1}^{n}c_{j}y_{j}\leq\sum_{j=k+1}^{n}y_{j}<y_{k}\leq
y_{k}+\sum_{j=k+1}^{n}b_{j}y_{j},$

so $y_{k}+\sum_{j=k+1}^{n}b_{j}y_{j}>\sum_{j=k+1}^{n}c_{j}y_{j}$, a
contradiction. ∎

We automatically have $\mathcal{W}(\mathbf{y})\subseteq
1+\mathcal{S}(\mathbf{y})$ due to Lemma 4.4, so we show the reverse inclusion.
Let $s=\mathbf{b}^{\top}\mathbf{y}\in\mathcal{S}(\mathbf{y})$ and
$\mathbf{x}=(1^{n-1},1+s)$. Consider any permutation
$\mathbf{x}^{\prime}=(x^{\prime}_{1},x^{\prime}_{2},\dots,x^{\prime}_{n})$ of
$\mathbf{x}$ such that $x^{\prime}_{1}\neq 1+s$. Under the parking experiment
for $\mathbf{x}^{\prime}$, the first car occupies $[1,y_{1}]$, and
$|[1,y_{1}]|=y_{1}>\sum_{j=2}^{n}y_{j}\geq\sum_{j=1}^{n}b_{j}y_{j}=s$.
Moreover, there exists $i\in[n]$ such that $x^{\prime}_{i}=1+s$, and
$\mathbf{x}^{\prime}_{|_{i-1}}=(1^{i-1})\in\mathsf{PA}_{i-1}(\mathbf{y}_{|_{i-1}})$.
Thus, by Lemma 3.2,
$\mathbf{x}^{\prime}_{|_{i}}\in\mathsf{PA}_{i}(\mathbf{y}_{|_{i}})$. The
remaining cars all have preference 1, so parking succeeds and
$\mathbf{x}^{\prime}\in\mathsf{PA}_{n}(\mathbf{y})$. Now, consider the
remaining permutation $(1+s,1^{n-1})$. Under its parking experiment, the first
car leaves $[1,s]$ empty. Claim 4.5.1 guarantees that a unique subset of the
remaining $n-1$ cars, say cars $i_{1},i_{2},\dots,i_{q}$, can precisely fill
$[1,s]$, so $\sum_{j=1}^{q}y_{i_{j}}=s$.

######  Claim 4.5.2.

Cars $i_{1},i_{2},\dots,i_{q}$ are the only ones that will park in $[1,s]$
under the parking experiment for $(1+s,1^{n-1})$.

###### Proof.

Due to (2),

$y_{2}>y_{3}>\dots>y_{i_{1}-1}>\sum_{j=i_{1}}^{n}y_{j}\geq\sum_{j=1}^{q}y_{i_{j}}=s,$

so cars $2,3,\dots,i_{1}-1$, all with preference $1$, will drive past $[1,s]$
and successively park immediately after. Thus, car $i_{1}$ must park in
$[1,s]$, establishing the base case of our claim. Now, inductively, assume
that cars $i_{1},i_{2},\dots,i_{p}$ are the only ones that parked in $[1,s]$
among the first $i_{p}$ cars, where $p\in[q-1]$. Note that the unoccupied
spots of $[1,s]$ are $[\sum_{j=1}^{p}y_{i_{j}},s]$, which has length
$\sum_{j=p+1}^{q}y_{i_{j}}$. Then by (2), we have

$y_{i_{p}+1}>y_{i_{p}+2}>\dots>y_{i_{p+1}-1}>\sum_{j=i_{p+1}}^{n}y_{j}\geq\sum_{j=p+1}^{q}y_{i_{j}},$

so cars $i_{p}+1,i_{p}+2,\dots,i_{p+1}-1$ will drive past
$[\sum_{j=1}^{p}y_{i_{j}},s]$ (and successively park immediately after). Thus,
car $i_{p+1}$ is the next car to park in $[1,s]$, completing the induction. ∎

From Claim 4.5.2, it follows that parking succeeds since each car $j$, where
$j\in[n]\setminus\\{1,i_{1},i_{2},\dots,i_{q}\\}$, has preference $1$ and
drives past $[1,s]$, so they will successively fill $[1+s+y_{1},m]$. Hence, we
have $(1^{n-1},1+s)\in\mathsf{PA}_{n}(\mathbf{y})$, so
$\mathbf{x}\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$ and
$\mathcal{W}(\mathbf{y})=1+\mathcal{S}(\mathbf{y})$.

To conclude, we will prove the following.

######  Claim 4.5.3.

If $\mathbf{y}$ satisfies (2), then $\chi(\mathbf{y})=1$.

###### Proof.

We first prove that there cannot exist $1<w_{1}\leq w_{2}$ such that
$(1^{n-2},w_{1},w_{2})\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$. Assume
otherwise. Then Lemma 4.2, Lemma 4.4, and our result above that
$\mathcal{W}(\mathbf{y})=1+\mathcal{S}(\mathbf{y})$ guarantee
$w_{1}-1=\mathbf{b}^{\top}\mathbf{y}$ for some
$\mathbf{b}\in\\{0\\}\times\\{0,1\\}^{n-1}$. Now, let

$k=\min\\{i\in[n]:b_{i}=1\\}$

(we note that $k>1$ since $b_{1}=0$). Consider the preferences
$(w_{1},1^{k-2},w_{2},1^{n-k})$. Under its parking experiment, the first car
leaves $[1,\mathbf{b}^{\top}\mathbf{y}]$ empty, where
$|[1,\mathbf{b}^{\top}\mathbf{y}]|=\mathbf{b}^{\top}\mathbf{y}$. By Claim
4.5.1, $\mathbf{b}$ is unique, so to ensure $[1,\mathbf{b}^{\top}\mathbf{y}]$
is completely filled, car $k$ must park here. However, by construction, this
is not the case since car $k$ has preference $w_{2}\geq
w_{1}=1+\mathbf{b}^{\top}\mathbf{y}$. Hence, $[1,\mathbf{b}^{\top}\mathbf{y}]$
will have unoccupied spaces by the end of the parking experiment, so parking
fails, and it follows that if
$\mathbf{x}\in\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$, then
$\deg\mathbf{x}\neq 2$. Thus, $\chi(\mathbf{y})<2$ by Theorem D(b), and so
$\chi(\mathbf{y})=1$ since $\mathcal{W}(\mathbf{y})\supsetneq\\{1\\}$. ∎

Therefore,
$\mathsf{PA}^{\mathrm{inv},\uparrow}_{n}(\mathbf{y})=\\{(1^{n-1},1+s):s\in\mathcal{S}(\mathbf{y})\\}$,
as desired.

For our count, note that the only nondecreasing invariant parking assortments
of $\mathbf{y}$ are of the form $(1^{n-1},1+s)$, where
$s=\mathbf{b}^{\top}\mathbf{y}$ for some
$\mathbf{b}\in\\{0\\}\times\\{0,1\\}^{n-1}$. Claim 4.5.1 ensures that
$\mathbf{b}$ is unique, so each choice of $\mathbf{b}$ gives a distinct value
of $s$. Thus, by definition,
$|\mathsf{PA}^{\mathrm{inv},\uparrow}_{n}(\mathbf{y})|=|\mathcal{W}(\mathbf{y})|=2^{n-1}$.

Lastly, note that each of the $2^{n-1}-1$ nontrivial elements of
$\mathsf{PA}^{\mathrm{inv},\uparrow}_{n}(\mathbf{y})$ have $n$ distinct
permutations of their entries due to their unique non-$1$ entry. Therefore,
$|\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})|=n(2^{n-1}-1)+1=2^{n-1}n-n+1$, as
claimed. ∎

We are now ready to prove the rest of Theorem E, which gives a necessary
condition for equality to be achieved in Theorem E(b).

######  Lemma 4.6.

Let $\mathbf{y}=(y_{1},y_{2},\dots,y_{n})\in\mathbb{N}^{n}$. If
$1+\sum_{j=2}^{n}y_{j}\in\mathcal{W}(\mathbf{y})$, then
$y_{1}=\max\mathbf{y}$.

###### Proof.

If $y_{1}<\max\mathbf{y}$, let $k\in[n]\setminus\\{1\\}$ satisfy
$y_{k}=\max\mathbf{y}$, and consider the preferences
$(1^{k-1},1+\sum_{j=2}^{n}y_{j},1^{n-k})$. Then under its parking experiment,
the first $k-1$ cars park successively to fill $[1,\sum_{j=1}^{k-1}y_{j}]$.
Car $k$ occupies $[s,s+y_{k}-1]$, where $s\geq 1+\sum_{j=2}^{n}y_{j}$, so
$s+y_{k}-1\geq y_{k}+\sum_{j=2}^{n}y_{j}>m$ and hence parking fails. Thus,
$(1^{n-1},1+\sum_{j=2}^{n}y_{j})\notin\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$,
so we have the contrapositive of the desired result. ∎

###### Proof of Theorem E(d).

If $|\mathcal{W}(\mathbf{y})|=2^{n-1}$, then
$|\mathcal{W}(\mathbf{y})|=|\mathcal{S}(\mathbf{y})|=2^{n-1}$. Thus, there
cannot exist $\mathbf{b},\mathbf{c}\in\\{0\\}\times\\{0,1\\}^{n-1}$ such that
$\mathbf{b}\neq\mathbf{c}$ and
$\mathbf{b}^{\top}\mathbf{y}=\mathbf{c}^{\top}\mathbf{y}$; otherwise,
$|\mathcal{S}(\mathbf{y})|\leq 2^{n-1}-1$. Then
$1+\mathbf{b}^{\top}\mathbf{y}\in\mathcal{W}(\mathbf{y})$ for any
$\mathbf{b}\in\\{0\\}\times\\{0,1\\}^{n-1}$. In particular, choosing
$\mathbf{b}=(0,1^{n-1})$ gives
$1+\sum_{j=2}^{n}y_{j}\in\mathcal{W}(\mathbf{y})$. Lemma 4.6 then ensures
$y_{1}=\max\mathbf{y}$, so that $y_{1}\geq y_{2}$.

We now show that the remaining inequality detailed in (3) holds via induction.
For the base case, suppose $y_{2}\leq\sum_{i=3}^{n}y_{i}$. For
$\mathbf{b}=(0^{2},1^{n-2})$, we have
$1+\sum_{i=3}^{n}y_{i}\in\mathcal{W}(\mathbf{y})$. Hence,
$(1+\sum_{i=3}^{n}y_{i},1^{n-1})\in\mathsf{PA}_{n}(\mathbf{y})$, so under its
parking experiment, the first car leaves $[1,\sum_{i=3}^{n}y_{i}]$ empty for
other cars to fill. As $y_{2}\leq\sum_{i=3}^{n}y_{i}$, car 2 parks in
$[1,\sum_{i=3}^{n}y_{i}]$. Thus, there exists
$\mathbf{c}=(c_{1},c_{2},\dots,c_{n})\in\\{0\\}\times\\{0,1\\}^{n-1}$ with
$c_{2}=1$ such that
$\mathbf{c}^{\top}\mathbf{y}=\sum_{i=3}^{n}y_{i}=\mathbf{b}^{\top}\mathbf{y}$,
a contradiction since $\mathbf{b}\neq\mathbf{c}$. This shows that
$y_{2}>\sum_{i=3}^{n}y_{i}$.

Now, assume that for some $p\in[n]\setminus\\{1\\}$, we have
$y_{j}>\sum_{i=j+1}^{n}y_{i}$ for all $j\in[p-1]\setminus\\{1\\}$. We seek to
prove that $y_{p}>\sum_{i=p+1}^{n}y_{i}$. To do so, we will employ the same
argument from above. Assume $y_{p}\leq\sum_{i=p+1}^{n}y_{i}$. Choosing
$\mathbf{b}=(0^{p},1^{n-p})$ yields
$(1+\sum_{i=p+1}^{n}y_{i},1^{n-1})\in\mathsf{PA}_{n}(\mathbf{y})$, so under
its parking experiment, $[1,\sum_{i=p+1}^{n}y_{i}]$ is filled by a subset of
cars $2,3,\dots,n$. By the inductive hypothesis, for any
$j\in[p-1]\setminus\\{1\\}$,

$y_{j}>\sum_{i=j+1}^{n}y_{i}>\sum_{i=p+1}^{n}y_{i}.$

Since $y_{p}\leq\sum_{i=3}^{n}y_{i}$, car $p$ must be the first to park in
$[1,\sum_{i=p+1}^{n}y_{i}]$. Thus, there exists
$\mathbf{c}=(c_{1},c_{2},\dots,c_{n})\in\\{0\\}\times\\{0,1\\}^{n-1}$ with
$c_{p}=1$ such that
$\mathbf{c}^{\top}\mathbf{y}=\sum_{i=p+1}^{n}y_{i}=\mathbf{b}^{\top}\mathbf{y}$,
so we arrive at another contradiction. Therefore,
$y_{p}>\sum_{i=p+1}^{n}y_{i}$, completing the induction. ∎

######  Remark 4.7.

The condition (3) is not sufficient for $|\mathcal{W}(\mathbf{y})|=2^{n-1}$.
For $\mathbf{y}=(7,5,3,1)$, one can check that
$\mathcal{W}(\mathbf{y})=\\{1,2,4,5,6,7,9\\}$, so
$|\mathcal{W}(\mathbf{y})|=7<2^{3}$.

Given what was discussed above, we conclude by proving Theorem F, which gives
an upper bound on $|\mathsf{PA}^{\mathrm{inv},\uparrow}_{n}(\mathbf{y})|$
independent of $m$.

###### Proof of Theorem F.

The set inclusion
$\mathsf{PA}^{\mathrm{inv},\uparrow}_{n}(\mathbf{y})\subseteq\\{1\\}^{n-\chi(\mathbf{y})}\times\mathcal{W}(\mathbf{y})^{\chi(\mathbf{y})}$
follows by Definition 1.7 and Lemma 4.2. To prove the bound, note that the
nondecreasing elements of $\mathcal{W}(\mathbf{y})^{\chi(\mathbf{y})}$ are
precisely multisets of cardinality $\chi(\mathbf{y})$ taken from
$\mathcal{W}(\mathbf{y})$. Letting $|\mathcal{W}(\mathbf{y})|=W$ and
$\chi(\mathbf{y})=C$, by stars and bars, the number of such multisets is
$B(W,C)\coloneqq\binom{W+C-1}{C}$. By Pascal’s identity,
$B(W+1,C)=\binom{(W+1)+C-1}{C}=\binom{(W+1)+C-2}{C-1}+\binom{(W+1)+C-2}{C}=\binom{W+C-1}{C}+\binom{(W+1)+C-2}{C-1}\geq
B(W,C)$, so $B(W,C)$ is nondecreasing with respect to $W$. Similarly,
$B(W,C+1)=\binom{W+(C+1)-1}{C+1}=\binom{W+C-1}{C}+\binom{W+C-1}{C+1}\geq
B(W,C)$, so $B(W,C)$ is nondecreasing with respect to $C$. Therefore, since
$W\leq 2^{n-1}$ by Theorem E(b) and $C\leq n-1$, we have
$|\mathsf{PA}^{\mathrm{inv},\uparrow}_{n}(\mathbf{y})|\leq B(W,C)\leq
B(2^{n-1},n-1)=\binom{2^{n-1}+n-2}{n-1}$, as claimed. ∎

##  5\. Open Problems

We now suggest various problems for future research.

###  5.1. Length Vectors of Non-Maximal Characteristic

In Section 2, we found a simple closed form for the set
$\\{\mathbf{y}\in\mathbb{N}^{n}:\chi(\mathbf{y})=n-1\\}$. A natural follow-up
to this is to consider finding closed forms for other characteristics.

######  Open Problem 1.

Give a direct characterization of the preimage
$\chi^{-1}_{n}(\alpha)\coloneqq\\{\mathbf{y}\in\mathbb{N}^{n}:\chi(\mathbf{y})=\alpha\\}$
for any $\alpha\in[n-1]_{0}$.

We note that Theorem A gives a containment of $\chi^{-1}_{n}(0)$ in a
relatively simple set. However, refining this containment is the main
difficulty. For any $\alpha$, we suspect that an effective way to approach the
problem is to look at repeated entries of $\mathbf{y}$ or any matching partial
sums of the entries of $\mathbf{y}$ and study how these factors affect
$\chi(\mathbf{y})$.

###  5.2. Preserving the Characteristic

As discussed, Theorem D(d) gives an easy way to bound $\chi(\mathbf{y})$ given
that we know $\chi(\mathbf{y}_{|_{k}})$ for some $k<n$. This can simplify the
process for computing $\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$ given
$\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y}_{|_{k}})$, but there are still a
great deal of possibilities to check especially if $k\ll n$. In light of this
case, we ask the following.

######  Open Problem 2.

Let $\mathbf{y}\in\mathbb{N}^{n}$, where $\chi(\mathbf{y})=\alpha$, and
$\mathbf{y}^{+}=(\mathbf{y},y_{n+1})\in\mathbb{N}^{n+1}$. What must be true
about $\mathbf{y}$ and $\mathbf{y}^{+}$ to guarantee that
$\chi(\mathbf{y}^{+})=\alpha$?

Note that if $\alpha=0$, then an answer to the above can help one construct
$\chi(0,n)$ using a recursive-like technique. Moreover, given a condition on
$\mathbf{y}$ and $\mathbf{y}^{+}$, one tool that may be useful in showing that
$\chi(\mathbf{y}^{+})\neq n+1$ is Theorem E(a).

###  5.3. Sharper Bounds

Recall that in Theorem F, we had an upper bound for the size of
$\mathsf{PA}^{\mathrm{inv},\uparrow}_{n}(\mathbf{y})$ depending only on $n$.
One might ask if this is the best such bound or if there is a similar bound
for the size of $\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})$. For our bound,
we posit that the answer is no, and our computational experiments suggest that
there is a familiar connection between the best upper bound for
$|\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})|$ and the best upper bound for
$|\mathsf{PA}^{\mathrm{inv},\uparrow}_{n}(\mathbf{y})|$, which is described
below.

######  Open Problem 3.

Let $\mathbf{y}\in\mathbb{N}^{n}$. Do
$|\mathsf{PA}^{\mathrm{inv}}_{n}(\mathbf{y})|\leq(n+1)^{n-1}$ and
$|\mathsf{PA}^{\mathrm{inv},\uparrow}_{n}(\mathbf{y})|\leq C_{n}$ hold for any
$n$?

If this is true, then the upper bounds are automatically sharp since constant
$\mathbf{y}$ are examples of the equality case. A potential way to approach
this problem is to examine and understand which elements of
$1+\mathcal{S}(\mathbf{y})$ also are in $\mathcal{W}(\mathbf{y})$, as well as
apply any results for Open Problems 1 and 2.

## Acknowledgements

I would like to thank Carlos Martínez and Pamela Harris for fruitful
discussions.

## References

  * [1] Aruzhan Amanbayeva and Danielle Wang  “The Convex Hull of Parking Functions of Length $n$”  In _Enumerative Combinatorics and Applications_ 2.2, 2022, pp. Article #S2R10
  * [2] D.. Bailey  “Counting Arrangements of $1$’s and $-1$’s”  In _Mathematics Magazine_ 69.2, 1996, pp. 128–131
  * [3] Carolina Benedetti, Rafael S. González D’León, Christopher R.. Hanusa, Pamela E. Harris, Apoorva Khare, Alejandro H. Morales and Martha Yip  “A Combinatorial Model for Computing Volumes of Flow Polytopes”  In _Transactions of the American Mathematical Society_ 372.5, 2019, pp. 3369–3404
  * [4] Douglas M. Chen, Pamela E. Harris, J. Martínez Mori, Eric J. Pabón-Cancel and Gabriel Sargent  “Permutation Invariant Parking Assortments”  In _Enumerative Combinatorics and Applications_ 4.1, 2024, pp. Article #S2R4
  * [5] Laura Colmenarejo, Pamela E. Harris, Zakiya Jones, Christo Keller, Andrés Ramos Rodríguez, Eunice Sukarto and Andrés R. Vindas-Meléndez  “Counting $k$-Naples Parking Functions through Permutations and the $k$-Naples Area Statistic”  In _Enumerative Combinatorics and Applications_ 1.2, 2021, pp. Article #S2R11
  * [6] Jennifer Elder, Pamela E. Harris, Jan Kretschmann and J. Martínez Mori  “Boolean Intervals in the Weak Order of $\mathfrak{S}_{n}$”  In _arXiv preprint arXiv:2306.14734_ , 2023
  * [7] Spencer J Franks, Pamela E Harris, Kimberly Harry, Jan Kretschmann and Megan Vance  “Counting Parking Sequences and Parking Assortments Through Permutations”  In _Enumerative Combinatorics and Applications_ 4.1, 2024, pp. Article #S2R2
  * [8] Pamela E. Harris, Brian M. Kamau, J. Martínez Mori and Roger Tian  “On the Outcome Map of MVP Parking Functions: Permutations Avoiding $321$ and $3412$, and Motzkin Paths”  In _Enumerative Combinatorics and Applications_ 3.2, 2023, pp. Article #S2R11
  * [9] Pamela E. Harris, J. Martínez Mori, Eric J. Pabón-Cancel and Gabriel Sargent, Personal communication, 2022
  * [10] Caleb Ji and James Propp  “Brussels Sprouts, Noncrossing Trees, and Parking Functions”  In _Enumerative Combinatorics and Applications_ 1.1, 2021, pp. Article #S2R1
  * [11] Alan G. Konheim and Benjamin Weiss  “An Occupancy Discipline and Applications”  In _SIAM Journal on Applied Mathematics_ 14.6, 1966, pp. 1266–1274
  * [12] Richard P. Stanley and Jim Pitman  “A Polytope Related to Empirical Distributions, Plane Trees, Parking Functions, and the Associahedron”  In _Discrete and Computational Geometry_ 27.4, 2002, pp. 603–634
  * [13] Catherine H. Yan  “On the Enumeration of Generalized Parking Functions”  In _Proceedings of the Thirty-first Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 2000)_ 147, 2000, pp. 201–209
  * [14] Catherine H. Yan  “Parking Functions”  In _Handbook of Enumerative Combinatorics_ Boca Raton, FL: CRC Press, 2015, pp. 835–894