# Generalized parking function polytopes

Mitsuki Hanada  Department of Mathematics
University of California, Berkeley
https://math.berkeley.edu/~mhanada/<EMAIL_ADDRESS>,  John Lentfer
Department of Mathematics
University of California, Berkeley
https://math.berkeley.edu/~jlentfer/<EMAIL_ADDRESS>and  Andrés R.
Vindas-Meléndez  Department of Mathematics
University of California, Berkeley
https://math.berkeley.edu/~vindas<EMAIL_ADDRESS>
###### Abstract.

A classical parking function of length $n$ is a list of positive integers
$(a_{1},a_{2},\ldots,a_{n})$ whose nondecreasing rearrangement $b_{1}\leq
b_{2}\leq\cdots\leq b_{n}$ satisfies $b_{i}\leq i$. The convex hull of all
parking functions of length $n$ is an $n$-dimensional polytope in
$\mathbb{R}^{n}$, which we refer to as the classical parking function
polytope. Its geometric properties have been explored in (Amanbayeva and Wang
2022) in response to a question posed in (Stanley 2020). We generalize this
family of polytopes by studying the geometric properties of the convex hull of
$\mathbf{x}$-parking functions for $\mathbf{x}=(a,b,\dots,b)$, which refer to
as $\mathbf{x}$-parking function polytopes. We explore connections between
these $\mathbf{x}$-parking function polytopes, the Pitman-Stanley polytope,
and the partial permutahedra of (Heuer and Striker 2022). In particular, we
establish a closed-form expression for the volume of $\mathbf{x}$-parking
function polytopes. This allows us to answer a conjecture of (Behrend et al.
2022) and also obtain the first closed-form expression for the volume of the
convex hull of classical parking functions as a corollary.

Hanada is partially supported by the Funai Overseas Scholarship.

Lentfer is supported by the National Science Foundation Graduate Research
Fellowship DGE-2146752.

Vindas-Meléndez is partially supported by the National Science Foundation
under Award DMS-2102921.

##  1\. Introduction

A classical parking function of length $n$ is a list
$(a_{1},a_{2},\ldots,a_{n})$ of positive integers whose nondecreasing
rearrangement $b_{1}\leq b_{2}\leq\cdots\leq b_{n}$ satisfies $b_{i}\leq i$.
It is well-known that the number of classical parking functions of length $n$
is $(n+1)^{n-1}$; this number surfaces in a variety of places, for example, it
counts the number of rooted labeled trees on $n+1$ vertices, and the number of
regions of a Shi arrangement (see [22] for further discussion). Let
$\mathsf{PF}_{n}$ denote the convex hull of all parking functions of length
$n$ in $\mathbb{R}^{n}$. In 2020, Stanley [17] asked for the number of
vertices, the number of faces, the number of lattice points
$\mathsf{PF}_{n}\cap\mathbb{Z}^{n}$, and the volume of $\mathsf{PF}_{n}$.
These questions were first answered by Amanbayeva and Wang [1].

In Section 2, we revisit the classical parking function polytope
$\mathsf{PF}_{n}$. We provide new results on the appearance of both lower-
dimensional parking function polytopes and permutahedra as facets of
$\mathsf{PF}_{n}$. We connect the classical parking function polytope with the
recent work of Heuer and Striker [8] and Behrend et al. [2] on partial
permutahedra, and show when they are integrally equivalent. We collect
different characterizations of the normalized volume of $\mathsf{PF}_{n}$ in
Theorem 2.9 and give the first closed-form, i.e., non-recursive, answer to
Stanley’s original question on the volume of $\mathsf{PF}_{n}$.

A natural direction is to extend these results for generalizations of parking
functions. In this paper we consider $\mathbf{x}$-parking functions, where
$\mathbf{x}$ is a vector of positive integers. They have been explored from an
enumerative perspective previously by Yan [20, 21, 22] and Pitman and Stanley
[18]. In Section 3, we consider when $\mathbf{x}=(a,b,b,\ldots,b)$ and
generalize results of Amanbayeva and Wang [1]. We establish in Theorem 1.1 a
closed-form normalized volume formula for all positive integers $a,b$.

######  Theorem 1.1.

For any positive integers $a,b,n$, the normalized volume of the
$\mathbf{x}$-paraking function polytope
$\operatorname{NVol}(\mathcal{X}_{n}(a,b))$ is given by

$\operatorname{NVol}(\mathcal{X}_{n}(a,b))=-n!\left(\frac{b}{2}\right)^{n}\sum_{i=0}^{n}\binom{n}{i}(2i-3)!!\left(2n-1+\frac{2a-2}{b}\right)^{n-i}.$

The proof of Theorem 1.1 uses tools from analytic combinatorics and analytic
number, e.g., Ramanujan’s Master Theorem. By determining when partial
permutohedra are integrally equivalent to $\mathbf{x}$-parking functions, we
also prove a conjecture of Behrend et al. [2], as Corollary 3.28.

In Section 4, we introduce weakly increasing $\mathbf{x}$-parking functions,
which are $\mathbf{x}$-parking functions that are in weakly increasing order
$a_{1}\leq a_{2}\leq\cdots\leq a_{n}$ without any rearrangement. We explore a
subpolytope of the $\mathbf{x}$-parking function polytope which is constructed
as the convex hull of weakly increasing $\mathbf{x}$-parking functions. We
show that the convex hull of weakly increasing $\mathbf{x}$-parking functions
is integrally equivalent to certain Pitman-Stanley polytopes. In the
literature, the Pitman-Stanley polytope has been called the “parking function
polytope” as its volume is related to parking functions. However, we will call
the convex hull of any generalization of parking functions a parking function
polytope.

We conclude with Section 5 where we present some routes for further study on
unimodular triangulations, Ehrhart theory, other generalizations where
$\mathbf{x}\neq(a,b,\ldots,b)$, and rational parking functions.

##  2\. The classical parking function polytope

The classical parking function polytope was first studied in [1]. As mentioned
in the introduction, a classical parking function of length $n$ is a list
$(a_{1},a_{2},\ldots,a_{n})$ of positive integers whose nondecreasing
rearrangement $b_{1}\leq b_{2}\leq\cdots\leq b_{n}$ satisfies $b_{i}\leq i$.
Let $\mathsf{PF}_{n}$ denote the convex hull of all parking functions of
length $n$ in $\mathbb{R}^{n}$, which we call the classical parking function
polytope. For example, the classical parking functions of length $3$ are
$111$, $112$, $121$, $211$, $113$, $131$, $311$, $122$, $212$, $221$, $123$,
$132$, $231$, $213$, $312$, and $321$. For $\mathsf{PF}_{3}$, their convex
full in $\mathbb{R}^{3}$, see Figure 1 (left).

Figure 1. On the left, we have the classical parking function polytope
$\mathsf{PF}_{3}$, where the hexagonal facet is the regular permutahedron
$\Pi_{3}$ and the three triangular facets are copies of $\mathsf{PF}_{2}$. On
the right, we have the the Schlegel diagram of $\mathsf{PF}_{4}$.

###  2.1. Face structure

We are able to say more about its face structure by using the regular
permutahedron, which we now define.

######  Definition 2.1 (Example 0.10, [24]; Definition 2.1, [13]).

The regular permutahedron $\Pi_{n}\subseteq\mathbb{R}^{n}$ is the
$(n-1)$-dimensional polytope obtained as the convex hull of all vectors
obtained by permuting the coordinates of the vector $(1,2,\ldots,n)$. Its
vertices can be identified with the permutations in $S_{n}$ by associating
with $(x_{1},x_{2},\ldots,x_{n})$ the permutation that maps $x_{i}\mapsto i$
such that two permutations are adjacent if and only if the corresponding
permutations differ by an adjacent transposition. More generally, for
$\mathbf{r}:=(r_{1},\ldots,r_{n})\in\mathbb{R}^{n}$, a permutahedron
$\Pi_{n}(\mathbf{r})$ is the convex hull of all vectors that are obtained by
permuting the coordinates of the vector $\mathbf{r}$.

The defining inequalities for $\Pi_{n}$ (Proposition 2.5, [13]; [14]) are of
the form

$x_{1}+\cdots+x_{n}=\frac{n(n+1)}{2},$

and for all nonempty subsets
$\\{i_{1},\ldots,i_{k}\\}\subseteq\\{1,\ldots,n\\}$,

$x_{i_{1}}+\cdots+x_{i_{k}}\leq
n+\cdots+(n-k+1)=\frac{n(n+1)}{2}-\frac{k(k+1)}{2}.$

######  Example 2.2.

Consider the classical parking function polytope $\mathsf{PF}_{3}$, observe
that one facet is the hexagon with vertices $(1,2,3)$, $(1,3,2)$, $(2,3,1)$,
$(2,1,3)$, $(3,1,2)$, and $(3,2,1)$. This aligns exactly with the description
of the regular permutahedron $\Pi_{3}$. Note that $\Pi_{3}$ is the
intersection of $\mathsf{PF}_{3}$ with the supporting hyperplane given by the
linear functional $x_{1}+x_{2}+x_{3}=\frac{3(3+1)}{2}=6$. See Figure 1 (left).

######  Example 2.3.

For $\mathsf{PF}_{4}$, there is only one three-dimensional face that is the
convex hull of 24 vertices, which are exactly the $4!$ permutations of
$(1,2,3,4)$; it is $\Pi_{4}$. Similarly, we can find that there are exactly 8
two-dimensional faces which are the convex hulls of 6 vertices, which are, of
course, the 8 hexagonal faces (and thus 2-dimensional permutahedra) which are
facets of the three-dimensional permutahedra. See Figure 1 (right) for the
Schlegel diagram of $\mathsf{PF}_{4}$.

We have the following result on when the permutahedron appears as a facet of
the classical parking function polytope.

######  Proposition 2.4.

The regular permutahedron appears as a facet of the classical parking function
polytope exactly once.

###### Proof.

By the definition of the parking function polytope $\mathsf{PF}_{n}$, it is
the convex hull of all vertices given by permutations of

$(\underbrace{1,\ldots,1}_{k},\underbrace{k+1,k+2,\ldots,n-2,n-1}_{n-k}),$

for $1\leq k\leq n$ (here, $k=0$ would be superfluous). Each permutation of
$(1,2,\ldots,n)$ appears as a vertex. Thus, the convex hull of these $n!$
vertices, which is exactly $\Pi_{n}$, is contained within $\mathsf{PF}_{n}$.

We now use the hyperplane description of $\mathsf{PF}_{n}$. Consider the
hyperplane $H$ defined by $x_{1}+x_{2}+\cdots+x_{n}=\frac{n(n+1)}{2}$. We
claim $H\cap\mathsf{PF}_{n}=\Pi_{n}$. Since all permutations of
$(1,2,\ldots,n)$ satisfy $1+2+\cdots+n=\frac{n(n+1)}{2}$, the vertices that
give the vertex description of $\Pi_{n}$ are in $H\cap\mathsf{PF}_{n}$. By
taking their convex hull, it follows that $\Pi_{n}\subseteq
H\cap\mathsf{PF}_{n}$.

Now, suppose $\mathbf{x}:=(x_{1},x_{2},\ldots,x_{n})$ is a point in
$H\cap\mathsf{PF}_{n}$. As we are dealing with a subset of a polytope
intersecting a hyperplane, $H\cap\mathsf{PF}_{n}$ is a polytope of dimension
(at most) $n-1$. Suppose towards a contradiction that $\mathbf{x}$ is not in
$\Pi_{n}$. This means that by the defining inequalities for $\Pi_{n}$,

  1. (1)

$x_{1}+\cdots+x_{n}\neq\frac{n(n+1)}{2}$, a contradiction, or

  2. (2)

there exists some nonempty subset
$\\{i_{1},\ldots,i_{k}\\}\subseteq\\{1,\ldots,n\\}$ such that

$x_{i_{1}}+\cdots+x_{i_{k}}>n+\cdots+(n-k+1)=\frac{n(n+1)}{2}-\frac{k(k+1)}{2}.$

But (2) is not allowed by the defining inequalities for a parking function
polytope. Hence, $\mathbf{x}$ is in $\Pi_{n}$, so
$\Pi_{n}=H\cap\mathsf{PF}_{n}$ is a facet of $\mathsf{PF}_{n}$.

To show uniqueness, it suffices to show that the only hyperplane in the
inequality description that corresponds to a facet with $n!$ vertices is $H$.
Assume a facet with $n!$ vertices corresponds to a hyperplane of the form

$x_{i_{1}}+\cdots+x_{i_{k}}=n+\cdots+(n+1-k),\text{ where }1\leq k\leq n-2.$

By the vertex description of $\mathsf{PF}_{n}$, the number of vertices that
satisfy this equation is given by

$k!\sum_{m=1}^{n-k}\frac{(n-k)!}{m!},$

where $m$ is the number of coordinates in the vertex that have value 1. Note
that since $1\leq k\leq n-2$, it follows that
$n=\binom{n}{1}\leq\binom{n}{k}$. Rearranging the inequality, we get that
$n\cdot k!(n-k)!\leq n!$. We can also see that

$\frac{1}{1}+\frac{1}{2!}+\cdots+\frac{1}{(n-k)!}<(n-k)<n.$

Hence,

$k!(n-k)!\sum\limits_{m=1}^{n-k}\frac{1}{m!}<n\cdot k!(n-k)!\leq n!.$

Therefore, $H$ is the only possible hyperplane in the inequality description
of $\mathsf{PF}_{n}$ that corresponds to a facet with $n!$ many variables. ∎

The following lemma allows us to establish a lower bound for the number of
permutahedra of any dimension in the parking function polytope.

######  Lemma 2.5.

The $(n-2)$-dimensional permutahedron $\Pi_{n-1}$ appears as a facet of
$\Pi_{n}$ exactly $2n$ times.

###### Proof.

Consider the defining inequalities of $\Pi_{n}$ given in Definition 2.1. We
claim that the hyperplanes that correspond to $\Pi_{n-1}$ as facets are those
of the form

$x_{i}\leq n\text{ and }x_{i_{1}}+\cdots+x_{i_{n-1}}\leq n+(n-1)+\cdots+2.$

We can see that for any $i$, the vertices of $\Pi_{n}$ that satisfy $x_{i}=n$
are those where the $i$-th coordinate is $n$ and all the other coordinates can
be written as a permutation of $(1,2,\dots,n-1)$. This facet is exactly
$\Pi_{n-1}$. Similarly, we can see the vertices that satisfy

$x_{i_{1}}+\cdots+x_{i_{n-1}}=n+(n-1)+\cdots+2,\text{ where
}\\{i_{1},\dots,i_{n-1}\\}=\\{1,\ldots,n\\}\setminus\\{k\\},\text{ for some
}k,$

are vertices where the $k$-th coordinate is 1 and all the other coordinates
can be written as a permutation of $(2,\dots,n)$. Thus, facets that correspond
to hyperplanes of these forms are $\Pi_{n-1}$.

