%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2025}
\articlenumber{145}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}
\usepackage{tikz,mathtools, tabu, float}
\usepackage{subcaption}
\newcommand{\Fub}{\text{Fub}}
\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}

\usepackage{lipsum}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\newcommand{\jennifer}[1]{\textcolor{orange}{[Jennifer: #1]}}
\newcommand{\pamela}[1]{\textcolor{blue}{[Pamela: #1]}}
\newcommand{\kph}[1]{\textcolor{magenta}{[Kimberly: #1]}}
\newcommand{\kyle}[1]{\textcolor{violet}{[Kyle: #1]}}
\newcommand{\matt}[1]{\textcolor{purple}{[Matt: #1]}}
\newcommand{\kim}[1]{\textcolor{olive}{[Kim: #1]}}
\newcommand{\Mei}[1]{\textcolor{cyan}{[Mei: #1]}}
\definecolor{navy}{rgb}{0.0,0.0,0.6}
\newcommand{\amanda}[1]{\textcolor{navy}{[Amanda: #1]}}
\newcommand{\Gabe}[1]{\textcolor{red}{[Gabe: #1]}}
\newcommand{\jeremy}[1]{\textcolor{teal}{[Jeremy: #1]}}
\newcommand{\ari}[1]{\textcolor{Green}{[Ari: #1]}}
\newcommand{\keith}[1]{\textcolor{brown}{[Keith: #1]}}
\newcommand{\red}[1]{\textcolor{red}{#1}}
\newcommand{\blue}[1]{\textcolor{blue}{#1}}

\newcommand{\suchthat}{\colon} % if we want to argue about colons versus bars, this will make it easy to implement whatever we decide
% \newcommand{\fr}[1]{\mathrm{FR}_{#1}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\renewcommand{\P}{\mathbb{P}}
\renewcommand{\S}{\mathfrak{S}}
\newcommand{\Sym}{\mathfrak{S}}
\newcommand{\eqpd}{\, .}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\con}{\mathrm{c}}

\DeclareMathOperator{\des}{des}
\DeclareMathOperator{\Des}{Des}
\DeclareMathOperator{\asc}{asc}
\DeclareMathOperator{\im}{im}
\DeclareMathOperator{\inv}{inv}
\DeclareMathOperator{\linv}{linv}
\DeclareMathOperator{\luinv}{linv}
\DeclareMathOperator{\Inv}{Inv}
\DeclareMathOperator{\maj}{maj}
\DeclareMathOperator{\tie}{tie}
\DeclareMathOperator{\area}{area}
\DeclareMathOperator{\blocks}{blocks}
\DeclareMathOperator{\Out}{\mathcal{O}}
\DeclareMathOperator{\IPF}{IPF} %%Interval parking functions
\DeclareMathOperator{\PF}{PF}
\DeclareMathOperator{\UPF}{UPF} %%Unit interval parking function
\DeclareMathOperator{\upf}{upf} %% number of unit interval parking functions
\DeclareMathOperator{\OP}{OP}
\DeclareMathOperator{\U}{U}%%inv-generating function for \UPF
\DeclareMathOperator{\fb}{fub}
\DeclareMathOperator{\fix}{fix}
\DeclareMathOperator{\std}{std}
\renewcommand{\L}{\operatorname{L}}
 \newcommand{\fr}[1]{\text{FR}_{#1}}
 \DeclareMathOperator{\FW}{FW}
 \DeclareMathOperator{\supp}{supp}
  \DeclareMathOperator{\Comp}{Comp}
    \DeclareMathOperator{\WComp}{WComp}
\DeclareMathOperator{\pinv}{pinv}
\DeclareMathOperator{\statsplit}{stat}
\DeclareMathOperator{\ps}{ps}
\DeclareMathOperator{\ch}{ch}
\renewcommand{\subset}{\subseteq}

\newcommand{\norm}[1]{\left\lVert#1\right\rVert}
\newcommand{\tr}{\textcolor{red}}
\DeclareMathOperator{\out}{out} % used in the ell=2 section
\DeclareMathOperator{\disp}{disp} % used in the ell=2 section
%\newcommand{\st}{\colon} % "such that"; using a macro for consistency; used in ell=2 section --- can be replaced with \mid if we decide to use bars instead of colons %Kyle heavily prefers \mid.
\newcommand{\defterm}{\textbf} % for terms being defined; again using a macro for consistency; Jeremy likes boldface for this but italics are more common
\DeclareMathOperator{\E}{\mathbb{E}}
% \DeclareMathOperator{\F}{\mathbb{F}}
\DeclareMathOperator{\C}{\mathfrak{C}}
\DeclareMathOperator{\bP}{\mathbb{P}}
\DeclareMathOperator{\Exp}{Exp}

\newcommand{\qbinom}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}}%q-bi/multinomial coefficients

\newcommand{\lp}{\left(}
\newcommand{\rp}{\right)}
\newcommand{\lb}{\left[}
\newcommand{\rb}{\right]}

\newcommand{\bl}[1]{{\color{blue} #1}}
\newcommand*{\Pref}[1]{\mathsf{Pref}_{#1}}

% \theoremstyle{definition} 
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
 \newtheorem{example}[theorem]{Example}
 \newtheorem{exercise}[theorem]{Exercise}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{question}[theorem]{Question}


  




%% define your title in the usual way
\title[Inversions in Parking Functions]{Inversions in Parking Functions}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
%% for more than 3 names, use the Oxford comma: One Author, Two Author, Red Author, \and Blue Author
\author[Celano, Elder, Hadaway, Harris, Priestley, and Udell]{\texorpdfstring{
Kyle Celano\thanks{\href{mailto:celanok@wfu.edu}{celanok@wfu.edu}}\addressmark{1},
Jennifer Elder\thanks{\href{mailto:jelder8@missouriwestern.edu}{jelder8@missouriwestern.edu}}\addressmark{2},
Kimberly P. Hadaway\thanks{\href{mailto:kph3@iastate.edu}{kph3@iastate.edu}}\addressmark{3},
Pamela E. Harris\thanks{\href{mailto:peharris@uwm.edu}{peharris@uwm.edu}}\addressmark{4},
%\and
%Jeremy L. Martin\thanks{\href{mailto:jlmartin@ku.edu}{jlmartin@ku.edu}}\addressmark{5}
Amanda Priestley\thanks{\href{mailto:amandapriestley@utexas.edu}{amandapriestley@utexas.edu}}\addressmark{5},
\and
Gabe Udell\thanks{\href{mailto:gru5@cornell.edu}{gru5@cornell.edu}}\addressmark{6}
}{
Kyle Celano,
Jennifer Elder,
Kimberly P. Hadaway,
Pamela E. Harris,
%and
%Jeremy L. Martin
Amanda Priestley,
and
Gabe Udell
}}

%% then use \addressmark to match authors to institutions here

\address{
\addressmark{1}Department of Mathematics, Wake Forest University, NC\\
\addressmark{2}Department of Computer Science, Mathematics and Physics, Missouri Western State University, St. Joseph, MO\\
\addressmark{3}Department of Mathematics, Iowa State University, Ames, IA \\
\addressmark{4}Department of Mathematical Sciences, University of Wisconsin-Milwaukee, Milwaukee, WI\\
\addressmark{5}Department of Computer Science, The University of Texas at Austin, Austin, TX\\
\addressmark{6}Department of Mathematics, Cornell University, Ithaca, NY 
}
% \addressmark{5}Department of Mathematics, University of Kansas, Lawrence, KS 66045\\

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{
% Parking functions can be thought of as a set of words containing permutations. 
% As such, one can study permutation statistics on them, like inversions. 
% \Gabe{I feel that we can study inversions because parking functions are words in $[n]$ and not because they generalize in versions.} 
% \kph{i agree with gabe's comment and propose: ``Parking functions, like permutations, are a subset of words in $[n]$, and as such, we can explore permutation statistics on parking functions. 
% A very common permutation statistic is inversions; however, there is a gap in the literature as these two concepts have been studied independently and not together.''}
% However, despite both inversions and parking functions being well-studied concepts, they appear to have never been considered together. 
% \jeremy{I would actually cut everything above this and start with the next sentence.  What Gabe and Kimberly say is logical, but I think the inTtroduction is the place for that, not the abstract.  Here we should state as concisely as possible what our results are.}
In this paper, we obtain a $q$-exponential generating function for inversions on parking functions in two ways (1) via symmetric function theory and (2) through a direct bijection to labeled rooted forests. 
Moreover, we obtain an expression for the total number of inversions across all parking functions via a probabilistic approach. 
Finally, by applying these techniques to \textit{unit interval parking functions} (defined by Hadaway 2021) we give analogous results. 
}

%% put your French abstract here, or comment this out if you don't have one
% \resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{inversions, parking functions, symmetric functions, generating functions}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
 \usepackage[backend=bibtex, giveninits]{biblatex}
\addbibresource{sample.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle

\section{Introduction}
Throughout we let $\P\coloneqq\{1,2,\dots\}$, and if $n\in\P$, then $[n]\coloneqq\{1,2,\ldots,n\}$. 
We let $\S_n$ denote the set of permutations of $[n]$.
Konheim and Weiss \cite{Konheim1966} defined ``parking functions'' as follows: consider a one-way street with $n$ parking spots (labeled in increasing order) and $n$ cars, each of which has a preferred spot. 
As each car parks, it drives to its preferred spot and parks there if it is unoccupied. 
If that spot is not available, the car continues driving and parks in the next available spot, if any exists.  
We encode the information of the preferred spots as an positive integer-valued \defterm{preference list} $\alpha = (\alpha_1,\alpha_2,\dots,\alpha_n)\in [n]^n$, where for each $i\in[n]$, the positive integer $\alpha_i$ indicates the preferred spot of car $i$. 
We say the preference list $\alpha$ is a \defterm{parking function} if all cars are able to park using the aforementioned parking rule. The \defterm{outcome permutation} $\pi(\alpha)$ is defined by setting $\pi(\alpha)(j)=i$ if car $i$ parks in spot $j$.
We let $\PF_n$ be the set of all parking functions of length $n$. 
In 1974, Pollak proved that the number of parking functions of length $n$ is $(n+1)^{n-1}$ (see \cite{bib:stanleydocpollakproof}).

Introduced by Hadaway \cite{bib:HadawayUndergradThesis},  a \defterm{unit interval parking function} of length $n$ is a parking function $\alpha\in \PF_n$ such that $\pi(\alpha)^{-1}(i)-\alpha_i\leq 1$ for all $i\in[n]$. Let $\UPF_n$ denote the set of unit interval parking functions of length $n$. 
Hadaway \cite{bib:HadawayUndergradThesis} proves that $|\UPF_n|=\Fub_n$, which is the \textit{$n$-th Fubini number} and counts the number of ordered set partitions of $[n]$ (OEIS \seqnum{A000670}). Unit interval parking functions have been studied in connection to enumerating Boolean intervals of 
the weak Bruhat order of the symmetric group and in connection to the faces of the permutohedron \cite{unit_perm,elder2024parking}.

We are interested in the study of inversions of parking functions and unit interval parking functions. 
Recall that for a word $w\in \P^n$, an \defterm{inversion} is a pair $(i,j)$ of integers in $[n]$ such that $i<j$ and $w_i>w_j$. We denote the set of inversions of a word $w$ by $\Inv(w)$ and let $\inv(w)=|\Inv(w)|$. 
For each $n\in\P$, define the polynomials
\[\PF_n(q)=\sum_{\alpha\in \PF_n}q^{\inv(\alpha)}\quad \mbox{and}\quad\UPF_n(q)=\sum_{\alpha\in \UPF_n}q^{\inv(\alpha)}, \]
and set $\PF_0(q)=\UPF_0(q)=1$. 
Define
\[\Exp_q(z)=\sum_{n\geq 0}q^{\binom{n}{2}}\frac{z^n}{[n]_q!}\quad \mbox{and }\quad\exp_q(z)=\sum_{n\geq 0}\frac{z^n}{[n]_q!},\]
where $[n]_q=1+q+\cdots+q^{n-1}$ and $[n]_q!=[n]_q[n-1]_q\cdots[1]_q$.
Using combinatorial techniques, we derive the following generating functions. 
\begin{theorem}\label{eq:pf-upf-inv-gen-functs} The $q$-exponential generating functions for $\PF_n(q)$ and $\UPF_n(q)$ are 
    \[\sum_{n\geq 0}\PF_n(q)\frac{z^{n+1}}{[n]_{q}!}=(z\Exp_{q}(-z))^{\langle -1\rangle }\quad \mbox{and }\quad\sum_{n\geq 0}\UPF_n(q)\frac{z^{n}}{[n]_{q}!}=\frac{1}{2-\exp_q(z)},\]
    where $F(z)^{\langle -1\rangle}$ denotes the
    compositional inverse of $F(z)$.
\end{theorem}
\Cref{eq:pf-upf-inv-gen-functs} gives $q$-analogues of  classical results of Konheim and Weiss \cite{Konheim1966} and Cayley \cite{cayley1856}, respectively: 
\begin{equation}\label{eq:results2}
    \sum_{n\geq 0}|\PF_n|\frac{z^{n+1}}{n!}=(ze^{-z})^{\langle -1\rangle }\quad \mbox{and } \quad \sum_{n\geq 0}|\UPF_n|\frac{z^{n}}{n!}=\frac{1}{2-e^z}.
\end{equation}
The latter result follows from the work of Cayley and the bijection between unit interval parking functions and Cayley words (see \cite{bib:HadawayUndergradThesis}).
We also show that the equations in \eqref{eq:results2} follow from a more general theory of symmetric functions. The main result is as follows.
\begin{theorem}\label{eq:pf-upf-sym-gen-functs}There are $\S_n$-modules $\CC[\PF_n]$ and $\CC[\UPF_n]$ such that 
\begin{equation}\label{eq:frobenius_char}
    \sum_{n\geq 0}\ch\CC[\PF_n]z^{n+1}=(zE(-z))^{\langle -1\rangle }\quad \mbox{and } \quad \sum_{n\geq 0}\ch \CC[\UPF_n]z^n=\frac{1}{2-H(z)} \ ,
\end{equation}
where $\ch$ denotes the Frobenius characteristic map from $\S_n$-modules to symmetric functions of degree $n$.
Here,
$E(z)=\sum_{n\geq 0}e_nz^n$ and $H(z)=\sum_{n\geq 0}h_nz^n$
are generating functions for the complete homogeneous symmetric functions and the elementary symmetric functions, respectively.\end{theorem} 
The Frobenius character in \eqref{eq:frobenius_char} for parking functions was computed algebraically by Haiman \cite{haiman_conjectures_1994}, and we provide a new combinatorial proof using labeled rooted forests. 
Then, using a modified version of stable principal specialization, we use \Cref{eq:pf-upf-sym-gen-functs} to provide a second proof of \Cref{eq:pf-upf-inv-gen-functs}.

The passage from symmetric functions to inversions can be more generally done at the level of any $\S_n$-invariant set of words (see \Cref{lem:character-of-words-inversions}). Similarly, we show that for any  $\S_n$-invariant subset $W\subset \P^n$ of positive integers, we have the curious equality
    \begin{equation}\label{eq:sum-inv-ws-intro}\sum_{w\in W}\inv(w)=\frac{n}{2}\sum_{w\in W}\des(w),\end{equation}
where $\des(w)$ is the number of \defterm{descents} of $w$ i.e., the number of positions $i\in [n-1]$ such that $w_i>w_{i+1}$.
We use probabilistic methods to prove \eqref{eq:sum-inv-ws-intro}. This allows us to obtain analogous results of Schumacher \cite{bib:DescentsInPF}.
\begin{theorem}
\label{eq:sum-invs-pf-upfs-intro}
Let $(\Fub_n)_{n\geq 1}$ denote the Fubini numbers. Then, for all $n\geq 1$, we have that
     \[\sum_{\alpha\in \PF_n}\inv(\alpha)=\frac{n(n+1)^{n-2}}{2}\binom{n}{2}\quad \mbox{and} \quad \sum_{\alpha\in \UPF_n}\inv(\alpha)=\frac{n(n-1)}{4}(\Fub_n-\Fub_{n-1}).\]
\end{theorem}

This article is organized as follows.
 In \Cref{sec:labeled rooted forests}, we describe a new inversion statistic, an $\S_n$-action on labeled rooted forests, and a bijection between parking functions and labeled rooted forests that preserves inversions and the $\S_n$-action. 
 In \Cref{sec:inversions-in-pfs}, we use this bijection to provide combinatorial proofs of \Cref{eq:pf-upf-inv-gen-functs} and \Cref{eq:pf-upf-sym-gen-functs} for parking functions. 
 We also give the probabilistic argument establishing \eqref{eq:sum-inv-ws-intro} from which we prove \Cref{eq:sum-invs-pf-upfs-intro} for parking functions. 
 In \Cref{sec:inversions-in-upfs}, we apply the techniques from \Cref{sec:inversions-in-pfs} to show \Cref{eq:pf-upf-inv-gen-functs}, \Cref{eq:pf-upf-sym-gen-functs}, and \Cref{eq:sum-invs-pf-upfs-intro} for unit interval parking functions. 
 We finish with a brief discussion of future work in \Cref{sec:future-work}.


\section{Labeled rooted forests}\label{sec:labeled rooted forests}
We assume the reader is familiar with basic notions from graph theory: namely trees, forests, rooted trees, and rooted forests. The main objective of this section is to describe a statistic on labeled rooted forests and a bijection to parking functions taking this statistic to inversions of parking functions. 
To begin, recall that parking functions are in bijection with combinatorial objects called \defterm{labeled rooted forests} \cite{Konheim1966}, where a rooted forest is made up of rooted trees in which every vertex is given a unique integer. 
We denote the set of labeled rooted forests on vertex set $[n]$ by $\F_n$. 
If $T$ is a labeled rooted tree and $v$ is a nonroot vertex of $T$, define the \defterm{parent} $p(v)$ to be first element on the path from $v$ to the root. We say that $v$ is a \defterm{child} of $u$ if $p(v)=u$.
For a labeled rooted tree $T$, let $r(T)$ denote its root. The \defterm{subtrees} of a labeled rooted tree $T$ are labeled rooted subtrees $T_1,T_2,\dots,T_k$ such that $r(T_i)$ is adjacent in $T$ to $r(T)$ for each $i\in [k]$, where we order the trees so that $r(T_1)<r(T_2)<\cdots<r(T_k)$. Next we introduce technical definitions used in our proofs.

\begin{definition}
Let $T$ be a labeled rooted tree with root $r$. The \defterm{preorder traversal permutation} $w(T)$ of $T$ is defined recursively by setting 
\[w(T)=\begin{cases}
    r(T)&\text{if $T$ is a single vertex $r(T)$}\\
    r(T)\cdot w(T_1)w(T_2)\cdots w(T_k)&\text{if $T$ has subtrees $T_1,T_2,\dots,T_k$},
\end{cases}\]
where $u\cdot v$ denote concatenation of words $u$ and $v$.

 For $F\in \F_n$, define the \defterm{preorder traversal permutation} of $F$ to be the permutation $w(F)$ on $\{0,1,\dots,n\}$ defined as follows: Suppose $F$ has trees $T_1,T_2,\dots,T_k$ with roots $r_1<r_2<\cdots<r_k$. 
 Add a new vertex 0 to $F$ and connect the roots of $T_1,T_2,\dots,T_k$ to $0$ to make a rooted tree $T(F)$
 rooted at 0.  Then define $w_F=w(T(F)).$
\end{definition}

For $i$, a vertex of a labeled rooted forest $F$, let $p(i)$ denote the parent of $i$. Fran\c{c}on \cite{francon_acyclic_1975} defines a bijection $\rho:\F_n\to \PF_n$ by
    $\rho(F)=(w_F^{-1}(p(1)),\cdots, w_F^{-1}(p(n))).$
 \Cref{fig:root-forest-bij-pf} provides an example of $\rho$, 
  where, for instance, the entries in positions $3,10,$ and $14$ of $\rho(F)$ are $2$ because the parent, $5$, of $3,10$ and $14$ in $T(F)$ is in position $2$ of $w(F)$. 
\begin{figure}
    \centering
    \begin{subfigure}[b]{0.4\textwidth}
    \centering
        \begin{tikzpicture}[yscale=-1, scale=.8]
        \node (0) at (0,0) {\textcolor{white}{0}};
        \node (1) at (2,3) {1};
        \node (2) at (-3.5,3) {2};
        \node (3) at (-3,2) {3};
        \node (4) at (-1.5,3) {4};
        \node (5) at (-1.5,1) {5};
        \node (6) at (-.5,3) {6};
        \node (7) at (0,1) {7};
        \node (8) at (1.5,1) {8};
        \node (9) at (-2.5,3) {9};
        \node (10) at (-2,2) {10};
        \node (11) at (0,2) {11};
        \node (12) at (1,2) {12};
        \node (13) at (2,2) {13};
        \node (14) at (-1,2) {14};
        \draw (5)--(3)--(2);
        \draw (3)--(9);
        \draw (5)--(10);
        \draw (5)--(14)--(4);
        \draw (14)--(6);
        \draw (7)--(11);
        \draw (8)--(13)--(1);
        \draw (8)--(12);
    \end{tikzpicture}
    \caption{Labeled rooted forest $F$}
    \label{fig:rooted-forest}
    \end{subfigure}
     \begin{subfigure}[b]{0.4\textwidth}
    \centering
        \begin{tikzpicture}[yscale=-1, scale=.8]
        \node (0) at (0,0) {1};
        \node (1) at (2,3) {15};
        \node (2) at (-3.5,3) {4};
        \node (3) at (-3,2) {3};
        \node (4) at (-1.5,3) {8};
        \node (5) at (-1.5,1) {2};
        \node (6) at (-.5,3) {9};
        \node (7) at (0,1) {10};
        \node (8) at (1.5,1) {12};
        \node (9) at (-2.5,3) {5};
        \node (10) at (-2,2) {6};
        \node (11) at (0,2) {11};
        \node (12) at (1,2) {13};
        \node (13) at (2,2) {14};
        \node (14) at (-1,2) {7};
        \draw (0)--(5)--(3)--(2);
        \draw (3)--(9);
        \draw (5)--(10);
        \draw (5)--(14)--(4);
        \draw (14)--(6);
        \draw (0)--(7)--(11);
        \draw (0)--(8)--(13)--(1);
        \draw (8)--(12);
    \end{tikzpicture}
    \caption{Preorder traversal of $T(F)$}
    \label{fig:rooted-forest-preorde-traversal}
    \end{subfigure}
  \caption[This is the caption; This is the second line]
    {\tabular[t]{@{}l@{}}$w(F)=(0,5,3,2,9,10,14,4,6,7,11,8,12,13,1)$\\ $\rho(F)=(14,3,2,7,1,7,1,1,3,2,10,12,12,2)$ \endtabular}\label{fig:root-forest-bij-pf}
\end{figure}

    \begin{definition}
         Suppose $F\in \F_n$. The pair $(i,j)$ of integers $i,j\in [n]$ is called a \defterm{parental preorder inversion} of $F$ provided $i<j$ and $w_F^{-1}(p(i))>w_F^{-1}(p(j))$. We denote the number of parental preorder inversions of $F$ by $\pinv(F)$.
    \end{definition}


     Observe that $(i,j)$ is an inversion of $\rho(F)$ if and only if $i<j$ and $w_F^{-1}(p(i))>w_F^{-1}(p(j))$. 
    Hence, $\pinv(F)=\inv(\rho(F))$ and thus we have shown:
   \begin{proposition}
   For all $n\geq 1$, 
    $    \PF_n(q)=\displaystyle\sum_{F\in \F_n}q^{\pinv(F)}$.
   \end{proposition}

The constant term of $\PF_n(q)$ is the Catalan number $C_n=\frac{1}{n+1}\binom{2n}{n}$ (OEIS \seqnum{A000108}) because on one hand it is counting the weakly increasing planar forests and on the other hand, it is counting unlabeled planar forests (see \cite{stanley2015catalan}).
 
\section{Inversions in parking functions}\label{sec:inversions-in-pfs}
In this section, we  investigate inversions for parking functions by combining the bijection $\rho:\F_n\to \PF_n$ with the classical parking function symmetric function of Haiman \cite{haiman_conjectures_1994}. We assume a basic understanding of symmetric functions and $\S_n$-representation theory e.g. \cite[Chapter 7]{stanley1999enumerative} and \cite{sagan2013symmetric}.

\subsection{On the \texorpdfstring{$\S_n$}{Sn}-module of parking functions and labeled rooted forests}
The symmetric group $\S_n$ acts on $\PF_n$ via permutation of its entries, making the module $\CC[\PF_n]$. The set $\F_n$ can also be made into an $\S_n$-module $\CC[\F_n]$ as follows. 
For $F\in \F_n$ and an index $i\in [n-1]$, define $s_i(F)$ to be the labeled rooted forest obtained by swapping the labels of $i$ and $i+1$. Then define the $\S_n$-action by setting
\begin{equation}
    (i,i+1)\cdot F=\begin{cases}
       s_i(F)&p(i)\neq p(i+1)\\
       F&p(i)=p(i+1)
    \end{cases}
\end{equation}
for each $i\in [n-1]$ and $F\in \F_n$. Then, $\rho$ extends to a map of modules $\rho:\CC[\F_n]\to \CC[\PF]_n$.
\begin{proposition}\label{isomorphism-Sn-module}
    The map $\rho:\CC[\F_n]\to \CC[\PF_n]$ is an isomorphism of $\S_n$-modules.
\end{proposition}
\begin{example}
    
    Recall that the \defterm{area} of  $\alpha=(\alpha_1,\alpha_2,\ldots,\alpha_n)\in \PF_n$ is the quantity
    $\area(\alpha)=\binom{n+1}{2}-\sum_{i=1}^n\alpha_i$.
    If $\rho(F)=\alpha$ for some $F\in \F_n$, then if we define the quantity
    $\area(F)=\binom{n+1}{2}-\sum_{i=1}^n w(p(i))$,
    we have that $\area(F)=\area(\alpha)$.  Moreover, the area statistic on $\F_n$ is $\S_n$-invariant, i.e. $\area(\pi\cdot F)=\area(F)$.  Since $\area(\pi\cdot \alpha)=\area(\alpha)$, $\CC[\mathcal{F
    }_n]$ and $\CC[\PF_n]$ are isomorphic as \textit{graded} $\S_n$-modules by \Cref{isomorphism-Sn-module}.

    Note that this not the usual statistic on $\F_n$ that is related to the area on $\PF_n$. An \defterm{inversion} of $F\in \F_n$ is a pair $(i,j)$ with $1\leq i<j\leq n$ such that $j$ is an ancestor of $i$. Let $\inv(F)$ denote the number of inversions of $F$. 
    Kreweras \cite{kreweras1980famille} showed that $\inv$ on $\F_n$ is equidistributed with $\area$ on $\PF_n$. Hence, our results show that $\inv$ on $\F_n$ is equidistributed with $\area$ on $\F_n$. 
    We leave it to the reader to construct a direct bijection. 
    \end{example}

Let $\PF_n(\mathbf{x})$ be the Frobenius characteristic of $\CC[\PF_n]$, or equivalently (by \Cref{isomorphism-Sn-module}) of $\CC[\mathcal{F}_n]$. This is called the \defterm{parking function symmetric function} and was first introduced by Haiman \cite{haiman_conjectures_1994}. 
Define the \defterm{parental content} of $F\in \F_n$ to be the vector $\con(F)=(c_1,c_2,\dots, c_{n})$, where $c_i$ is the number of children of $w_F(i)$. It is straightforward to verify that $\con(F)=\con(\rho(F))$. Let $\F_n^\uparrow$ be the set of labeled rooted forests with no parental preorder inversions.
Then, we have 
\begin{equation}
    \PF_n(\mathbf{x})=\sum_{\alpha\in \PF_n^\uparrow}h_{\con(\alpha)}=\sum_{F\in \F_n^\uparrow}h_{\con(F)},
\end{equation}
where $h_{\con}=h_{c_1}h_{c_2}\cdots h_{\ell(c)} $ is the complete homogeneous symmetric function. 
Haiman provides a generating function formula for $\PF_n(\mathbf{x})$.

\begin{theorem}[{\cite{haiman_conjectures_1994}}]\label{thm:lambet-w-symmetric}
    We have
    $\PF(\mathbf{x},z):=\sum_{n\geq 0}\PF_n(\mathbf{x})z^{n+1}=(zE(-z))^{\langle -1\rangle }$.
\end{theorem}
We provide a combinatorial proof of \Cref{thm:lambet-w-symmetric} via the map $\rho$.
\begin{proof}
    Since $H(z)E(-z)=1$, the claim is equivalent to showing that
    \begin{equation}\label{eq:symmetric-function-recurrsion}\PF(\mathbf{x},z)=H(z\PF(\mathbf{x},z))=\sum_{n\geq 0}z^n \sum_{k=0}^n h_k \sum_{c\in \Comp(n,k)}\prod_{i=1}^k \PF_{c_{i-1}}(\mathbf{x}),
    \end{equation}
    where $\Comp(n,k)$ is the set of compositions of $n$ with $k$ parts.  In other words,
    \begin{equation}
        \PF_n(\mathbf{x})=\sum_{k=0}^n h_k \sum_{c\in \Comp(n,k)}\prod_{i=1}^k \PF_{c_{i-1}}(\mathbf{x}).
    \end{equation}
    This is easiest to see in labeled rooted forests: we can create an increasing labeled rooted forest $F\in \mathcal{F}_n$ by first deciding that there are $k$ trees (hence contributing $h_k$), deciding how large the $k$ trees are (i.e.\ choosing a composition $c$ of $n$ with $k$ parts), and then creating those $k$ trees (with each contributing  $\PF_{c_i-1}(\mathbf{x})).$
\end{proof}


\subsection{Generating function formula for inversions on parking functions}
The next ingredient in understanding inversions for parking functions is a general statement about words. For this, first recall that the \defterm{stable principal specialization} $\ps(f)$ of a symmetric function $f=f(x_1,x_2,\dots)$ is obtained by setting $x_i$ to $q^{i-1}$ for all $i\in \P$.
Next, for all nonnegative integers $n$, define $(q;q)_n:=\prod_{i=1}^n(1-q^i)$.
We need the following general statement about words. 
\begin{proposition}\label{lem:character-of-words-inversions}
    Let $W\subseteq \P^n$ be a set of $\S_n$-invariant words of positive integers. Let $F(\mathbf{x})$ be the Frobenius character of the $\S_n$-module $\CC[W]$. Then, 
    \[(q;q)_n\ps(F(\mathbf{x}))=\sum_{w\in W}q^{\inv(w)}.\]
\end{proposition}
From this, we apply stable principal specialization to $\PF(\mathbf{x},z)$ and set $z=(1-q)z$ to obtain a generating function for the inversion enumerator for parking functions.
\begin{corollary} \label{thm:PF-is-q-LambertW-Inverse} We have 
$\sum_{n\geq 0}\PF_n(q)\frac{z^{n+1}}{[n]_{q}!}=(z\Exp_{q}(-z))^{\langle -1\rangle }$.
\end{corollary}
\begin{proof}
We  provide a more elementary explanation of the result. First, let  $\WComp(n,k)$ be the set of weak compositions of $n$ with $k$ parts. The corollary is equivalent to \begin{equation}\label{eq:PF-inversion-decomposition}\PF_n(q)=\sum_{k=0}^n\sum_{c\in \WComp(n-k,k)}\qbinom{n}{k}_q\qbinom{n-k}{c_1,c_2,\dots, c_k}_q  \prod_{i=1}^k \PF_{c_i}(q).\end{equation}
    Now we can prove the equivalent statement of \eqref{eq:PF-inversion-decomposition} for labeled rooted forests. Suppose a labeled rooted forest $F$ has roots $R=\{r_1<r_2<\cdots<r_k\}$ and each tree is on vertex set $r_i\cup B_{i}$.
    Then, we can see that parental preorder inversions $(i,j)$ of $F$ come from one of three places: (1) $i\in B_k$ and $j\in R$; (2) $i\in B_k$, $j\in B_\ell$ and $k>\ell$; or (3) $i,j$ are both in the same $B_k$.
    These correspond to the 3 factors in \Cref{eq:PF-inversion-decomposition}, proving the claim.\end{proof}


\subsection{Total number of inversions}
In this section, we provide another fundamental result on $\S_n$-invariant sets of words connecting the total number of inversions on the set to the total number of descents. The parking function motivation comes from Schumacher's \cite[Theorem 10]{bib:DescentsInPF} establishing
\begin{equation}\label{eq: Schumacker descents}
    \sum_{\alpha\in \PF_n} \des(\alpha)=\binom{n}{2}(n+1)^{n-2}.
\end{equation}
We derive a similar result for inversions through probabilistic techniques. Let $\Des(w)$ denote the set of descents of $w\in \P^n$. For $w\in \P^n$ and integers $1\leq i<j\leq n$, define
\[\inv_{(i,j)}(w)=\begin{cases}
    1&(i,j)\in \Inv(w)\\
    0&(i,j)\not\in \Inv(w)
\end{cases}\qquad \mbox{and }\qquad\des_i(w)=\begin{cases}
    1&i\in \Des(w)\\
    0&i\not\in \Des(w).
\end{cases}\]
Hence, 
$\sum_{1\leq i<j\leq n}\inv_{i,j}(w)=\inv(w)$ and $\sum_{i=1}^{n-1}\des_{i}(w)=\des(w)$ for all $w \in \P^n$. 
We can think of the functions $\inv_{i,j}$, $\inv$, $\des_i,$ and $\des$ as \textit{random variables} on $\P^n$. Hence, we can rephrase \eqref{eq: Schumacker descents} as a statement about the \textit{expectation} $\E_{\PF_n}\left[\des\right]$ of $\des$ as a random variable on $\PF_n$.
Accordingly, we want to compute the expectation $\E_{\PF_n}\left[\inv\right]$. We prove a general theory on words to do so.



\begin{theorem}\label{thm:inv-and-des-sums-for-words}
    Let $W\subset \P^{n}$ be an $\S_n$-invariant set of words of positive integers. Then we have
    \begin{enumerate}[label=(\alph*)]
        \item $\E_{W}\left[\inv\right]=\binom{n}{2}\mathbb{P}_{W}\left(\des_1=1\right)$,
        \item $\E_{W}\left[\des\right]=(n-1)\bP_{W}\left(\des_1=1\right)$, and
        \item $\E_{W}\left[\inv\right]=\frac{n}{2}\E_{W}\left[\des\right]$.
    \end{enumerate}
\end{theorem}
\noindent
Note that the last part of \Cref{thm:inv-and-des-sums-for-words} is equivalent to  $\sum_{w\in W}\inv(w)=\frac{n}{2}\sum_{w\in W}\des(w)$.
\begin{proof}[Sketch of (a)]
For a fixed pair $i,j$ with $1\leq i<j\leq n$, one can show using the $\S_n$-invariance of $W$ and the 2-transitivity of $\S_n$ that
\begin{equation}
    \bP_W\left( 
    \inv_{(i,j)}(\alpha) =1 \right)=\bP_W\left(\inv_{(1,2)}(\alpha)=1\right)=\bP_W\left(\des_{1}(\alpha)=1\right)
\end{equation}
and hence the claim follows by linearity of expectation. \qedhere
\end{proof}
It is unclear what the representation theoretic significance of \Cref{thm:inv-and-des-sums-for-words} is. The enumerative significance on the other hand is as follows.
\begin{corollary}\label{thm:total-number-of-inversions-in-parking-functions}
    For $n\geq 1$, the total number of inversions across all parking functions is
    \[\sum_{\alpha\in \PF_n}\inv(\alpha)=\frac{n(n+1)^{n-2}}{2}\binom{n}{2}.\]
\end{corollary}

The only property of $\S_n$ used in \Cref{thm:inv-and-des-sums-for-words} is that it acts 2-transitively on $[n]$.  Thus we have the following generalization.
    \begin{proposition}\label{prop:2-transitive-G-invariant-words}
        Let $G$ be a group that acts $2$-transitively on $[n]$ and let $W\subset \P^{n}$ be a $G$-invariant set of words of positive integers. Then the conclusions of \Cref{thm:inv-and-des-sums-for-words} hold.
    \end{proposition}
    \begin{example}
    Let $\S_n^+$ denote the \textit{alternating subgroup} of $\S_n$. Since $\S_n^+$ is $2$-transitive for $n\geq 4$, one can use \Cref{thm:inv-and-des-sums-for-words} and the work of D{\'e}sarm{\'e}nien and Foata \cite{desarmenien1992signed} and Fulman et al. \cite[Equation~(7)]{fulman2021jointdistributiondescentssigns})  to show that 
      \begin{equation}
         \sum_{\pi\in \S^+_{n}}\inv(\pi) = \frac{n!n(n-1)}{8}.
    \end{equation}
\end{example}

\section{Inversions in unit interval parking functions}\label{sec:inversions-in-upfs}
\subsection{A connection to Cayley permutations and descents}\label{subsec-descents-in-UPF}

We begin by providing a connection between Cayley permutations and unit interval parking functions.
A \emph{Cayley permutation} of length $n$ is a word $w\in \P^n$ such that if $i$~appears in $w$, then each $j\in [i]$ also appear in $w$. 
We denote the set of all Cayley permutations of length $n$ by $\mathfrak{C}_n$. 
Cayley permutations appear in the literature under various names, including \emph{Fubini words}, \textit{packed words}, \textit{surjective words}, and \textit{initial words} \cite{Marberg_2021}. 
 We note that Cayley permutations have also been viewed as ordered set partitions, and descent generating functions for Cayley permutations have been studied in~\cite{caylerian}. 
In forthcoming work, we give a bijection between Cayley permutations and unit interval parking functions
through an extension of \cite[Theorem 2.9]{bradt2024unit}. Namely, we define a bijection $\psi:\UPF_n\to \C_n$ such that $\Inv(\psi(\alpha))=\Inv(\alpha)$ for all $\alpha\in \UPF_n$.
This allows us to compute the total number of descents across all unit interval parking functions, thus obtaining an analogous result of Schumacher 
%for all parking functions 
\cite[Theorem 10]{bib:DescentsInPF}. 




\begin{theorem}
    For $n\geq 1$, we have 
    \[\sum_{\alpha\in \UPF_n}\des(\alpha)=\sum_{\alpha\in \C_n}\des(\alpha)=\frac{n-1}{2}(\Fub_n-\Fub_{n-1}).\]
\end{theorem}

Since $\C_n$ is an $\S_n$-invariant set, we can apply \Cref{thm:inv-and-des-sums-for-words} to count the total number of inversions.

\begin{corollary}\label{cor:total-num-inversions-in-UPF}
    For $n\geq 1$, we have
    \[\sum_{\alpha\in \UPF_n}\inv(\alpha)=\sum_{\alpha\in \C_n}\inv(\alpha)=\frac{n(n-1)}{4}(\Fub_n-\Fub_{n-1}).\]
\end{corollary}


\subsection{Inversion generating function for unit interval parking functions}

For $\pi\in \S_n$, let $\asc(\pi)$ denote the number of \defterm{ascents} of $\pi$ i.e. the number of positions $i\in [n-1]$ such that $\pi(i)<\pi(i+1)$. Define for each $n\in \P$, the polynomials

\begin{equation}
        A_n^{\inv,\asc}(q,t)=\sum_{\pi \in \S_n} q^{\inv(\pi)}t^{\asc(\pi)}\qquad \mbox{and}\qquad
        \UPF_n(q)= \sum_{\alpha \in \UPF_n} q^{\inv(\alpha)}.
\end{equation}
We provide two methods for obtaining a $q$-exponential generating function for $\UPF_n(q)$:
(1) showing that $\UPF_n(q)$ is a specialization of $A_n^{\inv,\asc}(q,t)$ and applying a theorem of Stanley \cite{stanley1976binomial}; and (2) a direct computation. We start with the former.
\begin{proposition}\label{Theorem: inv from Sn}
     For $n\geq 1$,  $A_n^{\inv,\asc}(q,2)=\UPF_n(q).$
\end{proposition}


This follows from the following lemma. 
\begin{lemma}\label{lem: inv-2-asc}
    For each $\pi \in \S_n$, there are $2^{\asc(\pi)}$ unit interval parking functions $\alpha$ of length $n$ with outcome permutation $\pi(\alpha)=\pi$. Moreover, $\inv(\pi)=\inv(\alpha)$ if $\pi=\pi(\alpha)$ for each $\alpha\in \UPF_n$.
\end{lemma}
\begin{proof}[Proof of \Cref{Theorem: inv from Sn}]Applying \Cref{lem: inv-2-asc} consecutively, we have
\[A_n^{\inv,\asc}(q,2)
=\sum_{\pi\in \S_n}q^{\inv(\pi)}2^{\asc(\pi)}
=\sum_{\pi\in \S_n}q^{\inv(\pi)}\sum_{\substack{\pi\in\UPF_n\\\pi(\alpha)=\pi}}1
=\sum_{\alpha\in \UPF_n}q^{\inv(\alpha)}.\qedhere\]
\end{proof}





Stanley \cite[Corollary 3.6]{stanley1976binomial} proved that $A_n^{\inv,\asc}(q,t)$ satisfies
\begin{equation}\label{eq:inv-asc-gen-function}
    1+\sum_{n\geq 1}A_{n}^{\inv,\asc}(q,t)\frac{z^n}{[n]_q!}=\frac{1-t}{1-t\Exp_q(z(1-t))}.
\end{equation}
By combining \Cref{Theorem: inv from Sn} and \eqref{eq:inv-asc-gen-function}, the $q$-exponential generating function formula for unit interval parking functions is
\begin{equation}\label{eq:upf-inv-gen-func}
    \sum_{n\geq 0} \UPF_{n}(q)\frac{z^n}{[n]_q!}=\frac{1}{2-\exp_{q}(z)}.
\end{equation}
This result can be found directly without relying on \Cref{eq:inv-asc-gen-function}. Indeed, \cite[Theorem 2.9]{bradt2024unit} can be generalized to show that
\begin{equation}\UPF_n(q)=\sum_{c\in \Comp(n)} \qbinom{n}{c_1,c_2,\dots,c_{\ell(c)}}_q.\end{equation}
Then, \Cref{eq:upf-inv-gen-func} follows from elementary arguments.
To generalize to a result on symmetric functions, we require an $\S_n$-action on $\UPF_n$. Suppose $\alpha=(\alpha_1,\alpha_2,\dots,\alpha_n)\in \UPF_n$ has \textit{block structure} $\pi_1\mid\pi_2\mid \cdots\mid \pi_k$, which is an ordered set partition associated to $\alpha$ as in \cite[Definition 2.7]{bradt2024unit}. Then for $i\in [n-1]$, define $(i,i+1)\cdot \alpha=\alpha$ if $\alpha_i,\alpha_{i+1}$ are in the same $\pi_j$ and $(\alpha_1,\dots,\alpha_{i+1},\alpha_i,\dots,\alpha_n)$ if $\alpha_i,\alpha_{i+1}$ are in different $\pi_j$.
One can check that this defines an $\S_n$-action on $\UPF_n$ whose orbits are uniquely determined by a choice of $c\in \Comp(n)$.  Thus, $\UPF_n(\mathbf{x})=\sum_{c\in \Comp(n)}h_c$.
\begin{theorem}\label{thm:UPF-sym-generating-function}
    We have
    $\sum_{n\geq 0}\UPF_n(\mathbf{x})z^n=\frac{1}{2-H(z)}$.
\end{theorem}
  \begin{proof}The result follows by writing
  \[\frac{1}{2-H(z)}=\sum_{k\geq 0} \frac{1}
    {2^{k+1}}\lp \sum_{ n\geq 0}h_nz^n\rp ^{k}=\sum_{n\geq 0}z^n\sum_{c\in \Comp(n)}h_c\sum_{j\geq 0}\binom{\ell(c)+j}{j}\frac{1}{2^{\ell(c)+j+1}}
    \]
    and noting that $\sum_{j\geq 0}\binom{\ell(c)+j}{j}\frac{1}{2^{\ell(c)+j+1}}=1$.
    \end{proof}

While setting $t=2$ makes sense for polynomials, it is not clear what the representation theoretic meaning is. In particular, we do not know how to derive \Cref{thm:UPF-sym-generating-function} from a known $\S_n$-representation on $\S_n.$ 




\section{Future work}\label{sec:future-work}
We  conclude with some directions for further study.
One can study inversions of parking functions for other variations and special subsets of parking functions, including
$k$-Naples parking functions, vacillating parking functions, 
and parking sequences and assortments. For a summary of some of these sets, refer to \cite{bib:Carlson+}. 
Thus, the program of this extended abstract may be applied to them.
\begin{problem}
    For other families of parking functions, find nice expressions for their inversion generating functions. Furthermore, determine if there is a natural $\S_n$-action on the family and determine its Frobenius character.
\end{problem} 
Inversions are just one of many word statistics to consider on parking functions. Hence, one research agenda is as follows:
\begin{problem}
    Investigate generating functions for other word statistics on parking functions and their subsets and generalizations. 
\end{problem} 
Finally, we have seen that some $q$-analogues can be explained via representation theoretic formulas. We would like fully representation theoretic explanations of all of the results in this extended abstract. In particular, we pose the following.
\begin{problem}
    Determine the representation theoretic interpretation of \Cref{thm:inv-and-des-sums-for-words} and of the equality $A_n^{\inv,\asc}(q,2)=\UPF_n(q)$.
\end{problem}

\acknowledgements{
The genesis for this project was the 2024 Graduate Research Workshop in Combinatorics, hosted by University of Wisconsin, Milwaukee and funded by the NSF (Grant No. DMS~--~1953445).
We thank the developers of 
SageMath~\cite{sage} and CoCalc~\cite{SMC}, which were useful in this research.
We also thank Steve Butler and Mei Yin, for their comments and guidance at the start of this project, and Kimberly J. Harry, for initial contributions. Special thanks also to Ari Cruz, Jeremy L. Martin, Matt McClinton, and Keith Sullivan.}

% \bibliographystyle{plain}
% \bibliography{Bibliography.bib}
\printbibliography
\end{document}