Inversions in parking functions
Kyle Celano, Jennifer Elder, Kimberly P. Hadaway, Pamela E. Harris, Amanda Priestley, Gabe Udell · 2025
Read Inversions in parking functions by Kyle Celano, Jennifer Elder, Kimberly P. Hadaway, Pamela E. Harris, Amanda Priestley, Gabe Udell (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-11587.txt.
Introduction
Celano and co-authors count flips in car-park lists, a known math toy. A car-park list gives spots picked by cars in a set row. A flip counts a pair whose pick order runs the wrong way. The team builds a q-count sum for flips by two routes. One route runs through shape-sum tools for tied counts. One route pairs each list with a tagged tree in a direct swap.
Unit-span lists get like sums by the same pair of routes. A chance-based read then gives the full flip count for all lists. That read also gives sums for more list traits at once. The traits span word sets held shut when their parts get reshuffled. Two roads to one sum cross-check each path.
Catalog record
| CREATOR | Kyle Celano, Jennifer Elder, Kimberly P. Hadaway, Pamela E. Harris, Amanda Priestley, Gabe Udell |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 88 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-11587
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Inversions in parking functions Kyle Celano, Jennifer Elder, Kimberly P. Hadaway, Pamela E. Harris, Amanda Priestley, Gabe Udell Abstract . In this paper, we obtain a q q -exponential generating function for inversions on parking functions via symmetric function theory and also through a direct bijection to rooted labeled forests. We then apply these techniques to unit interval parking functions to give analogous results. We conclude by introducing a probabilistic approach through which we obtain formulas for the total number of inversions and several other statistics across all parking functions and other sets of words closed under rearrangement. 1. Introduction Throughout, let \mathbb{N}=\{1,2,\dots\} , and if n\in\mathbb{N} , then [n]=\{1,2,\ldots,n\} . Also, let \mathfrak{S}_{n} denote the set of permutations of [n] . Konheim and Weiss [ 30 ] 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 occupied, then the car continues driving and parks in the next available spot, if any exists. We encode the information of the preferred spots as a positive integer-valued 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 parking function if all cars are able to park using the aforementioned parking rule. The outcome permutation of \alpha , denoted \pi(\alpha) , is defined by setting \pi(\alpha)(i)=j if car j parks in spot i for each i\in[n] . We let \PF_{n} be the set of all parking functions of length n . Konheim and Weiss establish that the number of parking functions of length n is (n+1)^{n-1} , see [ 30 , Lemma 1] . A second proof of this count was given by Pollak by parking the cars on a circle with one new parking spot, see [ 16 ] . Introduced by Hadaway [ 25 ] , a 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] . In other words, these are parking functions in which, for all i\in[n] , car i parks either in its preference a_{i} or in the spot after its preference a_{i}+1 . Let \UPF_{n} denote the set of unit interval parking functions of length n . Hadaway [ 25 ] proves that |\UPF_{n}|=\Fub_{n} , which is the n^{th} Fubini number and counts the number of ordered set partitions of [n] [ 29 , 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 [ 9 , 13 ] . We are interested in the study of inversions of parking functions and unit interval parking functions. Recall that for a word w\in\mathbb{N}^{n} , an 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)| . Treating parking functions as words, for each n\in\mathbb{N} , we 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 . The inversion generating function \PF_{n}(q) appeared incidentally in [ 37 , Section 8] in their study of remixed Eulerian numbers and as we explain in Section 3 , it appears as a specialization of certain symmetric functions studied in [ 28 ] . Beyond this, little has been said about inversions in parking functions directly. 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} . With these definitions, using combinatorial techniques, we derive the following generating functions. Theorem 1.1 . 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) . Theorem 1.1 gives q -analogues of classical results of Konheim and Weiss [ 30 ] and Cayley [ 7 ] , respectively: (1) \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}}, where the latter result follows from the bijection between unit interval parking functions and Cayley permutations (see [ 25 ] ). We also show that the equations in ( 1 ) follow from a more general theory of symmetric functions. The main result is as follows. Theorem 1.2 . There are \mathfrak{S}_{n} -modules \mathbb{C}[\PF_{n}] and \mathbb{C}[\UPF_{n}] such that (2) \sum_{n\geq 0}\ch\mathbb{C}[\PF_{n}]z^{n+1}=(zE(-z))^{\langle-1\rangle}\quad\mbox{and }\quad\sum_{n\geq 0}\ch\mathbb{C}[\UPF_{n}]z^{n}=\frac{1}{2-H(z)}\ , where \ch denotes the Frobenius characteristic map from \mathfrak{S}_{n} -modules to symmetric functions of degree n . Here, E(z)=\sum_{n\geq 0}e_{n}z^{n} and H(z)=\sum_{n\geq 0}h_{n}z^{n} are generating functions for the elementary symmetric functions and the complete homogeneous symmetric functions, respectively. The Frobenius image in ( 2 ) for parking functions was computed algebraically by Haiman [ 28 ] . In Section 3 , we provide a new combinatorial proof using labeled rooted forests, which we construct in Section 2 . Then, using a modified version of stable principal specialization, Theorem 1.2 gives a second proof of Theorem 1.1 . For unit interval parking functions, we provide two ways of computing its Frobenius characteristic in Section 4 : one by specializing a formula of Stanley and the other by more elementary arguments. \begin{array}[]{|c|c||c|c|c|}\hline\cr&\mathfrak{S}_{n}&\PF_{n}&\mbox{ Theorem }&\mbox{ OEIS/Sequence }\\ \hline\cr\inv&\frac{n!n(n-1)}{4}&\frac{n(n+1)^{n-2}}{2}\binom{n}{2}&\mbox{ \lx@cref{creftypecap\lx@tilde refnum}{thm:total-number-of-inversions-in-parking-functions}}&\hrefhttp://oeis.org/A386011^{\text{\textdagger}}\\ \hline\cr\des&\frac{n!(n-1)}{2}&\binom{n}{2}(n+1)^{n-2}&\text{\cite[cite]{[\@@bibref{}{bib:DescentsInPF}{}{}, Theorem 10]}}&\hrefhttp://oeis.org/A053507\\ \hline\cr\des_{1}&\frac{n!}{2}&\frac{n}{2}(n+1)^{n-2}&\text{\cite[cite]{[\@@bibref{}{bib:DescentsInPF}{}{}, Theorem 10]}{\color[rgb]{1,0,0}*}}&\hrefhttp://oeis.org/A386015^{\text{\textdagger}}\\ \hline\cr\tie&0&(n-1)(n+1)^{n-2}&\mbox{ \lx@cref{creftypecap\lx@tilde refnum}{cor:ties in parking functions}}&\hrefhttp://oeis.org/A071720\\ \hline\cr\tie_{1}&0&(n+1)^{n-2}&\mbox{\lx@cref{creftypecap\lx@tilde refnum}{prop:parktie}}&\hrefhttp://oeis.org/A007830\\ \hline\cr\sdes&(n-1)(n-1)!&(n-1)(n+1)^{n-2}&\mbox{ \lx@cref{creftypecap\lx@tilde refnum}{prop:sdes_sinv_bdes_binvPF}}&\hrefhttp://oeis.org/A071720\\ \hline\cr\sdes_{1}&(n-1)!&(n+1)^{n-2}&\mbox{ Equation}\eqref{eq:exp-of-1-sdes-pf}{\color[rgb]{1,0,0}*}&\hrefhttp://oeis.org/A007830\\ \hline\cr\sinv&\frac{n!(n-1)}{2}&\binom{n}{2}(n+1)^{n-2}&\mbox{ \lx@cref{creftypecap\lx@tilde refnum}{prop:sdes_sinv_bdes_binvPF}}&\hrefhttp://oeis.org/A053507\\ \hline\cr\bdes&\binom{n-1}{2}(n-1)!&\binom{n-1}{2}(n+1)^{n-2}&\mbox{ \lx@cref{creftypecap\lx@tilde refnum}{prop:sdes_sinv_bdes_binvPF}}&\hrefhttp://oeis.org/A386860^{\text{\textdagger}}\\ \hline\cr\bdes_{1}&\frac{n-2}{2}(n-1)!&\frac{n-2}{2}(n+1)^{n-2}&\mbox{ \lx@cref{creftypecap\lx@tilde refnum}{prop:sdes_sinv_bdes_binvPF}}{\color[rgb]{1,0,0}*}&\hrefhttp://oeis.org/A387047^{\text{\textdagger}}\\ \hline\cr\binv&\binom{n-1}{2}\frac{n!}{2}&\frac{n}{4}(n-1)(n-2)(n+1)^{n-2}&\mbox{\lx@cref{creftypecap\lx@tilde refnum}{prop:sdes_sinv_bdes_binvPF} }&\hrefhttp://oeis.org/A386861^{\text{\textdagger}}\\ \hline\cr\end{array} Table 1 . Totals of certain statistics over \mathfrak{S}_{n} and \PF_{n} . The references to theorems and OEIS entries given refer to the results for parking functions in particular. The analogous results for the symmetric group are classical (e.g. [ 57 , 59 ] ), except those involving sdes and those listed in the rows below it, which are given by Proposition 5.17 . The references marked with ( * ), are the result of applying Theorem 5.2 to the statistics indicated. OEIS entries that were added as a result of this project are marked with ( † ). For any OEIS entry which is unmarked, except those for descents, our project contributes a new combinatorial perspective in terms of parking functions. The study of the inversion statistic on \PF_{n} and \mathfrak{S}_{n} has an important commonality: both set of words are \mathfrak{S}_{n} -invariant. Hence, we focus studying the average behavior of statistics in general on \mathfrak{S}_{n} -invariant sets of words. With this approach in mind, in Section 5 , we show that for any \mathfrak{S}_{n} -invariant subset W\subset\mathbb{N}^{n} of positive integers, we have a curious equality: (3) \sum_{w\in W}\inv(w)=\frac{n}{2}\sum_{w\in W}\des(w), where \des(w) is the number of descents of w i.e., the number of positions i\in[n-1] such that w_{i}>w_{i+1} . The intuition behind ( 3 ) involves noting that the total number of inversions can be written as the sum over all i<j of the number of words with (i,j) as an inversion. The key 1 1 1 We credit Eyob Tsegaye for inspiring this approach. is to use the \mathfrak{S}_{n} -action to move the positions (i,j) to the positions (1,2) . Then, the probability that (i,j) is an inversion is the same as the probability that (1,2) is an