To show that these are the only hyperplanes that can correspond to
$\Pi_{n-1}$, we will show that the only hyperplanes that can correspond to a
facet with $(n-1)!$ vertices are the ones mentioned above. The proof is
similar to the uniqueness proof of Proposition 2.4.

For a hyperplane $x_{i_{1}}+\cdots+x_{i_{k}}=n+\cdots+(n-k+1)$ consisting of
$k$ many variables, we can see that there are $k!(n-k)!$ vertices of $\Pi_{n}$
that satisfy it. If we have that $k$ is neither equal to $1$ nor $n-1$, it
follows that $k!(n-k)!<(n-1)!$. Hence, if a hyperplane with $k$ many variables
corresponds to $\Pi_{n-1}$, which has $(n-1)!$ vertices, it follows that $k$
equals $1$ or $n-1$. ∎

######  Proposition 2.6.

The $(n-1)$-dimensional parking function polytope $\mathsf{PF}_{n-1}$ appears
as a facet of the $n$-dimensional parking function polytope $\mathsf{PF}_{n}$
exactly $n$ times.

###### Proof.

Consider the inequality description of $\mathsf{PF}_{n}$:

(1) $\displaystyle 1\leq x_{i}$ $\displaystyle\leq n,$ $\displaystyle\text{
for }1\leq i\leq n,$ (2) $\displaystyle x_{i}+x_{j}$ $\displaystyle\leq
n+(n-1),$ $\displaystyle\text{ for }i<j,$ (3) $\displaystyle
x_{i}+x_{j}+x_{k}$ $\displaystyle\leq n+(n-1)+(n-2),$ $\displaystyle\text{ for
}i<j<k,$ $\displaystyle\vdots$ (4) $\displaystyle
x_{i_{1}}+x_{i_{2}}+\cdots+x_{i_{n-2}}$ $\displaystyle\leq n+(n-1)+\cdots+3,$
$\displaystyle\text{ for }i_{1}<i_{2}<\cdots<i_{n-2},$ (5) $\displaystyle
x_{1}+x_{2}+\cdots+x_{n}$ $\displaystyle\leq n+(n-1)+\cdots+1.$

Fix $x_{i}=n$ for some $i$; without loss of generality say $i=n$. Then we
proceed to reduce the system of inequalities. For all $1\leq i\leq n-1$, we
still have $1\leq x_{i}$, but if any

$x_{i}>n-1,\text{ then }x_{i}+x_{n}>n+(n-1),$

which contradicts (2). Thus, we have $1\leq x_{i}\leq n-1$ for $1\leq i\leq
n-1$. Next, for $i<j<n$, if

$x_{i}+x_{j}>(n-1)+(n-2),\text{ then }x_{i}+x_{j}+x_{n}>n+(n-1)+(n-2),$

which contradicts (3). Thus, we have $x_{i}+x_{j}\leq(n-1)+(n-2)$ for $i<j<n$.
Continuing this process, we can refine the inequalities up through: for
$i_{1}<i_{2}<\cdots<i_{n-3}<n$, if

$x_{i_{1}}+x_{i_{2}}+\cdots+x_{i_{n-3}}>(n-1)+(n-2)+\cdots+3,$

then

$x_{i_{1}}+x_{i_{2}}+\cdots+x_{i_{n-3}}+x_{n}>n+(n-1)+(n-2)+\cdots+3,$

which contradicts (4). Thus, we have

$x_{i_{1}}+x_{i_{2}}+\cdots+x_{i_{n-3}}\leq(n-1)+(n-2)+\cdots+3.$

Lastly, consider if $x_{1}+x_{2}+\cdots+x_{n-1}>(n-1)+\cdots+1$. Then

$x_{1}+x_{2}+\cdots+x_{n-1}+x_{n}>n+(n-1)+\cdots+1,$

which contradicts (5). Thus,

$x_{1}+x_{2}+\cdots+x_{n-1}\leq(n-1)+\cdots+1.$

Collecting these results gives the following inequality description.

$\displaystyle 1\leq x_{i}$ $\displaystyle\leq n-1,$ $\displaystyle\text{ for
}1\leq i\leq n-1,$ $\displaystyle x_{i}+x_{j}$ $\displaystyle\leq(n-1)+(n-2),$
$\displaystyle\text{ for }i<j<n,$ $\displaystyle x_{i}+x_{j}+x_{k}$
$\displaystyle\leq(n-1)+(n-2)+(n-3),$ $\displaystyle\text{ for }i<j<k<n,$
$\displaystyle\vdots$ $\displaystyle x_{i_{1}}+x_{i_{2}}+\cdots+x_{i_{n-3}}$
$\displaystyle\leq(n-1)+(n-2)+\cdots+3,$ $\displaystyle\text{ for
}i_{1}<i_{2}<\cdots<i_{n-2}<n,$ $\displaystyle x_{1}+x_{2}+\cdots+x_{n-1}$
$\displaystyle\leq(n-1)+\cdots+1.$

This is exactly the inequality description for $\mathsf{PF}_{n-1}$. Hence,
$\mathsf{PF}_{n-1}$ is a facet of $\mathsf{PF}_{n}$. Now, as the choice of $i$
was arbitrary, there are $n$ choices for $i$, so there are $n$ copies of
$\mathsf{PF}_{n-1}$ appearing as facets of $\mathsf{PF}_{n}$.

Now we will show that these are the only occurrences. We know that
$\mathsf{PF}_{n-1}$ has $(n-1)!\sum\limits_{m=1}^{n-1}\frac{1}{m!}$ many
vertices. Similarly to the proof of Proposition 2.4, we can see that for a
hyperplane with $k$ variables, there are
$k!(n-k)!\sum\limits_{m=1}^{n-k}\frac{1}{m!}$ many vertices that satisfy it.
If $k$ is not equal to $1$ or $n$, we have $n\leq\binom{n}{k}$, thus
$k!(n-k)!\leq(n-1)!$. Then since

$k!(n-k)!\sum\limits_{m=1}^{n-k}\frac{1}{m!}<k!(n-k)!\sum\limits_{m=1}^{n-1}\frac{1}{m!}\leq(n-1)!\sum\limits_{m=1}^{n-1}\frac{1}{m!},$

these hyperplanes cannot correspond to a facet with
$(n-1)!\sum\limits_{m=1}^{n-1}\frac{1}{m!}$ many vertices. If $k=n$, then the
vertices that satisfy the equation are exactly all permutations of
$(1,2,\dots,n)$, which is $n!>(n-1)!\sum\limits_{m=1}^{n-1}\frac{1}{m!}$ many
vertices, hence this hyperplane cannot correspond to $\mathsf{PF}_{n-1}$.

For a hyperplane of the form $x_{i}=1$, there are
$\sum_{m=0}^{n-1}\frac{(n-1)!}{m!}\neq\sum_{m=1}^{n-1}\frac{(n-1)!}{m!}$ many
vertices that satisfy the equation, hence it also cannot correspond to
$\mathsf{PF}_{n-1}$. Thus, the only hyperplanes that support a facet of the
form $\mathsf{PF}_{n-1}$ are the $n$ mentioned above. ∎

###  2.2. Volume

Next, we consider a collection of related polytopes, called partial
permutahedra, which were first introduced in [8] in terms of partial
permutation matrices; a recursive volume formula was presented in [2]. For our
purposes, it suffices to consider their vertex description.

######  Definition 2.7 (Proposition 5.7, [8]; Proposition 2.6, [2]).

The _partial permutahedron_ $\mathcal{P}(n,p)$ is the polytope with all
permutations of the vectors

$(\underbrace{0,\ldots,0}_{n-k},\underbrace{p-k+1,\ldots,p-1,p}_{k}),$

for all $0\leq k\leq\min(n,p)$, as vertices.

Two integral polytopes $P\subseteq\mathbb{R}^{m}$ and
$Q\subseteq\mathbb{R}^{n}$ are _integrally equivalent_ if there exists an
affine transformation $\Phi:\mathbb{R}^{m}\rightarrow\mathbb{R}^{n}$ whose
restriction to $P$ preserves the lattice. We establish the following simple
result relating partial permutahedra and classical parking functions.

######  Proposition 2.8.

The classical parking function polytope $\mathsf{PF}_{n}$ is integrally
equivalent to the partial permutahedron $\mathcal{P}(n,n-1)$.

###### Proof.

Note that all vertices of $\mathcal{P}(n,n-1)$ given in Definition 2.7 map to
all vertices of $\mathsf{PF}_{n}$ by the translation
$(x_{1},x_{2},\ldots,x_{n})\mapsto(x_{1}+1,x_{2}+1,\ldots,x_{n}+1)$. ∎

We can now establish the equivalence of several different formulas throughout
the literature, as they count the normalized volume of the same polytope.
Additionally, while [1] provided the first answer to Stanley’s question to
find the volume of $\mathsf{PF}_{n}$ in [17], the following theorem gives the
first closed-form answer to Stanley’s question.

######  Theorem 2.9.

The following are equivalent normalized volume formulas for the classical
parking function polytope, where
$\operatorname{NVol}(\mathsf{PF}_{n}):=n!V_{n}$ denotes the normalized volume:

  1. (i)

From [1], with $\operatorname{NVol}(\mathsf{PF}_{0})=1$ and
$\operatorname{NVol}(\mathsf{PF}_{1})=0$, for $n\geq 2$ we have recursively,

$\operatorname{NVol}(\mathsf{PF}_{n})=(n-1)!\sum_{k=0}^{n-1}\binom{n}{k}\frac{(n-k)^{n-k-1}(n+k-1)}{2}\frac{\operatorname{NVol}(\mathsf{PF}_{k})}{k!}.$

  2. (ii)

From [2], for $\mathcal{P}(n,n-1)$, with
$\operatorname{NVol}(\mathsf{PF}_{0})=1$ and
$\operatorname{NVol}(\mathsf{PF}_{1})=0$, for $n\geq 2$ we have recursively,

$\operatorname{NVol}(\mathsf{PF}_{n})=(n-1)!\sum_{k=1}^{n}k^{k-2}\frac{\operatorname{NVol}(\mathsf{PF}_{n-k})}{(n-k)!}\left(k(n-1)-\binom{k}{2}\right)\binom{n}{k}.$

  3. (iii)

$\operatorname{NVol}(\mathsf{PF}_{n})=-\frac{n!}{2^{n}}\sum_{i=0}^{n}\binom{n}{i}(2i-3)!!(2n-1)^{n-i}.$

  4. (iv)

From [15], equation (33), for $n\geq 2$,

$\operatorname{NVol}(\mathsf{PF}_{n})=\frac{n!}{2^{n}}\sum_{i=0}^{n}(2i-1)(2i-1)!!\binom{n}{i}(2n-1)^{n-i-1}.$

  5. (v)

From [15], equation (23), for $n\geq 2$,

$\operatorname{NVol}(\mathsf{PF}_{n})=n!\frac{n-1}{2^{n-1}}\sum_{i=0}^{n-2}(2i+1)!!\binom{n-2}{i}(2n-1)^{n-i-2}.$

  6. (vi)

From [15], $\operatorname{NVol}(\mathsf{PF}_{n})$ equals the number of
$n\times n$ $(0,1)$-matrices with two 1’s in each row that have positive
permanent.

###### Proof.

Proposition 2.8 implies $(i)\iff(ii)$. In the next section, we show Theorem
1.1, which by taking $a=1$ and $b=1$ implies $(i)\iff(iii)$.

Next, $(iv)\iff(v)\iff(vi)$ is given in cite [15].

We finish by showing that $(iii)\iff(iv)$. This is equivalent to showing that
their difference is $0$. From $(iv)$, subtract $(iii)$, which gives

$\displaystyle\frac{n!}{2^{n}}\sum_{i=0}^{n}(2i-1)(2i-1)!!\binom{n}{i}(2n-1)^{n-i-1}+\frac{n!}{2^{n}}\sum_{i=0}^{n}\binom{n}{i}(2i-3)!!(2n-1)^{n-i}$
$\displaystyle=\frac{n!}{2^{n}}\sum_{i=0}^{n}\binom{n}{i}(2i-3)!!(2n-1)^{n-i-1}[(2i-1)^{2}+(2n-1)]$
$\displaystyle=\frac{n!}{2^{n}}\sum_{i=0}^{n}\binom{n}{i}\frac{(2i)!}{2^{i}i!(2i-1)}(2n-1)^{n-i-1}[(2i-1)^{2}+(2n-1)].$

We now use Wilf-Zeilberger theory. We need only show that
$f(n):=\sum_{i=0}^{n}F(n,i)$ is $0$, where

$F(n,i):=\binom{n}{i}\frac{(2i)!}{2^{i}i!(2i-1)}(2n-1)^{n-i-1}[(2i-1)^{2}+(2n-1)].$

Note that as $F(n,i)$ contains a binomial coefficient, the sum
$f(n)=\sum_{i\in\mathbb{Z}}F(n,i)$. We use Zeilberger’s creative telescoping
algorithm ct in the package EKHAD as described in Chapter 6.5 of [12] and
available from [23]. Calling

ct(binomial(n,i)*(2*i)!*(2*n-1)^(n-i-1)*
((2*i-1)^2+(2*n-1))/(2^i*i!*(2*i-1)),0,i,n,N);

in Maple gives output $1\cdot f(n)+0\cdot f(n+1)=0$, that is $f(n)=0$, with
certificate $R(n,i)=(-2n+1)i/(2i^{2}-2i+n)$. If we wish to check our solution,
let $G(n,i):=R(n,i)\cdot F(n,i)$. Then one can verify that
$1=(G(n,i+1)-G(n,i))/F(n,i)$ via some algebra. ∎

The sequence for the normalized volume of $\mathsf{PF}_{n}$ begins

$0,1,24,954,59040,5295150,651354480,105393619800,21717404916480,\ldots$

and is OEIS sequence A174586 [10].

##  3\. The convex hull of $\mathbf{x}$-parking functions

Next, we discuss a generalization of the classical parking functions. Let
$\mathbf{x}=(x_{1},\dots,x_{n})\in\mathbb{Z}_{>0}^{n}$. Define an
$\mathbf{x}$_-parking function_ to be a sequence $(a_{1},\dots,a_{n})$ of
positive integers whose nondecreasing rearrangement $b_{1}\leq
b_{2}\leq\cdots\leq b_{n}$ satisfies $b_{i}\leq x_{1}+\cdots+x_{i}$. As
mentioned in [21], from work of Pitman and Stanley [18], the number of
$\mathbf{x}$-parking functions for $\mathbf{x}=(a,b,b,\ldots,b)$ is the
following:

######  Theorem 3.1 (Theorem 1, [21]).

