\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\newcommand{\mybinom}[2]{\genfrac{(}{)}{0pt}{}{#1}{#2}}
\DeclareMathOperator{\PF}{PF}
\DeclareMathOperator{\IP}{IP}
\DeclareMathOperator{\LD}{LD}
\DeclareMathOperator{\LT}{LT}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf Descents in Parking Functions
}
\vskip 1cm
\large
Paul R. F. Schumacher\\
1512 Oakview Street\\
Bryan, TX 77802 \\
USA\\
\href{mailto:Paul.R.F.Schumacher@gmail.com}{\tt Paul.R.F.Schumacher@gmail.com}
\end{center}
\vskip .2 in
\begin{abstract}
Parking functions are a superset of permutations. In this article, we
count the number of parking functions of length $n$ with a fixed number
of ties, as well as the number of descents in those parking functions.
The steps to achieve this result also reveal many things about
their internal structure.
\end{abstract}
\section{Introduction}
Parking functions were introduced in 1966 by Konheim and Weiss \cite{KonheimAndWeiss}. The original concept was that of a linear parking lot with $n$ available spaces, and $n$ cars with a stated parking preference. Each car would, in order, attempt to park in its preferred spot. If the car found its preferred spot occupied, it would move to the next available slot. A parking function is a sequence of parking preferences that would allow all $n$ cars to park using this method. We refer to the set of parking functions of length $n$ as $\PF_n$.
\begin{definition}
Throughout, we use the notation $[n]$ to mean the set of integers
$\{1,2,\ldots,n \}$.
\end{definition}
\begin{definition}
Let $a$ be a map from $[n]$ to $[n]$ (written \((a_1 \:a_2 \cdots
a_n)\)) such that for all $i \leq n$, the number of $j$ such that
$a_j \leq i$ is greater than or equal to $i$. (Alternatively, if $b_i$
are the $a_i$ sorted into non-decreasing order, then $b_i \leq i$.) A
map that satisfies this property is called a \emph{parking function} of
length $n$ \cite{KonheimAndWeiss}.
\end{definition}
The Pr\"{u}fer codes given by Foata and Riordan are important when exploring many aspects of parking functions, since they reduce the parking function to the distances between successive elements. They also lead to a deeper understanding of the internal structure of the parking functions, and their relationship to other combinatorial objects, such as trees. The authors proved that the map from parking functions to Pr\"{u}fer codes was a bijection between $\PF_n$ and $[n+1]^{n-1}$ (proof omitted for brevity), giving us an alternate method of counting $|\PF_n|=(n+1)^{(n-1)}$.
\begin{definition}
For a parking function $f =(a_1 a_2 \cdots a_n)
\in \PF_n$, define the \emph{Pr\"{u}fer code} of $f$ to be $((a_2-a_1)
\bmod (n+1),
\ldots, (a_n-a_{n-1}) \bmod (n+1))$. See
\cite{FoataAndRiordan}.
\label{PFCount}
\end{definition}
There are many equivalent definitions for Dyck paths. We use the
following:
\begin{definition}
Given $n$, a \emph{Dyck path} of length
$2n$ is a set of $n$ up steps $(0,1)$ and $n$ over steps $(1,0)$, such
that for any over step, the number of up steps preceding it is more
than the number of over steps preceding it. (Equivalently, the path
never falls below the diagonal $x=y$.) A \emph{peak} in a Dyck path is
an up step followed by an over step \cite{Loehr}.
\end{definition}
\begin{definition}We define the \emph{labeled Dyck paths} of length $2n$ ($\LD_n$) to be these paths with the up steps labeled with the elements of $[n]$ such that any up step immediately preceded by another up step has a higher label than the preceding up step.\end{definition}
\begin{theorem}$\PF_n \cong \LD_{n}$.\label{DyckProof}\label{ParkDyck}\end{theorem}
\begin{proof}Let $b_i$ be the number of $i$'s in the parking function $f$. We create a Dyck path with $b_i$ up steps in column $i$. Then we label the $i$th column with the locations of $i$ in the parking function, in ascending order.
Since $c_i= \# \{j \ : \ a_j \leq i\} \geq i$, there are $c_i \geq i$ up steps before the $i$th over step.
Given a labeled Dyck path, let $d_i$ be the number of up steps before the $i$th over step. By the definition of the labeled Dyck paths, $d_i \geq i$. If we use the inverse of the process above, this means that $d_i$ elements of the parking function are less than or equal to $i$ for all $i$, and $d_i \geq i$, meaning we have a valid parking function. Thus, we have a map from $\PF_n \rightarrow \LD_n$ and exhibited an inverse. (Proof paraphrased from Loehr \cite{Loehr}, given here to exhibit the map we use later. See Figure \ref{fig:LabelledDyck} for an illustrative example.)\end{proof}
\begin{figure}[ht]
\begin{center}
\includegraphics[width=4in]{Dyck}
\caption{Labelled Dyck path to parking function example.}
\label{fig:LabelledDyck}
\end{center}
\end{figure}
Let $\IP_n$ be the set of non-decreasing parking functions, i.e., those parking functions $(a_1 \: a_2 \cdots a_n)$ where $a_i \leq a_{i+1}$ for all $1 \leq i \leq n-1$. Let $D_n$ be the set of Dyck paths of length $2n$.
\begin{corollary}$\IP_n \cong D_n$.\end{corollary}
\begin{proof}Given any Dyck path, if we apply the trivial labeling where the labels occur in increasing order as we follow the path, we get a parking function where all of the elements equal to $i$ come after those elements less than $i$.\end{proof}
\section{Descents in parking functions}
\subsection{Counting descents}
\begin{definition}Given a parking function \( (a_1\: a_2 \cdots a_n) \), we call a pair \((a_i$, $a_{i+1})\) a \emph{step} in the parking function. We call this step a \emph{tie} if $a_i = a_{i+1}$, a \emph{descent} if $a_i > a_{i+1}$, and an \emph{ascent} if $a_i < a_{i+1}$.\end{definition}
There are $n-1$ steps in each parking function. For example, in the parking function \( (1422)\), the step $14$ is an ascent, the step $42$ is a descent, and the step $22$ is a tie.
\begin{definition}Let $\PF_{(n,i)} \subset \PF_n$ be the set of parking functions of length $n$ with $i$ ties.\end{definition}
We can count the number of parking functions with $i$ ties and $j$ descents and arrange the results as a table such that $i$ decreases as we read down the table and $j$ decreases as we go from left-to-right. If we do this, we get a triangular set of numbers (see Figure \ref{fig:desdist}) with several interesting properties. The right side of the triangle shows the numbers of non-decreasing parking functions with $i$ ties, from $n$ ties at the top to $0$ ties at the bottom. The left side, by symmetry shows non-increasing parking functions in the same way.
\begin{figure}[ht]
\begin{center}
\begin{tabular}{ccccccccccc}
&&&&&1\\
&&&&15&&15\\
&&&50&&200&&50\\
&&50&&1030&&1030&&50\\
&15&&1240&&3970&&1240&&15\\
1&&407&&3480&&3480&&407&&1\\
\end{tabular}
\caption{Parking function distribution for $n=6$}
\label{fig:desdist}
\end{center}
\end{figure}
\begin{theorem}\label{thm:descount}There are \( \mybinom{n}{2} (n+1)^{n-2}\) total descents among all parking functions in $\PF_n$.\end{theorem}
In order to prove this result, we will take small steps exploring the internal distribution of the ties, ascents, and descents in $\PF_n$, using counting arguments.
\begin{lemma}If $\IP_{(n,i)}$ is the set of non-decreasing parking functions with $i$ ties of length $n$, and $D_{(n,j)}$ is the set of Dyck paths of length $2n$ with $j$ peaks, then $\IP_{(n,i)} \cong D_{(n,n-i)}$.\end{lemma}
\begin{proof}Given any non-decreasing parking function with $i$ ties, we note that there must be exactly $n-i$ different elements in the parking function. When we use the map from \eqref{ParkDyck} to a Dyck path, we get a Dyck path with exactly $n-i$ peaks.\end{proof}
\begin{lemma}
The number of parking functions of length $n$ with no
descents and $i$ ties is $$
\frac{1}{i+1}\mybinom{n}{i}\mybinom{n-1}{i}.$$
\label{thm:EdgeCount}
\end{lemma}
\begin{proof}The number of Dyck paths with exactly $j$ peaks is given by the triangle of Narayana numbers \seqnum{A001263}, \(T(n,j)= \frac{1}{j}\mybinom{n}{j-1}\mybinom{n-1}{j-1}\). From above, we know that this is also the number of non-decreasing parking functions of length $n$ with $n-j$ ties.
Letting $i = n-j$, we see that
$$\frac{1}{n-i}\mybinom{n-1}{n-i-1}\mybinom{n}{n-i-1}
= \frac{1}{i+1}\mybinom{n-1}{i}\mybinom{n}{i}.$$
\end{proof}
\begin{theorem}\label{thm:TieCount}There are \( \mybinom{n-1}{i}
n^{n-1-i} \) parking functions in $\PF_{(n,i)}$.
\end{theorem}
\begin{proof}Using the bijection in Definition \ref{PFCount}, we note that each tie in a parking function becomes a $0$ in the corresponding Pr\"{u}fer code, and that any sequence of \((b_1 b_2 \cdots b_{n-1})\) in $[n+1]_0^{n-1}$ is a valid Pr\"{u}fer code. Therefore, if we want a parking function with $i$ ties, we fix $i$ zeroes in the code, and the other elements can be arbitrary elements of $[n]$ (nonzero elements of $[n+1]_0$). This gives us a total of \( \mybinom{n-1}{i} n^{n-1-i} \) codes with exactly $i$ zeroes, which, in turn, gives us the required count of parking functions in $\PF_{(n,i)}$.\end{proof}
\begin{remark}This proof
was given by the author in his dissertation in 2009 \cite[Thm
A.4]{schumacher1}. The result can also be derived from the $q$-nomial
formula given by Yan in 2015 \cite[Corollary 1.3 in Chapter
13]{NewEnumerative}.
\end{remark}
\begin{lemma}The generating function of parking functions with $j$ non-tie steps in $\PF_n$ is \[ \sum_{i=0}^{n-1} \mybinom{n-1}{j} n^{j} x^j = (1+nx)^{n-1}\text{.}\]\end{lemma}
\begin{proof}This is a summation of the result from Theorem \ref{thm:TieCount} with \(j = n-1 -i\).\end{proof}
\begin{lemma} The distribution of ascents and descents in $\PF_n$ and $\PF_{(n,i)}$ are symmetrical.
That is, the total descents among the parking functions in either set is the same as the total ascents among the parking functions in that set.\end{lemma}
\begin{proof}
If we flip a parking function and look at \((a_n a_{n-1}
\cdots a_1)\), we see that we still have a parking function. In other
words, this reordering is an automorphism of $\PF_n$. However, under
this automorphism, all ascents become descents, all descents become
ascents, and all ties remain ties. This symmetry tells us that the
number of descents in $\PF_n$ must equal the number of ascents. Since
the ties are unchanged, this automorphism also preserves the subsets
$\PF_{(n,i)}$ of $\PF_n$, meaning that the number of descents in
$\PF_{(n,i)}$ must equal the number of ascents.\end{proof}
\begin{lemma}\label{DescentTieCount}There are \(
\frac{n-1-i}{2}\mybinom{n-1}{i}n^{n-1-i}\) total descents among all
parking functions in $\PF_{(n,i)}$.
\end{lemma}
\begin{proof}
Since there are $n-1$ steps for each parking function in
$\PF_{(n,i)}$, and $i$ of each of these are ties, this leaves $n-1-i$
non-ties for each parking function in $\PF_{(n,i)}$, and by the
symmetry noted above, half of these are descents.
\end{proof}
\begin{theorem}\label{DescentGen} If $a_i$ is the number of descents in parking functions of length $n$ with $i$ ties, then its generating function is $ \sum_{i=0}^{n-1} a_i y^i = \mybinom{n}{2} (n+y)^{n-2}$.\end{theorem}
\begin{proof}From Lemma \ref{DescentTieCount}, we know that there are \( \frac{n-1-i}{2}\mybinom{n-1}{i}n^{n-1-i}\) descents in $\PF_{(n,i)}$, so we sum this number over $i$, giving
\[ \sum_{i=0}^{n-1} \frac{n-1-i}{2}\mybinom{n-1}{i}n^{n-1-i}y^{i} \text{.}\]
Setting \( j = n-1-i\) gives us \[ \sum_{j=0}^{n-1} \frac{j}{2}\mybinom{n-1}{j}n^j y^{n-1-j} = \sum_{j=0}^{n-1} \frac{n}{2}\mybinom{n-1}{j}j n^{j-1}y^{n-1-j}\text{.}\]
Temporarily replacing $n^{j-1}$ with $x^{j-1}$ yields
\begin{align*}
&\left[ \sum_{j=0}^{n-1} \frac{n}{2}\mybinom{n-1}{j}j x^{j-1}y^{n-1-j}\right]_{x=n} \\
=&\frac{n}{2}\left[ \frac{\partial }{\partial x} \left( \sum_{j=0}^{n-1} \mybinom{n-1}{j} x^j y^{n-1-j}\right)\right]_{x=n} \\
=&\frac{n}{2} \left[\frac{\partial }{\partial x} (x+y)^{n-1}\right]_{x=n}\\
=&\frac{n (n-1)}{2} (n+y)^{n-2}\\
=&\mybinom{n}{2} (n+y)^{n-2}\text{.}
\end{align*}
\end{proof}
Setting $y=1$ completes our proof of Theorem \ref{thm:descount}.
\begin{corollary}
The density of descents among steps is \(\frac{n}{2
(n+1)}\), or an average of \( \mybinom{n}{2} \frac{1}{n+1}\) descents
per parking function in $\PF_n$.
\end{corollary}
\begin{proof}There are \( (n-1) (n+1)^{n-1} \) steps in $\PF_n$.
Of these, \( \mybinom{n}{2} (n+1)^{n-2}\) are descents.
Division of the latter by the former gives us a density of \( \frac{n}{2 (n+1)}\). Multiplying by $n-1$ steps per parking function gives us the average number of descents per parking function.\end{proof}
By symmetry, all of these results hold for ascents.
\begin{remark}
This proof was given by the
author in his dissertation in 2009 \cite[Corollary A.12]{schumacher1}.
A probabilistic argument was given in 2017 by Diaconis and Hicks in
\cite[Eq.~4.1]{DiaconisAndHicks}.
\end{remark}
\section{Tree implications}
Two related results for trees are implied by the relationship of trees to
Pr\"{u}fer codes.
\begin{theorem}$\PF_n \cong \LT_{n+1}$, the set of labeled trees on $n+1$ nodes.\label{ParkTree}\end{theorem}
\begin{proof}Each parking function can be transformed into a corresponding
Pr\"{u}fer code, as shown above. Each Pr\"{u}fer code corresponds to exactly one labeled tree, as follows: Given a tree with vertices labeled $0$ to $n$, remove the node of valence one with the highest label, and note which node it was removed from. Repeat this process until only two nodes remain, forming a sequence of $n-1$ removals. The remaining two nodes will necessarily be the $0$ node and the last referenced node in the sequence other than $0$. (If all of the previous nodes were removed from $0$, the non-zero node must necessarily be the smallest non-zero node in the tree, i.e., $1$.) This gives us the Pr\"{u}fer code for the tree. For any sequence of $n-1$ elements of $[n+1]_0$, we get exactly one tree. Since we already have a bijection from the parking functions to the Pr\"{u}fer codes, this gives us a bijection to the labeled trees as well. (Proof paraphrased from Foata and Riordan \cite{FoataAndRiordan}, repeated here to show the map we use below.)\end{proof}
The algorithm for generating a Pr\"{u}fer code for a tree naturally removes nodes of valence one from the tree until only the node labeled $0$ remains. Because of this, by convention, we refer to the labeled trees as if they were rooted at the $0$ node. This allows us to refer to a node's parent, which is either the $0$ node, or the node on a path between a given node and the $0$ node.
\begin{corollary} There are \(\mybinom{n-1}{i} n^{n-1-i} \) labeled trees with $n+1$ nodes rooted at $0$ such that the node labeled $0$ has degree $i+1$.\end{corollary}
\begin{proof}In the Pr\"{u}fer code for any labeled tree, a $0$ in the code designates a node being removed that was connected to the node labeled $0$. When the tree is down to two nodes, one of them is the zero node, and the other is removed from it. This last node removal is understood and thus not listed in the Pr\"{u}fer code. This means that there were a total of $i+1$ nodes attached to the zero node, where $i$ is the number of zeroes in the Pr\"{u}fer code for the tree. The number of such codes is counted in the proof of Theorem \ref{thm:TieCount}.\end{proof}
\begin{corollary} If we fix a label $a \in \{1,\ldots,n\}$, there are \( \mybinom{n-1}{i} n^{n-1-i} \) labeled trees with $n+1$ nodes rooted at $0$ such that the node labeled $a$ has valence $i+1$.\end{corollary}
\begin{proof} We can create an automorphism on the set of labeled trees that switches the labels $0$ and $a$, and then re-root the tree at 0. Therefore, the number of trees with node $0$ having degree $i+1$ is the same as the number of trees with label $a$ having valence $i+1$.\end{proof}
\section{Remaining questions}
This article has explored the structure of the steps of parking functions and given formulas for several aspects of that structure, but there are questions remaining to be explored further.
If we count the number of parking functions in $\PF_n$ with $i$ ties and $j$ descents (leaving $n-1-j-i$ ascents), and arrange the totals in a grid (see Figure \ref{fig:desdist}), several interesting properties appear. The numbers along the diagonal edges are the Narayana numbers (as shown in Theorem \ref{thm:EdgeCount}). The row sums are given in Theorem \ref{thm:TieCount}. However, a general formula which gives the individual elements within each row (for rows of length $\geq 3$) is, as yet unknown. The elements within the rows show no nice properties, nor are they given by any sequence in the OEIS. Investigation into these elements shows that the inner terms are given by summation of multiples of earlier elements in the table. This can be seen by creating $\PF_{n}$ from $\PF_{i