\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}

\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}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}

\usepackage{tikz,multicol,enumitem}
%\usepackage[utf8]{inputenc}
%\usepackage{hyperref,longtable,multirow}
\usepackage{multirow}
%\usepackage[normalem]{ulem}
\usepackage{mathrsfs}
\usepackage{ytableau}

\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}

\newcommand{\Sym}{\ensuremath{\mathfrak{S}}}
\newcommand{\Des}{\mathrm{Des}}
\newcommand{\Asc}{\mathrm{Asc}}
\newcommand{\flick}{\mathrm{flick}}

\DeclareMathOperator{\A}{\texttt{A}}
% \newcommand{\A}{\texttt{A}}
\newcommand{\D}{\texttt{D}}
\newcommand{\T}{\texttt{T}}
\newcommand{\NDPF}{\mathrm{PF}^{\uparrow}}
\newcommand{\PF}{\mathrm{PF}}
\newcommand{\x}{\mathbf{x}}
\newcommand{\y}{\mathbf{y}}
\newcommand{\des}{\mathrm{des}}
\newcommand{\NN}{\mathbb{N}}

\newcommand{\Tie}{\mathrm{Tie}}
\newcommand{\Val}{\mathrm{Val}}
\newcommand{\PTPF}{\mathrm{PTPF}}
\newcommand{\VTPF}{\ensuremath{\mathrm{VTPF}}}
\newcommand{\stat}{\ensuremath{\mathrm{stat}}}
\newcommand{\BT}{\ensuremath{\mathrm{BT}}}
\newcommand{\tr}[1]{\textcolor{red}{#1}}
\newcommand{\tb}[1]{\textcolor{blue}{#1}}

\newcommand{\edit}[1]{\textcolor{blue}{#1}}


\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}
\newtheorem{problem}[theorem]{Problem}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf  On Some Discrete Statistics of \\
\vskip .1in
Parking Functions
}
\vskip 1cm
\large
            Ari Cruz,
            Pamela E. Harris,\footnote{P.~E.~Harris was partially supported by a Karen Uhlenbeck EDGE Fellowship.}
            Kimberly J.~Harry,
            Jan Kretschmann,\\ 
            Matt McClinton, 
            Alex Moon, and
            John O. Museus\\
            Department of Mathematical Sciences\\
            University of Wisconsin-Milwaukee\\
            Milwaukee, WI 53211\\
            USA\\
            \href{mailto:aricruz@arizona.edu}{\tt aricruz@arizona.edu}\\
            \href{mailto:kjharry@uwm.edu}{\tt kjharry@uwm.edu}\\
            \href{mailto:mcclin33@uwm.edu}{\tt mcclin33@uwm.edu}\\
            \href{mailto:jomuseus@uwm.edu}{\tt jomuseus@uwm.edu}\\
            \href{mailto:peharris@uwm.edu}{\tt peharris@uwm.edu}\\
            \href{mailto:kretsc23@uwm.edu}{\tt kretsc23@uwm.edu}\\
            \href{mailto:ajmoon@uwm.edu}{\tt ajmoon@uwm.edu}\\
            \ \\
            Eric Redmon\\
            Department of Mathematics and Statistics\\
            Marquette University\\
            Milwaukee, WI 53233\\
            USA\\
            \href{mailto:eric.redmon@marquette.edu}{\tt eric.redmon@marquette.edu}\\
\end{center}

\vskip .2 in


\begin{abstract}
A parking function is a sequence $\alpha=(a_1,a_2,\ldots,a_n)\in[n]^n$ whose nondecreasing rearrangement
$\beta=(b_1,b_2,\ldots,b_n)$ satisfies $b_i\leq i$ for all $1\leq i\leq n$.  
We study parking functions by their ascents (indices at which $a_i<a_{i+1}$),  descents (indices at which $a_i>a_{i+1}$), and ties (indices at which $a_i=a_{i+1}$).
By using multiset Eulerian polynomials, we give a generating function for the number of parking functions of length $n$ with $i$ descents. 
We present a recursive formula for the number of parking functions of length $n$ with descents at a specified subset of $[n-1]$. 
We establish the set of parking functions with descent set $I$ and the set of parking functions with descent set $J=\{n-i : i\in I\}$ are in bijection, and hence these sets have the same cardinality. 
As a special case, we show that the number of parking functions of length $n$ with descents at the first $k$ indices is given by $\frac{1}{n}\binom{n}{k}\binom{2n-k}{n-k-1}$. 
We prove this by bijecting to the set of standard Young tableaux of shape $((n-k)^2,1^k)$, which are enumerated by the same formula. 
We also study peaks and valleys of parking functions, which are indices at which $a_{i-1}<a_i>a_{i+1}$ and $a_{i-1}>a_i<a_{i+1}$, respectively. 
We show that the set of parking functions with no peaks and no ties is enumerated by the Catalan numbers, and the set of parking functions with no valleys and no ties is enumerated by the Fine numbers. 
We conclude our study by characterizing when a parking function is uniquely determined by its statistic encoding; a word indicating which indices in the parking function are ascents, descents, and ties. 
We provide open problems throughout.
\end{abstract}

\section{Introduction}
Throughout, we let $\mathbb{N}=\{1,2,3,\ldots\}$ and $[n]=\{1,2,\ldots,n\}$ for $n\in\mathbb{N}$. We define $[0]=\emptyset$.
Moreover, we let $\mathfrak{S}_n$ denote the set of permutations of $[n]$ and 
we use the one-line notation $\pi=\pi_1~\pi_2~\cdots~\pi_n$ to denote elements of~$\mathfrak{S}_n$.
If $\pi_{i}>\pi_{i+1}$, then  $\pi$ has a \textit{descent} at index $i$; and if $\pi_{i}<\pi_{i+1}$, then $\pi$ has an \textit{ascent} at index~$i$.
There is a long history of studying and enumerating permutations with certain descents and ascents.
This dates back to the work of MacMahon, who established that for a fixed set $I$, with $n \geq \max(I)$ varying, the number of permutations in $S_n$ with descent set $I$ is a polynomial in $n$~\cite[Art.\ 157]{MacMahon}. 
These polynomials are often referred to as \textit{descent polynomials}, and the coefficients of these polynomials and their roots are studied
in the literature \cite{Bencs,DescentPolys}. 
Moreover, there is ample work on generalizing these findings to multipermutations \cite{Elizalde,jiradilok2021roots,Raychev}. 
In the present paper, we are motivated by the work of 
Schumacher, who enumerated descents, ascents, and ties in parking functions \cite{Schumacher}. 

\begin{figure}[htbp]
    \centering
\begin{tikzpicture}[yscale=.5, xscale=.75]
\draw[thick] (0.5,6.5)--(0.5,0.5)--(9.5,0.5);
\node at (0,1)[scale=.75]{$1$};
\node at (0,2)[scale=.75]{$2$};
\node at (0,3)[scale=.75]{$3$};
\node at (0,4)[scale=.75]{$4$};
\node at (0,5)[scale=.75]{$5$};
\node at (0,6)[scale=.75]{$6$};
\draw[thick] (1,3)--(2,1)--(3,5)--(4,6)--(5,4)--(6,3)--(7,3)--(8,2)--(9,1);
\node at (1,3){$\bullet$};
\node at (2,1){$\bullet$};
\node at (3,5){$\bullet$};
\node at (4,6){$\bullet$};
\node at (5,4){$\bullet$};
\node at (6,3){$\bullet$};
\node at (7,3){$\bullet$};
\node at (8,2){$\bullet$};
\node at (9,1){$\bullet$};
\node at (1,0)[scale=.75]{$1$};
\node at (2,0)[scale=.75]{$2$};
\node at (3,0)[scale=.75]{$3$};
\node at (4,0)[scale=.75]{$4$};
\node at (5,0)[scale=.75]{$5$};
\node at (6,0)[scale=.75]{$6$};
\node at (7,0)[scale=.75]{$7$};
\node at (8,0)[scale=.75]{$8$};
\node at (9,0)[scale=.75]{$9$};
\end{tikzpicture} 
\caption{Graph of the parking function $(3,1,5,6,4,3,3,2,1)\in\PF_{9}$.}
    \label{fig:enter-label}
\end{figure}

A parking function is a sequence $\alpha=(a_1,a_2,\ldots,a_n)\in[n]^n$ whose nondecreasing rearrangement
$\beta=(b_1,b_2,\ldots,b_n)$ satisfies $b_i\leq i$ for all $1\leq i\leq n$.
Parking functions encode the parking preferences for $n$ cars in a queue attempting to park on a one-way street with $n$ parking spots numbered sequentially as follows. 
For $i\in [n]$, car $i$ enters the street and attempts to park in spot $a_i$. 
If that parking spot is available, car $i$ parks.
If the parking spot is occupied, then the car moves forward attempting to park in the first available spot the car encounters.
If no such a spot exists, we say the car fails to park. 
If all cars are able to park under this parking scheme, then $\alpha$ is a parking function.

We let $\PF_n$ denote the set of parking functions of length $n$. 
If $\alpha=(a_1,a_2,\ldots,a_n)\in\PF_n$, then $\alpha$ has descents and ascents defined in the analogous way as for permutations, and $\alpha$ has a \textit{tie} at $i$ if $a_i=a_{i+1}$. 
In Figure \ref{fig:enter-label}, we plot $(i,a_i)$ to illustrate the parking function $\alpha=(3,1,5,6,4,3,3,2,1)\in\PF_{9}$
has descents at $1$, $4$, $5$, $7$, and $8$, ascents at $2$ and $3$, and a tie at $6$.
Let $\des(\alpha)$ denote the number of descents in $\alpha$.
Schumacher showed that
the number of descents among all parking functions of length $n$ is  $\binom{n}{2}(n+1)^{n-2}$ \cite[Theorem 10]{Schumacher}.
Schumacher also showed that the set of parking functions with exactly $i$ ties, denoted $\PF_{(n,i)}$, is enumerated by
\begin{align}\label{rowsums}
|\PF_{(n,i)}|&=\binom{n-1}{i}n^{n-1-i}
\end{align}
\cite[Theorem 13]{Schumacher} and
\begin{align*}
\sum_{\alpha\in\PF_{(n,i)}}\des(\alpha)&=\frac{n-1-i}{2}\binom{n-1}{i}n^{n-1-i},\label{thm:pfs with i ties}
\end{align*}
\cite[Lemma 17]{Schumacher}.
Let $T_n(i,j)$ denote the number of parking functions of length $n$ with $i$ ties and $j$ descents. 
If $i+j\geq n$, then $T_n(i,j)=0$. 
Table \ref{recreate table} provides the values of $T_6(i,j)$ arranged in a triangular array such that 
$i$ decreases from top to bottom and $j$ decreases from left to right.\footnote{Table \ref{recreate table} first appeared in a paper by Schumacher \cite[Figure 2]{Schumacher}, however there was a typographical error for the value $T_6(3,1)$, which should be 260.} 
More information on this triangle can be found on the OEIS \seqnum{A333829}.

\begin{figure}[htbp]
    \centering
    \begin{tabular}{cccccccccccccc}
        &&&&&&&&\rotatebox{45}{$j=0$}&&&&&\\
         $i=5$&&&&&&&1&&\rotatebox{45}{$j=1$}&&&&\\
         $i=4$&&&&&&15&&15&&\rotatebox{45}{$j=2$}&&&\\
         $i=3$&&&&&50&&260&&50&&\rotatebox{45}{$j=3$}&&\\
         $i=2$&&&&50&&1030&&1030&&50&&\rotatebox{45}{$j=4$}&\\
         $i=1$&&&15&&1240&&3970&&1240&&15&&\rotatebox{45}{$j=5$}\\[4.5mm]
         $i=0$&&1&&407&&3480&&3480&&407&&1&
    \end{tabular}
    \caption{Parking function distribution for $n = 6$.}\label{recreate table}
\end{figure}

For general $n$, the numbers along the diagonal edges of the triangular array in Figure \ref{recreate table} are the Narayana numbers \cite[Theorem 12]{Schumacher}
\[T_n(i,0)=T_n(n-1-i,i)=\frac{1}{i+1}\binom{n}{i}\binom{n-1}{i},\]
and the row sums are given by \eqref{rowsums}.
General closed formulas for the values of $T_n(i,j)$ remain {unknown}.
However, in Section \ref{sec:eulerian}, we utilize multiset Eulerian polynomials to give a generating function for the values $\sum_{i=0}^nT_n(i,j)$. 
Our first result follows which we prove later in this section.

\begingroup
\def\thetheorem{\ref{thm:eulerian}}
\begin{theorem}
    Consider the generating function $\sum_{n =1}^{\infty}\sum_{j=1}^{n-1}d(n,j)y^jx^n$, where $d(n,j)$ is the number of parking functions in $\PF_n$ that have $j$ descents, and let $\NDPF_n$ denote the set of nondecreasing parking functions of length $n$. 
    Then 
    \begin{align*}
\sum_{n=1}^{\infty}\sum_{\alpha \in \PF_n} x^ny^{\des(\alpha)} = \sum_{n =1}^{\infty}\sum_{j=1}^{n-1}d(n,j)x^ny^j = \sum_{n=1}^{\infty} \left(\sum_{\beta \in \NDPF_n} A_{M(\beta)}(y) \right) x^n,
    \end{align*}
    where $A_\beta(y)$ denotes the multiset Eulerian polynomial in $y$ on all multipermutations of $\beta$.
\end{theorem}
\addtocounter{theorem}{-1}
\endgroup

Now, we turn our attention to \textit{descent sets} of parking functions. 
Given a multiset $X$ of size $n$ with elements in $[n]$, we let $W(X)$ denote the set of multiset permutations of $X$, written as words $w = w_1~w_2~\cdots~w_n$.
If $I\subseteq[n-1]$, then the set of words in $W(X)$ whose descent set is exactly $I$ is denoted
\begin{align*}
D_X(I)&=\{w\in W(X)\,:\,\Des(w)=I \},
\end{align*}
where $\Des(w)=\{i\in[n-1]: w_{i}>w_{i+1}\}$.
Let $D_X(I)=|D_X(I)|$.
Let $X$ be the set of nondecreasing parking functions where each $\beta\in\NDPF_n$ is considered as a multiset, denoted as $M(\beta)$.
If $I\subseteq[n-1]$, then define
\[D(I;n)=\{\alpha\in\PF_n:\Des(\alpha)=I\}=\displaystyle\bigsqcup_{\beta\in\NDPF_n}D_{M(\beta)}(I),\]
where $\bigsqcup$ denotes the sets are disjoint.
We let
$d(I;n)=|D(I;n)|=\sum_{\beta\in\NDPF_n}d_{M(\beta)}(I)$.
The set $D(\emptyset;n)=\NDPF_n$,  and it is known that $|\NDPF_n|=C_n=\frac{1}{n+1}\binom{2n}{n}$, the $n$th Catalan number \seqnum{A000108}. 
Hence, $d(\emptyset;n)=C_n$.

In Section~\ref{sec:descent sets}, we consider nonempty descent sets $I\subseteq[n-1]$ and establish the following results:
\begin{itemize}
    \item Theorem~\ref{thm:I and J}: The set of parking functions with descent set $I$ and the set of parking functions with descent set $J=\{n-i : i\in I\}$ are in bijection, and hence these sets have the same cardinality. 
    Namely, $d(I;n)=d(J;n)$.
    \item Theorem~\ref{thm:recursion}:
    Let $I\subseteq[n-1]$ be nonempty, $m=\max(I)$, and $I^-=I\setminus\{m\}$.  
Then
\begin{align}
d(I;n)=\sum_{\beta\in \NDPF_n}\; \left(\sum_{X\in\mathcal{M}(\beta,m)}d_{X}(I^-)\right)-d(I^-;n),\label{eq:recursion}
\end{align}
where, for $\beta\in\NDPF_n$,  $\mathcal{M}(\beta,m)$ denotes  the collection of multisets consisting of $m$ elements of $\beta$.


We remark that Equation~\eqref{eq:recursion} is a generalization of Diaz-Lopez, Harris, Insko, Omar, and Sagan's result \cite[Proposition 2.1]{DescentPolys}, which gives a recursion for the number of permutations with a given descent set. 
\item Proposition~\ref{prop:biject to SYT}: Let $n\geq 1$ and $0 \leq k \leq n-1$. 
If $[k]\subseteq[n-1]$, then
\begin{align}\label{descent binome}
    d([k];n) = \frac{1}{n}\binom{n}{k}\binom{2n-k}{n-k-1}.
\end{align}
The proof of Proposition~\ref{prop:biject to SYT} is given by a bijection between parking functions of length $n$ with descent set $[k]$ and the set of standard Young tableaux of shape $\lambda=((n-k)^2, 1^k)$. 
Hence, Equation~\eqref{descent binome} can be seen as the reindexing $d([k];n) = f(n, n-k-1)$.
\end{itemize}

Other permutation statistics of interest are peaks and valleys.
Let $\pi=\pi_1~\pi_2~\cdots~\pi_n\in\mathfrak{S}_n$. Recall that if $\pi_{i-1}<\pi_i$ and $\pi_{i} >\pi_{i+1}$, then $i$ is a \textit{peak} of $\pi$. Also recall that if $\pi_{i-1}>\pi_i$ and $ \pi_{i}<\pi_{i+1}$, then $i$ is a \textit{valley} of~$\pi$.
Billey, Burdzy, and Sagan \cite{billey:peak-set} showed that the number of elements in $\mathfrak{S}_n$ with peaks exactly at $I\subset[n-1]$ is given by $p(n)2^{|I|-1}$, where $p(n)$ is a polynomial in $n$ whose degree is one less than the maximum of the set $I$.
The polynomial $p(n)$ is called the \textit{peak polynomial}.
It was conjectured that $p(n)$ has a positive integer expansion in a binomial basis centered at the maximum of $I$ and was proven in the affirmative by Diaz-Lopez, Harris, Insko, and Omar \cite{peakpoly}.
Motivated by these results, we study the set $\PTPF_n$ consisting of peakless-tieless parking functions of length $n$, which is the subset of parking functions that have no peaks and no ties.

In Section \ref{sec:PTPFN}, we prove the following:
\begin{itemize}
\item Corollary~\ref{cor:peakless tieless catalan}: If $n\geq 1$, then $|\PTPF_{n}|=C_n$, the $n$th Catalan number.    
\item Corollary~\ref{cor:cat triangle}:
    If $\PTPF_{n}(i)=\{\alpha=(a_1,a_2,\ldots,a_n)\in\PTPF_{n}: a_n=i\}$, then 
    \[|\PTPF_{n}(i)|=C_{n,i}\;,
    \]
    where $C_{n,i}$ denotes the $i$th entry in the $n$th row of the Catalan triangle  \seqnum{A009766}. 
\end{itemize} 
We also prove in Theorem~\ref{thm:main2} that the number of parking functions of length $n$ with no valleys 
and no ties is the Fine numbers 
\seqnum{A000957}.
To those who are used to thinking about permutations, this asymmetry between peaks and valleys may be surprising.
It remains an open problem to enumerate all parking functions with a particular peak or valley set. 

In Section \ref{sec:statistic encoding}, we study the characterization of parking functions by the locations of their ascents, descents, and ties which we call the statistic encoding of a parking function. 
We establish the existence of parking functions for every statistic encoding and fully characterize the parking functions that are uniquely identified by their statistic encoding.

\begin{remark}
    We present open problems, labeled ``Problem $n$'', throughout the paper.
\end{remark}

\section{Permutations of multisets}\label{sec:eulerian}
For a multiset $M$ of positive integers, we let $m_i$ denote the multiplicity of $i$ in $M$ for all $i\in[n]$.
A \textit{multipermutation} of $M$ is a word $\pi=\pi_1~\pi_2~\cdots~\pi_{m}$ where $m=m_1+m_2+\cdots+m_n$ and $\pi$ contains $i$ exactly $m_i$ times for all $i \in [n]$.
We let $\mathfrak{S}_M$ denote the set of multipermutations on $M$.
A \emph{descent} in a multipermutation $\pi$ is an index $j$ such that $\pi_j > \pi_{j+1}$.
As before, we let $\mathrm{des}(\pi)$ be the number of descents of $\pi$. 
Then
\begin{align}
\label{eq:eulerianDef}
    A_{M}(t) = \sum_{\pi \in \mathfrak{S}_M} t^{\mathrm{des}(\pi)}
\end{align}
is
the \emph{multiset Eulerian polynomial}, 
where $\mathfrak{S}_M$ is the set of all multipermutations on $M$.
The coefficients of $A_M(t)$ 
count the number of permutations of a given multiset with a certain number of descents and are known as the \emph{Simon Newcomb numbers}.
MacMahon~\cite[p.~211]{MacMahon} showed that $A_M(t)$ occurs as the numerator of the following generating function:
\begin{align}
    \label{eq:genmac}
    \frac{A_M(t)}{(1-t)^{m +1}} = \sum_{\ell=1}^{\infty}\prod_{i=1}^{n} \binom{m_i+\ell}{\ell}t^\ell.
\end{align}
Equation~\eqref{eq:genmac} allows for the explicit computation of the coefficients as
\begin{align}
\label{eq:eulercoeff}
[t^k] A_M(t)=\left|\left\{\pi\in \mathfrak{S}_M : \mathrm{des}(\pi)=k\right\}\right| = \sum_{\ell=0}^k(-1)^{\ell}\binom{m +1}{\ell}\prod_{i=1}^n\binom{m_i + k - \ell}{k - \ell},
\end{align}
where $[t^k] A_M(t)$ denotes the coefficient of $t^k$ in $A_M(t)$. 
Using \eqref{eq:eulercoeff}, we enumerate descents in parking functions, a superset of permutations, and generalize the results of 
Schumacher~\cite{Schumacher}. 

Now consider the generating function
\begin{align}
    \label{eq:genFcNoSol}
    \sum_{n =1}^{\infty}\sum_{j=1}^{n-1}d(n,j)x^ny^j,
\end{align}
where $d(n,j)$ is the number of parking functions in $\PF_n$ that have $j$ descents.
We can now prove Theorem~\ref{thm:eulerian} and use it to compute~\eqref{eq:genFcNoSol}. 
We restate the theorem more succinctly below.
\begin{theorem}\label{thm:eulerian}
Let $n \in \mathbb{N}$, then the generating function encoding the number of descents throughout all $\PF_n$ is given by
\begin{align*}
    \sum_{n=1}^{\infty}\sum_{\alpha \in \PF_n} x^ny^{\des(\alpha)} = \sum_{n =1}^{\infty}\sum_{j=1}^{n-1}d(n,j)x^ny^j = \sum_{n=1}^{\infty} \left(\sum_{\beta \in \NDPF_n} A_{M(\beta)}(y) \right) x^n.
\end{align*}
\end{theorem}
\begin{proof}
The result follows from Equation~\eqref{eq:eulerianDef}. 
For more details, reference the work by Dillon and Roselle~\cite[Equation~3.7]{dillon}.
\end{proof}
\setcounter{section}{2}
To better understand Theorem~\ref{thm:eulerian}, we present the case where $n=3$.
\begin{example}
\label{ex:multieuler}
    Let $n=3$. 
    We have $\NDPF_3=\{(1,1,1),(1,1,2),(1,1,3),(1,2,2),(1,2,3)\}$.
    We can partition the set $\PF_3$ into $\Sym_3$-orbits of the elements of $\NDPF_3$, where $\Sym_3$ acts by permuting preferences:
    \[
        \PF_3= \Sym_3 (1,1,1) \bigsqcup \Sym_3 (1,1,2) \bigsqcup \Sym_3 (1,1,3) \bigsqcup \Sym_3 (1,2,2) \bigsqcup \Sym_3 (1,2,3).
    \]
    We can compute $A_\alpha(y)$ for each $\alpha\in\NDPF_3$ 
    using~\eqref{eq:eulercoeff}.
    For example, we find
    \[
        \Sym_3 (1,1,2) = \{(1,1,2),(1,2,1),(2,1,1)\},
    \]
    and therefore
    $
        A_{(1,1,2)}(y) = 2y+1
    $.
    Summing over all elements of $\NDPF_3$, we retrieve
    \[
        \sum_{\alpha \in \NDPF_3} A_{\alpha}(y) =y^2+10y+5.
    \]
    Similarly, we can recover results from Schumacher~\cite[Figure~2]{Schumacher} (see Figure~\ref{recreate table}), who provides counts for the numbers of parking functions with $i$ ties and $j$ descents.
    Setting $n=6$, we find
    \[
        \mathcal{A}_6 = \sum_{\alpha \in \NDPF_6} A_{\alpha}(y)= y^5 + 422y^4 + 4770y^3 + 8530y^2 + 2952y + 132.
    \]
    Each coefficient in $\mathcal{A}_6$ agrees with the sum of a diagonal of Schumacher's triangle (from the top left to the bottom right): there is $1$ element in $\PF_6$ with $5$ descents, there are $422$ elements in $\PF_6$ with $4$ descents, and so on.
\end{example}

\begin{remark}
    Recall that $|\NDPF_n|=C_n$, where $C_n$ is the $n$th Catalan number. 
    Therefore, partitioning $\PF_n$ into $\Sym_n$-orbits 
    means partitioning $\PF_n$ into $C_n$ disjoint subsets.
    Setting $t=1$ in 
    $\sum_{\alpha \in \NDPF_n}A_\alpha(t)$
    gives us
    the known enumeration for parking functions: 
    \[(n+1)^{n-1}=\sum_{\alpha \in \NDPF_n}A_\alpha(1).\]
\end{remark}

\begin{problem} Give formulas for $T_n(i,j)$ which denotes the number of parking functions of length $n$ with $i$ ties and $j$ descents. 
\end{problem}

\section{Descent sets of parking functions}\label{sec:descent sets}
We now consider parking functions with a specified descent or ascent set. 
We restate the definition of $\Des(\alpha)$ for clarity for the reader and define $\Asc(\alpha)$.
For $\alpha=(a_1,a_2,\ldots,a_n)\in\PF_n$, we let 
$\Des(\alpha)=\{i\in[n-1]: a_{i}>a_{i-1}\}$ {and $\Asc(\alpha) = \{i \in [n-1]: a_{i} < a_{i-1}\}$}. 
For $I\subseteq[n-1]$, define 
\begin{align*}D(I;n)&=\{\alpha\in\PF_n:\Des(\alpha)=I\},\mbox{ and}\\{A(I;n)}&={\{\alpha \in \PF_n:\Asc(\alpha) = I\}},
\end{align*}
and denote {their cardinalities} by $d(I;n)=|D(I;n)|$ {and $a(I;n) = |A(I;n)|$.}

Recall that $D(\emptyset;n)=\NDPF_n$ and 
that $|\NDPF_n|=C_n=\frac{1}{n+1}\binom{2n}{n}$, the $n$th Catalan number \seqnum{A000108}. 
Hence, $d(\emptyset;n)=C_n$.
For $1\leq n\leq 4$, Table \ref{tab:descent sets} provides data on the number of parking functions with a given descent set.

\begin{table}
\centering
\begin{tabular}{|c|c|c|p{4in}|}
    \hline
         $n$&$I\subseteq[n-1]$&$d(I,n)$&$D(I,n)$     
 \\\hline\hline
 $1$ & $\emptyset$&$C_1=1$ & $1$ \\\hline
 \multirow{2}*{2}&$\emptyset$&$C_2=2$ & $11$, $12$\\\cline{2-4}
 &$\{1\}$ & $1$ & $21$\\\hline
         \multirow{4}*{3}&$\emptyset$ &$C_3=5$&
         $111$,
$112$,
$113$,
$122$,
$123$\\\cline{2-4}
&$\{1\}$ & $5$ &
$211$,
$311$,
$212$,
$213$,
$312$
\\\cline{2-4}
&$\{2\}$ & $5$ &
$131$,
$121$,
$221$,
$132$,
$231$
\\\cline{2-4}
&$\{1,2\}$ & $1$ & $321$ \\\hline
\multirow{17}*{4}&$\emptyset$&\multirow{2}*{$C_4=14$}&
$1111$, 
$1112$,
$1113$
$1114$,
$1122$,
$1123$,
$1124$,
$1133$,
$1134$,
$1222$,
$1223$,
$1224$,
$1233$,
$1234$\\\cline{2-4}
&\multirow{3}*{$\{1\}$}&\multirow{3}*{21}&
$2111$,
$3111$,
$4111$,
$2112$,
$2113$,
$3112$,
$2114$,
$4112$,
$3113$,
$3114$,
$4113$,
$2122$,
$2123$,
$3122$,
$4122$,
$2133$,
$3123$,
$2134$,
$3124$,
$4123$,
$2124$
\\\cline{2-4}
&\multirow{4}*{$\{2\}$}&\multirow{4}*{31}&
$1211$,
$1311$,
$1411$,
$1212$,
$2211$,
$1213$,
$1312$,
$2311$,
$1214$,
$1412$,
$2411$,
$1313$,
$3311$,
$1314$,
$1413$,
$3411$,
$2212$,
$1322$,
$2213$,
$2312$,
$1422$,
$2214$,
$2412$,
$1323$,
$2313$,
$3312$,
$1324$,
$1423$,
$2314$,
$2413$,
$3412$
\\\cline{2-4}
&\multirow{3}*{$\{3\}$}&\multirow{3}*{21}&
$1121$,
$1131$,
$1141$,
$1221$,
$1132$,
$1231$,
$1142$,
$1241$,
$1331$,
$1143$,
$1341$,
$2221$,
$1232$,
$2231$,
$1242$,
$2241$,
$1332$,
$2331$,
$1243$,
$1342$,
$2341$
\\\cline{2-4}
&$\{1,2\}$& $9$ &
$3211$,
$4211$,
$4311$,
$3212$,
$4212$,
$3213$,
$3214$,
$4213$,
$4312$
\\\cline{2-4}
&$\{1,3\}$& $19$ &
$2121$,
$2131$,
$3121$,
$4121$,
$3131$,
$2141$,
$3141$,
$4131$,
$2132$,
$3221$,
$2142$,
$3121$,
$3231$,
$4221$,
$2143$,
$3142$,
$3241$,
$4132$,
$4231$
\\\cline{2-4}
&$\{2,3\}$& $9$ &
$1321$,
$1421$,
$1431$,
$2421$,
$3321$,
$1432$,
$2431$,
$2321$,
$3421$
\\\cline{2-4}
&$\{1,2,3\}$& $1$ & $4321$
\\\hline
    \end{tabular}
    \caption{Parking functions of length $1\leq n\leq 4$ with a given descents set.}
    \label{tab:descent sets}
    \end{table}
    

    
Next, we prove some preliminary results which help establish that the number of parking functions with descents at the indices in $I\subseteq[n-1]$ is the same as the number of parking functions with descents at indices in $J=\{n-i:i\in I\}$.

\begin{proposition}\label{prop:flipflop}
    Let $I \subseteq [n-1]$ and $J = \{n-i:i \in I\}$. 
    Then $d(I;n) = a(J;n)$
\end{proposition}
\begin{proof}
    Given $\alpha = (\alpha_1,\alpha_2,\ldots, \alpha_n)$ with $\Des(\alpha) = I$, then $(\alpha_n,\alpha_{n-1},\ldots,\alpha_1)$ has $\Asc(\alpha) = J$. 
    This defines a bijection between the sets $D(I;n)$ and $A(J;n)$. 
    Thus, $d(I;n)=a(J;n)$, as claimed.
\end{proof}

Next, we define a function used in our subsequent results.
To simplify notation, we denote tuples in one-line notation and refer to them as words, i.e., the tuple $(w_1, w_2, \ldots, w_n)$ is written as the word $w_1~w_2~\cdots ~w_n$. 

\begin{definition}\label{def:nu}
    Let $\Sym_n(\y)$
    denote the orbit of $\y \in \mathbb{N}^n$ under the action of the symmetric group $\Sym_n$ permuting indices.
    Given $\x\in\Sym_n(\y)$, let $\argmin(\x)$ denote the set of indices of minimal elements of $\x$ and $\argmax(\x)$ denote the set of indices of maximal elements of $\x$.
    
    Define the map $\nu: \Sym_n(\y) \to \Sym_n(\y)$ recursively as follows.
    For $\x\in\Sym_n(\y)$:
    \begin{enumerate}[leftmargin=.7in]
    \item[Case $0$:] If the length of $\x$ is $0$ or $1$, then $\nu(\x)=\x$. 
        \item[Case $1$:] 
        If the length of $\x$ is larger than $1$ and $a \geq b$ for all $a \in \argmin(\x)$ and $b \in \argmax(\x)$,
        then let $i = \max(\argmin(\x))$ and $j = \min(\argmax(\x))$. 
        Then 
        \[\nu(\x) = \nu(x_1~x_2~\cdots~x_{j-1}) \,~ x_i \,~ \nu(x_{j+1}~\cdots~  x_{i-1}) \, ~x_j \,~ \nu(x_{i+1} ~\cdots~ x_n).\]

        \item[Case $2$:] 
        If the length of $\x$ is larger than $1$ and there is some $a < b$ with $a \in \argmin(\x)$ and $b \in \argmax(\x)$,  then
        let $i$ be the greatest element of $\argmin(\x)$ that is smaller than some element of $\argmax(\x)$ and let $j$ be the smallest element of $\argmax(\x)$ greater than $i$. 
        Then  
        \[\nu(\x) = \nu(x_1~x_2~\cdots ~x_{i-1}) \, ~x_j~ \, \nu(x_{i+1}~\cdots~ x_{j-1}) \,~ x_i \,~ \nu(x_{j+1} ~\cdots~ x_n).\]
    \end{enumerate}
\end{definition}

We illustrate Definition \ref{def:nu} in the following example.

\begin{example}\label{ex:nu}
Let $\y=(1,1,1,1,2,3,3,4,4)\in \mathbb{N}^9$ and
consider $\x = (1,4,1,3,4,3,1,2,1) \in \Sym_n(\y) $. 
We write $\x$ in one-line notation as:
    $\x = 1~4~1~3~4~3~1~2~1$. 
    Note $\Asc(\x) = \{1,3,4,7\}$,  
    $\argmin(\x)=\{1,3,7,9\}$, and $\argmax(\x)=\{2,5\}$. 
    We use Definition \ref{def:nu} to give $\nu(\x)$.
    \begin{itemize}
        \item Since the length of $\x$ is larger than $1$ and there exists $a\in\argmin(\x)$ and $b\in\argmax(x)$ with $a<b$, we are in Case~$2$.  
        Then $i=3$ and $j=5$. 
        Hence,
        \begin{align}
        \nu(\x) &= \nu(1~4)~\underbrace{4}_{~x_5}~\nu(3)~~\underbrace{1}_{x_3}~~\nu(3~1~2~1).\label{exofnu}
        \end{align}
        We now consider $\nu(1~4)$, $\nu(3)$ and $\nu(3~1~2~1)$ independently.
        \item For the subword $1~4$, we are again in Case $2$.
        So, $\nu(1~4)=4~1$. 
        \item Since $3$ has length $1$, by Case 0,
        $\nu(3)=3$.
        \item For the subword $3~1~2~1$, $\argmin(3~1~2~1)=\{2,4\}$ and $\argmax(3~1~2~1)=\{1\}$. 
        Hence by Case 1, 
        $\nu(3~1~2~1)=1~\nu(1~2)~3$. 
        Then by Case 2, $\nu(1~2)=2~1$. 
    \end{itemize}
    Substituting these findings into Equation~\eqref{exofnu} yields
    \[\nu(1~4~1~3~4~3~1~2~1)=4~1~4~3~1~1~2~1~3
    .\]
\end{example}

The following remark is helpful and uses wording we implement in subsequent proofs.
\begin{remark}\label{rem:useful}
In Definition \ref{def:nu},
    Case $1$ only considers words $\x$ whose minimal value(s) all appear to the right of all of its maximal value(s).
    Applying $\nu$ to $\x$, the result is a word $\nu(\x)$ that has 
    all maximal value(s) to the right of all minimal value(s).
    Whenever $\x$ has a minimal value to the left of a maximal value, then Case $2$ in Definition~\ref{def:nu} is applied.
    Applying $\nu$ to $\x$ results in $\nu(\x)$ having a minimal value to the left of a maximal value. 
\end{remark}

\begin{proposition}\label{prop:NN-AscToDes}
    Fix $\y \in \mathbb{N}^n$.
    The restriction of the map $\nu$ 
    taking the set of elements of $\Sym_n(\y)$ with ascent set $I$ to the set of elements of $\mathfrak{S}(\y)$ with descent set $I$ is a bijection.
\end{proposition}

Before proving Proposition~\ref{prop:NN-AscToDes}, we need the following lemmas.

\begin{lemma}\label{lem:AsctoDes}
    Let $\y\in\mathbb{N}^n$ and $\x\in\Sym_n(\y)$. 
    Then $\Asc(\x) = \Des(\nu(\x))$ for $\nu$ as defined in Definition~\ref{def:nu}.
\end{lemma}

\begin{example}
    Continuing Example~\ref{ex:nu}, observe that 
        $\Asc(\x) = \Asc(1~4~1~3~4~3~1~2~1) = \{1, 3, 4, 7\}$ and $\Des(\nu(\x)) = \Des(4~1~4~3~1~1~2~1~3) = \{1, 3, 4, 7\}$, thus $\Asc(\x) = \Des(\nu(\x))$.
\end{example}

\begin{proof}[Proof of Lemma~\ref{lem:AsctoDes}]
    Let $x$ and $y$ have length $n$.
    For the base case, if $n=0$ or $n=1$, then by Case 0 
    of Definition~\ref{def:nu}, $\nu(\x)=\x$ and 
    $\Asc(\x) = \emptyset = \Des(\nu(\x))$. 
    
Fix $n>1$, $\y\in\mathbb{N}^n$, and $\x\in\Sym_n(\y)$.
Assume, for strong induction, that for all $k < n$, $\y' \in \mathbb{N}^{k}$, and $\x' \in \Sym_{k}(\y')$, we have $\Asc(\x') = \Des(\nu(\x'))$. 
We now consider $\nu(\x)=\nu(x_1~x_2~\cdots~x_n)$ and proceed via a case-by-case analysis given by the cases in Definition \ref{def:nu}.
    \begin{enumerate}[leftmargin=.7in]
    \item[Case $1$:] Suppose $a \geq b$ for all $a \in \argmin(\x)$ and $b \in \argmax(\x)$.        
    Let $M=\max(\x)$ and let $m=\min(\x)$. 
    Then
        \begin{align*}
            \x &= x_1~ x_{2}~\cdots~x_{j-1}~ \underbrace{M}_{j} ~ x_{j+1}~\cdots~x_{i-1}~ \underbrace{m}_{i} ~x_{i+1}~ \cdots ~x_{n}
        \end{align*}
        where $j = \min(\argmax(\x))$ and $i = \max(\argmin(\x))$.
        By Case $1$ in Definition \ref{def:nu},
        \begin{align*}
            \nu(\x) &= \nu(x_1~x_2~\cdots~x_{j-1}) \,~ \underbrace{m}_{j} \,~ \nu(x_{j+1}~\cdots~  x_{i-1}) \, ~\underbrace{M}_{i} \,~ \nu(x_{i+1} ~\cdots~ x_n).
        \end{align*}
        By the inductive hypothesis, for each \[\x'\in\{x_1
        ~x_2~\cdots~x_{j-1},~x_{j+1}~x_{j+2}~\cdots~ x_{i-1},~ x_{i+1}~x_{i+2}~\cdots~ x_{n}\}\] we know $\Asc(\x') = \Des(\nu(\x'))$.
        Thus, we only need to examine $\nu(\x)$ at indices $j-1$, $j$, $i-1$, and $i$.
        We proceed with a case-by-case analysis: 
        \begin{enumerate}
            \item       
            Consider the value at index $j-1$: 
            
            If $j = 1$, then $j-1=0$, and hence there is no ascent, descent, or tie in $\x$ at index $0$. 
            Thus, the ascent and descent sets are empty and $\nu$ simply maps the empty set to the empty set.
            
            If $j>1$, then $\x$ has an ascent at position $j-1$
            because $M=\max(\x)$ and $j=\min(\argmax(\x))$.
            Since $\argmin(\x) \subseteq \{j, j+1, \ldots, i-1, i\}$, the element at index $j - 1$ in $\nu(x)$ is larger than $m$. Since $\nu$ places $m$ in position $j$, $\nu(\x)$ has a descent at position $j-1$.
            
            \item Consider the values at indices $j$ and $i-1$: 
            
            Note, that $\x$ must have a non-ascent at position $j$ because $M$ is a maximal element causing either a tie or descent at $j$. 
            Likewise, there is a non-ascent in position $i$ because $m$ is a minimal element.
 
            Swapping $m$ and $M$ in $\nu(x)$ 
            results in
            the following: First, since $m$ is a minimal element, placing $m$ at position $j$ ensures that at this index we either have an ascent or tie. 
            This means $\nu(x)$ has a non-descent at index $j$. 
            Second, since $M$ is a maximal element, placing $M$ at position $i$ ensures that the index prior is less than or equal to $M$. 
            This implies
            that $\nu(\x)$ has a non-descent at index $i-1$.
  
            \item Consider the value at index $i$: 
            
            If $i = n$, then there is no ascent, descent, or tie at position $i$ in $\x$, and the proposition is vacuously true. 
             
            If $i < n$, the reasoning is symmetric to the case for $j-1$; $\x$ has an ascent at position $i$ and $\nu(\x)$ has a descent at the same position.
        \end{enumerate}
    \item[Case $2$:] Suppose there is some $a < b$ with $a \in \argmin(\x)$ and $b \in \argmax(\x)$. 
    Let $i$ be the greatest element of $\argmin(\x)$ that is smaller than some element of $\argmax(\x)$ and let $j$ be the smallest element of $\argmax(\x)$ greater than $i$. 
    Furthermore, let $M=\max(\x)$ and let $m=\min(\x)$. 
        Then
        \begin{align*}
            \x &= x_1~ x_{2}~\cdots~x_{i-1}~ \underbrace{m}_{i} ~ x_{i+1}~\cdots~x_{j-1}~ \underbrace{M}_{j} ~x_{j+1}~ \cdots ~x_{n}
        \end{align*}
        and from Case $2$ in Definition \ref{def:nu},
        \begin{align*}
            \nu(\x) &= \nu(x_1~x_2~\cdots~x_{i-1}) \,~ \underbrace{M}_{i} \,~ \nu(x_{i+1}~\cdots~  x_{j-1}) \, ~\underbrace{m}_{j} \,~ \nu(x_{j+1} ~\cdots~ x_n).
        \end{align*}
        We again only need to examine positions $i-1$, $i$, $j-1$, and $j$.
        We proceed with a case-by-case analysis: 
        \begin{enumerate}
            \item Consider the value at index $i - 1$: 
            
            If $i = 1$, then $i-1=0$, and hence there is no ascent, descent, or tie in $\x$ at index $0$. 
            Thus, the ascent and descent sets are both necessarily empty, so $\nu$ simply maps the empty set to the empty set.            
            
            If $i>1$, 
            then in $\x$ there is a non-ascent at position $i-1$.
            Then swapping $m$ and $M$, ensures that there is a non-descent at position $i-1$ in $\nu(\x)$.
 
            \item Consider the values at positions $i$ and $j-1$: 
            
            There are no minimal or maximal elements in $x_{i+1} ~\cdots ~x_{j-1}$, but $x_i = m$ and $x_j = M$. 
            Therefore, $\x$ has ascents in positions $i$ and $j-1$.
            
            Then for the same reasons, because $\nu$ places $m$ in position $j$ and $M$ in position $i$, $\nu(\x)$ has descents at positions $i$ and $j-1$.

            \item Consider the value at index $j$: 
            
            If $j = n$, then there is no ascent, descent, or tie 
            at position $j$; 
            and the ascent and descent sets are empty and $\nu$ is again mapping the empty set to the empty set.

            If $j < n$, the reasoning is symmetric to the case for $i-1$; $\x$ must have a non-ascent at position $j$ and $\nu(\x)$ must have a non-descent at the same position.
        \end{enumerate}
    \end{enumerate}
    Therefore, $\Asc(\x) = \Des(\nu(\x))$.
\end{proof}

\begin{lemma}\label{lem:nu-inj}
    The map $\nu$ of Definition \ref{def:nu} is injective.
\end{lemma}

\begin{proof}
    We now left-invert $\nu$ by inducting on length. 
    In the base case, when the length is 
    zero or 
    one, 
    then $\nu$ acts as the identity 
    causing the left-inverse to also be the identity, hence injective. 
    Assume for strong induction, that $\nu$ is left-invertible for all inputs of length less than $n$ (i.e.,~of length $1<k<n$). 
    Now consider $\nu(\x)$ of length $n$.
    We left invert $\nu(\x)$ by uniquely identifying $\x$. 
    Let $m = \min(\nu(\x))$ and $M = \max(\nu(\x))$. 
    By Definition~\ref{def:nu}, $\nu$ does not change the content of the input.
    Hence, $m=\min(\nu(\x))=\min(\x)$ and $M = \max(\nu(\x))=\max(\x)$.
    Given that $n>1$, then either: 
    \begin{enumerate}
        \item $\x$ has the property of either Case $1$
         of Definition \ref{def:nu} and
    \[\nu(\x) = \nu(x_1~x_2~\cdots~x_{j-1}) \,~ \underbrace{m}_{j} \,~ \nu(x_{j+1}~\cdots~  x_{i-1}) \, ~\underbrace{M}_{i} \,~ \nu(x_{i+1} ~\cdots~ x_n),\] or 
    \item $\x$ is of the from in Case $2$ of Definition \ref{def:nu} and 
    \[\nu(\x) = \nu(x_1~x_2~\cdots ~x_{i-1}) \, ~\underbrace{M}_{i}~ \, \nu(x_{i+1}~\cdots~ x_{j-1}) \,~ \underbrace{m}_{j} \,~ \nu(x_{j+1} ~\cdots~ x_n),\]
    \end{enumerate}
    Thus, $i$ and $j$ are indices determined using Definition \ref{def:nu}. 
    
    Given $\nu(\x) \in \nu(\Sym_n(\y))$, if the indices $i$ and $j$ can be uniquely identified by the structure of the word $\nu(\x)$, then we can inductively construct $\nu^{-1}$ by swapping the $i$th and $j$th entries of $\nu(\x)$ and then applying $\nu^{-1}$ to each of the subwords of $\nu(\x)$ with smaller length.
    This then would uniquely identify the input $\x$, and establish injectivity. 

    The key to creating the inverse relies on determining whether $\nu(\x)$ satisfies either:
    \begin{enumerate}[leftmargin=.7in]
        \item[Case (a):] all minimal elements are to the left of all maximal elements, or 
        \item[Case (b):] there exists a minimal element to the right of a maximal element. 
    \end{enumerate}
We consider each of the above cases independently. 

For Case (a) where all minimal elements are to the left of all maximal elements in $\nu(\x)$, the first step in applying $\nu$ to $\x$ cannot have arisen from Case $2$ in Definition \ref{def:nu}, because Case $2$ explicitly places a minimal element to the right of a maximal element. 
Therefore, the first step in applying $\nu$ to $\x$ arose from Case $1$ in Definition \ref{def:nu}. 
This implies that $\x$ has all maximal elements to the left of all minimal elements and in the subword $x_{j+1}~\cdots~ x_{i-1}$, all instances of $M$ are to the left of all instances of $m$. 
Therefore, if $x_{j+1} ~\cdots~ x_{i-1}$ has instances of both $M$ and $m$, $\nu$ acts on $x_{j+1} ~\cdots~ x_{i-1}$ as in Case $1$ of Definition~\ref{def:nu}.
Then  
\[\nu(\x) = \nu(x_1~x_2~\cdots~x_{j-1}) \,~ \underbrace{m}_{j} \,~ \nu(x_{j+1}~\cdots~  x_{i-1}) \, ~\underbrace{M}_{i} \,~ \nu(x_{i+1} ~\cdots~ x_n),\]  
where index $j$ is the smallest index that contains a minimal element and index $i$ is the largest index that contains a maximal element.
Therefore, $i=\max(\argmax(\nu(\x)))$ and $j=\min(\argmin(\nu(\x)))$. 
Then by induction hypothesis, we have uniquely identified $\x$, which gave rise to $\nu(\x)$.

Now consider Case (b) where there exists a minimal element to the right of a maximal element in $\nu(\x)$.
Recall that $\nu(\x)\in\nu(\Sym_n(\y))$.
By induction on the minimum of the number of minimal and maximal elements in $\y$,
if $\nu(\x)$ was the output from Case $1$ in Definition~\ref{def:nu}, then $\nu(\x)$ would have all minimal elements to the left of all maximal elements.
But by assumption $\nu(\x)$ satisfies Case~(b).
Therefore, the first step in applying $\nu$ to $\x$ arose from Case $2$ in Definition \ref{def:nu}. 
Then $i$ is the index in $\x$ containing the rightmost minimal element that has a maximal element to its right in $\x$, and $j$ is the leftmost maximal element to the right of $i$.
        Thus,
        \[\x = x_1~ x_{2}~\cdots~x_{i-1}~ \underbrace{m}_{i} ~ x_{i+1}~\cdots~x_{j-1}~ \underbrace{M}_{j} ~x_{j+1}~ \cdots~ x_{n}.\]
        By the maximality of $i$, all instances of $m$ must appear to the right of all instances of $M$ in the subword $x_{j+1} ~\cdots ~ x_n$. 
        Moreover, by our construction of $i$ and $j$, there are no instances of $m$ or $M$ in the subword $x_{i+1}~ \cdots ~x_{j-1}$.
        Hence, 
        \[\nu(\x) = \nu(x_1~x_2~\cdots ~x_{i-1}) \, ~\underbrace{M}_{i}~ \, \nu(x_{i+1}~\cdots~ x_{j-1}) \,~ \underbrace{m}_{j} \,~ \nu(x_{j+1} ~\cdots~ x_n),\]
        and $\nu(x_{j+1}~\cdots~x_n)$ causes all instances of $m$ to appear to the left of all instances of $M$ according to Case $1$ of Definition \ref{def:nu}. 
        It follows that $i$ is the index of the rightmost maximal element of $\nu(\x)$ with a minimal element to its right, and $j$ is the index of the leftmost minimal element to the right of $i$
        in $\nu(\x)$.
        Then by the induction hypothesis, we have uniquely identified $\x$, which gave rise to $\nu(\x)$.

Thus, we have shown that whether $\nu(\x)$ satisfies Case (a) or Case (b), we can uniquely recover $\x$ which gives rise to $\nu(\x)$. 
This establishes that $\nu$ is an injection. 
\end{proof}

We are now ready to prove Proposition \ref{prop:NN-AscToDes}.

\begin{proof}[Proof of Proposition \ref{prop:NN-AscToDes}]
    By Lemma~\ref{lem:nu-inj} and Lemma~\ref{lem:AsctoDes}, $\nu$, as constructed in Definition~\ref{def:nu}, is an injective map $\Sym_n(\y) \to \Sym_n(\y)$ for all 
    $\y \in \mathbb{N}^n$
    such that $\Asc(\x) = \Des(\nu(\x))$.
    Then since $|\mathfrak{S}(\y)|$ is finite,  $\nu$ must also be a surjection.
    Therefore, $\nu$ is the desired bijection.
\end{proof}

 \begin{remark}
    As defined in Proposition \ref{prop:NN-AscToDes}, $\nu$ maps the ascent set to the descent set but does not (and cannot possibly) make additional promises about mapping the descent set to the ascent set. 
    In Example \ref{ex:nu}, $\Asc(\x) = \{1, 3, 4, 7\} = \Des(\nu(\x))$, but $\Des(\x) = \{2, 6, 8\}$ and $\Asc(\nu(\x)) = \{2, 5, 6, 8\}$. 
    The map that takes the descent set to the ascent set is $\nu^{-1}$.
\end{remark}

\begin{corollary}\label{cor:PF-AscToDes}
    There is a bijection $D(I;n) \to A(I;n)$.
\end{corollary}

\begin{proof}
    Apply $\nu$ from Proposition \ref{prop:NN-AscToDes} to a parking function.
\end{proof}

\begin{theorem}\label{thm:I and J} The set of parking functions with descent set $I$ and the set of parking functions with descent set $J=\{n-i : i\in I\}$ are in bijection, and hence $d(I;n)=d(J;n)$. 
\end{theorem}

\begin{proof}
This result follows from Proposition~\ref{prop:flipflop} and Corollary~\ref{cor:PF-AscToDes}.
\end{proof}

In what follows, we say the sets $I\subseteq[n-1]$ and $J=\{n-i:i\in I\}$ are \textit{self-dual} if $I=J$. 
We now give a formula for the number of self-dual sets.

Our next objective is to give a recursive formula for the number of parking functions of length $n$ with 
descent set
$I\subseteq[n-1]$. 
We begin with some general definitions and notation. 
Given a multiset $X$ of positive integers with size $n$, let $W(X)$ denote the set of multipermutations of $X$. 
For $I\subseteq[n-1]$, let 
\begin{align*}
D_X(I)&=\{w\in W(X)\,:\,\Des(w)=I \},
\end{align*}
and $D_X(I)=|D_X(I)|$. 

\begin{lemma}
Given $\beta \in\NDPF_n$,
let $M(\beta)$ be the multiset of entries of $\beta$. 
If $I\subseteq[n-1]$, then 
\[\sum_{\beta\in\NDPF_n}d_{M(\beta)}(I)=d(I;n).\] 
\end{lemma}
\begin{proof}
    This follows from definitions of $D_X(I)$ and $D(I;n)$, and 
    that each parking function is a rearrangement of a unique increasing parking function.
\end{proof}

Recall that $d(\emptyset;n)=C_n$, the $n$th Catalan number. 
We now give a recursion for the number of parking functions with a nonempty descent set. 
 
\begin{theorem} \label{thm:recursion}
    Let $I\subseteq[n-1]$ be nonempty, $m=\max(I)$, and $I^-=I\setminus\{m\}$.  
    Then
\[d(I;n)=\sum_{\beta\in \NDPF_n}\; \left(\sum_{X\in\mathcal{M}(\beta;m)}d_{X}(I^-;m)\right)-d(I^-;n),\]
where, for $\beta\in\NDPF_n$,  $\mathcal{M}(\beta,m)$ denotes  the collection of multisets consisting of $m$ elements of~$\beta$.
\end{theorem}

\begin{proof}
Consider the set $P$ of parking functions $\alpha\in\PF_n$ that can be written as a concatenation $\alpha=\alpha'+\alpha''$ and satisfy
\begin{enumerate}
    \item that the length of $\alpha'$ is $m$ and the length of $\alpha''$ is $n-m$ and
    \item $\Des(\alpha')=I^-$ and $\Des(\alpha'')=\emptyset$.
\end{enumerate}
We now count the elements of $P$ in two ways. 

First, observe that we can write $P$ as the disjoint union of those $\alpha$ where $\alpha'_m>\alpha''_1$ and those where $\alpha'_m\leq \alpha''_1$.
Hence, \begin{align}
    |P|&=d(I^-;n)+d(I;n).\label{eq P1}
\end{align}

On the other hand, the elements of $P$ can be constructed as follows. 
Consider every $\beta\in\NDPF_n$ as a multiset with $n$ elements.
For a fixed multiset $\beta\in\NDPF_n$, $\mathcal{M}(\beta,m)$ is the collection of multisets of size $m$ with entries in $\beta$.

For every 
$X\in\mathcal{M}(\beta,m)$, 
arrange the elements so that they have descent set $I^-$.
This can be done in $d_{X}(I^-)$ ways.
The remaining $n-m$ values in $\beta\setminus X$ are used to construct $\alpha''$ by placing those remaining values in nondecreasing order, so as to have no descents. 
This can be done in a unique way. 
Thus, the number of elements of $P$ 
is given by \begin{align}
|P|&=\sum_{\beta\in \NDPF_n}\; \left(\sum_{X\in\mathcal{M}(\beta,m)}d_{X}(I^-)\right).\label{eq P2}
\end{align}
Solving Equation~\eqref{eq P1} for $d(I;n)$ and substituting the right hand-side of Equation~\eqref{eq P2} in for $|P|$ yields the desired result.
\end{proof}

\begin{example}\label{ex:complicated}
Let $I=\{1,3\}$. 
Then by Theorem~\ref{thm:recursion},
\[d(I;4)=\sum_{\beta\in\NDPF_4}\left(\sum_{X\in\mathcal{M}(\beta;3)}d_X(I^-)\right) - d(I^-;4).\] 
To compute the sum, select subsets of size $3=\max(I)$ for each multiset $\beta\in\NDPF_4$ and arrange the entries so that they have descents at $I^-=\{1\}$. 
Table~\ref{tab:complicated}  details the computations establishing
 \[\sum_{\beta\in\NDPF_4}\left(\sum_{X\in\mathcal{M}(\beta,3)}d_X(I^-)\right)=40.\]
 Now $d(I^-;4)=21$, from which we get $d(I;4)=40-21=19$
 as expected. 
 In fact, Table~\ref{tab:descent sets} gives the elements of $D(J;4)$ for all subsets $J\subseteq[3]$; and in particular, we list the elements in $D(I;4)$ confirming that $d(I;4)=19$.
 \begin{table}[htbp]
     \centering
 \begin{tabular}{|c|l|l|}\hline
\multirow{2}{*}{$\beta\in\NDPF_4$} & \multirow{2}{*}{$\mathcal{M}(\beta,3)$} & \multirow{2}{*}{$\displaystyle\sum_{X\in\mathcal{M}(\beta;3)}d_X(I^-)$}\\
&&\\\hline\hline
      $\{1,1,1,1\}$& $\{\{1,1,1\}\}$& $0$\\\hline
      $\{1,1,1,2\}$ & $\{\{1,1,1\},\{1,1,2\}\}$ & $0+1=1$\\\hline
      $\{1,1,1,3\}$ & $\{\{1,1,1\}, \{1,1,3\}\}$ & $0+1=1$\\\hline
      $\{1,1,1,4\}$ & $\{\{1,1,1\}, \{1,1,4\}\}$  &$0+1=1$\\\hline
      $\{1,1,2,2\}$ & $\{\{1,1,2\}, \{1,2,2\}\}$ &$1+1=2$\\\hline
      $\{1,1,2,3\}$ & $\{\{1,1,2\}, \{1,1,2\}, \{1,2,3\}\}$&$1+1+2=4$\\\hline
      $\{1,1,2,4\}$ & $\{\{1,1,2\}, \{1,1,4\}, \{1,2,4\}\}$ &$1+1+2=4$\\\hline
      $\{1,1,3,3\}$ & $\{\{1,1,3\}, \{1,3,3\}\}$&$1+1=2$\\\hline
      $\{1,1,3,4\}$ & $\{\{1,1,3\}, \{1,1,4\}, \{1,3,4\}\}$&$1+1+2=4$\\\hline
      $\{1,2,2,2\}$ & $\{\{1,2,2\}, \{2,2,2\}\}$ &$1+0=1$\\\hline
      $\{1,2,2,3\}$ & $\{\{1,2,2\}, \{1,2,3\}, \{2,2,3\}\}$&$1+2+1=4$\\\hline
      $\{1,2,2,4\}$ & $\{\{1,2,2\}, \{1,2,4\}, \{2,2,4\}\}$&$1+2+1=4$\\\hline
        $\{1,2,3,3\}$ & $\{\{1,2,3\},\{1,3,3\},\{2,3,3\}\}$ &$2+1+1=4$\\\hline
      $\{1,2,3,4\}$& $\{\{1,2,3\},\{1,2,4\},\{1,3,4\},\{2,3,4\}\}$&$2+2+2+2=8$\\\hline
 \end{tabular}
 \caption{Computations for Example \ref{ex:complicated}.}
 \label{tab:complicated}
 \end{table}
\end{example}

Next, we enumerate parking functions with descents at the first $k$ indices by bijecting onto the set of standard Young tableaux of shape $((n-k)^2,1^k)$, which are known to be enumerated by $f(n, n-k-1)=\frac{1}{n}\binom{n}{k}\binom{2n-k}{n-k-1}$ (\seqnum{A033282}).

For natural number $n$, a \textit{partition} $\lambda$ of $n$ is a weakly decreasing tuple $(\lambda_1, \ldots, \lambda_k)$ such that $\sum_i \lambda_i = n$. 
Whenever $\lambda$ is a partition of $n$ we write $\lambda \vdash n$.

\begin{definition} [{\cite[p.~1]{Fulton}}] 
    Given a partition $\lambda \vdash n$, a \textit{Young diagram of shape $\lambda$} is a left-justified collection of boxes with $\lambda_i$ boxes in row $i$ and where the top row is row $1$. 
    A \textit{standard Young tableau of shape $\lambda$} is a filling of the Young diagram of shape $\lambda$ with the numbers $\{1, \ldots, n\}$ such that the rows and columns are strictly increasing left to right and top to bottom.
\end{definition}

\begin{definition}
    A \textit{Dyck word} $w$ of semilength $n$ is a word that contains $U$'s and $D$'s where $U$ and $D$ each appear $n$ times 
    such that for all $1 \leq i \leq n$, the $i$th $D$ in $w$ appears after the $i$th $U$. 
    If $U$ is the $i$th $U$ in $w$, then $i$ is the \textit{semi-index} of the specified $U$.
\end{definition}

\begin{lemma}\label{lem:DyckTableau}\cite{Gudmundsson:DyckPaths}, Theorem 6.
    There is a bijection $f$ between Dyck words $w$ of semilength $n$ and standard Young tableaux of shape $(n, n)$ which is given as follows: 
    If $w_i = U$ (respectively, $D$), then $i$ appears in the first (respectively, second) row of $f(w)$. 
\end{lemma}
For more on bijections between Dyck paths and standard Young tableaux, we point the interested reader to Gil, McNamara, Tirrell, and Weiner \cite{pathsSYT}.

\begin{lemma}\label{lem:DyckPark}
    There is a bijection $g$ between Dyck words $w$ of semilength $n$ and nondecreasing parking functions of length $n$ which is given as follows: The $i$th entry in $g(w)$ is one plus the number of $D$'s before the $i$th $U$ in $w$.
\end{lemma}
\begin{proof}
    Because there are strictly less than $i$ $D$'s before the $i$th $U$ in $w$, the $i$th entry in $g(w)$ never exceeds $i$. Then the map is well-defined. It is also injective because a Dyck word can be uniquely determined by the data of the number of $D$'s before the $i$th $U$ for all $i$. This fact also yields surjectivity, as $g^{-1}(\alpha)$ is the unique Dyck word that has $\alpha_i - 1$ $D$'s before the $i$th $U$.
\end{proof}

\begin{proposition}\label{prop:biject to SYT}
Let $n\geq 1$ and $0 \leq k \leq n-1$. 
If $[k]\subseteq[n-1]$, then 
\begin{align*}
    d([k];n) = \frac{1}{n}\binom{n}{k}\binom{2n-k}{n-k-1}.
\end{align*}
\end{proposition}

\begin{proof}
    Consider the standard Young tableau
    \[T=\ytableausetup
 {mathmode, boxframe=normal, boxsize=2em}
\begin{ytableau}
 a_1 & a_2 & a_3 & \none[\dots]
              2
& \scriptstyle a_{n-k}\\
 b_1 & b_2 & b_3 & \none[\dots]
              2
& \scriptstyle b_{n-k}\\
c_1\\
c_2\\
       \none[\vdots] \\
   c_k\\
  \end{ytableau}\]
whose entries strictly increase along the columns and rows. 
We construct a bijection $\tau$ mapping such a tableau to a parking function of length $n$ with descent set $k$.
Construct a word $w = w_1~w_2~\cdots ~ w_{2n-k}$ for all $1\leq i\leq 2n-k$ by letting
\[w_i = \begin{cases}
    U, & \text{if $i$ is in the first row;}\\
    D, & \text{if $i$ is in the second row;}\\
    X, &  \text{if $i$ is in the third row or beyond.}
\end{cases}\]
Because $b_i > a_i$, removing all $X$'s from $w$ would make $w$ a Dyck word.
Moreover, inserting a $U~D$ into the middle of a Dyck path returns another Dyck path.
We construct the word $w'$ of length $2n$ by replacing every $X$ in $w$ with a $U~D$. 
Let $I$ consist of the semi-indices of the inserted $U$'s.
Using Lemma~\ref{lem:DyckPark}, let $\alpha$ be the nondecreasing parking function corresponding to $w'$.
We then construct $\alpha'$ with descent set $[k]$ from $\alpha$ by moving the entries whose indices are in $I$ to the front of the parking function $\alpha$ in decreasing order.
By the construction of $\alpha$, each such index in $I$ is the last appearance of that index's values, hence the chosen entries are distinct. 
Then $\tau(T) = \alpha'$.

In the reverse direction, given a parking function $\alpha'\in \PF_n$ with descent set $[k]$, record the values in the first $k$ entries in $\alpha'$ in the set $V$.  
Let $\alpha$ be the nondecreasing rearrangement of $\alpha'$, and let $I$ be the set of indices of the last appearance of each element of $V$ in $\alpha$. 
Let $w'$ be the Dyck word corresponding to $\alpha$, and the $U$ in $w'$ with semi-index $i$ has a $D$ immediately to its right for all $i \in I$. 
Then for each $i \in I$, replace the subword $U~D$, consisting of the $i$th $U$ and the $D$ immediately to its right, with an $X$.
Then construct the corresponding standard Young tableau $T = \tau^{-1}(\alpha')$ by reversing the process from the Dyck word built from a standard Young tableau, as detailed above. 

As $\tau$ and $\tau^{-1}$ are inverse maps of each other and each is defined on the entire desired domain, $\tau$ is the desired bijection. 
\end{proof}

We illustrate the bijection in the proof of Proposition \ref{prop:biject to SYT} next.

\begin{example}
Consider $n = 7$, $k = 3$, and the standard Young tableau with shape \\
$((7-3)^2,1^3)=(4, 4, 1, 1, 1)$:
\[T = \begin{ytableau}
    1 & 3 & 7 & 8\\
    2 & 5 & 9 & 10\\
    4\\
    6\\
    11
\end{ytableau}\;.\]
The corresponding word is $w=U~D~U~X~D~X~U~U~D~D~X$. 
For record-keeping, we underline elements instead of using the set $I$.
Replacing $X$'s with $\underline{U~D}$ in $w$ yields
\[w'=U~D~U~\underline{U~D}~D~\underline{U~D}~U~U~D~D~\underline{U~D}.\]
The corresponding $\alpha\in\NDPF_n$ is given by 
$\alpha=(1,2,\underline{2},\underline{4},5,5,\underline{7})$.
Move the underlined numbers in $\alpha$ to the front (in decreasing order) to get
$\alpha'=(7,4,2,1,2,5,5)$ which has the desired descent set $[3]$. 

For an example of the reverse direction, consider 
$\alpha'=(5,3,2,1,1,2,2)$, which has descent set $[3]$. 
Underline the first $3$ entries and write $\alpha'$ in nondecreasing order
$(1,1,2,2,\underline{2},\underline{3},\underline{5})$. 
The $2$'s are repeated and the right-most $2$ is the underlined value.
Then construct 
$w'=U~U~D~U~U~\underline{U~D}~\underline{U~D}~D~\underline{U~D}~D~D$.  
Replacing $\underline{U~D}$ with $X$ in $w'$ yields
\[w=U~U~D~U~U~X~X~D~X~D~D.\] 
Then $w$ corresponds to the standard Young tableau
\[T = \begin{ytableau}
    1 & 2 & 4 & 5\\
    3 & 8 & 10 & 11\\
    6\\
    7\\
    9
\end{ytableau}\;.\]
\end{example}

Although we have a recursive formula for the number of parking functions of length $n$ with descent set $I\subseteq[n-1]$ (Theorem~\ref{thm:recursion}), we pose the following problem.
\begin{problem} Give non-recursive formulas for the number of parking functions with other interesting descent sets $I\subseteq[n-1]$? 
\end{problem}

\section{Peaks of parking functions} \label{sec:PTPFN}
The Catalan numbers are one of the most well-studied integer sequences, with $214$ different combinatorial explanations in Stanley's work \cite{stanley:catalan}, and many more are found on the OEIS \seqnum{A000108}. 
We now establish that the set of parking functions of length $n$ that have no peaks and no ties, i.e., peakless-tieless parking functions, are a new set of Catalan objects. 

We begin by setting some needed definitions and notation.
\begin{definition}\label{def:tie and value set}
    Let $\alpha=(a_1,a_2,\ldots,a_n)\in[n]^n$. 
    \begin{itemize}
        \item  Define the \textit{tie set} of $\alpha$ as
        \[\Tie(\alpha)=\{j+1\in[n]: a_{j}=a_{j+1}\}\]
        and order the elements 
        $\Tie(\alpha)=\{t_1<t_2<\cdots<t_j\}$, where $j=|\Tie(\alpha)|$.
        \item Define the \textit{value set} of $\alpha$ as 
        \[\Val(\alpha)=\{b'_1, b'_2, \ldots, b'_k\},\]
        such that set of elements of $\alpha$ are in increasing order $1 = b'_1 < b'_2 < \dots < b'_k$, where $k$ is the number of distinct elements of $\alpha$.
    \end{itemize}
\end{definition}

\begin{definition}\label{def:function}
Define the function $\varphi:\NDPF_{n}\to \mathbb{N}^{n}$ 
by
\begin{align}
    \varphi(\alpha)&=(t_j,t_{j-1},\ldots,t_2,t_1,b_1,b_2,\ldots ,b_k)\label{eq:construction},
    \end{align}
    where $\Tie(\alpha)=\{t_j>t_{j-1}>\cdots>t_1>1\}$ and $\Val(\alpha)=\{1=b_1<b_2<\cdots<b_k\}$ are as in Definition~\ref{def:tie and value set}.
    \end{definition}
In fact, we show $\varphi:\NDPF_{n}\to \PTPF_{n}$ 
and illustrate these definitions next.
\begin{example} Consider the nondecreasing parking function 
$\alpha=(1,1,2,3,4,4)\in\NDPF_6$.
Then  $\Tie(\alpha)=\{2, 6\}$ and  $\Val(\alpha)=\{1,2,3,4\}$.
Now $\varphi(\alpha)$ returns the tuple whose first $|\Tie(\alpha)|$ elements are the integers in $\Tie(\alpha)$ arranged in decreasing order, while the remaining values are the elements of $\Val(\alpha)$ listed in increasing order. 
Namely, $\varphi(\alpha)=(6,2,1,2,3,4)$. 
The result is a peakless-tieless parking function, as claimed.
\end{example}

\begin{theorem}\label{thm:bijection}
    The function $\varphi$ in Definition \ref{def:function} is a well-defined bijection $\varphi:\NDPF_n\to \PTPF_n$.
\end{theorem}

\begin{proof}
    Let $\alpha\in\NDPF_{n}$.
    In this construction, $|\Val(\alpha)|=k$ is the number of values appearing in $\alpha$ and $|\Tie(\alpha)|=j$ is the number of ties in $\alpha$.
    Because $\alpha \in \NDPF_n$ and 
    a value in $\alpha$ either repeats or appears exactly once, $k+j=n$.
    Moreover, the construction in Equation~\eqref{eq:construction} ensures $b_1=1$ since the letter $1$ must appear in $\NDPF_n$.
    Also, the letters before $1$ (if they exist) decrease down to $1$, and the letters after $1$ (if they exist) increase.
    Hence, $\varphi(\alpha)$ has no peaks and no ties. 
    Additionally, all cars are still able to park with preferences $\varphi(\alpha)$. 
    To see this, observe that $\alpha=(a_1,a_2,\ldots,a_n) \in \NDPF_n$.
    The cars park in the order they arrive: car $1$ parks in spot $1$, car $2$ in spot $2$, and so on.
    To show that $\varphi(\alpha)$ parks, we define $\gamma = (g_1, \ldots, g_n)$ from $\alpha$ by replacing each $a_i$ where $a_i=a_{i-1}$ with $i$. 
    Because $\alpha$ parks, each unchanged preference satisfies $g_i \leq i$. 
    If $g_j$ is a changed preference, then $g_j=j \leq j$.
    Thus, we conclude that $\gamma$ parks. 
    Now, since $\gamma$ and $\varphi(\alpha)$ may be permuted into each other, $\varphi(\alpha)$ must also park.  
    Thus, $\varphi(\alpha)\in\PTPF_n$.

\medskip
    
\noindent\textit{Injectivity:} Let $\alpha,~ \beta \in \NDPF_n$, and let $\varphi(\alpha)=\varphi(\beta)$. 
    This implies that $\Tie(\alpha)=\Tie(\beta)$ and $\Val(\alpha) = \Val(\beta)$.
    Notice that nondecreasing parking functions $x \in \NDPF_n$ are completely determined by their tie sets, $\Tie(x)$, and their value sets, $\Val(x)$.
    When reconstructing 
    $\alpha$ and $\beta$ from the value set and the tie set, the repeated values in $x$ are the same for both $\varphi(\alpha)$ and $\varphi(\beta)$.
    Thus, $\alpha=\beta$.

\medskip

\noindent  \textit{Surjectivity:} 
Let $\beta = (t_j, t_{j-1}, \ldots, t_2, t_1, b_1, b_2, \ldots, b_k) \in \PTPF_n$, where 
    $T = \{1<t_1< t_2<\cdots<t_{j-1}<t_{j}\}$
    and $B = \{1 = b_1 < b_2< \cdots < b_k\}$. 
    It is sufficient to find $\alpha \in \NDPF_n$ with $\Tie(\alpha) = T$ and $\Val(\alpha) = B$. 
    Order the elements of $X=[n]\setminus T=\{x_1<x_2<\cdots<x_{n-j}\}$.
    Construct 
    $\alpha=(a_1,a_2,\ldots,a_n)$ as follows.
    \begin{enumerate}
        \item In $\alpha$, place the elements of $B$ in order $1=b_1<b_2<\cdots<b_k$ at the indices indexed by $X$ in order $x_1<x_2<\cdots<x_{n-j}=x_k$. 
        Namely, let $a_{x_i}=b_i$ for all $1\leq i\leq k$.
        \item For every $j\in T$, set $a_j=a_{j-1}$.
    \end{enumerate}
Since $\alpha = (a_1, a_2, \dots, a_n)$ is a nondecreasing tuple, $\alpha$ parks if and only if $a_i \leq i$ for all $1 \leq i \leq n$. 
    If $a_i = a_{i-1}$ and $a_{i-1} \leq i - 1$, then $a_i \leq i$. 
    Therefore, it is sufficient to check that $a_{x_i} = b_i \leq x_i$ for all $1 \leq i \leq n-j$. 
    
    Let $P=(p_1, p_2, \ldots, p_n)$ be $\beta$ in nondecreasing order.
    This is a parking function, so $p_i\leq i$.
    \begin{enumerate}
        \item If there is no duplicate in $(a_1, \ldots, a_i)$: $t_1 >i$.
        Then in $P$, $t_1$ has index at lest $i+1$, implying $\Val(a_1, \ldots , a_i) \subset \Val(p_1, \ldots, p_i)$.
        \item If there is a duplicate, without loss of generality, we assume $a_{i-1}=a_i$.\\
        Then $\Val(a_1, \ldots, a_{i-1}) \subset \Val(p_1, \ldots, p_{i-1})$.
        Notice then, that since $a_{i-1}=a_i$, we have \[\Val(a_1, \ldots, a_{i})=\Val(a_1, \ldots, a_{i-1}) \subset \Val(p_1, \ldots, p_{i-1}) \subseteq \Val(p_1, \ldots, p_i).\]
    \end{enumerate}
    Because of this, we satisfy the claim.
    If we take $a_i \in \alpha$, we can find some $\ell_i \leq i$ such that $a_i = p_{\ell_i} \leq \ell_i \leq i$.
    Then $a_i \leq i$ and $\alpha \in \NDPF_n$.\qedhere
\end{proof}

The bijection in Theorem~\ref{thm:bijection} immediately implies the following. 
\begin{corollary}\label{cor:peakless tieless catalan}
If $n\geq 1$, then $|\PTPF_{n}|=C_n$, the $n$th Catalan number. 
\end{corollary}

We now provide a connection between peakless-tieless parking functions and the entries of the Catalan triangle \seqnum{A009766}, which are defined by
\begin{align}
C_{n+1,i} &= \sum_{j=0}^{i} C_{n,j}.\label{eq:Cat triangle}
\end{align}
Table \ref{tab:cat triangle} provides some of the initial values in the Catalan triangle. 
The sum along the $n$th row of the Catalan triangle is given by $C_n$.

\begin{table}[htbp]
\centering
\begin{tabular}{|c|c|c|c|c|c|c|c|}\hline
$n\setminus k$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$\\\hline
$1$ & $1$	&		&		&		&		&		&			\\\hline
$2$ & $1$	&	$1$	&		&		&		&		&			\\\hline
$3$ & $1$	&	$2$	&	$2$	&		&		&		&			\\\hline
$4$ & $1$	&	$3$	&	$5$	&	$5$	&		&		&			\\\hline
$5$ & $1$	&	$4$	&	$9$	&	$14$	&	$14$	&		&			\\\hline
$6$ & $1$	&	$5$	&	$14$	&	$28$	&	$42$	&	$42$	&			\\\hline
$7$ & $1$	&	$6$	&	$20$	&	$48$	&	$90$	&	$132$	&	$132$		\\\hline
\end{tabular}
\caption{The entries of the Catalan triangle for $1\leq n,i\leq 7$.}\label{tab:cat triangle}
\end{table}

\begin{corollary}\label{cor:cat triangle}
    If $\PTPF_{n}(i)=\{\alpha=(a_1,a_2,\ldots,a_n)\in\PTPF_{n}: a_n=i\}$, then 
    $|\PTPF_{n}(i)|=C_{n,i}$.
\end{corollary}
\begin{proof}
We proceed by induction on $n$ and $i\in[n]$.
When $n=1$, the set $|\PTPF_1(1)|=|\{(1)\}|=1=C_{1,1}$. 
When $n=2$, the set $|\PTPF_2(1)|=|\{(2,1)\}|=1=C_{2,1}$ and $|\PTPF_2(2)|=|\{(1,2)\}|=1=C_{2,2}$. 

Assume for induction that for all $n\leq k$ and $i\leq n$, $|\PTPF_{n}(i)|=C_{n,i}$.
Let $\beta=(b_1,b_2,\ldots,b_{n-1},i)\in\PTPF_{n}(i)$. 
Prepending $n+1$ to $\beta$ yields $(n+1,b_1,b_2,\ldots,b_{n-1},i)\in\PTPF_{n+1}(i)$.
By induction, we construct $C_{n,i}$ many elements of $\PTPF_{n+1}(i)$. 
For every element $\gamma=(b_1,b_2,\ldots,b_{n-1},j)\in \PTPF_{n}(j)$ with $1\leq j\leq i-1$, appending $i$ to $\gamma$ yields 
$(b_1,b_2,\ldots,b_{n-1},j,i)\in\PTPF_{n+1}(i)$,
and we construct $\sum_{j=1}^{i-1}C_{n,j}$ elements.
These constructions yield distinct elements of $\PTPF_{n+1}(i)$ since the construction creates tuples beginning with $n+1$, while the second begins with $b_1\in[n]$.
As these are the only possible values with which the tuple may begin, applying the induction hypothesis yields
\[|\PTPF_{n+1}(i)|=C_{n,i}+\sum_{j=1}^{i-1}C_{n,j}=\sum_{j=1}^{i}C_{n,j}=C_{n+1,i}\]
where the last equality holds by Equation~\eqref{eq:Cat triangle}.
\end{proof}

\subsection{Valleys of parking functions}
In permutations, the map $i\to n-i+1$ gives a bijection on permutations, which sends peaks to valleys. 
This establishes that the number of permutations with $k$ peaks is the same as the number of permutations with $k$ valleys. 
However, this map is not well-defined for parking functions. 
For example, $(1,1,1)$ goes to $(3,3,3)$ which is not even a parking function. 
Moreover, the number of parking functions with $k$ peaks is not the same as the number with $k$ valleys. 
For example, when $n=3$, there are four parking functions with one peak:
\[
    (1,2,1), (1,3,1), (1,3,2), (2,3,1).
\]
Whereas, there are three parking functions with one valley:
\[
    (2,1,2), (2,1,3), (3,1,2).
\]

We now consider the set of valleyless-tieless parking functions; parking functions for which there is no index $1\leq i\leq n-1$ such that $a_i=a_{i+1}$ nor index $2\leq i\leq n-1$ such that $a_{i-1}>a_i<a_{i+1}$. 
We let $\VTPF_n$ denote the set of valleyless-tieless parking functions of length $n$. 
Our main result is as follows.
 
\begin{theorem}\label{thm:main2}
Valleyless-tieless parking functions of length $n$ are enumerated by $|\VTPF_n|=F_{n+2}$, where
$F_n$ is the $n$th Fine number (as defined by Deutsch and Shapiro \cite{FineNums}) with the first ten values of the sequence being  $(1\leq n\leq 10)$:
\[1, 2, 6, 18, 57, 186, 622, 2120, 7338, 25724.\]
\end{theorem}

To prove Theorem~\ref{thm:main2}, in Subsection \ref{subsec1},
we establish a bijection between the set of valleyless-tieless parking functions and certain types of peakless-tieless parking functions.  
In Subsection \ref{subsec2}, we show that the special set of peakless-tieless parking functions are counted by the Fine numbers (\seqnum{A000957}).
This result implies Theorem~\ref{thm:main2}.

\subsection{Bijective maps}\label{subsec1}
We let $\VTPF_{n+1}(a_1=1,a_{n+1}>1)$ be the set of valleyless-tieless parking functions of length $n+1$ in which the first value is one and the last is larger than one. 
A more formal definition of peakless-tieless parking functions of length $n+1$
is the set of parking functions of length $n+1$ for which there is no index $i\in[n]$ such that $a_i=a_{i+1}$ or $a_{i-1}<a_i>a_{i+1}$. 

We let 
$\PTPF_{n+1}(a_1>a_{n+1})$ be the set of peakless-tieless parking functions of length $n+1$ in which the first value is larger than the last. 

\begin{lemma}\label{lem:bijection longer star with 1}
The function $\psi:\VTPF_n\to \VTPF_{n+1}(a_1=1,a_{n+1}>1)$ defined by 
\[(a_1,a_2,\ldots,a_n)\to(1,a_1+1,a_2+1,\ldots,a_n+1)\]
is a bijection.    
\end{lemma}

\begin{proof}
First, we show injectivity. 
If $\alpha=(a_1,a_2,\ldots,a_n), \beta=(b_1,b_2,\ldots,b_n) \in \VTPF_n$, and $\psi(\alpha) = \psi(\beta)$, then $a_i+1 = b_i+1$ for all $i \in [n]$. 
Then $a_i = b_i$ for all $i \in [n]$, so $\alpha = \beta$. 

For surjectivity, suppose $\alpha = (1, a_2, \ldots, a_n) \in \VTPF_{n+1}(a_1 = 1, a_{n+1}>1)$. 
We wish to show that $\beta=(a_1-1,a_2-1,\ldots,a_n-1)\in\VTPF_n$. 
For $i \in [n]$, $a_i > 1$ and in general an element of $\VTPF_n$ can only have a $1$ in the first and/or last position.
If an instance of $1$ has a neighbor both to its left and right and there are no ties, then both of $1$'s neighbors are greater than $1$, creating a valley and giving rise to a contradiction. 
Recall $\alpha$ satisfies $a_n > 1$, so $a_i > 1$ for all $i \in [n]$. 
Moreover, $a_i-1\leq n$ for all $i\in[n]$.
Hence, $\beta\in[n]^n$.

Next, we show that $\beta$ is a parking function. 
Let $\alpha^\uparrow = (1, x_1, x_2, \ldots, x_n)$ be the nondecreasing rearrangement of $\alpha$. 
Since $\alpha$ is a parking function, we know that $1 < x_i \leq i+1$ for all $i \in [n]$.
Then the nondecreasing rearrangement $\beta^\uparrow$ of $\beta$ is $(x_1 - 1, x_2 - 1,\ldots, x_n-1)$, which satisfies 
$0 < x_n - 1 \leq i$, so $\beta$ parks. 
Removing the first element of a parking function, in particular of $\alpha$, does not create a valley or a tie that was not there before.
This ensures that $\beta$ also does not have ties nor valleys. 
This then establishes that $\beta\in\VTPF_n$ and satisfies $\psi(\beta)=\alpha$.
\end{proof}

\begin{remark}
    In a valleyless-tieless parking function there is a unique maximal entry. 
    If this were not the case and the maximum value $k$ appeared twice.
    Then either they are consecutive entries in the tuple, creating a tie (a contradiction), or they are nonadjacent entries in the tuple and thus the value(s) between them would either be larger or create a valley, giving a contradiction. 
\end{remark}

In the following, we reverse parts of a tuple. 
To this end, we define the following.

\begin{definition}
    Let $(x_1,x_2,\ldots,x_n)\in[n]^n$. 
    For $i\in[n-1]$ let
    \begin{align*}
        &\flick_i(x)=(x_i,x_{i-1},\ldots,x_1,x_n,x_{n-1},\ldots,x_{i+1}) \\
        \intertext{and}
        &\flick_n(x)=(x_n,x_{n-1},\ldots,x_2,x_1).
    \end{align*}
\end{definition}
For example, if $\textbf{x}=(1,2,1,3,5,6,3,2)$, then $\flick_4(\textbf{x})=(3,1,2,1 ,2,3,6,5)$ and $\flick_6(\textbf{x})=(6,5,3,1,2,1,2,3)$.
\begin{proposition}
\label{prop:g-is-l}
Define the map $\varphi: \VTPF_{n+1}(a_1=1,a_{n+1}>1) \to \PTPF_{n+1}(a_1 > a_{n+1})$ as follows:
 If $v=(v_1,v_2,\ldots,v_{n+1})\in \VTPF_{n+1}(a_1=1,a_{i+1}>1)$ and $i\in [n+1]$ is the unique index containing the maximal entry of $v$, then  \[\varphi(v)=\flick_i(v).\]
The map $\varphi$ is a bijection.   
\end{proposition}
\begin{proof}
    By definition, $\flick_i$ is an involution that, as a rearrangement, maps parking functions to parking functions. 
    Let $\alpha = (a_1, a_2, \ldots, a_{n+1}) \in \PTPF_{n+1}(a_1 > a_{n+1})$ with $i$ being the index of the unique instance of $1 \in \alpha$. 
    Then it is sufficient to show that $\beta = (b_1, b_2, \ldots, b_{n+1}) = \flick_i(\alpha)$ is an element of $\VTPF_{n+1}(a_1=1, a_{n+1}>1)$. 
    Recall that since $\alpha\in\PTPF_{n+1}(a_1>a_{n+1})$, we have that 
    \begin{align}\label{eq:ineqs}a_1 > a_2 > \dots > a_{i-1} > a_i < a_{i+1} < \dots < a_{n+1}
    \end{align} 
    and $a_1 > a_{n+1}$. 
    Then by definition of $\flick_i(\alpha)$ and the inequalities in Expression~\eqref{eq:ineqs}, we have that  \[1 = a_i < a_{i-1} < \dots < a_2 < a_1 > a_{n+1} > a_n > \dots > a_{i+1}. \]
    So $\beta=(b_1,b_2,\ldots,b_{n+1})=\flick_i(\alpha)$ ensures that 
    \begin{align}
    \label{inequalities2}
    1 = b_1 < b_2 < \dots < b_{i-1} < b_i > b_{i+1} > b_{i+2} > \dots > b_{n+1}
    \end{align}
    with $b_1 = 1$ and $b_{n+1} > b_1 = 1$.
    The inequalities in Expression~\eqref{inequalities2} imply that $\beta\in \VTPF_{n+1}(b_1 = 1, b_{n+1} > 1)$.

    Then $\flick_i$ is a well-defined involution between the desired domains. 
    Therefore, we get the bijection as desired.
\end{proof}

\subsection{Valleyless-tieless parking functions and the Fine numbers}\label{subsec2}
We now define a set partition which is useful in proving Theorem~\ref{thm:main2}.
    \begin{definition} For $n\geq 0$, we partition the set $\PTPF_{n+1}$ as follows:
        \begin{itemize}
            \item $\mathscr{G}_{n+1}=\{\alpha \in \PTPF_{n+1}:a_1 > a_{n+1}\}$, 
            \item $\mathscr{E}_{n+1}=\{\alpha \in \PTPF_{n+1}:a_1=a_n\}$, and 
            \item $\mathscr{L}_{n+1}=\{\alpha \in \PTPF_{n+1}:a_1 < a_{n+1}\}$.
        \end{itemize}
    For convenience $\mathscr{G}_1=\mathscr{L}_1=\emptyset$ and $\mathscr{E}_1=\{(1)\}$. 
    Let $G_{n+1} = |\mathscr{G}_{n+1}|$, $E_{n+1} = |\mathscr{E}_{n+1}|$, and $L_{n+1} = |\mathscr{L}_{n+1}|$.
    \end{definition} 
    As expected, 
    \begin{align}
        G_{n+1}+E_{n+1}+L_{n+1}&=|\PTPF_{n+1}| = C_{n+1},\label{eq:cat}
    \end{align}
    the $(n+1)$th Catalan number, and where the last equality holds by Corollary~\ref{cor:peakless tieless catalan}.

\begin{remark}\label{rem:properties of ptpfs}
Let $\alpha=(a_1,a_2,\ldots,a_n)$ be a peakless-tieless parking function of length $n \geq 2$. 
If $a_i=n$ for some index $i$, then $i=1$ or $i=n$, but not both. 
This is because if both $a_1=n$ and $a_n=n$,  then $\alpha$ is not a parking function. 
If $a_i=n$ for $i\in[2,n-1]$, then either $\alpha$ has a peak at $i$ or there is a tie in position $i-1$ or $i$, contradicting that $\alpha$ is peakless and tieless. 
\end{remark}
    
    \begin{lemma}\label{lemma:l-is-e}
        If $n \geq 1$, then $E_{n+1} = L_n$, and if $n\geq 0$, then  $G_{n+1} = L_{n+1}$. 
    \end{lemma}
    \begin{proof}
    For the first equality, we establish a bijection between $\mathscr{E}_{n+1}$ and $\mathscr{L}_n$, from which the result follows.
    
        Let $e = (e_1,e_2,\ldots, e_{n+1}) \in \mathscr{E}_{n+1}$, so that $e_1=e_{n+1}$. 
        Notice that $e$ is peakless-tieless.
        Since $e_1=e_{n+1}$ and
        $e_2 < e_1$, 
        then we have that $e_2<e_{n+1}$. 
        Furthermore, removing $e_1$ from $e$ does not create a peak, nor a tie. 
        By Remark \ref{rem:properties of ptpfs}, the largest possible value in $e$ is $n-1$ and 
        would occur at the endpoints. 
        This implies that $e_1=e_{n+1}\leq n-1$. 
        Hence, 
        the tuple $(e_2,e_3,\ldots,e_{n+1})$ would allow the cars to park. 
        Thus, $(e_2,e_3,\ldots, e_{n+1}) \in \mathscr{L}_n$. 
        
        In the reverse direction, if $\ell = (\ell_1,\ell_2, \ldots, \ell_n) \in \mathscr{L}_n$, then
        the tuple $\ell'=(\ell_n,\ell_1,\ell_2,\dots, \ell_n)$ has no peaks and no ties as $\ell_n>\ell_1$. 
        Moreover, we know $\ell_n\leq n$.
        Hence, the largest value in $\ell'$ is $n$, and all $n+1$ cars can park.
        Therefore, we get
        $\ell'\in \mathscr{E}_{n+1}$.

        If $\alpha=(a_1,a_2,\ldots,a_{n+1})\in\mathscr{G}_{n+1}$, the map $\flick_n(\alpha)=(a_{n+1},a_{n},\ldots,a_1)$ gives a bijection from $\mathscr{G}_{n+1}$ to $\mathscr{L}_{n+1}$. Hence, 
        $G_{n+1} = L_{n+1}$. 
    \end{proof}
    
    \begin{theorem}\label{thm:Fine count}
        If $n\geq 0$, then $|\PTPF_{n+1}(a_1<a_{n+1})|=F_{n+1}$, the $(n+1)$th Fine number.
    \end{theorem}
    \begin{proof}
        Note, that 
        $\PTPF_{n+1} = \mathscr{C}_{n+1}\bigsqcup\mathscr{E}_{n+1}\bigsqcup\mathscr{L}_{n+1}$,
        so by Equation~\eqref{eq:cat}, we have that \[C_{n+1} = G_{n+1} + E_{n+1} + L_{n+1}.\] 
        By Lemma~\ref{lemma:l-is-e}, $E_{n+1} = L_n$ and $G_{n+1}=L_{n+1}$, implying
        \[C_{n+1} = 2L_{n+1} + L_n.\]
      The initial values are $L_1=0$; and since  $\mathscr{L}_2=\{(1,2)\}$, we have $L_2=1$.
      Deutsch and Shapiro \cite[p.~8]{FineNums} proved the following identity relating the Fine numbers to the Catalan numbers
    \[C_{n+1} = 2F_{n+2} + F_{n+1}\]
    where $F_1=0$ and $F_2=1$.
Together, this implies that $L_{n+1} = F_{n+2}$.
    \end{proof}

The bijections in Lemma~\ref{lem:bijection longer star with 1} and Proposition~\ref{prop:g-is-l}, along with the the enumerative result of Theorem~\ref{thm:Fine count} together imply Theorem~\ref{thm:main2}, establishing that the number of valleyless-tieless parking functions is given by a Fine number.


\subsection{Open problems}
 There are many open problems remaining when considering the set of parking functions of length $n$ with $j$ peaks and $k$ ties, which we denote by 
 $\PF_n(j,k)$. 
Table \ref{tab:no peaks k ties} provides the cardinality of the set $\PF_n(0,k)$ for small values of $n$ and $k$.
The column corresponding to $k=0$ gives the Catalan numbers, which we prove in Corollary~\ref{cor:peakless tieless catalan}. 

\begin{table}[htbp]
    \centering
    \begin{tabular}{|c|c|c|c|c|c|c|}\hline
         $n \setminus k $ ties& $0$ & $1$ & $2$ & $3$ & $4$ & $5$  \\\hline
         $1$ & $1$ &  $0$ & $0$ & $0$ & $0$ &  $0$\\\hline
         $2$ & $2$ &  $1$ & $0$ & $0$ & $0$ &  $0$\\\hline
         $3$ & $5$ &  $6$ & $1$ & $0$ & $0$ &  $0$ \\\hline
         $4$ & $14$ &  $32$ & $12$ & $1$ & $0$ &  $0$\\\hline
         $5$ & $42$ &  $178$ & $110$ & $20$ & $1$ &  $0$\\\hline
         $6$ & $132$ & $1078$ & $978$ & $280$ & $30$ &  $1$\\\hline
    \end{tabular}
    \caption{Number of parking functions of length $n$ with $0$ peaks and $k$ ties.}
    \label{tab:no peaks k ties}
\end{table}

We prove the following two results related to the value of $\PF_n(0,k)$ with $k=n-2,n-1$.

\begin{lemma}
 If $n\geq 1$, then $|\PF_n(0,n-1)|=1$.
 \end{lemma}
 \begin{proof}
     A tuple in $[n]^n$ with $n-1$ ties must have the same value at every entry. 
     The only such parking functions is the all ones tuple. 
 \end{proof}
 \begin{lemma}
 If $n\geq 1$, then $|\PF_n(0,n-2)|=n(n+1)$, the $n$th Oblong number \seqnum{A002378}.
\end{lemma}
\begin{proof}
    Such a tuple has exactly one non-tie. 
    If there is exactly one ascent, the tuple begins
    with $1 \leq i \leq n$ many ones, followed by $n-i$ many repeated values $k$ where $2\leq k \leq i+1$. 
    So the number of possibilities is given by $\sum_{i=1}^ni=n(n+1)/2$. 
    We can reverse the tuple to account for the case where it has exactly one descent. 
    This yields a total of $n(n+1)$, as claimed.
\end{proof}
A general open problem follows.
\begin{problem}
For $n,j,k\in\mathbb{N}$, give recursive or closed formulas for the value of $|\PF_n(j,k)|$.
\end{problem}

One could also consider parking functions of length $n$ with $j$ peaks. 
This set is given by 
\[\PF_n^{j}=\bigcup_{k=0}^{n-1-2j}\PF_n(j,k).\] Table~\ref{tab:peak count} gives the cardinality of $|\PF_n^j|$ for $0\leq j\leq n\leq 6$. 
The first column corresponding to $j=0$ peaks is also given by the row sums in Table \ref{tab:no peaks k ties}. 
We can now pose another open problem.

\begin{problem}
    Characterize and enumerate the set $\PF_n^k$ for general values of $n$ and $k$.
\end{problem}

\begin{table}[htbp]
    \centering
    \begin{tabular}{|c|c|c|c|c|}\hline
         $n \setminus j $  peaks& $0$ & $1$ & $2$ & $3$  \\\hline
         $1$ & $1$ &  $0$ & $0$ & $0$\\\hline
         $2$ & $3$ &  $0$ & $0$ & $0$\\\hline
         $3$ & $12$ & $4$ & $0$ & $0$ \\\hline
         $4$ & $59$ & $66$ & $0$ & $0$\\\hline
         $5$ & $351$ &  $825$ & $120$ & $0$\\\hline
         $6$ & $2499$ & $9704$ & $4604$ & $0$\\\hline
         $7$ & $20823$ & $115892$ & $115959$ & $9470$\\\hline
         $8$ & $197565$ & $145478$ & $2479110$ & $651816$\\\hline
    \end{tabular}
    \caption{Number of parking functions of length $n$ with $j$ peaks.}
    \label{tab:peak count}
\end{table}

\section{Statistic 
encoding}\label{sec:statistic encoding}
We now study a collection of parking functions with a prescribed pattern at every index. 

\begin{definition}
Every $\alpha = (a_1, a_2, \ldots, a_n) \in \PF_n$ gives rise to a word $w = w_1~w_2~\cdots~ w_{n-1}\in\{\A,\D,\T\}^{n-1}$, where for each $i\in[n-1]$ we let
\[w_i=\begin{cases}
    \A, &\text{if $a_i < a_{i+1}$;}\\
    \D, &\text{if $a_i > a_{i+1}$;}\\
   \T, &\text{if $a_i = a_{i+1}$.}\\
\end{cases}\]
We call $w$ the \textit{statistic encoding of $\alpha$} and denote it as $\stat(\alpha)$.
\end{definition}
In defining a statistic encoding, we use the letter $\A$ to denote an ascent, $\D$ to denote a descent, and $\T$ to denote a~tie. 
The vast majority of statistic encodings are non-unique. 
For example, $\alpha = (1,1,2,3,4)$ and $\beta = (1,1,3,4,5)$ both have $w = \T\A\A\A$ as their statistic encoding. 

In this section, we answer the following questions: 
\begin{enumerate}
    \item Does there exist a parking function with statistic encoding $w$ for arbitrary $w$? \label{q:1}
    \item When is a statistic encoding determined by a unique parking function?\label{q:2} 
\end{enumerate}

To begin, we set the following notation. 
Let $W_{n-1}$ denote the set of all statistic encodings of length $n-1$, which implies $W_{n-1}=\{\A,\D,\T\}^{n-1}$. 
Our first result establishes that every word of length $n-1$ in the letters $\A,\D,\T$ arises as a statistic encoding for some parking function. 
Before proving the result, we illustrate this notation with an example.

\begin{example}
    To construct a parking function for the word $\D\A\T\A$, we begin with a parking function whose statistic encoding is  $\D\A\T$, such as $\alpha=(3,1,2,2)$. 
    To account for the added ascent at the end of the word $\D\A\T\A$, we simply append $5$ to $\alpha$ and obtain $(3,1,2,2,5)\in\PF_5$. 
    Notice that $(3, 1, 2, 2, 5)$ is not the only parking function with statistic encoding $\D\A\T\A$ as we could have also appended $3$ or $4$.

    If instead we want to construct a parking function with statistic encoding 
    $\A\T\A\D\D$, we begin with the parking function $\beta=(1,2,2,3,1)$ with a corresponding statistic encoding $\A\T\A\D$. 
    To construct a parking function with statistic encoding $\A\T\A\D\D$, we must create a new descent at the end of $\beta$. 
    To do this, we begin by incrementing every entry in $\beta$ by one, resulting in the tuple $(2,3,3,4,2)$. 
    Then append  $1$ to the end of that tuple creating $(2,3,3,4,2,1)$, which is an element of $\PF_6$ and has the desired statistic encoding $\A\T\A\D\D$.
\end{example}

We are now ready to settle Question~\eqref{q:1}.

\begin{theorem}\label{thm:stat ecoding}
If $w\in W_{n-1}$, then there exists $\alpha\in\PF_n$ which has $w$ as its statistic encoding.
\end{theorem}
\begin{proof}
    We proceed by induction on $n$, the length of the parking function. 
    We begin with the base case where $n = 1$ and observe that the empty statistic encoding arises from the parking function $(1)$.
    
    Assume for induction that for $n > 1$ and for every 
    $w\in\{\A,\D,\T\}^{n-1}$ 
    there is a parking function 
    $\alpha=(a_1,a_2,\ldots,a_{n})\in\PF_n$ 
    with statistic encoding $w$.

    Now consider a word 
    $w\in W_{n}=\{\A,\D,\T\}^{n}$ such that $w=w'x$ where $w' \in \{\A,\D,\T\}^{n-1}$ and $x \in \{\A, \D, \T\}$.
    By the inductive step, we can find some $P' = (p'_1, p'_2, \ldots, p'_{n}) \in \PF_{n}$
    whose statistic encoding is $w'$.
    To obtain a parking function $\alpha\in\PF_{n+1}$ with statistic encoding $w=w'x$, we append a new preference to $P'\in\PF_{n}$ based on the letter $x$ by the following criteria:
    \begin{enumerate}
    \item[C1:]\label{C1} If $x=\T$, we append $p_{n}'$  to $P'$ constructing 
    \[\alpha = (p_1', p_2', \ldots, p_{n}', p_{n}').\]
    Note, $\alpha$ is a parking function of length $n+1$ as $P'$ is a parking function of length $n$, and appending the value $p_n'$ ensures that car $n+1$ parks in spot $n+1$. 
    Moreover, this ensures that the parking function ends with a tie.
    \item[C2:]\label{C2} {If $x=\A$}, we append $n+1$ to $P'$ to get 
    \[\alpha = (p'_1, p'_2, \ldots, p'_n,n+1).\] 
    Note, $\alpha$ is a parking function of length $n+1$ and $P'$ is a parking function of length $n$. Appending the value $n+1$ to $\alpha$ ensures that car $n+1$ parks in spot $n+1$. 
    Moreover, this ensures that the parking function ends with an ascent.
    \item[C3:]\label{C3} {If $x=\D$}, we modify $P'$ by incrementing each $p_i'$ by one and then appending the value $1$ at the end of $P'$ to get
    \[\alpha =(p'_1 + 1, p'_2 + 1, \ldots, p'_{n} + 1, 1).\]
    Note, $P'$ is a parking function of length $n$, and by incrementing its values by one, the cars $1$ through $n$ in $\alpha$ park in spots $2$ through $n+1$. 
    Then car $n+1$ with preference $1$ parks in spot~$1$. 
    Thus, $\alpha$ is a parking function of length $n+1$. 
    Moreover, this ensures that the parking function ends with a descent.\qedhere
    \end{enumerate}
\end{proof}
In the next result, we use the notation $\A^*\T^*$ to describe a word with some nonnegative integer number of $\A$'s followed by a nonnegative integer number of $\T$'s.
When we specify that $\A^*\T^*\in W_{n-1}$, then the total number of $\A$'s and $\T$'s must be equal to $n-1$.
Whenever we want to specify the full set of such words, we write $\{\A^*\T^*\}$.
Likewise for $\T^*\D^*$ and $\{\T^*\D^*\}$. 

With this notation in mind, we now settle Question~\eqref{q:2}.
\begin{lemma}\label{lem:babysteps}
    Let $w \in W_{n-1}$. 
    If there is a unique $\alpha \in \PF_n$ such that $\stat(\alpha) = w$, then for all indices $i \in [n-1]$, $|\alpha_{i+1} - \alpha_i| \leq 1$.
    Moreover, if $m_p(\alpha) > 0$, then $m_q(\alpha) > 0$ for all $q < p$.
\end{lemma}

\begin{proof}
    Let $w\in W_{n-1}$.
    Assume towards a contradiction that $\alpha$ is a parking function with an index $i$ such that $|\alpha_{i+1} - \alpha_i| > 1$. 
    Without loss of generality, suppose $p = \alpha_{i+1} > \alpha_i$.
    Let $j$ be the first index after $i$ such that $\alpha_j \neq \alpha_{j+1}$. 
    In other words, let $\alpha$ have the following structure:
    \[(\alpha_1, \ldots, \alpha_i, \underbrace{p}_{i+1}, p, \ldots, \underbrace{p}_j, \alpha_{j+1}, \ldots, \alpha_n),\]
    where $\alpha_i, \alpha_{j+1} \neq p$. 
    Then the tuple
    \[\alpha' = (\alpha_1, \ldots, \alpha_i, \underbrace{p-1}_{i+1}, p-1, \ldots, \underbrace{p-1}_j, \alpha_{j+1}, \ldots, \alpha_n)\]
    has the same statistic encoding as $\alpha$. 
    We know that $\alpha'$ is a parking function because reducing the value of an element in a parking function always yields a parking function.
    Then $\stat(\alpha')=w$, yielding a contradiction.
    Thus, $\alpha$ is not the unique parking function such that $\stat(\alpha)=w$.

    The second part of the lemma results from induction on the maximal value $p$ in $\alpha$. 
    First, observe that $1$ appears at least once in every parking function. 
    Then if $p = 1$ or $p = 2$ the proposition is straightforward. 
    Now assume the inductive hypothesis on a parking function $\alpha$ with maximum value $p$. 
    Let $i$ be the first index such that exactly one of $\alpha_i$ and $\alpha_{i+1}$ is equal to $p$. 
    Without loss of generality, assume $\alpha_i = p$ and $\alpha_{i+1} \neq p$. 
    Then by the first part of the lemma, $\alpha_{i+1} = p - 1$. 
    Then $m_{p-1}(\alpha) > 0$, so by $m_q(\alpha) > 0$ for all $q < p$ by induction.
\end{proof}

\begin{lemma}\label{lem:extremes}
    Let $w \in W_{n-1}$. 
    If there is a unique $\alpha \in \PF_n$ with $\stat(\alpha) = w$, then the statistic encoding of the nondecreasing rearrangement $\beta$ of $\alpha$ is of the form \emph{$\A^*\T^*$}.
\end{lemma}

\begin{proof}
    For the sake of contradiction, suppose that $\alpha$ is the unique parking function with $\stat(\alpha) = w$ but the statistic encoding of the nondecreasing rearrangement $\beta$ of $\alpha$ is not of the form $\A^*\T^*$. 
    Then let $i$ be the index of the first $\A$ in $\stat(\beta)$ that comes after a $\T$. 
    Then $\alpha_{i} < i$. 
    By Lemma~\ref{lem:babysteps}, $\alpha_{j+1} \leq \alpha_j + 1$ for all $j \in [n-1]$. 
    Then using induction, $\alpha_j < j$ for all $j > i$. 
    Now let $p$ be the maximal value of $\alpha$. 
    In $\beta$, all instances of $p$ are strictly less than their index. 
    Then let $\alpha'$ be the tuple obtained by increment all instances of $p$ in $\alpha$. 
    Then $\alpha'$ is still a parking function and 
    has the same statistic encoding of $\alpha$. 
    This contradicts $\alpha$ being the unique parking function with statistic encoding $w$.
\end{proof}

\begin{lemma}\label{lem:ones}
    Let $w \in W_{n-1}$ with unique $\alpha \in \PF_n$ such that $\stat(\alpha) = w$. 
    If there exist indices $1 \leq i \leq j \leq n$ such that $\alpha_{i-1} > \alpha_i = \alpha_{i+1} = \cdots = \alpha_j < \alpha_{j+1}$ where $\alpha_{i-1}$ and $\alpha_{j+1}$ exist, then $\alpha_i = \cdots = \alpha_j = 1$.
\end{lemma}

\begin{proof}
    Let $w \in W_{n-1}$ with unique $\alpha \in \PF_n$ such that $\stat(\alpha) = w$.
    For the sake of contrapositive, let the indices satisfy
    $1 \leq i < j \leq n$ such that $\alpha_{i-1} > \alpha_i = \alpha_{i+1} = \cdots = \alpha_j < \alpha_{j+1}$
    with $\alpha_i > 1$.
    The parking function $\alpha'$ obtained by replacing $\alpha_i, \ldots, \alpha_j$ with $1, \ldots, 1$ has the same statistic encoding as $\alpha$. 
    Thus, $\alpha$ is not the unique parking function with $\stat(\alpha) = w$. 
\end{proof}

In other words, if $\alpha$ is the unique parking function with statistic encoding $w$, then the local minimum in $\alpha$ has value $1$.

\begin{theorem}
    Let $w \in W_{n-1}$. 
    Then there is a unique $\alpha\in\PF_n$ with statistic encoding $w$ if and only if \emph{$w \in \{\A^*\T^*\} \cup \{\T^*\D^*\}$}.
\end{theorem}

\begin{proof}
    $(\Rightarrow)$ First we show that if $w$ contains both $\A$ and $\D$, then there are multiple parking functions $\alpha$ with $\stat(\alpha) = w$.
    Suppose $w$ contains both $\A$ and $\D$. 
    Then there is some $n \geq 0$ such that either $\A\T^n\D$ or $\D\T^n\A$ is a contiguous subword of $w$.
    \begin{itemize}
        \item Suppose $v = \A\T^n\D$ is a contiguous subword of $w$. 
        Where $v$ first appears in $w$, let $i$ be the index $\A$ and let $j$ be the index of $\D$.
        Let $p$ be the minimum value in $\alpha$ with index weakly less than $i$ and let $q$ be the minimum value in $\alpha$ with index strictly greater than $j$. 
        By Lemma~\ref{lem:ones}, $p = q = 1$.
        Then the nondecreasing rearrangement $\beta$ of $\alpha$ starts with two $1$'s, but is not itself all ones. 
        This contradicts Lemma~\ref{lem:extremes}.
        \item Suppose $v = \D\T^n\A$ is a contiguous subword of $w$. 
        For the sake of contradiction, suppose $\alpha$ is the unique parking function with $\stat(\alpha) = w$. 
        By the previous bullet point, there is no $\A$ that comes before $\D$ in $w$. 
        Then $\alpha$ can be broken into a nonincreasing part $\alpha^*$, some amount of $1$'s, and a nondecreasing part $\alpha^{**}$. 
        We choose $\alpha^*$ and $\alpha^{**}$ such that neither contain $1$'s.
        By Lemma~\ref{lem:babysteps}, $\alpha^*$ ends with a $2$ and $\alpha^{**}$ begins with a $2$. 
        Then the nondecreasing rearrangement $\beta$ of $\alpha$ is of the form $(1, \ldots, 1, 2, 2, \ldots)$. 
        By Lemma~\ref{lem:extremes}, $\beta$ contains only one instance of the value $1$ and has no ascents after the first position. 
        Then $\alpha$ is of the form $(2, \ldots, 2, 1, 2, \ldots, 2)$. 
        However, the parking function $\alpha' = (3, \ldots, 3, 1, 2, \ldots, 2)$ has the same statistic encoding as $\alpha$, contradicting $\alpha$ being the unique parking function with statistic encoding $w$.
    \end{itemize}
    Now we consider the case where $w$ does not have both $\A$ and $\D$.
    \begin{itemize}
        \item Suppose that $w$ does not contain $\D$. 
        If $\stat(\alpha) = w$, $\alpha$ is nondecreasing.
        By Lemma~\ref{lem:extremes}, $w$ is of the form $\A^*\T^*$.
        \item Suppose that $w$ does not contain $\A$.
        If $\stat(\alpha) = w$, $\alpha$ is nonincreasing.
        The nondecreasing rearrangement $\beta$ of $\alpha$ is exactly the reverse of $\alpha$. 
        The statistic encoding of $\beta$ is of the form $\A^*\T^*$, so the statistic encoding of $\alpha$ is of the form $\T^*\D^*$.
    \end{itemize}
    
    ($\Leftarrow$)
    Let $w \in \{\A^*\T^*\} \cup \{\T^*\D^*\}$. 
    We consider the case where $w\in \{\A^*\T^*\}$ and $w\in\{\T^*\D^*\}$, separately and show that $\alpha$ with statistic encoding $w$ is unique.
    \begin{itemize}
        \item If $w=\A^i\T^{n-1-i}$ for some $i\in[n-1]$, then $a_1=1$. 
        We claim $a_j=j$ for all $2\leq j\leq i$. 
        For the sake of contraction, suppose that there exists $1<j'\leq i$ such that $a_{j'}\neq j'$.  
        Then the number $j'$ does not appear in $\alpha$ as its statistic encoding is  $w=\A^i\T^{n-1-i}$. 
        This would imply that no car parks in spot $j$ and hence $\alpha$ is not a parking function giving us a contradiction. 
        Thus, $a_j=j$ for all $1\leq j\leq i$. 
        Since $w=\A^i\T^{n-1-i}$, we now have that $a_{i+1}=a_{i+2}=\cdots=a_{n}=i$. 
        Thus, if $w=\A^i\T^{n-1-i}$, then $\alpha$ is unique and has the form
    \begin{align}
        \alpha=(1,2,\ldots,i-1,i,i+1,i+1,\ldots,i+1)\in\PF_n.\label{eq:first alpha}
    \end{align}
    \item If $w=\T^{n-1-i} \D^{i}$ for some $i\in[n-1]$, then $a_n=1$.
    By a similar argument in the bullet above, we can show $w$ is a unique parking function.
    We can reverse the parking function $\alpha$ given in Equation~\eqref{eq:first alpha} to create \[\alpha^*=(i+1,i+1,\ldots,i+1,i,i-1,\ldots,3,2,1),\] which is a parking function and has $w$ as its statistic encoding. 
    As $\alpha$ was unique, so is $\alpha^*$.\qedhere
    \end{itemize}
\end{proof}

We conclude by posing the following open problems.
\begin{problem}
    Fix a statistic encoding $w\in W_{n-1}$. 
    Characterize and enumerate the subset of parking functions of length $n$ which have $w$ as their statistic encoding.
\end{problem}
\begin{problem}
For which statistic encoding $w\in W_{n-1}$ is the subset of parking functions of length $n$ which have $w$ as their statistic encoding the largest?
\end{problem}

\section{Acknowledgments}
The authors thank the anonymous referee for an exceptionally detailed review process. We appreciate their feedback and care.

\begin{thebibliography}{99}

\bibitem{Bencs}
F.~Bencs, Some coefficient sequences related to the descent polynomial, {\em
  European J. Combin.} {\bf 98} (2021), 103396.

\bibitem{billey:peak-set}
S.~Billey, K.~Burdzy, and B.~Sagan, Permutations with given peak set, {\em J.
  Integer Sequences} {\bf 16} (2012), 
  \href{https://cs.uwaterloo.ca/journals/JIS/VOL16/Billey/billey2.html}{Article  13.6.1}.

\bibitem{FineNums}
E.~Deutsch and L.~W. Shapiro, A survey of the {F}ine numbers, {\em Discrete
  Math.} {\bf 241} (2001), 241--265.

\bibitem{peakpoly}
A.~Diaz-Lopez, P.~E. Harris, E.~Insko, and M.~Omar, A proof of the peak
  polynomial positivity conjecture, {\em J. Combin. Theory Ser. A} {\bf 149}
  (2017), 21--29.

\bibitem{DescentPolys}
A.~Diaz-Lopez, P.~E. Harris, E.~Insko, M.~Omar, and B.~E. Sagan, Descent
  polynomials, {\em Discrete Math.} {\bf 342} (2019), 1674--1686.

\bibitem{dillon}
J.~F. Dillon and D.~P. Roselle, Simon {N}ewcomb's problem, {\em SIAM J. App.
  Math.} {\bf 17} (1969), 1086--1093.

\bibitem{Elizalde}
S.~Elizalde, Descents on quasi-{S}tirling permutations, {\em J. Combin. Theory
  Ser. A} {\bf 180} (2021), 105429.

\bibitem{Fulton}
W.~Fulton, {\em Young {T}ableaux}, Cambridge University Press, 1997.

\bibitem{pathsSYT}
J.~B. Gil, P.~R.~W. McNamara, J.~O. Tirrell, and M.~D Weiner, From {D}yck paths
  to standard {Y}oung tableaux, {\em Ann. Comb.} {\bf 24} (2020), 69--93.

\bibitem{Gudmundsson:DyckPaths}
Hilmar Gudmundsson, Dyck paths, standard Young tableaux, and pattern avoiding
  permutations, ArXiv preprint 	arXiv:0912.4747 [math.CO], December 23 2009.  Available at \url{https://arxiv.org/abs/0912.4747}.

\bibitem{jiradilok2021roots}
P.~Jiradilok and T.~McConville, Roots of descent polynomials and an algebraic
  inequality on hook lengths, {\it Elect. J. Combinatorics} {\bf 30} (2003), P4.41.
  Available at \url{https://www.combinatorics.org/ojs/index.php/eljc/article/view/v30i4p41}.

\bibitem{MacMahon}
P.~A. MacMahon, {\em Combinatory Analysis}, Chelsea Publishing Co., 
  1960.

\bibitem{Raychev}
Angel Raychev, A generalization of descent polynomials, {\em Discrete Math.}
  {\bf 346} (2023), 113105.

\bibitem{Schumacher}
P.~R.~F. Schumacher, Descents in parking functions, {\em J. Integer Sequences} {\bf
  21} (2018), \href{https://cs.uwaterloo.ca/journals/JIS/VOL21/Schumacher/schu5.html}{Article 18.2.3}.

\bibitem{stanley:catalan}
R.~P. Stanley, {\em Catalan Numbers}, Cambridge University Press, 2015.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2020 \emph{Mathematics Subject Classification}: Primary 05A05; Secondary 05A15.

\noindent \emph{Keywords: } parking function, descent, ascent, tie, multiset, Eulerian polynomial, Catalan number, Fine number.

\bigskip 
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000108},
\seqnum{A000957},
\seqnum{A002378},
\seqnum{A009766},
\seqnum{A033282}, and
\seqnum{A333829}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received December 28 2023;
revised versions received  May 11 2024; October 31 2024; November 28 2024; November 29 2024.
Published in {\it Journal of Integer Sequences}, November 30 2024.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                