For $\mathbf{x}=(a,b,b,\ldots,b)\in\mathbb{Z}_{>0}^{n}$, the number of
$\mathbf{x}$-parking functions is given by $a(a+nb)^{n-1}$.

The following definition introduces an $n$-dimensional polytope associated to
$\mathbf{x}$-parking functions of length $n$ for the specific sequence
$\mathbf{x}=(a,b,b,\dots,b)\in\mathbb{Z}_{>0}^{n}$, which is one of the main
objects of study in this paper. We remark that we focus on
$\mathbf{x}=(a,b,b,\dots,b)$ following the work of Yan [20, 21].

######  Definition 3.2.

Define the _$\mathbf{x}$ -parking function polytope_ $\mathcal{X}_{n}(a,b)$ as
the convex hull of all $\mathbf{x}$-parking functions of length $n$ in
$\mathbb{R}^{n}$ for $\mathbf{x}=(a,b,b,\dots,b)\in\mathbb{Z}_{>0}^{n}$. See
Figure 2 for examples.

######  Remark 3.3.

Note that if $n=1$, $\mathbf{x}=(a)$, so no $b$ is used. As a result, we may
denote the $\mathbf{x}$-parking function polytope $\mathcal{X}_{1}(a,b)$
alternatively by $\mathcal{X}_{1}(a)$.

Figure 2. The $\mathbf{x}$-parking function polytopes, from left to right:
$\mathcal{X}_{3}(1,1)$, $\mathcal{X}_{3}(1,2)$, $\mathcal{X}_{3}(2,1)$, and
$\mathcal{X}_{3}(2,2)$. Observe that $\mathcal{X}_{3}(1,2)$ is a dilate of
$\mathcal{X}_{3}(1,1)$. Note that when $a>1$, there are new facets that do not
appear when $a=1$.

###  3.1. Face structure

In this subsection we describe the face structure of the _$\mathbf{x}$
-parking function polytope_ $\mathcal{X}_{n}(a,b)$.

From Theorem 3.1, we obtain an upper bound for the number of
$\mathbf{x}$-parking functions which arise as vertices of
$\mathcal{X}_{n}(a,b)$ since it is well-known that if a polytope can be
written as the convex hull of a finite set of points, then the set contains
all the vertices of the polytope (Proposition 2.2, [24]). We now give a vertex
description of $\mathcal{X}_{n}(a,b)$.

######  Proposition 3.4.

The vertices of $\mathcal{X}_{n}(a,b)$ are all permutations of

$(\underbrace{1,\ldots,1}_{k},\underbrace{a+kb,a+(k+1)b,\ldots,a+(n-2)b,a+(n-1)b}_{n-k}),$

for all $0\leq k\leq n$.

###### Proof.

Consider an $\mathbf{x}$-parking function $x=(x_{1},\ldots,x_{n})$ for which
there is a term $x_{i}>1$ such that
$(x_{1},\ldots,x_{i-1},x_{i}+1,x_{i+1},\ldots,x_{n})$ is also an
$\mathbf{x}$-parking function. Then $x$ is a convex combination of two other
$\mathbf{x}$-parking functions. Second, if

$x=(\underbrace{1,\ldots,1}_{k},\underbrace{a+kb,a+(k+1)b,\ldots,a+(n-2)b,a+(n-1)b}_{n-k})$

is a convex combination of $y,z\in\mathcal{X}_{n}(a,b)$, then $x=y=z$, as the
first $k$ coordinates of $x$ are minimal at 1 and the last $(n-k)$ coordinates
are maximized due to the condition on the nondecreasing rearrangement of
$\mathbf{x}$-parking functions. Thus, $x$ is a vertex of
$\mathcal{X}_{n}(a,b)$. ∎

Next, we enumerate the vertices of $\mathcal{X}_{n}(a,b)$. In the case that
$a=1$, we have the same number of vertices as in the case of the classical
parking function polytope $\mathsf{PF}_{n}$, as $b$ is a parameter that
increases the lengths of the edges of the polytope. However, when $a>1$, new
vertices and edges come into play.

######  Proposition 3.5.

The number of vertices of $\mathcal{X}_{n}(a,b)$ is

$\begin{cases}n!\left(\frac{1}{1!}+\cdots+\frac{1}{n!}\right)&\text{if }a=1\\\
n!\left(\frac{1}{0!}+\frac{1}{1!}+\cdots+\frac{1}{n!}\right)&\text{if
}a>1.\end{cases}$

###### Proof.

The vertices are the permutations of the following:

$\displaystyle v_{0}$ $\displaystyle=(\underbrace{1,\ldots,1}_{n}),$
$\displaystyle v_{1}$
$\displaystyle=(\underbrace{1,\ldots,1}_{n-1},a+(n-1)b),$ $\displaystyle
v_{2}$ $\displaystyle=(\underbrace{1,\ldots,1}_{n-2},a+(n-2)b,a+(n-1)b),$
$\displaystyle\vdots$ $\displaystyle v_{n-1}$
$\displaystyle=(1,\underbrace{a+b,\ldots,a+(n-1)b}_{n-1}),$ $\displaystyle
v_{n}$ $\displaystyle=(a,\underbrace{a+b,\ldots,a+(n-1)b}_{n-1}).$

Observe that there is one permutation of $v_{0}$, $n$ permutations of $v_{1}$,
$n(n-1)$ permutations of $v_{2}$, and in general, $n(n-1)\cdots(n-k+1)$
permutations of $v_{k}$. If $a>1$, then the vertices $v_{n-1}$ and $v_{n}$ are
distinct, so we count the contribution of both. However, if $a=1$, then
$v_{n-1}=v_{n}$, and we only count one. For $a>1$, this gives

$\displaystyle 1+n+n(n-1)+\cdots+\left(n(n-1)\cdots
2\right)+\left(n(n-1)\cdots 2\cdot 1\right)$
$\displaystyle=n!\left(\frac{1}{n!}+\frac{1}{(n-1)!}+\frac{1}{(n-2)!}+\cdots+\frac{1}{1!}+\frac{1}{0!}\right),$

and for $a=1$,

$\displaystyle 1+n+n(n-1)+\cdots+\left(n(n-1)\cdots 2\right)$
$\displaystyle=n!\left(\frac{1}{n!}+\frac{1}{(n-1)!}+\frac{1}{(n-2)!}+\cdots+\frac{1}{1!}\right).$

∎

We continue by presenting an inequality description of $\mathcal{X}_{n}(a,b)$.

######  Proposition 3.6.

The $\mathbf{x}$-parking function polytope $\mathcal{X}_{n}(a,b)$ is given by
the following minimal inequality description:

_For all_ $1\leq i\leq n$, $\displaystyle 1$ $\displaystyle\leq
x_{i}\leq(n-1)b+a,$ _for all_ $1\leq i<j\leq n$, $\displaystyle x_{i}+x_{j}$
$\displaystyle\leq\left((n-2)b+a\right)+\left((n-1)b+a\right),$ _for all_
$1\leq i<j<k\leq n$, $\displaystyle x_{i}+x_{j}+x_{k}$
$\displaystyle\leq\left((n-3)b+a\right)+\left((n-2)b+a\right)+\left((n-1)b+a\right),$
$\displaystyle\vdots$ _for all_ $1\leq i_{1}<i_{2}<\cdots<i_{n-2}\leq n$,
$\displaystyle x_{i_{1}}+x_{i_{2}}+\cdots+x_{i_{n-2}}$
$\displaystyle\leq(2b+a)+\cdots+\left((n-2)b+a\right)+\left((n-1)b+a\right),$
_if $a>1$, for all_ $1\leq i_{1}<i_{2}<\cdots<i_{n-1}\leq n$, $\displaystyle
x_{i_{1}}+x_{i_{2}}+\cdots+x_{i_{n-1}}$
$\displaystyle\leq(b+a)+\cdots+\left((n-2)b+a\right)+\left((n-1)b+a\right),$
_and (regardless of $a$),_ $\displaystyle x_{1}+x_{2}+\cdots+x_{n}$
$\displaystyle\leq a+\cdots+\left((n-2)b+a\right)+\left((n-1)b+a\right).$

###### Proof.

We use the vertex description given in Proposition 3.4, which states that the
vertices of $\mathcal{X}_{n}(a,b)$ are all permutations of

$(\underbrace{1,\ldots,1}_{k},\underbrace{a+kb,a+(k+1)b,\ldots,a+(n-2)b,a+(n-1)b}_{n-k})$

for all $0\leq k\leq n$.

First consider that since $a,b\geq 1$, all coordinates in a vertex of
$\mathcal{X}_{n}(a,b)$ are at least $1$, i.e., $1\leq x_{i}$ for all $1\leq
i\leq n$. Now, we turn our attention to inequalities that are solely upper
bounds, so we can assume that $k=0$ and only consider the largest possible
coordinates. The largest a single coordinate could be is $a+(n-1)b$, so
$x_{i}\leq a+(n-1)b$ for all $1\leq i\leq n$.

Next, summing the largest two coordinates is at most
$\left((n-2)b+a\right)+\left((n-1)b+a\right)$, so

$x_{i}+x_{j}\leq\left((n-2)b+a\right)+\left((n-1)b+a\right),\text{ for all
}1\leq i<j\leq n.$

Repeating the same process with summing the largest possible $3,\ldots,n$
variables, completes the inequality description.

Note that in the case that $a=1$, the inequality that bounds the sum of any
$n-1$ variables is not needed in the minimal inequality description. We
justify this as follows. Given that $a=1$, the inequality is that

$x_{i_{1}}+x_{i_{2}}+\cdots+x_{i_{n-1}}\leq\frac{n(n-1)}{2}b+n-1\text{ for all
}1\leq i_{1}<i_{2}<\cdots<i_{n-1}\leq n.$

Also, we always need the final inequality
$x_{1}+x_{2}+\cdots+x_{n}\leq\frac{n(n-1)}{2}b+n$. If we sum the $n-1$ largest
terms of

$(a,a+b,a+2b,\ldots,a+(n-2)b,a+(n-1)b),$

the only value that is not used is $a$, which in this case equals $1$. Hence,
the final inequality

$x_{1}+x_{2}+\cdots+x_{n}\leq\frac{n(n-1)}{2}b+n$

is sufficient, because removing one coordinate from the sum on its left hand
side subtracts $a=1$ from the right hand side, exactly yielding the inequality

$x_{i_{1}}+x_{i_{2}}+\cdots+x_{i_{n-1}}\leq\frac{n(n-1)}{2}b+n-1.$

Note that this only happens in the case that $a=1$ because if $a>1$, we are
able to get a tighter inequality when we subtract $a>1$ from the right hand
side as before.

We now show that the inequality description is minimal. Observe that by
construction for each of these defining inequalities, there exists an extremal
point of the polytope which gives equality. It is clear that the inequalities
$1\leq x_{i}$ in each coordinate are necessary, as they are the only lower
bounds on the coordinates. We only need to consider the minimality of the set
of inequalities which are upper bounds on partial sums of the coordinates. A
general inequality on $1\leq k\leq n$ variables says

$\displaystyle x_{i_{1}}+x_{i_{2}}+\cdots+x_{i_{k}}$ $\displaystyle\leq
b\left(nk-\frac{k^{2}+k}{2}\right)+ka$

for some variables $1\leq i_{1}<i_{2}<\cdots<i_{k}\leq n$. Observe that for
each of the inequalities on $k$ variables (and of course excluding the case of
$a=1$ and $k=n-1$), it is strictly stronger on at least one point than all
inequalities on $1,\ldots,k-1$ variables. Explicitly, a general inequality on
$1\leq k-1\leq n$ variables says

(6) $\displaystyle x_{i_{1}}+x_{i_{2}}+\cdots+x_{i_{k-1}}$ $\displaystyle\leq
b\left(n(k-1)-\frac{(k-1)^{2}+k-1}{2}\right)+(k-1)a$
$\displaystyle=b\left(nk-\frac{k^{2}+k}{2}+(k-n)\right)+ka-a$
$\displaystyle=b\left(nk-\frac{k^{2}+k}{2}\right)+ka+[b(k-n)-a].$

Note that adding one coordinate $x_{k}$ to the left hand side of (6) and
$a+(n-1)b$ to the right hand side gives

$\displaystyle x_{i_{1}}+x_{i_{2}}+\cdots+x_{i_{k}}$ $\displaystyle\leq
b\left(nk-\frac{k^{2}+k}{2}\right)+ka+[b(k-n)-a]+a+(n-1)b$
$\displaystyle=b\left(nk-\frac{k^{2}+k}{2}\right)+ka+b(k-1),$

which is a worse bound for all $k>1$ due to the $b(k-1)$ term. As we
constructed this inequality description in increasing order on the number of
variables, each one refining the previous, the inequality description is an
irredundant system of inequalities and is therefore minimal. ∎

Since we have a minimal inequality description of $\mathcal{X}_{n}(a,b)$, by
enumerating the number of defining inequalities we obtain a count for the
number of facets of $\mathcal{X}_{n}(a,b)$.

######  Corollary 3.7.

The number of facets of $\mathcal{X}_{n}(a,b)$ is $2^{n}-1$ if $a=1$ and
$2^{n}-1+n$ if $a>1$.

###### Proof.

It suffices to count the number of minimal defining inequalities given in
Proposition 3.6. Note that there are $\binom{n}{k}$ different inequalities
with $1<k<n-1$ or $k=n$ distinct variables. We have $2\binom{n}{1}$ many
inequalities with one variable since we have $1\leq x_{i}$ and
$x_{i}\leq(n-1)b+a$. If $a=1$, there are no inequalities in $n-1$ variables.
Then the number of inequalities is

$\binom{n}{1}+\binom{n}{1}+\binom{n}{2}+\cdots+\binom{n}{n-2}+\binom{n}{n}=2^{n}-1.$

If $a>1$, then there are $\binom{n}{n-1}$ inequalities in $n-1$ variables, so
the number of inequalities is

$\binom{n}{1}+\left[\binom{n}{1}+\binom{n}{2}+\cdots+\binom{n}{n-2}+\binom{n}{n-1}+\binom{n}{n}\right]=n+2^{n}-1.$

∎

Next we study the edges of $\mathcal{X}_{n}(a,b)$.

######  Definition 3.8.

Let $x$ be a vertex of $\mathcal{X}_{n}(a,b)$. Then it is a permutation of

$(1,\ldots,1,a+kb,a+(k+1)b,\ldots,a+(n-2)b,a+(n-1)b),$

for some unique $1\leq k\leq n$ if $a=1$ or $0\leq k\leq n$ if $a>1$. We say
that $x$ is on layer $n-k$. For $x=(1,\ldots,1)$, we say that it is on layer
0.

######  Lemma 3.9.

If $v,u$ are two vertices of $\mathcal{X}_{n}(a,b)$ such that $vu$ is an edge,
then the layers of $v$ and $u$ differ by at most 1.

###### Proof.

The proof follows almost identically to that of Proposition 2.1 in [1] in the
case that $a=1$. In the case that $a>1$, there is just one more layer to
address.

Let $c\cdot x=c_{1}x_{1}+\cdots+c_{n}x_{n}$ be the dot product of vectors
$c,x\in\mathbb{R}^{n}$. If $vu$ is an edge, then there exists
$c\in\mathbb{R}^{n}$ such that $c\cdot v=c\cdot u>c\cdot w$ for any vertex $w$
of $\mathcal{X}_{n}(a,b)$ such that $w\neq v,u$. Note that
$\mathcal{X}_{n}(a,b)$ is invariant under permutation of the coordinates, so
without loss of generality, assume that $c_{1}\leq c_{2}\leq\cdots\leq c_{n}$.

Suppose for the sake of contradiction that $v,u$ are $t\geq 2$ layers apart.
Without loss of generality, suppose that $u$ is below $v$. Hence, $v$ is (up
to permutation)

$(1,\ldots,1,a+kb,a+(k+1)b,\ldots,a+(n-2)b,a+(n-1)b),$

and $u$ is (up to permutation)

$(1,\ldots,1,a+(k+t)b,a+(k+t+1)b,\ldots,a+(n-2)b,a+(n-1)b),$

where $1\leq k<k+2\leq k+t\leq n$ if $a=1$ and $0\leq k<k+2\leq k+t\leq n$ if
$a>1$. Specifically, since $v,u$ uniquely maximizes $c\cdot x$, then by the
rearrangement inequality, $v$ and $u$ are exactly

$(1,\ldots,1,a+kb,a+(k+1)b,\ldots,a+(n-2)b,a+(n-1)b),$

and

$(1,\ldots,1,a+(k+t)b,a+(k+t+1)b,\ldots,a+(n-2)b,a+(n-1)b),$

respectively (not just up to permutation), and $c_{k-1}<c_{k}<\cdots<c_{n}$.
Consider two cases. First, if $c_{k+t-1}\geq 0$, then for
$w=(1,\ldots,1,a+(k+t-1)b,a+(k+t)b,\ldots,a+(n-2)b,a+(n-1)b)\in\mathcal{X}_{n}(a,b)$
which is not equal to $v,u$, we have that $c\cdot w\geq c\cdot u$, a
contradiction. Otherwise, if $c_{k+t-1}<0$, we have
$c_{k}<\cdots<c_{k+t-1}<0$, so $c\cdot v-c\cdot
u=c_{k}(a+kb-1)+c_{k+1}(a+(k+1)b-1)+\cdots+c_{k+t-1}(a+(k+t-1)b-1)<0$. This
implies $c\cdot v<c\cdot u$, a contradiction. ∎

######  Remark 3.10.

For fixed $n$, if $a=1$, then regardless of the value for $b$, there are the
same number of layers. If $a>1$, then regardless of the value for $b$, there
are the same number of layers, which is one more than in the case where $a=1$.

######  Proposition 3.11.

For each vertex $v$ of $\mathcal{X}_{n}(a,b)$, there are exactly $n$ edges of
$\mathcal{X}_{n}(a,b)$ with $v$ as one of the vertices. That is,
$\mathcal{X}_{n}(a,b)$ is a simple polytope.

###### Proof sketch.

In the case that $a=1$, the proof is identical to the proof of Proposition 2.2
in [1], where all instances of coordinates $(1,\ldots,1,k+1,k+2,\ldots,n-1,n)$
are replaced by $(1,\ldots,1,1+kb,1+(k+1)b,\ldots,1+(n-2)b,1+(n-1)b)$. The
same proof works because $a=1$, so no new layers are introduced.

In the case that $a>1$, there is one more layer to address, as
$(1,a+b,a+2b,\ldots,a+(n-2)b,a+(n-1)b)\neq(a,a+b,a+2b,\ldots,a+(n-2)b,a+(n-1)b)$
are distinct now. By modifying the proof from the case of $a=1$, one only
needs to check that layers $n-2$, $n-1$ (the new layer, meaning the layer that
causes new facets to appear), and $n$ have vertices with the correct number of
edges. ∎

######  Proposition 3.12.

The number of edges of $\mathcal{X}_{n}(a,b)$ is
$\frac{n}{2}\operatorname{Ver}(\mathcal{X}_{n}(a,b))$, where
$\operatorname{Ver}(\mathcal{X}_{n}(a,b))$ denotes the number of vertices
$\mathcal{X}_{n}(a,b)$.

###### Proof.

By Proposition 3.11, the graph of $\mathcal{X}_{n}(a,b)$ is an $n$-regular
graph. This gives the desired formula, where the number of vertices is given
by Proposition 3.5. ∎

Up to this point we have the number of $0$-dimensional faces (vertices), the
$1$-dimensional faces (edges), and $(n-1)$-dimensional facets (facets). In
what comes next, we study the faces of higher dimension.

######  Proposition 3.13.

Let $f_{k}$ be the number of $k$-dimensional faces of $\mathcal{X}_{n}(a,b)$
for $k\in\\{0,\ldots,n\\}$. Then if $a=1$,

$f_{k}=\sum_{m=0,\ m\neq 1}^{n-k}\binom{n}{m}\cdot(n-k-m)!\cdot
S(n-m+1,n-k-m+1),$

and if $a>1$,

$f_{k}=\sum_{m=0}^{n-k}\binom{n}{m}\cdot(n-k-m)!\cdot S(n-m+1,n-k-m+1),$

where $S(n,k)$ are the Stirling numbers of the second kind.

###### Proof sketch.

In the case that $a=1$, the proof is identical to the proof of Theorem 3.1 in
[1], where all instances of coordinates $(1,\ldots,1,k+1,k+2,\ldots,n-1,n)$
are replaced by $(1,\ldots,1,1+kb,1+(k+1)b,\ldots,1+(n-2)b,1+(n-1)b)$. The
same proof works because $a=1$, so no new layers are introduced, and thus no
new faces are introduced.

In the case that $a>1$, there is one more layer to address, as
$(1,a+b,a+2b,\ldots,a+(n-2)b,a+(n-1)b)\neq(a,a+b,a+2b,\ldots,a+(n-2)b,a+(n-1)b)$
are distinct now. By modifying the proof from the case of $a=1$, the
restriction given in Lemma 3.1 in [1] which causes $m=1$ to be excluded from
the sum in the proof of Theorem 3.1 in [1] is removed due to the additional
layer. ∎

The faces of a convex polytope $P$ form a lattice called its _face lattice_ ,
denoted by $\mathcal{F}(P)$, where the partial ordering is given by set
inclusion of the faces. Two polytopes whose face lattices are isomorphic (as
unlabeled partially ordered sets) are _combinatorially equivalent_. We
continue with a characterization of which $\mathcal{X}_{n}(a,b)$ are
combinatorially equivalent.

######  Proposition 3.14.

For fixed $n$ and for $a=1$, the $\mathcal{X}_{n}(1,b)$ are combinatorially
equivalent for all $b\geq 1$. Additionally, for fixed $n$, the
$\mathcal{X}_{n}(a,b)$ are combinatorially equivalent for all $a>1$ and $b\geq
1$.

###### Proof.

By Proposition 3.13, for each $b$, the face lattice of $\mathcal{X}_{n}(1,b)$
has the same number of elements, and the same number of elements at each level
corresponding to the dimension of the face. For a face lattice, the join of
two elements in the same layer will be in the layer above it, and the meet of
two elements in the same layer will be in the layer below it, as face
inclusions pass through faces of one dimension more/less (face inclusions of
faces of the same dimension result in equality). Thus, it only remains to
construct the isomorphism. Define
$\varphi:\mathcal{F}(\mathcal{X}_{n}(1,b_{1}))\to\mathcal{F}(\mathcal{X}_{n}(1,b_{2}))$
by replacing $b_{1}$ by $b_{2}$ in the vertex description of each face in the
face lattice. It is clear that this is an isomorphism, as the inverse is given
by replacing $b_{2}$ by $b_{1}$. Therefore, the $\mathcal{X}_{n}(1,b)$ are
combinatorially equivalent for $a=1$ and for any $b\geq 1$.

Similarly as before, for all $a>1$, we define
$\varphi:\mathcal{F}(\mathcal{X}_{n}(a_{1},b_{1}))\to\mathcal{F}(\mathcal{X}_{n}(a_{2},b_{2}))$
by replacing $a_{1}$ by $a_{2}$ and $b_{1}$ by $b_{2}$ in the vertex
description of each face in the face lattice. Hence, the
$\mathcal{X}_{n}(a,b)$ are combinatorially equivalent for any $a>1$ and for
all $b\geq 1$. ∎

###  3.2. Volume

We turn our attention to calculating the volume of $\mathbf{x}$-parking
function polytopes $\mathcal{X}_{n}(a,b)$. We extend previous work of [1] to
find a recursive volume formula in Theorem 3.22. Then, by using exponential
generating functions, we find a closed-form expression for the volume of
$\mathcal{X}_{n}(a,b)$ in Theorem 1.1. We also consider the relationship
between the $\mathbf{x}$-parking function polytopes and partial permutahedra,
allowing us to expand known results on the volume of partial permutahedra. The
relationship between partial permutahedra and $\mathbf{x}$-parking function
polytopes is given by the following proposition.

######  Proposition 3.15.

Up to integral equivalence, the intersection of the set of all partial
permutahedra $\mathcal{P}(n,p)$ with the set of $\mathbf{x}$-parking function
polytopes corresponds to those partial permutahedra $\mathcal{P}(n,p)$ where
$p\geq n-1$ and those $\mathbf{x}$-parking functions where $b=1$ (for $n>1$).

Specifically, if $n\geq 2$ and $p\geq n-1$, then $\mathcal{P}(n,p)$ is
integrally equivalent to $\mathcal{X}_{n}(a,b)$ if and only if $b=1$ and
$a=p-n+2$. If $n=1$ and $p\geq n-1$, then $\mathcal{P}(1,p)$ is integrally
equivalent to $\mathcal{X}_{1}(a)$ if and only if $a=p+1$.

###### Proof.

First, recall from Remark 3.3 that when $n=1$ for an $\mathbf{x}$-parking
function, $b$ is unused. The case $n=1$ is clear, as these polytopes are just
1-dimensional line segments of length $a-1=p$. Thus, we reduce to the case
that $n\geq 2$.

For two polytopes to be integrally equivalent, they must have the same
dimension (relative to its affine span), which justifies using $n$ to denote
the dimension for both.

We will show that the conditions $b=1,a=p-n+2$ are necessary for
$\mathcal{P}(n,p)$ and $\mathcal{X}_{n}(a,b)$ to be integrally equivalent by
comparing “maximal” vertices. Apply the coordinate transformation to increase
the each coordinate by one in $\mathcal{P}(n,p)$ (as in the proof of
Proposition 2.8) to match the minimal vertices of the two polytopes. Consider
the “maximal” vertices

$v=(a,a+b,\ldots,a+(n-2)b,a+(n-1)b)$

of $\mathcal{X}_{n}(a,b)$ and $u=(\max(p-n+2,1),\ldots,p,p+1)$ of the shifted
$\mathcal{P}(n,p)$, where “maximal” means the maximal vertex where all the
coordinates are weakly increasing. If the two polytopes are integrally
equivalent, we must have $v=u$. If $b\neq 1$, the difference between the last
two coordinates of $v$ is $b\geq 2$ while the difference between the last two
coordinates of $u$ is 1, thus $u\neq v$. Hence, $b=1$ is a necessary
condition.

Furthermore, consider $a\neq p-n+2$. If $n\leq p+1$, the first coordinate of
$u$ is $\max(p-n+2,1)=p-n+2$, which gives us $u\neq v$. If $n>p+1$, we can see
that $\max(p-n+2,1)=1$. Additionally, the second coordinate of $u$ is at most
$1$, since $(p-n+2)+1\leq 1$. Thus we have the first two coordinates of $u$
must be 1. However, the first two coordinates of $u$ are $a,a+b$, where $b$ is
nonzero, thus $u\neq v$.

Hence, the conditions $b=1$, and $a=p-n+2$ are necessary for
$\mathcal{P}(n,p)=\mathcal{X}_{n}(a,b)$.

We next show that they are sufficient. Consider $\mathcal{X}_{n}(a,b)$ where
$b=1$, and $a=p-n+2$. Note that this second condition implies $n\leq p+1$.
Using the vertex description of Proposition 3.4, we can consider
$\mathcal{X}_{n}(a,b)$ to be the convex hull of all permutations of

$(\underbrace{1,\ldots,1}_{k},\underbrace{p-n+k+2,p-n+k+3,\ldots,p,p+1}_{n-k}),$

for all $0\leq k\leq n$. Since $n\leq p+1$ implies min$(n,p)=n$, this is
exactly the vertex description of shifted $\mathcal{P}(n,p)$. ∎

We now recall the recursive volume formula for the classical parking function
polytope.

######  Theorem 3.16 (Theorem 4.1, [1]).

Define a sequence $\\{V_{n}\\}_{n\geq 0}$ by $V_{0}=1$ and
$V_{n}=\operatorname{Vol}(\mathsf{PF}_{n})$ for all positive integers $n$.
Then $V_{1}=0$ and for all $n\geq 2$,

$V_{n}=\frac{1}{n}\sum_{k=0}^{n-1}\binom{n}{k}\frac{(n-k)^{n-k-1}(n+k-1)}{2}V_{k}.$

We are able to obtain some immediate corollaries of these results by
considering dilations of $\mathsf{PF}_{n}$.

######  Definition 3.17.

For any positive integer $d$, the $d$-dilate of an $\mathbf{x}$-parking
function polytope $\mathcal{X}_{n}(a,b)$ is given by the following map on
points $\varphi_{d}:\mathbb{R}^{n}_{\geq 1}\to\mathbb{R}^{n}_{\geq 1}$ defined
by

$(x_{1},\ldots,x_{n})\mapsto(d(x_{1}-1)+1,\ldots,d(x_{n}-1)+1).$

In general, a $d$-dilate of any polytope is the image of a map which (up to
translation) multiplies all coordinates by $d$.

######  Lemma 3.18.

  1. (1)

The $\mathbf{x}$-parking function polytope $\mathcal{X}_{n}(1,b)$ is a
$b$-dilate of $\mathcal{X}_{n}(1,1)$.

  2. (2)

Fix $a\geq 1$. The $\mathbf{x}$-parking function polytope
$\mathcal{X}_{n}(a+(b-1)(a-1),b)$ is a $b$-dilate of $\mathcal{X}_{n}(a,1)$.

###### Proof.

This follows from applying the $b$-dilate map $\varphi_{b}$ onto all the
vertices of $\mathcal{X}_{n}(1,1)$ and $\mathcal{X}_{n}(a,1)$ given by
Proposition 3.4, which results in all the vertices of $\mathcal{X}_{n}(1,b)$
and $\mathcal{X}_{n}(a+(b-1)(a-1),b)$. ∎

Knowing that one polytope is a dilate of another allows for more direct
approach to finding volumes for some of these parking function polytopes.

######  Corollary 3.19.

  1. (1)

Fix a positive integer $b$. Then
$\operatorname{Vol}(\mathcal{X}_{n}(1,b))=b^{n}\operatorname{Vol}(\mathcal{X}_{n}(1,1))$.

  2. (2)

Fix positive integers $a,b$. Then
$\operatorname{Vol}(\mathcal{X}_{n}(a+(b-1)(a-1),b))=b^{n}\operatorname{Vol}(\mathcal{X}_{n}(a,1))$.

###### Proof.

Note that the dilation of an $n$-dimensional polytope by a factor of $b$
increases the volume by a factor of $b^{n}$. The result then follows from
Lemma 3.18. ∎

Using the following result on partial permutahedra, we can then calculate the
volume of more $\mathbf{x}$-parking function polytopes.

######  Theorem 3.20 (Theorem 4.2, [2]).

For any $n$ and $p$ with $p\geq n-1$, the normalized volume of
$\mathcal{P}(n,p)$ is given recursively by

$\operatorname{NVol}(\mathcal{P}(n,p))=(n-1)!\sum_{k=1}^{n}k^{k-2}\frac{\operatorname{NVol}(\mathcal{P}(n-k,p-k))}{(n-k)!}\left(kp-\binom{k}{2}\right)\binom{n}{k},$

with the initial condition $\operatorname{NVol}(\mathcal{P}(0,p))=1$.

######  Remark 3.21.

By Proposition 3.15, $\mathcal{X}_{n}(a,1)$ for $a>1$ is integrally equivalent
to $\mathcal{P}(n,p)$ where $p=n+a-2>n-1$. Thus, the volume
$\operatorname{Vol}(\mathcal{X}_{n}(a+(b-1)(a-1),b))$ can be calculated using
Corollary 3.19(2), and converting between volume and normalized volume.

These results, however, do not give $\operatorname{Vol}(\mathcal{X}_{n}(a,b))$
for all $a,b\geq 1$. To do so, we need a more general construction, which is
given by the following recursive volume formula.

######  Theorem 3.22.

Fix two positive integers $a,b$. Define a sequence $\\{V_{n}^{a,b}\\}_{n\geq
0}$ by $V^{a,b}_{0}=1$ and
$V^{a,b}_{n}=\operatorname{Vol}(\mathcal{X}_{n}(a,b))$ for all positive
integers $n$. Then $V^{a,b}_{1}=a-1$ and for $n\geq 2$, $V^{a,b}_{n}$ is given
recursively by

$V_{n}^{a,b}=\frac{1}{n}\sum_{k=0}^{n-1}\binom{n}{k}\frac{(b(n-k))^{n-k-1}(nb+kb-b+2a-2)}{2}V^{a,b}_{k}.$

In the proof of this theorem, we will use the following decomposition lemma.

######  Lemma 3.23 (Proposition 4.1, [1]; Proposition 2, [6]; Section 19.4,
[5]).

Let $K_{1},\ldots,K_{n}$ be some convex bodies of $\mathbb{R}^{n}$ and suppose
that $K_{n-m+1,\ldots,K_{n}}$ are contained in some $m$-dimensional affine
subspace $U$ of $\mathbb{R}^{n}$. Let $MV_{U}$ denote the mixed volume with
respect to the $m$-dimensional volume measure on $U$, and let $MV_{U^{\perp}}$
be defined similarly with respect to the orthogonal complement $U^{\perp}$ of
$U$. Then the mixed volume of $K_{1},\ldots,K_{n}$

$\displaystyle MV(K_{1},\ldots,K_{n-m},K_{n-m+1},\ldots,K_{n})$
$\displaystyle=\binom{n}{m}^{-1}MV_{U^{\perp}}(K_{1}^{\prime},\ldots,K_{n-m}^{\prime})MV_{U}(K_{n-m+1,\ldots,K_{n}),}$

where $K_{1}^{\prime},\ldots,K_{n-m}^{\prime}$ denote the orthogonal
projections of $K_{1},\ldots,K_{n-m}$ onto $U^{\perp}$, respectively.

We will also use the following fact.

######  Lemma 3.24 (Lemma 4.1, [2]).

The Euclidean volume of the regular permutahedron
$\Pi_{n}\subseteq\mathbb{R}^{n}$ is $n^{n-2}\sqrt{n}$.

###### Proof of Theorem 3.22.

The case where $a=1$ follows from Theorem 3.16 and Corollary 3.19(1). They
imply that

$\displaystyle V^{1,b}_{n}$ $\displaystyle=b^{n}V_{n}$
$\displaystyle=\frac{b^{n}}{n}\sum_{k=0}^{n-1}\binom{n}{k}\frac{(n-k)^{n-k-1}(n+k-1)}{2}V_{k}$
$\displaystyle=\frac{b^{n}}{n}\sum_{k=0}^{n-1}\binom{n}{k}\frac{(n-k)^{n-k-1}(n+k-1)}{2}\frac{V^{1,b}_{k}}{b^{k}}$
$\displaystyle=\frac{1}{n}\sum_{k=0}^{n-1}\binom{n}{k}\frac{b^{n-k}(n-k)^{n-k-1}(n+k-1)}{2}V^{1,b}_{k}.$

For the case where $a>1$, we generalize the proof of Theorem 4.1 in [1].
Divide $\mathcal{X}_{n}(a,b)$ into $n$-dimensional (full dimensional) pyramids
with facets of $\mathcal{X}_{n}(a,b)$ which do not contain $I=(1,\ldots,1)$ as
the base, and point $I$ as a vertex. Recall from Theorem 3.7 that there are
$2^{n}-1+n$ facets since $a>1$. Of those, exactly $n$ have $I$ as a vertex, so
the number of pyramids is $2^{n}-1$. Each pyramid has a base which is a facet
$F$ with points of $\mathcal{X}_{n}(a,b)$ satisfying the equation

$x_{i_{1}}+x_{i_{2}}+\cdots+x_{i_{k}}=((n-k)b+a)+\cdots+((n-2)b+a)+((n-1)b+1),$

for some $k\in\\{1,2,\ldots,n-1,n\\}$ and distinct $i_{1}<\cdots<i_{k}$, due
to the defining inequalities of $\mathcal{X}_{n}(a,b)$.

Now let
$\\{j_{1},j_{2},\ldots,j_{n-k}\\}=\\{1,2,\ldots,n\\}\setminus\\{i_{1},i_{2},\ldots,i_{k}\\}$.
Let $\mathcal{X}^{\prime}_{n-k}(a,b)$ be the polytope containing all points
$x^{\prime}$ such that $x_{p}^{\prime}=0$ for all
$p\in\\{i_{1},i_{2},\ldots,i_{k}\\}$ and for some $x\in F$,
$x_{p}^{\prime}=x_{p}$ for all $p\in\\{j_{1},j_{2},\ldots,j_{n-k}\\}$. Then
$\mathcal{X}^{\prime}_{n-k}(a,b)$ is an $(n-k)$-dimensional polytope, with the
following defining inequalities:

_For all_ $1\leq p\leq n-k$, $\displaystyle 1\leq x_{j_{p}}^{\prime}$
$\displaystyle\leq((n-k-1)b+a),$ _for all_ $1\leq p<q\leq n-k$, $\displaystyle
x_{j_{p}}^{\prime}+x_{j_{q}}^{\prime}$
$\displaystyle\leq((n-k-2)b+a)+((n-k-1)b+a),$ _for all_ $1\leq p<q<r\leq n-k$,
$\displaystyle x_{j_{p}}^{\prime}+x_{j_{q}}^{\prime}+x_{j_{r}}^{\prime}$
$\displaystyle\leq((n-k-3)b+a)+((n-k-2)b+a)+((n-k-1)b+a),$
$\displaystyle\vdots$ _for all_ $1\leq p_{1}<p_{2}<\cdots<p_{n-k-1}\leq n-k$,
$\displaystyle
x_{j_{p_{1}}}^{\prime}+x_{j_{p_{2}}}^{\prime}+\cdots+x_{j_{p_{n-k-1}}}^{\prime}$
$\displaystyle\leq(b+a)+(2b+a)+\cdots+((n-k-1)b+a),$ _and_ $\displaystyle
x_{j_{p_{1}}}^{\prime}+x_{j_{p_{2}}}^{\prime}+\cdots+x_{j_{p_{n-k}}}^{\prime}$
$\displaystyle\leq a+(b+a)+\cdots+((n-k-1)b+a).$

By comparing with the inequality description given in Proposition 3.6, we see
that $\mathcal{X}^{\prime}_{n-k}(a,b)\cong\mathcal{X}_{n-k}(a,b)$, as the
defining inequalities are the same. Hence the $(n-k)$-dimensional volume
$\operatorname{Vol}_{n-k}(\mathcal{X}^{\prime}_{n-k}(a,b))=\operatorname{Vol}_{n-k}(\mathcal{X}_{n-k}(a,b))=V_{n-k}^{a,b}$.

Let $Q^{a,b}_{k}$ be the polytope containing all points $x^{\prime}$ such that
for all $p\in\\{j_{1},j_{2},\ldots,j_{n-k}\\}$, we have $x_{p}^{\prime}=0$,
and for some $x\in F$, we have $x_{p}^{\prime}=x_{p}$ for all
$p\in\\{i_{1},i_{2},\ldots,i_{k}\\}$. Then the coordinate values of
$(x_{i_{1}}^{\prime},x_{i_{2}}^{\prime},\ldots,x_{i_{k}}^{\prime})$ of the
vertices of $Q^{a,b}_{k}$ are the permutations of
$((n-k)b+a,\ldots,(n-2)b+a,(n-1)b+a)$. Note that $Q^{a,b}_{k}$ is a translate
of the polytope $Q^{1,b}_{k}$ (both are $(k-1)$-dimensional polytopes), so
$Q^{a,b}_{k}$ and $Q^{1,b}_{k}$ have the same $(k-1)$-dimensional volume.
Furthermore, $Q^{1,b}_{k}$ is a $b$-dilate of $Q^{1,1}_{k}$, which is
integrally equivalent to $\Pi(1,\ldots,k)=\Pi_{k-1}$, the regular
permutahedron. As $\Pi_{k-1}$ has volume $k^{k-2}\sqrt{k}$ by Lemma 3.24, then
$Q^{a,b}_{k}$ has volume $b^{k-1}k^{k-2}\sqrt{k}$.

Thus, $F$ is a Minkowski sum of two polytopes
$\mathcal{X}^{\prime}_{n-k}(a,b)$ and $Q^{a,b}_{k}$ which lie in two
orthogonal subspaces of $\mathbb{R}^{n}$. Therefore, by Lemma 3.23, the volume
of $F$ is

$\operatorname{Vol}(F)=\sum_{p_{1},\ldots,p_{n}=1}^{2}MV(K_{p_{1}},K_{p_{2}},\ldots,K_{p_{n}})=V^{a,b}_{n-k}\cdot
b^{k-1}k^{k-2}\sqrt{k},$

where $K_{1}=\mathcal{X}_{n-k,a,b}^{\prime}$ and $K_{2}=Q^{a,b}_{k}$. Then the
volume of $\operatorname{Pyr}(I,F)$, the pyramid with $I$ as the vertex over
base $F$ is

$\operatorname{Vol}(\operatorname{Pyr}(I,F))=\frac{1}{n}h_{k}\operatorname{Vol}(F)=\frac{1}{n}h_{k}V^{a,b}_{n-k}\cdot
b^{k-1}k^{k-2}\sqrt{k},$

where $h_{k}$ denotes the minimum distance from point $I$ to the face $F$. We
calculate that

$\displaystyle h_{k}$
$\displaystyle=\frac{|1+\cdots+1-(((n-k)b+a)+\cdots+((n-2)b+a)+((n-1)b+1))|}{\sqrt{1+\cdots+1}}$
$\displaystyle=\frac{|k-k((2n-k-1)b+2a)/2|}{\sqrt{k}}$
$\displaystyle=\frac{k(2nb-kb-b+2a-2)}{2\sqrt{k}}.$

Thus,

$\displaystyle\operatorname{Vol}(\operatorname{Pyr}(I,F))$
$\displaystyle=\frac{1}{n}\cdot\frac{(2nb-kb-b+2a-2)}{2}V^{a,b}_{n-k}\cdot
b^{k-1}k^{k-1}.$

By the definition of the sequence, $V^{a,b}_{0}=1$. Note that
$V^{a,b}_{1}=a-1$, as the 1-dimensional volume (in this case length) of the
convex hull of colinear points $1,\ldots,a$ in $\mathbb{R}$ is of length
$a-1$. Thus for $n\geq 2$,

$\displaystyle V^{a,b}_{n}$
$\displaystyle=\sum_{F}\operatorname{Vol}(\operatorname{Pyr}(I,F))$
$\displaystyle=\sum_{k=1}^{n}\binom{n}{k}\frac{1}{n}\cdot\frac{(2nb-
kb-b+2a-2)}{2}V^{a,b}_{n-k}b^{k-1}k^{k-1}$
$\displaystyle=\frac{1}{n}\sum_{n-k=1}^{n}\binom{n}{n-k}\frac{(2nb-(n-k)b-b+2a-2)}{2}V^{a,b}_{k}b^{n-k-1}(n-k)^{n-k-1}$
$\displaystyle=\frac{1}{n}\sum_{k=0}^{n-1}\binom{n}{k}\frac{(b(n-k))^{n-k-1}(nb+kb-b+2a-2)}{2}V^{a,b}_{k}.$

∎

######  Theorem 1.1.

For any positive integers $a,b,n$, the normalized volume
$\operatorname{NVol}(\mathcal{X}_{n}(a,b))$ is given by

$\operatorname{NVol}(\mathcal{X}_{n}(a,b))=-n!\left(\frac{b}{2}\right)^{n}\sum_{i=0}^{n}\binom{n}{i}(2i-3)!!\left(2n-1+\frac{2a-2}{b}\right)^{n-i}.$

To prove this, we use the following lemma.

######  Lemma 3.25.

The exponential generating function for $\\{(bn)^{n-1}\\}_{n\geq 1}$

(7) $g_{b}(x):=\sum_{n\geq 1}\frac{(bn)^{n-1}}{n!}x^{n}$

satisfies

(8) $g_{b}(x)=-\frac{1}{b}W_{0}(-bx),$

where $W_{0}$ denotes the principal branch of the Lambert $W$ function, and

(9) $g_{b}(x)=xe^{bg_{b}(x)}.$

###### Proof.

Recall that

$W_{0}(z)=\sum_{n\geq 1}\frac{(-n)^{n-1}}{n!}z^{n},$

so substituting $z=-bx$ gives

(10) $W_{0}(-bx)=\sum_{n\geq 1}\frac{(-n)^{n-1}}{n!}(-bx)^{n}=-b\sum_{n\geq
1}\frac{(bn)^{n-1}}{n!}x^{n},$

which implies Equation (8). A well-known property of the Lambert $W$ function
is that $W_{0}(z)=ze^{-W_{0}(z)}$. Substituting $z=-bx$ gives
$W_{0}(-bx)=-bxe^{-W_{0}(-bx)}$, which by Equation (8) gives
$-bg_{b}(x)=-bxe^{bg_{b}(x)}$, which implies Equation (9). ∎

We also need the following exponential generating function for the (non-
normalized) volume of $\mathcal{X}_{n,a,b}$. This is a generalization of
Proposition 4.2 in [1].

######  Proposition 3.26.

Let $V^{a,b}_{n}$ denote the Euclidean volume of $\mathcal{X}_{n}(a,b)$. Let

(11) $f_{a,b}(x):=\sum_{n\geq 0}\frac{V^{a,b}_{n}}{n!}x^{n}$

be its exponential generating function. Then

(12)
$f_{a,b}(x)=e^{b\int\frac{x}{2}(g_{b}^{\prime}(x))^{2}\,dx}e^{(a-\frac{b}{2}-\frac{1}{2})g_{b}(x)},$

where $g_{b}(x)$ is the exponential generating function given in Lemma 3.25.

###### Proof.

By Theorem 3.22, we have that

$\displaystyle n\cdot\frac{V^{a,b}_{n}}{n!}$
$\displaystyle=\frac{1}{n!}\sum_{k=0}^{n-1}\binom{n}{k}\frac{(b(n-k))^{n-k-1}(nb+kb-b+2a-2)}{2}V^{a,b}_{k}$
$\displaystyle=\sum_{k=0}^{n-1}\frac{(b(n-k))^{n-k-1}(b(n-k)+2kb+(2a-b-2))}{2(n-k)!}\frac{V^{a,b}_{k}}{k!}$
$\displaystyle=\sum_{k=0}^{n-1}\frac{1}{2}\frac{(b(n-k))^{n-k}}{(n-k)!}\frac{V^{a,b}_{k}}{k!}+\sum_{k=0}^{n-1}\frac{(b(n-k))^{n-k-1}bk}{(n-k)!}\frac{V^{a,b}_{k}}{k!}$
$\displaystyle+\sum_{k=0}^{n-1}\frac{2a-b-2}{2}\frac{(b(n-k))^{n-k-1}}{(n-k)!}\frac{V^{a,b}_{k}}{k!},$

which by summing over all $x^{n}$ gives

(13)
$f_{a,b}^{\prime}(x)=\frac{1}{2}g_{b}^{\prime}(x)f_{a,b}(x)+bg_{b}(x)f_{a,b}^{\prime}(x)+\frac{2a-b-2}{2x}g_{b}(x)f_{a,b}(x).$

Note that by Equation (9),

$\displaystyle g_{b}^{\prime}(x)$ $\displaystyle=(xe^{bg_{b}(x)})^{\prime}$
$\displaystyle=e^{bg_{b}(x)}+bxg_{b}^{\prime}(x)e^{bg_{b}(x)}$
$\displaystyle=\frac{g_{b}(x)}{x}+bg_{b}^{\prime}(x)g_{b}(x),$

which implies that

(14) $xg_{b}^{\prime}(x)-g_{b}(x)=bxg_{b}^{\prime}(x)g_{b}(x),$

and

(15) $1-bg_{b}(x)=\frac{g_{b}(x)}{xg_{b}^{\prime}(x)}.$

Thus by Equation (13),

$\displaystyle f_{a,b}^{\prime}(x)(1-bg_{b}(x))$
$\displaystyle=\frac{1}{2}g_{b}^{\prime}(x)f_{a,b}(x)+\frac{2a-b-2}{2x}g_{b}(x)f_{a,b}(x)$
$\displaystyle=\frac{1}{2x}(xg_{b}^{\prime}(x)+(2a-b-2)g_{b}(x))f_{a,b}(x)$
$\displaystyle=\frac{1}{2x}(bxg_{b}^{\prime}(x)g_{b}(x)+(2a-b-1)g_{b}(x))f_{a,b}(x),$

where the last line follows by Equation (14). Then by dividing both sides by
Equation (15), we get

$\displaystyle f_{a,b}^{\prime}(x)$
$\displaystyle=\frac{xg_{b}^{\prime}(x)}{g_{b}(x)}\frac{1}{2x}(bxg_{b}^{\prime}(x)g_{b}(x)+(2a-b-1)g_{b}(x))f_{a,b}(x)$
$\displaystyle=\left(b\frac{x}{2}(g_{b}^{\prime}(x))^{2}+(a-\frac{b}{2}-\frac{1}{2})g_{b}^{\prime}(x)\right)f_{a,b}(x).$

This differential equation has solution

$\displaystyle f_{a,b}(x)$ $\displaystyle=e^{\int
b\frac{x}{2}(g_{b}^{\prime}(x))^{2}+(a-\frac{b}{2}-\frac{1}{2})g_{b}^{\prime}(x)\,dx}$
$\displaystyle=e^{b\int\frac{x}{2}(g_{b}^{\prime}(x))^{2}\,dx}e^{(a-\frac{b}{2}-\frac{1}{2})g_{b}(x)}.$

∎

Our proof will also use the following theorem (see for example Chapter 4,
Entry 11, [4]).

######  Theorem 3.27 (Ramanujan’s Master Theorem).

Let $\Gamma(s)$ denote the gamma function. If

(16) $f(x)=\sum_{n=0}^{\infty}\frac{\varphi(n)}{n!}(-x)^{n},$

then the Mellin transform of $f(x)$ is given by

(17) $\int_{0}^{\infty}x^{s-1}f(x)\,dx=\Gamma(s)\varphi(-s).$

Now we are ready to prove our theorem.

###### Proof of Theorem 1.1.

By Ramanujan’s Master Theorem, for $\varphi(n):=(-1)^{n}V^{a,b}_{n}$,

$\int_{0}^{\infty}x^{s-1}f_{a,b}(x)\,dx=\Gamma(s)\varphi(-s)=\Gamma(s)(-1)^{-s}V^{a,b}_{-s},$

where $\Gamma(s)$ denotes the gamma function, and taking $s=-n$, we get

$\int_{0}^{\infty}x^{-n-1}f_{a,b}(x)\,dx=\Gamma(-n)(-1)^{n}V^{a,b}_{n}.$

By Equation (9), we have that

(18) $x=g_{b}(x)e^{-bg_{b}(x)}\qquad\text{and}\qquad
dx=(1-bg_{b})e^{-bg_{b}}\,dg_{b}.$

By Equations (15) and (9), we have that

$(g_{b}^{\prime}(x))^{2}=\left(\frac{g_{b}(x)}{x(1-bg_{b}(x))}\right)^{2}=\left(\frac{xe^{bg_{b}(x)}}{x(1-bg_{b}(x))}\right)^{2}=\left(\frac{e^{bg_{b}(x)}}{(1-bg_{b}(x))}\right)^{2}.$

Thus

$\displaystyle bx(g_{b}^{\prime}(x))^{2}\,dx$
$\displaystyle=b\left(g_{b}e^{-bg_{b}}\right)\left(\frac{e^{bg_{b}}}{(1-bg_{b})}\right)^{2}(1-bg_{b})e^{-bg_{b}}\,dg_{b}$
$\displaystyle=\frac{bg_{b}}{1-bg_{b}}\,dg_{b}.$

By Proposition 3.26, we have

$\displaystyle f_{a,b}(x)$ $\displaystyle=e^{\frac{1}{2}\int
bx(g_{b}^{\prime}(x))^{2}\,dx}e^{(a-\frac{b}{2}-\frac{1}{2})g_{b}(x)}$
$\displaystyle=e^{\frac{1}{2}\int\frac{bg_{b}}{1-bg_{b}}\,dg_{b}}e^{(a-\frac{b}{2}-\frac{1}{2})g_{b}(x)}$
$\displaystyle=e^{\frac{1}{2}\int-1+\frac{1}{1-bg_{b}}\,dg_{b}}e^{(a-\frac{b}{2}-\frac{1}{2})g_{b}(x)}$
$\displaystyle=e^{-\frac{g_{b}(x)}{2}}e^{-\frac{1}{2}\ln(1-bg_{b}(x))}e^{(a-\frac{b}{2}-\frac{1}{2})g_{b}(x)}$
(19)
$\displaystyle=\frac{1}{\sqrt{1-bg_{b}(x)}}e^{(a-\frac{b}{2}-1)g_{b}(x)}.$

Thus by Equations (18) and (3.2), we have that

$\displaystyle\Gamma(-n)(-1)^{n}V^{a,b}_{n}$
$\displaystyle=\int_{0}^{-\infty}(g_{b}e^{-bg_{b}})^{-n-1}\frac{e^{(a-\frac{b}{2}-1)g_{b}}}{\sqrt{1-bg_{b}}}(1-bg_{b})e^{-bg_{b}}\,dg_{b}$
$\displaystyle=\int_{0}^{-\infty}g_{b}^{-n-1}\sqrt{1-bg_{b}}e^{(nb+a-\frac{b}{2}-1)g_{b}}\,dg_{b}$
and by replacing $g_{b}$ by $-t$ and $dg_{b}$ by $-dt$,
$\displaystyle=\int_{0}^{\infty}(-1)^{-n}t^{-n-1}\sqrt{1+bt}e^{-(nb+a-\frac{b}{2}-1)t}\,dt,$

which implies that

$V^{a,b}_{n}=\frac{1}{\Gamma(-n)}\int_{0}^{\infty}t^{-n-1}\sqrt{1+bt}e^{-(nb+a-\frac{b}{2}-1)t}\,dt.$

Note that as a formal power series,

$\sqrt{1+bt}=\sum_{\ell=0}^{\infty}\frac{(-1)^{\ell}(bt)^{\ell}(-\frac{1}{2})_{\ell}}{\ell!},$

where $(-\frac{1}{2})_{\ell}$ is the Pochhammer symbol, defined by
$(\lambda)_{\ell}:=\lambda(\lambda+1)\cdots(\lambda+\ell-1)$, for any positive
integer $\ell$, and by $(\lambda)_{0}:=1$. So,

$\displaystyle V^{a,b}_{n}$
$\displaystyle=\frac{1}{\Gamma(-n)}\int_{0}^{\infty}t^{-n-1}e^{-(nb+a-\frac{b}{2}-1)t}\sum_{\ell=0}^{\infty}\frac{(-1)^{\ell}(bt)^{\ell}(-\frac{1}{2})_{\ell}}{\ell!}\,dt$
$\displaystyle=\frac{1}{\Gamma(-n)}\sum_{\ell=0}^{\infty}\frac{(-1)^{\ell}b^{\ell}(-\frac{1}{2})_{\ell}}{\ell!}\int_{0}^{\infty}t^{\ell-n-1}e^{-(nb+a-\frac{b}{2}-1)t}\,dt,$

of which we consider the integral. Let $u=(nb+a-\frac{b}{2}-1)t$ so
$du=(nb+a-\frac{b}{2}-1)dt$. Then

$\displaystyle\int_{0}^{\infty}t^{\ell-n-1}e^{-(nb+a-\frac{b}{2}-1)t}\,dt$
$\displaystyle=\int_{0}^{\infty}\left(\frac{u}{nb+a-\frac{b}{2}-1}\right)^{\ell-n-1}\frac{e^{-u}}{nb+a-\frac{b}{2}-1}\,du$
$\displaystyle=\int_{0}^{\infty}e^{-u}\frac{u^{\ell-n-1}}{(nb+a-\frac{b}{2}-1)^{\ell-n}}$
$\displaystyle=\frac{\Gamma(\ell-n)}{(nb+a-\frac{b}{2}-1)^{\ell-n}}.$

Thus,

$\displaystyle V^{a,b}_{n}$
$\displaystyle=\sum_{\ell=0}^{\infty}\frac{(-1)^{\ell}b^{\ell}(-\frac{1}{2})_{\ell}\Gamma(\ell-n)}{\ell!\Gamma(-n)(nb+a-\frac{b}{2}-1)^{\ell-n}}$
$\displaystyle=\sum_{\ell=0}^{\infty}\frac{(-1)^{\ell}b^{\ell}(-\frac{1}{2})_{\ell}(-n)_{\ell}}{\ell!(nb+a-\frac{b}{2}-1)^{\ell-n}}$
$\displaystyle=(nb+a-\frac{b}{2}-1)^{n}\sum_{\ell=0}^{\infty}\frac{(-\frac{1}{2})_{\ell}(-n)_{\ell}}{\ell!}\left(\frac{-1}{n+\frac{a}{b}-\frac{1}{2}-\frac{1}{b}}\right)^{\ell},$

which is a multiple of a Poisson-Charlier polynomial. See for example [11] for
the following facts about the Poisson-Charlier polynomial.

$\displaystyle
C_{n}\left(\frac{1}{2};n+\frac{a}{b}-\frac{1}{2}-\frac{1}{b}\right)$
$\displaystyle=\sum_{i=0}^{n}(-1)^{i}\binom{n}{i}\binom{\frac{1}{2}}{i}i!\left(n+\frac{a}{b}-\frac{1}{2}-\frac{1}{b}\right)^{-i}$
$\displaystyle={}_{2}F_{0}\left(-n;-\frac{1}{2}{};-;\frac{-1}{n+\frac{a}{b}-\frac{1}{2}-\frac{1}{b}}\right)$
$\displaystyle=\sum_{\ell=0}^{\infty}\frac{(-\frac{1}{2})_{\ell}(-n)_{\ell}}{\ell!}\left(\frac{-1}{n+\frac{a}{b}-\frac{1}{2}-\frac{1}{b}}\right)^{\ell}.$

Thus,

$\displaystyle V^{a,b}_{n}$
$\displaystyle=(nb+a-\frac{b}{2}-1)^{n}C_{n}\left(\frac{1}{2};n+\frac{a}{b}-\frac{1}{2}-\frac{1}{b}\right)$
$\displaystyle=b^{n}\left(n+\frac{a}{b}-\frac{1}{2}-\frac{1}{b}\right)^{n}\sum_{i=0}^{n}(-1)^{i}\binom{n}{i}\binom{\frac{1}{2}}{i}i!\left(n+\frac{a}{b}-\frac{1}{2}-\frac{1}{b}\right)^{-i}$
$\displaystyle=b^{n}\sum_{i=0}^{n}(-1)^{i}\binom{n}{i}\binom{2i}{i}\frac{(-1)^{i+1}}{2^{2i}(2i-1)}i!\left(n+\frac{a}{b}-\frac{1}{2}-\frac{1}{b}\right)^{n-i}$
$\displaystyle=-b^{n}\sum_{i=0}^{n}\binom{n}{i}\frac{(2i)!}{i!2^{i}}\frac{1}{2^{i}(2i-1)}\left(n+\frac{a}{b}-\frac{1}{2}-\frac{1}{b}\right)^{n-i}$
$\displaystyle=-b^{n}\sum_{i=0}^{n}\binom{n}{i}(2i-1)!!\frac{1}{2^{i}(2i-1)}2^{i-n}\left(2n-1+\frac{2a-2}{b}\right)^{n-i}$
$\displaystyle=-\left(\frac{b}{2}\right)^{n}\sum_{i=0}^{n}\binom{n}{i}(2i-3)!!\left(2n-1+\frac{2a-2}{b}\right)^{n-i},$

and to get the normalized volume, we simply multiply by $n!$, which gives the
desired formula. ∎

As a corollary, we prove the following conjecture of Behrend et al. [2].

######  Corollary 3.28 (Conjecture 4.5 and Remark 4.6, [2]).

For any $n$ and $p$, with $p\geq n-1$,

(20)
$\operatorname{NVol}(\mathcal{P}(n,p))=n!\sum_{k=0}^{n}\binom{n}{k}\frac{c_{k}}{2^{k}}p^{n-k},$

where the sequence $c_{k}$ satisfies $c_{k}=2(k-1)(c_{k-1}-c_{k-2})$ and has
exponential generating function $\sqrt{1-2x}e^{x}$. Equivalently,

(21)
$\operatorname{NVol}(\mathcal{P}(n,p))=-\frac{n!}{2^{n}}\sum_{i=0}^{n}\binom{n}{i}(2i-3)!!(2p+1)^{n-i}.$

###### Proof.

The two statements are shown to be equivalent in [2], so we prove the latter.
By Proposition 3.15, for $p\geq n-1$,
$\operatorname{NVol}(\mathcal{P}(n,p)=\operatorname{NVol}(\mathcal{X}_{n}(p-n+2,1))$.
Then by Theorem 1.1,

$\displaystyle\operatorname{NVol}(\mathcal{X}_{n,p-n+2,1})$
$\displaystyle=-n!\left(\frac{1}{2}\right)^{n}\sum_{i=0}^{n}\binom{n}{i}(2i-3)!!\left(2n-1+2(p-n+2)-2\right)^{n-i}$
$\displaystyle=-\frac{n!}{2^{n}}\sum_{i=0}^{n}\binom{n}{i}(2i-3)!!(2p+1)^{n-i},$

as desired. ∎

##  4\. The convex hull of weakly increasing $\mathbf{x}$-parking functions

######  Definition 4.1.

A weakly increasing $\mathbf{x}$-parking function associated to a positive
integer vector of the form $(a,b,b,\ldots,b)$ is a weakly increasing sequence
$(a_{1},a_{2},\ldots,a_{n})$ of positive integers who satisfy $a_{i}\leq
a+(i-1)b$.

Denote the weakly increasing $\mathbf{x}$-parking function polytope associated
to a positive integer vector of the form $(a,b,b,\ldots,b)$ by
$\mathcal{X}_{n}^{w}(a,b)$, where $n$ is the length of the vector. Note that
the weakly increasing $\mathbf{x}$-parking functions are just the subset of
the $\mathbf{x}$-parking functions which are weakly increasing. Note that
$\mathcal{X}^{w}_{n}(1,b)$ is an $(n-1)$-dimensional polytope in
$\mathbb{R}^{n}$ since the first coordinate of any weakly increasing parking
function is $1$, that is $x_{1}=1$, which brings down the dimension of the
polytope by 1. See Figure 3 for examples.

Next, we reveal a connection between the weakly increasing
$\mathbf{x}$-parking function polytope and the Pitman-Stanley polytope. The
Pitman-Stanley polytope is a well-studied polytope, which has connections to
flow polytopes, parking functions, and many other combinatorial objects.

######  Definition 4.2.

For any $\mathbf{x}\in\mathbb{R}^{n}$, the Pitman-Stanley polytope
$\mathsf{PS}_{n}(\mathbf{x})$ is defined to be

$\\{\mathbf{y}\in\mathbb{R}^{n}:y_{i}\geq 0\text{ and }y_{1}+\cdots+y_{i}\leq
x_{1}+\cdots+x_{i}\text{ for all }1\leq i\leq n\\}.$

Figure 3. The weakly increasing $\mathbf{x}$-parking function polytopes, from
left to right: $\mathcal{X}_{3}^{w}(1,1)$, $\mathcal{X}_{3}^{w}(1,2)$,
$\mathcal{X}_{3}^{w}(2,1)$, $\mathcal{X}_{3}^{w}(2,2)$. Note that when $a=1$,
they are two-dimensional, and when $a>1$, they are three-dimensional.

######  Proposition 4.3.

The weakly increasing $\mathbf{x}$-parking function polytope
$\mathcal{X}^{w}_{n}(a,b)$ is integrally equivalent to the Pitman-Stanley
polytope $\mathsf{PS}_{n}(a-1,b,\dots,b)$.

###### Proof.

Let $T:\mathbb{R}^{n}\to\mathbb{R}^{n}$ be the linear transformation defined

$T(\mathbf{x})=(x_{1}-1,x_{2}-x_{1},x_{3}-x_{2},\dots,x_{n}-x_{n-1}).$

Note that if $\mathbf{x}\in\mathcal{X}_{n}^{w}(a,b)\cap\mathbb{Z}^{n}$, it
follows that $\mathbf{x}$ is also a weakly increasing $\mathbf{x}$-parking
function. We can see
$T(\mathbf{x})=\mathbf{y}\in\mathsf{PS}_{n}(a-1,b,\dots,b)\cap\mathbb{Z}^{n}$
since $1\leq x_{i}\leq x_{i+1}$ implies $y_{i}\geq 0$ and $1\leq x_{i}\leq
a+(i-1)b$ implies $\sum_{i=1}^{k}y_{i}=x_{k}-1\leq a+(i-1)b-1$ for all $i$.

Next, define the linear transformation $S:\mathbb{R}^{n}\to\mathbb{R}^{n}$ by

$S(\mathbf{y})=(1+y_{1},1+y_{1}+y_{2},\dots,1+y_{1}+\dots+y_{n}).$

For $\mathbf{y}\in\mathsf{PS}_{n}\cap\mathbb{Z}^{n}$, we have that
$\mathbf{x}=S(\mathbf{y})$ satisfies $x_{i}\leq x_{i+1}$ and

$x_{i}=1+\sum_{k=1}^{i}y_{k}\leq 1+(a-1)+(i-1)b=a+(i-1)b,$

hence $\mathbf{x}\in\mathcal{X}^{w}_{n}(a,b)\cap\mathbb{Z}^{n}$. By
construction, both $T$ and $S$ are injective. ∎

######  Corollary 4.4.

Let $t\in\mathbb{Z}_{\geq 0}$. The number of lattice points in the $t$-dilate
of $\mathcal{X}^{w}_{n}(a,b)$ is given by

$|t\mathcal{X}^{w}_{n}(a,b)\cap\mathbb{Z}^{n}|=\frac{1}{n!}(t(a-1)+1)(t(a-1+nb)+2)(t(a-1+nb)+3)\cdots(t(a-1+nb)+n).$

###### Proof.

By Proposition 4.3, $\mathcal{X}^{w}_{n}(a,b)$ is integrally equivalent to
$\mathsf{PS}_{n}(a-1,b,\dots,b)$. By substituting $a-1$ for $a$ in the
equation of Theorem 13 in [18], we obtain the result. ∎

Another consequence of Proposition 4.3 is the following:

######  Corollary 4.5.

For the special case when
$\mathbf{x}=(a,b,\dots,b)=(1,1,\dots,1)\in\mathbb{R}^{n}$, the weakly
increasing classical parking function $\mathcal{X}_{n}^{w}(1,1)$ has volume
$n^{n-2}$ and contains $C_{n}$ lattice points, where
$C_{n}=\displaystyle{\frac{1}{n+1}\binom{2n}{n}}$ denotes the $n$-th Catalan
number.

###### Proof.

The weakly increasing classical parking function $\mathcal{X}^{w}_{n}(1,1)$is
integrally equivalent to the Pitman-Stanley polytope
$\mathsf{PS}_{n-1}(1,1,\ldots,1)$. It follows from work by Pitman and Stanley
[18] and Benedetti et al. [3] that the Pitman-Stanley polytope is integrally
equivalent to a flow polytope arising from a graph consisting of a path
$1\rightarrow 2\rightarrow\cdots\rightarrow n$ and additional edges
$(1,n),(2,n),\dots,(n-2,n)$, for which the volume and lattice point count are
known. ∎

The following proposition known and can be deduced from the existing
literature detailed above, but we provide a proof for completeness.

######  Proposition 4.6.

The weakly increasing classical parking function polytope
$\mathcal{X}^{w}_{n}(1,1)$ is an $(n-1)$-dimensional polytope given by the
following equality and inequalities.

$\displaystyle x_{1}$ $\displaystyle=1,$ $\displaystyle x_{i}$
$\displaystyle\leq i,$ $\displaystyle\text{ \emph{for} }2\leq i\leq n,$
$\displaystyle x_{i-1}$ $\displaystyle\leq x_{i},$ $\displaystyle\text{
\emph{for} }2\leq i\leq n.$

Furthermore, $\mathcal{X}_{n}^{w}(1,1)$ has

  1. _(_ i _)_

$2(n-1)$ facets,

  2. _(_ ii _)_

$2^{n-1}$ vertices, and

  3. _(_ iii _)_

$2^{n-2}(n-1)$ edges.

###### Proof.

The inequality description follows similarly to the proof of Proposition 3.6
restricting ourselves to the weakly-increasing $\mathbf{x}$-parking functions.

  1. ($i$)

This follows from a straightforward enumeration of the inequalities in the
description above.

  2. ($ii$)

All the vertices are of the form

$(\underbrace{1,\ldots,1}_{k},v_{k+1},\dots,c_{n}),$

where $v_{k}=k$ and for each $k\leq i<n$ we have either $v_{i+1}=v_{i}$
(“min”) or $v_{i+1}=i+1$ (“max”). Hence, each vertex corresponds to a sequence
of $n-1$ binary choices.

  3. ($iii$)

We claim that vertices $v,u$ are connected by an edge if and only if their
construction (given above by a sequence of binary choices) differs by exactly
one choice.

We show this inductively. Assume this is true for $\mathcal{X}_{m}^{w}(1,1)$
where $m<n$ and let $u,v$ be two vertices in $\mathcal{X}_{n}^{w}(1,1)$ that
differ by the $k$-th choice. If $k=n$, we have that $u^{\prime}=v^{\prime}$
where $v^{\prime}=(v_{1},\dots,v_{n-1})$, which is a vertex of
$\mathcal{X}_{n-1}^{w}(1,1)$. Hence, there exists a
$c^{\prime}\in\mathbb{R}^{n-1}$ that maximizes it. Let
$c=(c^{\prime},0)\in\mathbb{R}^{n}$; it is evident that $c\cdot u=c\cdot
v>c\cdot w$ for any other vertex $w\in\mathcal{X}_{n}^{w}(1,1)$. If $k<n$ and
we continue to choose min for the rest of the choices after $k$, it follows
that

$\displaystyle u$
$\displaystyle=(u_{1},\dots,u_{k-1},\underbrace{u_{k-1},\dots,u_{k-1}}_{n-k+1}),$
$\displaystyle v$
$\displaystyle=(u_{1},\dots,u_{k-1},\underbrace{k,\dots,k}_{n-k+1}).$

∎

######  Remark 4.7.

It follows from the inequality description of $\mathcal{X}_{n}^{w}(1,1)$ that
all lattice points are weakly increasing parking functions.

##  5\. Further Directions and Discussion

We conclude this paper by providing some directions for future research.

###  5.1. On the classical parking function polytope

Given a term order $\prec$, every non-zero polynomial $f\in k[\mathbf{x}]$ has
a unique initial monomial, denoted by $in_{\prec}(f)$. If $I$ is an ideal in
$k[\mathbf{x}]$, then its initial ideal is the monomial ideal
$in_{\prec}(I):=\langle in_{\prec}(f):f\in I\rangle$. Let
$\mathcal{A}=\\{\mathbf{a}_{1},\ldots,\mathbf{a}_{k}\\}\subseteq\mathbb{Z}^{n}$
and denote the toric ideal of $\mathcal{A}$ by $I_{\mathcal{A}}$.

######  Proposition 5.1 (Corollary 8.9, [19]).

The initial ideal $in_{\prec}(I_{\mathcal{A}})$ is square-free if and only if
the corresponding regular triangulation $\Delta_{\prec}$ of $\mathcal{A}$ is
unimodular.

Using the theory of Gröbner bases, one may approach proving or disproving the
following conjecture that we pose.

######  Conjecture 5.2.

The parking function polytope $\mathsf{PF}_{n}$ admits a regular unimodular
triangulation.

######  Example 5.3.

Consider all lattice points of $\mathsf{PF}_{3}$, which includes the $16$
parking functions of length $3$ and the point $(2,2,2)$ which can be used for
a triangulation. Let $R=\mathbb{Q}[a,b,\ldots,p,q]$, where each variable
corresponds to a lattice point of $\mathsf{PF}_{3}$, and
$S=\mathbb{Q}[x,y,z,w]$, and take $f:S\to R$ to be defined by

$(x,y,z,w)\mapsto(x^{1}y^{1}z^{1}w,x^{1}y^{1}z^{2}w,x^{1}y^{2}z^{1}w,x^{2}y^{1}z^{1}w,x^{1}y^{1}z^{3}w,x^{1}y^{3}z^{1}w,x^{3}y^{1}z^{1}w,x^{1}y^{2}z^{2}w,$
$x^{2}y^{1}z^{2}w,x^{2}y^{2}z^{1}w,x^{1}y^{2}z^{3}w,x^{1}y^{3}z^{2}w,x^{2}y^{1}z^{3}w,x^{3}y^{1}z^{2}w,x^{3}y^{2}z^{1}w,x^{2}y^{3}z^{1}w,x^{2}y^{2}z^{2}w).$

Then the initial ideal is

$(ae,af,bf,ef,ag,bg,cg,eg,fg,ah,bh,gh,ai,bi,ci,fi,aj,bj,cj,ej,ak,bk,ck,dk,fk,gk,al,bl,cl,$
$dl,el,gl,il,am,bm,cm,dm,fm,gm,hm,an,bn,cn,dn,en,fn,hn,kn,ln,ao,bo,co,do,eo,fo,$
$ho,io,ko,lo,mo,ap,bp,cp,dp,ep,gp,hp,ip,kp,mp,np,aq,bq,cq,dq,eq,fq,gq,hq,iq,kq).$

Notice that the initial ideal is square-free; hence, there exists a unimodular
triangulation of this parking function polytope using on the parking functions
and an additional lattice point as vertices.

If this conjecture holds true, the following problem may be of interest.

######  Problem 5.4.

Find a bijection between the simplices of a unimodular triangulation of
$\mathsf{PF}_{n}$ and $(0,1)$-matrices with two 1’s in each row with positive
permanent, as discussed in Theorem 2.9.

The _Ehrhart function_ of a polytope $P\subset\mathbb{R}^{n}$ is
$\operatorname{ehr}_{P}(t):=|tP\cap\mathbb{Z}^{n}|$, where
$tP=\\{t\mathbf{x}:\ \mathbf{x}\in P\\}$. When $P$ is a lattice polytope (its
vertices have integer coordinates), the Ehrhart function is a polynomial in
$t$, with degree equal to the dimension of $P$, leading coefficient equal to
its normalized volume, second-leading coefficient equal to half the surface
area, and constant coefficient 1. The _Ehrhart polynomial_ of a lattice
polytope $P$ of dimension $n$ can always be written in the form
$\operatorname{ehr}_{P}(t)=\sum_{i=0}^{n}h_{i}^{*}\binom{t+n-i}{n}$; the
sequence $(h_{0}^{*},\dots,h_{n}^{*})$ is called the _$h^{*}$ -vector_.
Equivalently, $\sum_{t\geq
0}\operatorname{ehr}_{P}(t)z^{t}=\frac{h^{*}(P;z)}{(1-z)^{n+1}}$, where
$h^{*}(P;z)=h_{0}^{*}+h_{1}^{*}z+\cdots+h_{n}^{*}z^{n}$.

######  Problem 5.5.

Determine a formula for the Ehrhart polynomial (or equivalently, the
$h^{*}$-polynomial) of $\mathsf{PF}_{n}$.

If the conjecture above holds true, then it may be useful in studying the
$h^{*}$-polynomial due to the following proposition due to Stanley [16], which
would require us instead to study the $h$-polynomial of the triangulation.

######  Proposition 5.6.

If $P$ is a lattice polytope that admits a unimodular triangulation, then the
$h^{*}$-polynomial is given by the $h$-polynomial of the triangulation.

###  5.2. On $\mathbf{x}$-parking function polytopes

The main object of study in this paper is the $\mathbf{x}$-parking function
polytope for $\mathbf{x}=(a,b,\dots,b)$. One can ask for the face structure,
volume, and lattice-point enumeration for parking function polytopes where
$\mathbf{x}\neq(a,b,\dots,b)$. In the same spirit as Stanley’s original
problem [17], we pose the following:

######  Problem 5.7.

For $\mathbf{x}=(x_{1},\dots,x_{n})\in\mathbb{Z}_{>0}^{n}$, let
$\mathfrak{X}_{n}$ be the convex hull of $\mathbf{x}$-parking functions of
length $n$.

  1. (1)

Find the number of $k$-dimensional faces of $\mathfrak{X}_{n}$ for
$k\in\\{0,\ldots,n\\}$ and given $\mathbf{x}$.

  2. (2)

Find the volume of $\mathfrak{X}_{n}$ for given $\mathbf{x}$.

  3. (3)

Find the number of integer points in $\mathfrak{X}_{n}$ for given
$\mathbf{x}$, i.e., the number of elements of
$\mathfrak{X}_{n}\cap\mathbb{Z}^{n}$.

  4. (4)

More generally, find a formula for the Ehrhart polynomial (or equivalently,
the $h^{*}$-polynomial) of $\mathfrak{X}_{n}$ for given $\mathbf{x}$.

This problem is likely to be challenging in its full generality, as even
finding explicit formulas for the number of $\mathbf{x}$-parking functions for
arbitrary $\mathbf{x}$ is noted by Yan to be challenging [20]. General
enumerative results can be found in [9] in terms of Gončarov polynomials and
more on the history of enumerative results can be found in [7]. A starting
point for Problem 5.7 could be to consider some of those special cases from
[20] and explore the connection to Gončarov polynomials.

We note that the problem to determine the number of lattice points and the
Ehrhart polynomial (or $h^{*}$-polynomial) for the $\mathbf{x}$-parking
function polytope when $\mathbf{x}=(a,b,\dots,b)$, remains open.

###  5.3. Other generalizations of parking functions and their convex hulls

There are a plethora of generalizations of parking functions in the literature
and one can naturally ask similar problems to Problem 5.7 for their favorite
generalization. One such generalization is known as the $(a,b)$-_rational
parking functions_.

There is a well-known bijection between Dyck paths of length $n$ and all
possible increasing rearrangements of parking functions of length $n$. By
labeling the North steps of the Dyck paths with elements in
$[n]=\\{1,2,\dots,n\\}$ such that each element appears exactly once and the
labels increase within each column going North, we can construct a bijection
between the labeled Dyck paths of length $n$ and all parking functions of
length $n$. Now, let $a,b\in\mathbb{Z}_{>0}$. An $(a,b)$-_Dyck path_ is a
lattice path from $(0,0)$ to $(b,a)$ (that is, with $a$ North steps and $b$
East steps) which stays weakly above the diagonal line $y=\frac{a}{b}x$. A
$(n,n)$-Dyck path is just a standard Dyck path of length $n$. There is a
canonical bijection between $(n,n)$-Dyck paths and $(n,n+1)$-Dyck paths since
the last step of a $(n,n+1)$-Dyck paths must be an East step. If $a,b$ are
coprime, the number of $(a,b)$-Dyck paths is given by

$\frac{1}{a+b}\binom{a+b}{a,b}=\frac{(a+b-1)!}{a!b!},$

and is called the _rational Catalan number_.

######  Definition 5.8.

Let $a,b$ be coprime. An $(a,b)$-_parking function_ is an $(a,b)$-Dyck path
together with a labeling of the North steps by the set $[a]=\\{1,2,\dots,a\\}$
such that the labels increase within each column going North. Define the
$(a,b)$-_parking function polytope_ $\mathcal{P}_{a,b}$ as the convex hull of
all $(a,b)$-parking functions of length $n$ in $\mathbb{R}^{n}$.

######  Remark 5.9.

There are $b^{a-1}$ many $(a,b)$-parking functions for coprime $(a,b)$. The
classical parking functions are recovered when $(a,b)=(n,n+1)$.

The following are two propositions towards the study of the $(a,b)$-_parking
function polytope_ (proofs ommitted).

######  Proposition 5.10.

Consider the $(a,b)$-parking function polytope $\mathcal{P}_{a,b}$.

  1. (1)

$\mathcal{P}_{a,b}$ is an $a$-dimensional polytope where the vertices are
permutations of

$(\underbrace{1,\ldots,1\,}_{\text{$k$ many }},b_{k+1},b_{k+2},\ldots,b_{a}),$

for $1\leq k\leq a$ where $b_{i}=\lceil\frac{b}{a}(i-1)\rceil$ for $i>1$,
$b_{1}=1$.

  2. (2)

If $b>a$, then the number of vertices of $\mathcal{P}_{a,b}$ is

$a!\left(\frac{1}{1!}+\frac{1}{2!}+\cdots+\frac{1}{a!}\right).$

If $b<a$, for any $1\leq i\leq b$, let $m_{i}=|\\{j\text{ such that
}b_{j}=i\\}|$. Then the number of vertices of $\mathcal{P}_{a,b}$ is

$a!\left(\frac{1}{m_{1}!m_{2}!\cdots
m_{b}!}+\sum\limits_{k=2}^{b}M_{k}\right),$

where for $2\leq k\leq b$,

$M_{k}=\frac{1}{m_{k+1}!\cdots
m_{b}!}\left(\sum\limits_{i=1}^{m_{k}}\frac{1}{(m_{1}+\cdots+m_{k-1}+i)!(m_{k}-i)!}\right).$

######  Proposition 5.11.

The $(a,b)$-parking function polytope $\mathcal{P}_{a,b}$ is given by the
following minimal inequality description:

  * •

For $b>a$,

$\displaystyle 1$ $\displaystyle\leq x_{i}\leq b_{a},$ $\displaystyle\text{
for }1\leq i\leq a,$ $\displaystyle x_{i}+x_{j}$ $\displaystyle\leq
b_{a-1}+b_{a},$ $\displaystyle\text{ for }i<j,$ $\displaystyle\vdots$
$\displaystyle x_{i_{1}}+x_{i_{2}}+\cdots+x_{i_{a-2}}$ $\displaystyle\leq
b_{3}+b_{4}+\cdots+b_{a-1}+b_{a},$ $\displaystyle\text{ for
}i_{1}<i_{2}<\cdots<i_{a-2},$ $\displaystyle x_{1}+x_{2}+\cdots+x_{a}$
$\displaystyle\leq b_{1}+b_{2}+\cdots+b_{a}.$

Furthermore, the number of facets is equal to $2^{a}-1$.

  * •

If $b=a-1$, the minimal hyperplane description is

$\displaystyle 1$ $\displaystyle\leq x_{i}\leq b_{a},$ $\displaystyle\text{
for }1\leq i\leq a,$ $\displaystyle x_{i}+x_{j}$ $\displaystyle\leq
b_{a-1}+b_{a},$ $\displaystyle\text{ for }i<j,$ $\displaystyle\vdots$
$\displaystyle x_{i_{1}}+x_{i_{2}}+\cdots+x_{i_{a-3}}$ $\displaystyle\leq
b_{4}+b_{5}+\cdots+b_{a-1}+b_{a},$ $\displaystyle\text{ for
}i_{1}<i_{2}<\cdots<i_{a-3},$ $\displaystyle x_{1}+x_{2}+\cdots+x_{a}$
$\displaystyle\leq b_{1}+b_{2}+\cdots+b_{a}.$

Furthermore, the number of facets is equal to
$2^{a}-1-\binom{a}{a-2}=2^{a}-\frac{(n-2)(n+1)}{2}$.

## Acknowledgements

The authors thank Esme Bajo and Jason Zhao for helpful conversations and
Douglas Varela for his insight on the analytical tools used.

## References

  * [1] Aruzhan Amanbayeva and Danielle Wang, _The convex hull of parking functions of length $n$_, Enumer. Comb. Appl. 2 (2022), no. 2, Paper No. S2R10, 10.
  * [2] Roger E. Behrend, Federico Castillo, Anastasia Chavez, Alexander Diaz-Lopez, Laura Escobar, Pamela E. Harris, and Erik Insko, _Partial permutohedra_ , 2022\.
  * [3] Carolina Benedetti, Rafael S. González D’León, Christopher R. H. Hanusa, Pamela E. Harris, Apoorva Khare, Alejandro H. Morales, and Martha Yip, _A combinatorial model for computing volumes of flow polytopes_ , Trans. Amer. Math. Soc. 372 (2019), no. 5, 3369–3404.
  * [4] Bruce C. Berndt, _Ramanujan’s notebooks. Part I_ , Springer-Verlag, New York, 1985, With a foreword by S. Chandrasekhar.
  * [5] Yu. D. Burago and V. A. Zalgaller, _Geometric inequalities_ , Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 285, Springer-Verlag, Berlin, 1988, Translated from the Russian by A. B. Sosinskiĭ, Springer Series in Soviet Mathematics.
  * [6] Martin Dyer, Peter Gritzmann, and Alexander Hufnagel, _On the complexity of computing mixed volumes_ , SIAM J. Comput. 27 (1998), no. 2, 356–400.
  * [7] Petar Gaydarov and Sam Hopkins, _Parking functions and tree inversions revisited_ , Adv. in Appl. Math. 80 (2016), 151–179.
  * [8] Dylan Heuer and Jessica Striker, _Partial Permutation and Alternating Sign Matrix Polytopes_ , SIAM J. Discrete Math. 36 (2022), no. 4, 2863–2888.
  * [9] Joseph P. S. Kung and Catherine H. Yan, _Gončarov polynomials and parking functions_ , J. Combin. Theory Ser. A 102 (2003), no. 1, 16–37.
  * [10] OEIS Foundation Inc., _The on-line encyclopedia of integer sequences_ , Published electronically at https://oeis.org, 2022.
  * [11] Nejla Özmen and Esra Erkuş-Duman, _On the Poisson-Charlier polynomials_ , Serdica Math. J. 41 (2015), no. 4, 457–470.
  * [12] Marko Petkovšek, Herbert S. Wilf, and Doron Zeilberger, _$A=B$_ , A K Peters, Ltd., Wellesley, MA, 1996, With a foreword by Donald E. Knuth, With a separately available computer disk.
  * [13] Alexander Postnikov, _Permutohedra, associahedra, and beyond_ , Int. Math. Res. Not. IMRN (2009), no. 6, 1026–1106.
  * [14] Richard Rado, _An inequality_ , J. London Math. Soc. 27 (1952), 1–6.
  * [15] Vladimir S. Shevelev, _On the permanent of stochastic $(0,1)$-matrices with identical row sums_, Izv. Vyssh. Uchebn. Zaved. Sev.-Kavk. Reg. Estestv. Nauki (1997), no. 1, 21–38, 104.
  * [16] Richard P. Stanley, _Decompositions of rational convex polytopes_ , Ann. Discrete Math. 6 (1980), 333–342, Combinatorial mathematics, optimal designs and their applications (Proc. Sympos. Combin. Math. and Optimal Design, Colorado State Univ., Fort Collins, Colo., 1978).
  * [17] by same author, _Problem 12191_ , Problems and Solutions, Amer. Math. Monthly 127 (2020), no. 6, 563–571.
  * [18] Richard P. Stanley and Jim Pitman, _A polytope related to empirical distributions, plane trees, parking functions, and the associahedron_ , Discrete Comput. Geom. 27 (2002), no. 4, 603–634.
  * [19] Bernd Sturmfels, _Gröbner bases and convex polytopes_ , University Lecture Series, vol. 8, American Mathematical Society, Providence, RI, 1996.
  * [20] Catherine H. Yan, _On the enumeration of generalized parking functions_ , Proceedings of the Thirty-first Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 2000), vol. 147, 2000, pp. 201–209.
  * [21] by same author, _Generalized parking functions, tree inversions, and multicolored graphs_ , Adv. in Appl. Math. 27 (2001), no. 2-3, 641–670, Special issue in honor of Dominique Foata’s 65th birthday (Philadelphia, PA, 2000).
  * [22] by same author, _Parking functions_ , Handbook of enumerative combinatorics, Discrete Math. Appl. (Boca Raton), CRC Press, Boca Raton, FL, 2015, pp. 835–893.
  * [23] Doron Zeilberger, _EKHAD_ , https://sites.math.rutgers.edu/~zeilberg/tokhniot/EKHAD, 2018.
  * [24] Günter M. Ziegler, _Lectures on polytopes_ , Graduate Texts in Mathematics, vol. 152, Springer-Verlag, New York, 1995.