On statistics of prime parking functions,
Łukasiewicz paths, and quasisymmetric functions
January 28, 2026
Abstract
We recall that a parking function of length \(n+1\) is said to be prime if removing any instance of 1 yields a parking function of length \(n\). In this article, we study prime parking functions from multiple lenses. We derive an explicit formula for the average value of the total displacement of prime parking functions. We present a formula for the displacement-enumerator of prime parking functions that involves a sum over Łukasiewicz paths. We describe the one-to-one correspondence between parking functions and labeled Łukasiewicz paths via Dyck paths. We introduce the concept of \(\ell\)-forward differences and use this as a vehicle for examining ties, ascents, and descents in prime parking functions. We establish a link between Schur functions corresponding to the partition \((i,1^{n-i})\) and fundamental quasisymmetric functions indexed by prime parking function tie sets of size \(n-i.\)
1 Introduction↩︎
Classical parking functions were first introduced by Konheim and Weiss [1] in the study of the linear probes of random hashing functions. The original conceptual setting was a linear parking lot with \(n\) cars, labeled \(1\) through \(n\), each with a stated parking preference. In their labeled order, each car attempts to park in its preferred spot. If the car finds its preferred spot occupied, it moves to the next available spot. Formally, a (classical) parking function of length \(n\) is a sequence \(\pi=(\pi_1,\pi_2,\dots, \pi_n)\) of positive integers such that if \(\lambda_1\leq\lambda_2\leq \cdots\leq \lambda_n\) is the increasing rearrangement of \(\pi_1,\pi_2,\dots,\pi_n\), then \(\lambda_i\leq i\) for \(1\leq i\leq n\). We write \(\mathop{\mathrm{PF}}_n\) for the set of classical parking functions of length \(n\). It is well-known that \(\vert \mathop{\mathrm{PF}}_n \vert=(n+1)^{n-1}\). We refer to Yan [2] for a comprehensive survey.
An important subset of parking functions are prime parking functions. A parking function \(\pi\) is said to be a prime parking function of length \(n+1\), if removing a 1 from the tuple \(\pi\) results in a parking function of length \(n\). For example, \((3,2,1,1)\) is a prime parking function of length 4, since removing either instance of the value 1 results in the preference list \((3,2,1)\) which is a parking function of length 3. Notice that a prime parking function of length \(n+1\) never has an entry \(n+1\) because then removing a 1 would not yield a parking function of length \(n\). We denote the set of prime parking functions of length \(n+1\) by \(\mathop{\mathrm{PPF}}_{n+1}\). It is well known that \(\vert \mathop{\mathrm{PPF}}_{n+1} \vert=n^{n}\); for a proof we point the reader to the work of Kalikow [3].
In this article, we study (prime) parking functions from multiple lenses. We start with the average displacement of prime parking functions (2). The displacement of a parking function records the total number of additional spaces cars must travel beyond their preferred spots in order to park. Before deriving an explicit formula for the average displacement of prime parking functions, we first compute the expected value of a single coordinate, \(\pi_1\). Because the set of (prime) parking functions is closed under permutations of the cars, all coordinates have the same marginal distribution. In particular, for \(\pi=(\pi_1,\pi_2,\ldots, \pi_n)\) chosen uniformly at random from \(\mathop{\mathrm{PPF}}_{n+1}\), we have \[\mathbb{E}[\pi_i | \pi \in \mathop{\mathrm{PPF}}_{n+1}]= \mathbb{E}[\pi_1 | \pi \in \mathop{\mathrm{PPF}}_{n+1}]\] for all \(i\). Thus, it suffices to compute \(\mathbb{E}[\pi_1 | \pi \in \mathop{\mathrm{PPF}}_{n+1}]\). We prove the following exact and asymptotic results.
theoremexpectedvalueresult The expected value of \(\pi_1\) for prime parking functions \(\pi\in \mathop{\mathrm{PPF}}_{n+1}\) is \[\mathbb{E}[\pi_1 | \pi \in \mathop{\mathrm{PPF}}_{n+1}]=\frac{1}{2}\left(n+3-\frac{n!}{n^n}\sum_{s=0}^n\frac{n^{s}}{s!}\right).\]
corollaryexpectedvalueresultasymp The expected value of \(\pi_1\) for prime parking functions \(\pi\in \mathop{\mathrm{PPF}}_{n+1}\) is \[\mathbb{E}[\pi_1 | \pi \in \mathop{\mathrm{PPF}}_{n+1}]=\frac{1}{2} \left (n-\sqrt{\frac{\pi n}{2}} + \frac{7}{3} + o(1) \right ).\]
Using [thm:expected32value32of32pi1] and [cr:expected32value32of32pi1], we obtain the expected value for the displacement of prime parking functions.
corollaryexpecteddisplacementforPPFs The expected value of the displacement of prime parking functions is \[\mathbb{E}[\text{dis}(\pi)|\pi\in\mathop{\mathrm{PPF}}_{n+1}]=\frac{\sqrt{2\pi}}{4}n^{3/2}-\frac{n}{6}+o(n).\]
We also study the displacement-enumerator of prime parking functions. Just as classical parking functions may be encoded by Łukasiewicz paths, prime parking functions may also be encoded by Łukasiewicz paths, except that the path stays strictly above the \(x\)-axis other than at its start and end points \((0, 0)\) and \((n, 0)\). This alternative interpretation transforms the total displacement of a parking function into an area enclosed by the associated Łukasiewicz path and the \(x\)-axis. For more on these bijections, see the work of Selig and Zhu [4] and references therein. We relate the displacement-enumerator of prime parking functions to weights of Łukasiewicz paths, building upon earlier work for classical parking functions in Elvey-Price [5]. Our main result is as follows.
theoremPPFDisplacementEnumerator The displacement-enumerator of prime parking functions is \[\mathop{\mathrm{PPF}}_{n+1}(q)=(n+1)! ~~q^n \sum_{\substack{\text{all possible}\\\text{\L ukasiewicz~paths with} \\ \text{height sequence } \\ (h_0, h_1, \dots, h_n)}} \frac{1}{h_1-h_0+2} ~~\prod_{j=1}^{n} \frac{q^{h_{j}}}{(h_{j}-h_{j-1}+1)!},\] where \(\frac{q^{h_{j}}}{(h_{j}-h_{j-1}+1)!}\) denotes the weight of a step \(h_{j-1} \rightarrow h_{j}\) with \(h_{j} \geq h_{j-1}-1\) in the Łukasiewicz path.
We then apply the circular rotation construction for prime parking functions due to Kalikow [3] to study the generating function for ties, ascents, and descents in prime parking functions. We introduce \(\ell\)-forward differences \(\Delta_\ell f(\pi)\) in prime parking functions. This concept generalizes ties, which are \(0\)-forward differences, and is also related to ascents and descents. Our main result is the following.
propositionPPFRotationCount Take any integer \(\ell \in [0, n-2]\). Then we have \[\sum_{\pi \in \mathop{\mathrm{PPF}}_n} q^{ \Delta_{\ell} f(\pi)}=(q+n-2)^{n-1}.\]
Lastly, we bring quasisymmetric functions \(F_{n, S}\) and Schur functions \(s_\lambda\) into the mix and further demonstrate the intriguing characteristics displayed by \(\ell\)-forward differences in parking functions. The following theorem shows the interconnection between parking functions and other topics in combinatorics.
theoremPPFQuasiSymmetric Let \(m \neq \ell\). Then we have \[\sum_{\pi \in \mathop{\mathrm{PPF}}_n} q^{ \Delta_{\ell} f(\pi)} F_{n, S_{\Delta_{\ell}}(\pi)}=\sum_{i=1}^n q^{n-i}(n-2)^{i-1} s_{(i,1^{n-i})},\] and \[\sum_{\pi \in \mathop{\mathrm{PPF}}_n} q^{ \Delta_{\ell} f(\pi)} F_{n, S_{\Delta_{m}}(\pi)}= \sum_{i=1}^n (q+n-3)^{i-1} s_{(i,1^{n-i})}.\]
This article is organized as follows. In 2, we prove our results related to the expected value of \(\pi_1\) for a prime parking function and obtain the average displacement in prime parking functions. In 3, we give the necessary background on Łukasiewicz paths and express the displacement-enumerator of prime parking functions as a sum over Łukasiewicz paths, with weights determined by step heights. In 4, we introduce a labeled version of Łukasiewicz paths and describe the ties, ascents, and descents in parking functions directly from the labeled paths. In 5, we present \(\ell\)-forward differences as another vehicle for examining ties, ascents, and descents in prime parking functions. We find the generating function for the number of \(\ell\)-forward differences, and use this function to derive that the expected number of ties in a prime parking function is \(1\), while the expected number of descents and the expected number of ascents are both equal to \((n-2)/2\). In 6, we establish a link between Schur functions corresponding to the partition \((i,1^{n-i})\) and fundamental quasisymmetric functions indexed by prime parking function tie sets of size \(n-i.\) We conclude with some directions for future investigation.
2 Expected value results↩︎
A principle that plays an important role in our analysis is that, as with classical parking functions, prime parking functions are invariant under permutation. That is, if \(\pi\in\mathop{\mathrm{PPF}}_n\), and if \(\lambda\) is any rearrangement of the entries in \(\pi\), then \(\lambda \in \mathop{\mathrm{PPF}}_n\). By symmetry, the uniform distribution on (prime) parking functions is invariant under permutations of the cars and all coordinates have the same expected value.
Hence, for \(1\leq i\leq n+1\), \[\begin{align} \mathbb{E}[\pi_i | \pi \in \mathop{\mathrm{PPF}}_{n+1}]&=\mathbb{E}[\pi_1 | \pi \in \mathop{\mathrm{PPF}}_{n+1}] \notag \\ &=\sum_{j=1}^{n} j\cdot \mathbb{P}(\pi_1=j|\pi\in \mathop{\mathrm{PPF}}_{n+1})\tag{1}\\ &=\sum_{j=1}^n j\cdot \frac{| \{\pi\in\mathop{\mathrm{PPF}}_{n+1}:\pi_1=j\}|}{n^{n}}\tag{2}, \end{align}\] where in 1 we use the fact that none of the entries in \(\pi \in \mathop{\mathrm{PPF}}_{n+1}\) can be \(n+1\).
Example 1. Since \(\mathop{\mathrm{PPF}}_3=\{(1,1,1),(1,2,1),(1,1,2),(2,1,1)\}\), we have \[\mathbb{E}[\pi_1 | \pi \in \mathop{\mathrm{PPF}}_{3}]=\frac{1\cdot 3+2\cdot 1}{4}=\frac{5}{4}.\]
Write \([n]\) for the set of integers \(\{1,2, \dots, n\}\). Subsequently, for any tuple \(\alpha\in[n]^n\), we let \(N_1(\alpha)\) be the number of ones in \(\alpha\). Define \[f_{n}(j,k)=|\{\pi\in\mathop{\mathrm{PF}}_n:\pi_1=j, \;N_1(\pi)=k\}|.\] The count \(f_n(j,k)\) is for \(\mathop{\mathrm{PF}}_n\), but it will play a key role in deriving the expected value \(\mathbb{E}[\pi_1 | \pi \in \mathop{\mathrm{PPF}}_{n+1}]\) given in 2 , as we see in the following theorem.
Proof. For the \(j=1\) case, since \(\pi\in\mathop{\mathrm{PPF}}_{n+1}\) satisfies \(\pi_1=1\), removing this instance of 1 returns a parking function of length \(n\). There are \((n+1)^{n-1}\) parking functions of length \(n\), and so this case follows.
For the \(j>1\) case, let \(\sigma \in \mathop{\mathrm{PF}}_n\) with \(N_1(\sigma)=k\), i.e., \(\sigma\) has \(k\) ones, and such that \(\sigma_1=j\). Since \(\sigma_1=j>1\), we have \(1\leq k\leq n-1\). We can form a parking function \(\pi \in \mathop{\mathrm{PPF}}_{n+1}\) with \(k+1\) ones and \(\pi_1=j\) by inserting a 1 in one of the \(n\) spots between elements of \(\sigma\) or at the end of \(\sigma\). Each \(\pi \in \mathop{\mathrm{PPF}}_{n+1}\) with \(\pi_1=j\) will arise by this construction \(k+1\) times; once for each \(i\) with \(\pi_i=1\). ◻
A central ingredient in 1 is \(f_n(j, k)\). We develop a formula for its value when \(j=2,3,\ldots,n\) and \(k=1,2,\ldots,n-1\). To this end, we recall the definition of a parking function shuffle.
Definition 1 (Parking Function Shuffle, p. 129 [6]). We say that \(\pi_2,\pi_3,\ldots,\pi_n\) is a parking function shuffle of \(\alpha\in\mathop{\mathrm{PF}}_{k-1}\) and \(\beta\in \mathop{\mathrm{PF}}_{n-k}\), if \(\pi_2,\pi_3,\ldots,\pi_n\) is any permutation of the union of the two words \(\alpha\) and \(\beta+(k)\), where \(\beta+(k)\) is the set of values of \(\beta\) shifted by \(k\). The set of all such shuffles is denoted by \(Sh(k-1,n-k)\).
For example, a shuffle of \(\alpha=(1,3,2,2)\) and \(\beta =(2,1,2)\) is \((3,\underline{6},2, 1, 2,\underline{7},\underline{7})\) where we underline the original \(\beta\) shifted by \(k=5\). Diaconis and Hicks [6] proved that \((k, \pi_2,\pi_3,\ldots,\pi_n)\) is a valid parking function if and only if \((\pi_2,\pi_3,\ldots,\pi_n) \in Sh(\ell-1,n-\ell)\) for some \(\ell\geq k\), leading to the following count.
Corollary 1 (Corollary 1 in [6]). The number of \(\pi\in\mathop{\mathrm{PF}}_n\) with \(\pi_1=j\) is \[\sum_{\ell=j}^{n}\binom{n-1}{\ell-1}|\mathop{\mathrm{PF}}_{\ell-1}|\cdot|\mathop{\mathrm{PF}}_{n-\ell}|=\sum_{\ell=j}^{n}\binom{n-1}{\ell-1}\ell^{\ell-2}\cdot(n-\ell+1)^{n-\ell-1}.\]
The following result is well-known.
Theorem 2 (Corollary 1.16 in [2]). The number of parking functions \(\pi\in \mathop{\mathrm{PF}}_{n}\) with exactly \(k\) ones, i.e. \(N_1(\pi)=k\), is given by \[\bigl|\{\pi \in \mathop{\mathrm{PF}}_n: N_1(\pi)=k\}\bigr| = \binom{n-1}{k-1}n^{n-k}.\]
We are now ready to give a count for \(f_n(j, k)\), the number of parking functions of length \(n\) with \(k\) ones and fixed initial value \(j\).
Proposition 3. The number of \(\pi\in\mathop{\mathrm{PF}}_n\) with \(\pi_1=j\) and \(N_1(\pi)=k\) is given by \[\label{eq:f95n40j44k41} f_n(j,k)=\sum_{\ell=j}^n\binom{n-1}{\ell-1} \binom{\ell-2}{k-1}(\ell-1)^{\ell-1-k} \cdot (n-\ell+1)^{n-\ell-1}.\qquad{(1)}\]
Proof. Now when shuffling \(\alpha\in\mathop{\mathrm{PF}}_{\ell-1}\) and \(\beta\in\mathop{\mathrm{PF}}_{n-\ell}\), the only ones appearing in the shuffle must have come from \(\alpha\), which we know has length \(\ell-1\). This is because when shuffling \(\alpha\) and \(\beta\) we would increase all values in \(\beta\) by \(\ell\). This means that we have to count all possible \(\alpha\in\mathop{\mathrm{PF}}_{\ell-1}\) having \(k\) ones, which by 2 is given by \[\binom{\ell-2}{k-1}(\ell-1)^{\ell-1-k}.\] Replacing the factor of \(|\mathop{\mathrm{PF}}_{\ell-1}|=\ell^{\ell-2}\) with \(\binom{\ell-2}{k-1}(\ell-1)^{\ell-1-k}\) in 1 we get that the number of \(\pi\in\mathop{\mathrm{PF}}_{n}\) with \(\pi_1=j\) and \(N_1(\pi)=k\) is \[\begin{align} &\sum_{\ell=j}^n\binom{n-1}{\ell-1} \binom{\ell-2}{k-1}(\ell-1)^{\ell-1-k} \cdot |\mathop{\mathrm{PF}}_{n-\ell}|\\ &=\sum_{\ell=j}^n\binom{n-1}{\ell-1} \binom{\ell-2}{k-1}(\ell-1)^{\ell-1-k} \cdot (n-\ell+1)^{n-\ell-1}.\qedhere \end{align}\] ◻
Remark 1. Since the binomial coefficient \(\binom{n}{k}\) is \(0\) for \(k>n,\) the sum in ?? is equivalent to \[f_n(j,k)=\sum_{\ell=\max(j,k+1)}^n\binom{n-1}{\ell-1} \binom{\ell-2}{k-1}(\ell-1)^{\ell-1-k} \cdot (n-\ell+1)^{n-\ell-1}.\]
We now come to our main result. The proof makes use of special cases of Abel’s extensions of the binomial theorem, a portion of which we recall below.
Theorem 4 (Abel’s extension of the binomial theorem, derived from Pitman [7] and Riordan [8]). Let \[\label{b} A_n(x, y; p, q)=\sum_{s=0}^n \binom{n}{s} (x+s)^{s+p} (y+n-s)^{n-s+q}.\tag{3}\] Then \[\label{b2} A_n(x, y; p, q)=A_{n-1}(x, y+1; p, q+1)+A_{n-1}(x+1, y; p+1, q), \textrm{ and}\tag{4}\] \[\label{b3} A_n(x, y; p, q)=\sum_{s=0}^{n} \binom{n}{s}s!(x+s)A_{n-s}(x+s, y; p-1, q).\tag{5}\] Moreover, the following special instances hold via the basic recurrences listed above: \[\label{2} A_n(x, y; -1, 0)=x^{-1}(x+y+n)^n.\tag{6}\] \[\label{3} A_n(x, y; -1, 1)=x^{-1} \sum_{s=0}^n \binom{n}{s} (x+y+n)^s (y+n-s) (n-s)!.\tag{7}\]
Proof. Using 1 we have \[\begin{align} \mathbb{E}[\pi_1 | \pi \in \mathop{\mathrm{PPF}}_{n+1}]&=\sum_{j=1}^{n}j\cdot \mathbb{P}(\pi_1=j|\pi\in \mathop{\mathrm{PPF}}_{n+1})\nonumber\\ &=\frac{1}{n^n}\left((n+1)^{n-1}+\sum_{j=2}^n j\sum_{k=1}^{n-1}\frac{n}{k+1}f_n(j,k)\right).\label{eq:expected32value} \end{align}\tag{8}\] For ease of notation, denote the following sum by \(A\): \[\begin{align} A&\mathrel{\vcenter{:}}= \sum_{j=2}^n j\sum_{k=1}^{n-1}\frac{n}{k+1}f_n(j,k)\nonumber\\ &= \sum_{j=2}^n j\sum_{k=1}^{n-1}\frac{n}{k+1}\sum_{\ell=j}^n\binom{n-1}{\ell-1}\binom{\ell-2}{k-1}(\ell-1)^{\ell-1-k}(n-\ell+1)^{n-\ell-1},\label{eq:A} \end{align}\tag{9}\] where we apply Proposition 3 in the second equality. Notice that as pointed out in 1, the binomial coefficient \(\binom{\ell-2}{k-1}\) is non-zero only when \(k \leq \ell-1\) (\(k\) ones in a parking function of length \(\ell-1\)). In 9 , making the change of variables \(s=n-\ell\), we find \[\begin{align} A &=\sum_{j=2}^{n}j\sum_{k=1}^{n-1}\frac{n}{k+1}\sum_{s=0}^{n-j}\binom{n-1}{s}\binom{n-s-2}{k-1}(n-s-1)^{n-s-k-1}(s+1)^{s-1}\nonumber\\ &=\sum_{k=1}^{n-1}\frac{n}{k+1} \Big( \sum_{j=2}^{n}j \sum_{s=0}^{n-j}\binom{n-1}{s}\binom{n-s-2}{k-1}(n-s-1)^{n-s-k-1}(s+1)^{s-1} \Big)\nonumber\\ &=\sum_{k=1}^{n-1}\frac{n}{k+1} \Bigg( \sum_{s=0}^{n-2} \binom{n-1}{s}\binom{n-s-2}{k-1}(n-s-1)^{n-s-k-1}(s+1)^{s-1} \Big(\sum_{j=2}^{n-s} j\Big)\Bigg), \label{eq:A39} \end{align}\tag{10}\] where the last equality in 10 is obtained by interchanging the order of summation. Replacing the sum of \(j\) with \(\frac{1}{2} (n-s-1)(n-s+2)\), we can reorganize \(A\) as follows: \[\begin{align} A&=\frac{1}{2}\sum_{k=1}^{n-1}\frac{n}{k+1} \Bigg( \sum_{s=0}^{n-2} \binom{n-1}{s}\binom{n-s-2}{k-1}(n-s-1)^{n-s-k}(s+1)^{s-1} (n-s+2)\Bigg)\nonumber\\ &=\frac{1}{2}\sum_{s=0}^{n-1} \binom{n-1}{s} (s+1)^{s-1} (n-s+2) \Bigg( \sum_{k=1}^{n-s-1} \binom{n-s-2}{k-1}(n-s-1)^{n-s-k} \frac{n}{k+1}\Bigg),\label{eq:will32simplify32this32junk} \end{align}\tag{11}\] where the last equality in 11 involves interchanging the order of summation and setting a more explicit upper bound on \(k\) for the binomial coefficient \(\binom{n-s-2}{k-1}\) to be non-zero. We also note that the inner sum for \(k\) becomes empty when taking \(s=n-1\). Thus, changing the upper bound on \(s\) from \(n-2\) to \(n-1\) has no effect on the value of \(A\); we are implementing it for the application of Abel’s binomial theorem later. We proceed to simplify the inner sum over the indexing variable \(k\) to arrive at \[\begin{align} &\sum_{k=1}^{n-s-1}\frac{n}{k+1}\binom{n-s-2}{k-1}(n-s-1)^{n-s-k}\nonumber\\ &=\frac{n}{n-s}\sum_{k=2}^{n-s}(k-1)\binom{n-s}{k}(n-s-1)^{n-s-k}\qquad(by reindexing k \leftarrow k+1)\nonumber\\ &=\frac{n}{n-s}\Bigg[\sum_{k=0}^{n-s}(k-1)\binom{n-s}{k}(n-s-1)^{n-s-k}\nonumber\\ &-\left(-1\binom{n-s}{0}(n-s-1)^{n-s}+0\binom{n-s}{1}(n-s-1)^{n-s-1}\right)\Bigg]\nonumber\\ &=\frac{n}{n-s}\Bigg[\sum_{k=0}^{n-s}k\binom{n-s}{k}(n-s-1)^{n-s-k}\nonumber\\ &-\sum_{k=0}^{n-s}\binom{n-s}{k}(n-s-1)^{n-s-k}+(n-s-1)^{n-s}\Bigg].\label{return32here} \end{align}\tag{12}\] By reindexing \(k \leftarrow k-1\) in the first sum, both the first sum and the second sum over \(k\) in 12 equal \((n-s)^{n-s}\) after applying the binomial theorem, and so the entire expression 12 reduces to \[\frac{n}{n-s}(n-s-1)^{n-s}.\] Returning to 11 we have that \[\begin{align} A&=\frac{1}{2}\sum_{s=0}^{n-1}\binom{n-1}{s}(s+1)^{s-1}(n-s+2)\frac{n}{n-s}(n-s-1)^{n-s} \nonumber\\ &=\frac{1}{2}\sum_{s=0}^{n-1}\binom{n}{s}(n-s+2)(n-s-1)^{n-s}(s+1)^{s-1}\nonumber\\ &=\frac{1}{2}\sum_{s=0}^{n-1}\binom{n}{s}((n-s-1)+3)(n-s-1)^{n-s}(s+1)^{s-1}\nonumber\\ &=\frac{1}{2}\left(\sum_{s=0}^{n}\binom{n}{s}((n-s-1)+3)(n-s-1)^{n-s}(s+1)^{s-1}\right)-\frac{1}{2}2(-1)^0(n+1)^{n-1}\nonumber\\ &=\frac{1}{2}\left(\sum_{s=0}^{n}\binom{n}{s}(n-s-1)^{n-s+1}(s+1)^{s-1}+\sum_{s=0}^{n}3\binom{n}{s}(n-s-1)^{n-s}(s+1)^{s-1}\right) -(n+1)^{n-1}\nonumber\\ &= \frac{1}{2}\left(I+II\right)-(n+1)^{n-1},\label{eq:so32close} \end{align}\tag{13}\] where \[\begin{align} I&=\sum_{s=0}^{n}\binom{n}{s}(n-s-1)^{n-s+1}(s+1)^{s-1}\tag{14}\\ \intertext{and} II&=\sum_{s=0}^{n}3\binom{n}{s}(n-s-1)^{n-s}(s+1)^{s-1}\tag{15}. \end{align}\] By Abel’s 7 and 6 , we have that 14 and 15 , respectively become \[\begin{align} I&=A_n(1,-1;-1,1)\nonumber\\ &=\sum_{s=0}^{n}\binom{n}{s}n^s(n-s-1)(n-s)!\nonumber\\ &=\sum_{s=0}^n\frac{n!}{s!}n^s(n-1)-\sum_{s=0}^n\frac{n!}{s!}n^ss\nonumber\\ &=\sum_{s=0}^n\frac{n!}{s!}n^{s}(n-1)-\sum_{s=0}^{n-1}\frac{n!}{s!}n^{s+1}\nonumber\\ &=\sum_{s=0}^{n-1}\frac{n!}{s!}n^{s+1}+\frac{n!}{n!}n^{n+1}-\sum_{s=0}^n\frac{n!}{s!}n^{s}-\sum_{s=0}^{n-1}\frac{n!}{s!}n^{s+1}\nonumber\\ &=n^{n+1}-\sum_{s=0}^n\frac{n!}{s!}n^{s} \tag{16}\\ \intertext{and} II&=3A_n(1,-1;-1,0)=3n^n\tag{17}. \end{align}\]
Finally, substituting 16 and 17 into 13 we have that \[\begin{align} A&=\frac{1}{2}\left(n^{n+1}-\sum_{s=0}^n\frac{n!}{s!}n^{s}+3n^n\right)-(n+1)^{n-1}.\label{eq:yay} \end{align}\tag{18}\] Substituting 18 into 8 we find the expected value \[\begin{align} \mathbb{E}[\pi_1 | \pi \in \mathop{\mathrm{PPF}}_{n+1}] &=\frac{1}{n^n}\left((n+1)^{n-1}+\frac{1}{2}\left(n^{n+1}-\sum_{s=0}^n\frac{n!}{s!}n^{s}+3n^n\right)-(n+1)^{n-1}\right)\\ &=\frac{1}{2n^n}\left(n^{n+1}-\sum_{s=0}^n\frac{n!}{s!}n^{s}+3n^n\right)\\ &=\frac{1}{2}\left(n+3-\frac{n!}{n^n}\sum_{s=0}^n\frac{n^{s}}{s!}\right), \end{align}\] which completes the proof. ◻
Building upon [thm:expected32value32of32pi1], we derive the asymptotics for the expected value of \(\pi_1\) for large \(n\). First, we need a technical lemma.
Lemma 1. [9]Let \(X_1, X_2, \dots\) be iid Poisson\((1)\) random variables. Then \[\mathbb{P}(X_1+\cdots+X_n \leq n)=\frac{1}{2}+\frac{2}{3}\frac{1}{\sqrt{2\pi n}}+o\left(\frac{1}{\sqrt{n}}\right).\]
Proof. We recognize that \[e^{-n} \sum_{s=0}^{n} \frac{n^s}{s!}\] in [thm:expected32value32of32pi1] equals the probability that the sum of \(n\) iid Poisson\((1)\) random variables is less than or equal to \(n\), and so its asymptotics may be estimated by 1: \[\begin{align} e^{-n} \sum_{s=0}^n \frac{n^s}{s!} = \frac{1}{2}+\frac{2}{3}\frac{1}{\sqrt{2\pi n}}+o\left(\frac{1}{\sqrt{n}}\right).\label{eq:first} \end{align}\tag{19}\] By Stirling’s approximation: \[\begin{align} n!= \sqrt{2\pi n} e^{-n} n^n \left(1+\frac{1}{12n}+ o\Big(\frac{1}{n}\Big)\right).\label{eq:second} \end{align}\tag{20}\] Using 19 and 20 , we can express the expected value derived in [thm:expected32value32of32pi1] as follows: \[\begin{align} \mathbb{E}[ \pi_1 | \pi \in \mathop{\mathrm{PPF}}_{n+1}] &= \frac{1}{2} \left ( n+3 -\frac{\sqrt{2\pi n} e^{-n}n^n \left ( 1 + \frac{1}{12n}+ o\left (\frac{1}{n} \right ) \right )}{n^n} \cdot e^n \left (\frac{1}{2}+\frac{2}{3} \frac{1}{\sqrt{2\pi n}}+ o\left (\frac{1}{\sqrt{n}}\right ) \right )\right ) \nonumber \\ &= \frac{1}{2} \left (n+3 -\sqrt{2\pi n} \left ( \frac{1}{2} + \frac{2}{3}\frac{1}{\sqrt{2\pi n}} + o\left (\frac{1}{\sqrt{n}} \right ) \right ) \right ) \nonumber\\ & = \frac{1}{2} \left (n+3 -\sqrt{\frac{\pi n}{2}} - \frac{2}{3} + o(1) \right ) \nonumber\\ &= \frac{1}{2} \left (n-\sqrt{\frac{\pi n}{2}} + \frac{7}{3} + o(1) \right ), \nonumber \end{align}\] which is our claimed result. ◻
In the classical parking functions setting, [9] states that for \(n\) large and a preference vector \(\pi\in[n]^n\) chosen uniformly at random, \[\mathbb{E}[\pi_1|\pi\in\mathop{\mathrm{PF}}_n]=\frac{n+1}{2}-\frac{\sqrt{2\pi}}{4}n^{1/2}+\frac{7}{6}+o(1).\] Using the fact that \((n-1)^{1/2}=n^{1/2}+o(1),\) and applying [cr:expected32value32of32pi1] to prime parking functions of length \(n,\) we find that \[\mathbb{E}[\pi_1|\pi\in \mathop{\mathrm{PPF}}_n]=\frac{n-1}{2}-\frac{\sqrt{2\pi}}{4}(n^{1/2}+o(1))+\frac{7}{6}+o(1).\] Thus, asymptotically \(\mathbb{E}[\pi_1|\pi\in \mathop{\mathrm{PPF}}_n]\) is one less than \(\mathbb{E}[\pi_1|\pi\in \mathop{\mathrm{PF}}_n].\) This accords with our intuition, as an alternative interpretation for a classical parking function \(\pi=(\pi_1, \pi_2,\dots, \pi_n)\) to be prime is that for all \(1\leq i\leq n-1\), at least \(i+1\) cars want to park in the first \(i\) places, so asymptotically there is a shift down by one for the expected parking preference.
2.1 Average displacement of prime parking functions↩︎
Now that we have the average value of the first car’s preference across all prime parking functions of length \(n+1\), we compute the average displacement of prime parking functions.
Definition 2. Given a parking function \(\pi=(\pi_1,\pi_2,\ldots,\pi_n)\) in which car \(i\) parks in spot \(p_i\), we say the displacement of car \(i\) is \(d(i)=p_i-\pi_i\), and the displacement of \(\pi\) is given by \[\text{dis} (\pi)=\sum_{i=1}^n \left(p_i-\pi_i\right)=\frac{n(n+1)}{2} -\sum_{i=1}^n\pi_i.\]
Proof. Recall that prime parking functions are permutation invariant. Using [thm:expected32value32of32pi1] and [cr:expected32value32of32pi1] we have that \[\begin{align} \mathbb{E}[\text{dis} (\pi) | \pi \in \mathop{\mathrm{PPF}}_{n+1}]&=\sum_{i=1}^{n+1}(i-\mathbb{E}[\pi_i| \pi \in \mathop{\mathrm{PPF}}_{n+1}])\\ &=\frac{(n+1)(n+2)}{2}-(n+1)\mathbb{E}[\pi_1| \pi \in \mathop{\mathrm{PPF}}_{n+1}] \nonumber\\ &=\frac{(n+1)(n+2)}{2}-\frac{n+1}{2}\left(n-\sqrt{\frac{\pi n}{2}}+\frac{7}{3}+o(1) \right)\nonumber\\ &=\frac{n+1}{2}\left(2+\sqrt{\frac{\pi n}{2}}-\frac{7}{3}+ o(1)\right)\nonumber\\ &=\frac{\sqrt{2\pi}}{4}n^{3/2}-\frac{n}{6}+o(n). \nonumber\qedhere \end{align}\] ◻
3 Displacement-enumerator results↩︎
In their work on the connections between parking functions and lattice paths, Selig and Zhu [4] showed that in addition to the well-known connection between parking functions and Dyck paths, there is an intriguing and less studied connection between parking functions and Łukasiewicz paths. In particular, the displacement of a parking function can be interpreted as the area under an associated Łukasiewicz path. This viewpoint gives a helpful way to understand displacement statistics in terms of lattice path geometry. Building on this idea, we focus on prime parking functions and examine a weighted generating function that keeps track of their total displacement. We show that the displacement-enumerator can be expressed as a sum over Łukasiewicz paths, with weights determined by step heights. This result extends known enumerators for classical parking functions to the prime setting, where the additional constraint that paths stay strictly above the \(x\)-axis (except at the endpoints) adds an interesting layer of structure.
We start by introducing relevant notation and some of the needed terminology from [4] relating to Łukasiewicz paths.
Notation 1. For the remainder of the paper, we denote the displacement-enumerator of the set of prime parking functions of length \(n+1\) by \(\mathop{\mathrm{PPF}}_{n+1}(q)\). So, we have \[\mathop{\mathrm{PPF}}_{n+1}(q)= \sum_{\pi \in \mathop{\mathrm{PPF}}_{n+1}} q^{\mathop{\mathrm{dis}}(\pi)}.\]
Next, we recall the definition of a Łukasiewicz word and a Łukasiewicz path, as given by Selig and Zhu in [4].
Definition 3. A Łukasiewicz word of length \(n\) is a sequence \(\ell = (\ell_1,\ell_2, \ldots, \ell_n)\) of integers \(\ell_i \geq -1\), for all \(i\in[n]\), such that:
For any \(k \in [n]\), we have \(\sum\limits_{i=1}^k \ell_i \geq 0\).
We have \(\sum\limits_{i=1}^n \ell_i = 0\).
Following the conventions in [4], Łukasiewicz words can be represented with lattice paths by associating each \(\ell_i\) with a step of the form \((\ell_i+1,\ell_i)\). Throughout this section, we may refer to step \((\ell_i+1,\ell_i)\) as the step \(\ell_i\). These lattice paths are from \((0,0)\) to \((n,0)\) and they never fall below the \(x\)-axis. We call such a lattice path a Łukasiewicz path of length \(n\) and denote the set of all Łukasiewicz paths of length \(n\) by \(\mathcal{L}_n\).
Given a parking function \(\pi=(\pi_1,\pi_2,\ldots, \pi_n)\in \mathop{\mathrm{PF}}_n\), one can associate it to a Łukasiewicz path by defining \(\ell=(\ell_1,\ell_2,\ldots,\ell_n)\) where \(\ell_j= | \{ i : \pi_i=j\}|-1\) for each \(j\in [n]\). A bijection between the set of weakly increasing parking functions and Łukasiewicz paths was established in [4]. In addition, it was shown in [4] that the area under the Łukasiewicz path is equal to the total displacement of the parking function.
Our goal is to use this connection to find an expression for the displacement-enumerator for prime parking functions. For this purpose, we first extend the definition of Łukasiewicz path to that of prime Łukasiewicz path in the following natural way.
Definition 4. A Łukasiewicz path of length \(n\) is called prime if it only touches the \(x\)-axis at \((0,0)\) and \((n,0)\).
Example 2. Consider the (prime) parking function \(\pi=(1,1,1,3,4,4,6)\). The corresponding Łukasiewicz word is \(\ell=(2,-1,0,1,-1,0,-1)\) and the corresponding Łukasiewicz path is displayed in blue in 1. As the path only touches the \(x\)-axis at \((0,0)\) and \((7,0)\), it is a prime Łukasiewicz path of length \(7\).
As we see below, one can collect the height information of a Łukasiewicz path (after each step) in a sequence.
Notation 2. Given a parking function \(\pi \in \mathop{\mathrm{PF}}_n\) with its associated Łukasiewicz path \(\ell\), define the height sequence of \(\pi\) as \(h=(h_0,h_1,h_2,\ldots, h_n)\) such that \(h_0= h_n=0\) and \[h_j\mathrel{\vcenter{:}}= \sum_{i=1}^j \ell_i\] for each \(j\in [n-1]\). Notice that \(h_j\) is indeed the height of the corresponding Łukasiewicz path after step \(\ell_j\) and \(h_{j}-h_{j-1}=\ell_j\) for each \(j\in [n]\).
Example 3. The height sequence of the (prime) parking function given in 2 is \(h=(0,2,1,1,2,1,1,0)\).
Remark 2. Given a parking function \(\pi=(\pi_1,\pi_2,\ldots, \pi_n) \in \mathop{\mathrm{PF}}_n\) with the corresponding height sequence \(h=(h_0,h_1,\ldots, h_n)\), it is worth noticing that \[h_{j}-h_{j-1}+ 1= |\{ i: \pi_{i}=j\}|\] for each \(j\in [n]\). As a result, one can express the sum of all the preferences in \(\pi\) in the following way: \[\sum_{i=1}^{n}\pi_i = \sum_{j=1}^{n} j(h_j-h_{j-1}+1).\] Lastly, we have \(\displaystyle \sum_{j=1}^{n} (h_{j}-h_{j-1}+1) = \sum_{j=1}^{n} (\ell_{j} +1)= n\).
In what follows, we use these height sequences in expressing the displacement-enumerator of prime parking functions.
Proof. Recall from the definition of prime parking functions that every prime parking function \(\pi' \in \mathop{\mathrm{PPF}}_{n+1}\) can be obtained by inserting a \(1\) into a parking function \(\pi \in \mathop{\mathrm{PF}}_n\). Equivalently, given a prime parking function \(\pi'\), we can recover an associated parking function \(\pi\) by removing one occurrence of \(1\) from \(\pi'\). This relationship allows us to connect the set of prime parking functions of size \(n+1\) to the set of parking functions of size \(n\). See the proof of Theorem 1 for details. In particular, we can use this correspondence to express the displacement-enumerator of prime parking functions in terms of classical parking functions, as follows: \[\mathop{\mathrm{PPF}}_{n+1}(q)=\sum_{\pi' \in \mathop{\mathrm{PPF}}_{n+1}} q^{\mathop{\mathrm{dis}}(\pi')} = \sum_{\pi \in \mathop{\mathrm{PF}}_n} \Big( \frac{n+1}{h_1-h_0+2} \Big) q^{\sum\limits_{i=1}^{n+1}i-(1+\sum\limits_{i=1}^{n}\pi_i)},\] where \((h_0, h_1, \ldots, h_n)\) denotes the height sequence associated to the parking function \(\pi \in \mathop{\mathrm{PF}}_n\). Moreover, \(h_j-h_{j-1}+1\) is the number of occurrences of \(j\) in \(\pi\). So, \(h_1 - h_0 + 2\) is the number of entries equal to 1 in the prime parking function \(\pi' \in \mathop{\mathrm{PPF}}_{n+1}\). This factor is used to derive the final expression in the formula above, where the sum over \(\pi' \in \mathop{\mathrm{PPF}}_{n+1}\) is rewritten as a weighted sum over \(\pi \in \mathop{\mathrm{PF}}_n\).
We focus on the exponent of \(q\) in the final expression before proceeding further. We show that this exponent can be rewritten in terms of the entries of the height sequence. Observe the following sequence of equalities: \[q^{\sum\limits_{i=1}^{n+1}i-(1+\sum\limits_{i=1}^{n}\pi_i)} = q^n q^{(1+2+\cdots+ n) - \sum\limits_{i=1}^{n} i(h_i-h_{i-1}+1)} = q^n q^{-\sum\limits_{i=1}^{n} i(h_i-h_{i-1})} = q^n q^{\sum\limits_{i=0}^{n}h_i} = q^n \prod_{j=1}^{n}q^{h_{j}}.\] Thus, we have \[\mathop{\mathrm{PPF}}_{n+1}(q)= \sum_{\pi \in \mathop{\mathrm{PF}}_n} (n+1) q^n\Big( \frac{1}{h_1-h_0+2} \Big) \prod_{j=1}^{n} q^{h_{j}}.\]
To obtain the desired expression, we first note that different parking functions can share the same height sequence. For a fixed height sequence \((h_0, h_1, \ldots, h_n)\), the corresponding parking function \(\pi=(\pi_1,\pi_2, \dots, \pi_n)\) satisfies \(h_{j}-h_{j-1}+ 1= |\{ i: \pi_{i}=j\}|\). Summing over height sequences instead of parking functions thus introduces a combined multiplicity factor of \(\prod_{j=1}^n \frac{n! }{(h_{j}-h_{j-1}+1)!}\) in the product. Since there is a one-to-one correspondence between Łukasiewicz paths and height sequences, we can sum over all Łukasiewicz paths of length \(n\), as shown below: \[\begin{align} \mathop{\mathrm{PPF}}_{n+1}(q) &= (n+1)! ~~q^n \sum_{\substack{\text{all possible}\\\text{\L ukasiewicz~paths with} \\ \text{height sequence } \\ (h_0, h_1, \dots, h_n)}} \Big( \frac{1}{h_1-h_0+2} \Big) ~~ \prod_{j=1}^{n} \frac{q^{h_{j}}}{(h_{j}-h_{j-1}+1)!}. \qedhere \end{align}\] ◻
Remark 3. In a similar fashion, one can express the displacement-enumerator of prime parking functions in terms of prime Łukasiewicz paths as follows: \[\sum_{\pi' \in \mathop{\mathrm{PPF}}_{n+1}} q^{\mathop{\mathrm{dis}}(\pi')} =(n+1)! \sum_{ \substack{ \text{all possible} \\ \text{\L ukasiewicz~paths} \\ \text{with height sequence} \\ (h_0, h_1, \dots, h_{n+1}): \, h_i \geq 1 \, \forall\, 1\leq i\leq n}} \prod_{j=1}^{n+1} \frac{q^{h_{j}}}{(h_{j}-h_{j-1}+1)!}.\] The corresponding formula for the displacement-enumerator of (classical) parking functions in terms of Łukasiewicz paths was derived earlier by Elvey-Price in [5].
This concludes our discussion on the displacement-enumeration of prime parking functions in terms of Łukasiewicz paths. In the following section, we turn our attention to the structure of Łukasiewicz paths themselves in order to study additional statistics of prime parking functions.
4 Łukasiewicz paths and descents↩︎
In this section, we focus on descent statistics of Łukasiewicz paths. Descent sets and related statistics on parking functions have been studied in [10]–[13]. Our goal is to express the descent statistic in terms of Łukasiewicz paths. We do this by introducing a labeled version of Łukasiewicz paths, which naturally correspond to parking functions. This correspondence allows us to describe the descent, ascent, and tie sets directly from the labeled paths.
We start this section by recalling the notion of descent and other related statistics. Given a tuple \(\boldsymbol{x}= (x_1, x_2, \ldots, x_n) \in [n]^n\), we say that \(\boldsymbol{x}\) has a descent at \(i\) if \(x_i > x_{i+1}\), an ascent at \(i\) if \(x_i < x_{i+1}\), and a tie at \(i\) if \(x_i = x_{i+1}\). The descent set, ascent set, and tie set of \(\boldsymbol{x}\) are defined as \[\begin{align} \mathop{\mathrm{Des}}(\boldsymbol{x}) &\mathrel{\vcenter{:}}= \{\, i \in [n-1] : x_i > x_{i+1} \,\}, \\ \mathop{\mathrm{Asc}}(\boldsymbol{x}) &\mathrel{\vcenter{:}}= \{\, i \in [n-1] : x_i < x_{i+1} \,\}, \\ \mathop{\mathrm{Tie}}(\boldsymbol{x}) &\mathrel{\vcenter{:}}= \{\, i \in [n-1] : x_i = x_{i+1} \,\}. \end{align}\]
We use lower-case versions to denote the cardinality of the corresponding set, e.g. \(\mathrm{des}(\boldsymbol{x})=|\mathop{\mathrm{Des}}(\boldsymbol{x})|.\)
Definition 5. Let \(\ell = (\ell_1, \ell_2, \ldots, \ell_n)\) be a Łukasiewicz path of length \(n\), and let \(\mathcal{B} = (\beta_1, \beta_2, \ldots, \beta_n)\) be an ordered set partition of \([n]\) whose (possibly empty) parts satisfy \(|\beta_i| = \ell_i + 1\) for all \(i \in [n]\). A labeled Łukasiewicz path is the pair \(L = (\ell, \mathcal{B})\) obtained by labeling the portion of the \(x\)-axis under step \(\ell_i\) with the elements of \(\beta_i\), listed in increasing order. If \(\ell_i + 1 = 0\), then step \(\ell_i\) is vertical, so \(\beta_i\) is empty and no labeling occurs.
We let \(\alpha_L\) denote the permutation obtained by ordering the elements of each \(\beta_j\) in increasing order for \(j \in [n]\). This permutation \(\alpha_L\) is useful in describing the descents of parking functions in terms of \(L\).
Remark 4. Each labeled Łukasiewicz path \(L = (\ell, \mathcal{B})\) determines a parking function \(\alpha\) by setting \(\alpha_k = m\) whenever \(k \in \beta_m\). Equivalently, the interval on the \(x\)-axis under step \(\ell_m\) is labeled by the elements of \(\beta_m\), which may be interpreted as cars, with their block \(\beta_m\) indicating their preference.
This process can also be reversed. As discussed in 3, each parking function determines a Łukasiewiczpath \(\ell\). For the corresponding labeled Łukasiewiczpath, the set partition \(\mathcal{B}\) is obtained by labeling, along the \(x\)-axis under each step \(\ell_i\), the intervals with the cars that prefer spot \(i\), listed in increasing order.
We illustrate these concepts with an example and show how to obtain a parking function from a labeled Łukasiewicz path.
Example 4. Consider the Łukasiewicz path \(\ell = (2,0,1,0,-1,0,-1,-1)\) illustrated in 2, together with the ordered set partition \(\mathcal{B}= (\beta_1,\beta_2,\ldots, \beta_n)\) where \[\beta_1 = \{2,4,6\}, \;\beta_2 = \{1\}, \;\beta_3 = \{3,5\}, \;\beta_4 = \{8\}, \;\beta_5 = \emptyset, \;\beta_6 = \{7\}, \;\beta_7 = \emptyset, \;\beta_8 = \emptyset.\]
For each step \(\ell_i\), the elements of \(\beta_i\) are placed, in increasing order, along the intervals of the \(x\)-axis corresponding to that step, as shown in 2.
The corresponding parking function is \(\alpha = (2,1,3,1,3,1,6,4)\), obtained by setting \(\alpha_k = m\) whenever \(k \in \beta_m\). It is worth noting that \(\beta_i\) is the list of cars preferring spot \(i\) in \(\alpha\). Finally, the permutation \(\alpha_L\) associated to \(L\) from 5 is \(\alpha_L = (2,4,6,1,3,5,8,7)\).
As the previous discussion has hinted, there is a one-to-one correspondence between labeled Łukasiewicz paths and parking functions.
Theorem 5. The set of labeled Łukasiewicz paths of length \(n\) is in bijection with parking functions of length \(n\).
Instead of constructing this bijection directly, we prove 5 by first building a bijection between labeled Łukasiewicz paths and labeled Dyck paths. Since labeled Dyck paths are already known to be in bijection with parking functions [13], this will establish the theorem. We take this route to emphasize the close relationship between Łukasiewicz paths and Dyck paths.
Recall that a Dyck path of length \(n\) is a lattice path from \((0,0)\) to \((n,n)\) with north steps (\(\texttt{N}\)) and east steps (\(\texttt{E}\)) that stays weakly above the diagonal \(y=x\). A labeled Dyck path of length \(n\) assigns the labels \([n]\) bijectively to the north steps, with each vertical run labeled in increasing order from bottom to top. Given such a labeled Dyck path, the associated parking function \(\alpha=(\alpha_1,\ldots,\alpha_n)\) is defined by setting \(\alpha_i=j\) whenever label \(i\) appears on a north step in column \(j\) (columns are indexed from \(1\)). For further details on this bijection, see [13]. We illustrate this correspondence in the following example.
Example 5. Let \(\alpha\) be the parking function corresponding to the labeled Dyck path given in 3. Reading by columns: the north-step labels in column 1 are \(2,4,\) and \(6\), so \(\alpha_2=\alpha_4=\alpha_6=1\); column 2 has label \(1\), so \(\alpha_1=2\); column 3 has labels \(3,5\), so \(\alpha_3=\alpha_5=3\); column 4 has label \(8\), so \(\alpha_8=4\); and column 6 has label \(7\), so \(\alpha_7=6\). Thus \(\alpha=(2,1,3,1,3,1,6,4).\)
For the reverse direction, given the parking function \(\alpha=(2,1,3,1,3,1,6,4)\), we first group cars by preference. Notice that these sets form \(\mathcal{B}\), which is part of the data of the labeled Łukasiewicz path \(L=(\ell,\mathcal{B})\) corresponding to \(\alpha\) where \[\beta_1=\{2,4,6\}, \beta_2=\{1\}, \beta_3=\{3,5\}, \beta_4=\{8\}, \beta_5=\emptyset, \beta_6=\{7\}, \beta_7=\emptyset, \beta_8=\emptyset.\]
The column heights of the corresponding Dyck path are determined by the sizes of these sets: \(c = (3,1,2,1,0,1,0,0)\). Note that \(c = \ell + (1,\ldots,1)\). We then construct the Dyck path by taking, for each column \(j\), \(c_j\) north steps followed by one east step, which yields \(\texttt{N}\,\texttt{N}\,\texttt{N}\,\texttt{E}\; \texttt{N}\,\texttt{E}\; \texttt{N}\,\texttt{N}\,\texttt{E}\; \texttt{N}\,\texttt{E}\; \texttt{E}\; \texttt{N}\,\texttt{E}\; \texttt{E}\; \texttt{E}.\) Finally, label the north steps in each column from bottom to top with the elements of \(\beta_j\) in increasing order. This reproduces the labeled Dyck path in 3.
With this refresher in place, we are now ready to construct a bijection between labeled Dyck paths and labeled Łukasiewicz paths.
Proof of 5. Let \(L=(\ell,\mathcal{B})\) be a labeled Łukasiewicz path with \(\ell = (\ell_1,\ell_2,\ldots,\ell_n)\) and \(\mathcal{B} = (\beta_1,\beta_2,\ldots,\beta_n)\). We construct the corresponding Dyck path by interpreting \(\ell_i+1\) as the height of column \(i\) as follows: for \(i=1,2,\ldots,n\), take \(\ell_i+1\) north steps (\(\texttt{N}\)) followed by one east step (\(\texttt{E}\)).
Here \(\ell_i+1 = |\beta_i|\) is the number of north steps in column \(i\), which equals the number of cars in the corresponding parking function that prefer spot \(i\). The fact that \(\ell\) never goes below the \(x\)-axis guarantees that the constructed path never goes below the main diagonal, so it is indeed a Dyck path.
This procedure is reversible: given a Dyck path, the column heights recover \(\ell\), and the labels on the vertical runs recover \(\mathcal{B}\). Since the labeling of north steps of a Dyck path assigns the cars in increasing order from bottom to top, each element in \(\beta_i\) is in increasing order. This completes the bijection. ◻
In the following example, we illustrate how to move between a labeled Łukasiewicz path and labeled Dyck path, as described in the proof of 5.
Example 6. Consider the labeled Łukasiewicz path of 4 presented in 2 (also the left of 4) where \[L=((2,0,1,0,-1,0,-1,-1),(\{2,4,6\},\{1\},\{3,5\},\{8\},\emptyset,\{7\},\emptyset,\emptyset)).\] Using the steps given in the proof of 5, we show that the Dyck path given in 3 corresponds to \(L\). For the reader’s convenience, the two paths are presented side by side in 4.
Since \(\ell_1 = 2\), the Dyck path begins with three north steps followed by an east step \(\texttt{N}\texttt{N}\texttt{N}\texttt{E}\). This is followed by \(\texttt{N}\texttt{E}\) from \(\ell_2 = 0\), then \(\texttt{N}\texttt{N}\texttt{E}\) from \(\ell_3 = 1\). From \(\ell_4 = 0\) we again have \(\texttt{N}\texttt{E}\), while \(\ell_5 = -1\) contributes a single east step \(\texttt{E}\). Next, \(\ell_6 = 0\) yields \(\texttt{N}\texttt{E}\), \(\ell_7 = -1\) contributes another east step \(\texttt{E}\), and finally \(\ell_8 = -1\) gives the last east step \(\texttt{E}\). Thus the Dyck path is \(\texttt{N}\,\texttt{N}\,\texttt{N}\,\texttt{E}\; \texttt{N}\,\texttt{E}\; \texttt{N}\,\texttt{N}\,\texttt{E}\; \texttt{N}\,\texttt{E}\; \texttt{E}\; \texttt{N}\,\texttt{E}\; \texttt{E}\; \texttt{E}\). We now take the ordered set partition \((\{2,4,6\},\{1\},\{3,5\},\{8\},\emptyset,\{7\},\emptyset,\emptyset)\) and use the elements of the \(i\)th block to label, in increasing order, the run of north steps in column \(i\). This produces exactly the labeled Dyck path shown on the right of 4.
Remark 5. The labeled (prime) Łukasiewicz path perspective provides an alternative derivation for the number of (prime) parking functions of length \(n\). Let \(S_n\) denote the set of permutations of \([n]\). Given any Łukasiewicz path \(\ell \in \mathcal{L}_n\) and any permutation \(\pi \in S_n\), labeling the \(x\)-axis under \(\ell\) according to \(\pi\) produces a parking function. However, different permutations in \(S_n\) may yield the same parking function, since permuting the labels within a given step \(\ell_i\) does not change the resulting parking function. Thus, the total number of parking functions is given by \[|\mathop{\mathrm{PF}}_n|=\sum_{\ell\in\mathcal{L}_n}\frac{n!}{\prod\limits_{i=1}^{n}(\ell_i+1)!} .\] Similarly, denoting the set of prime Łukasiewicz paths by \(\mathcal{L}'_n,\) we have \[|\mathop{\mathrm{PPF}}_n|=\sum_{\ell\in\mathcal{L}'_n}\frac{n!}{\prod\limits_{i=1}^{n}(\ell_i+1)!}.\]
We now define the descent, ascent, and tie set of a labeled Łukasiewicz path.
Definition 6. Let \(L=(\ell,\mathcal{B})\) be a labeled Łukasiewicz path of length \(n\) with \(\ell=(\ell_1,\ell_2,\ldots,\ell_n)\) and \(\mathcal{B}=(\beta_1,\beta_2,\ldots,\beta_n)\). We define the descent, ascent, and tie set of \(L\) as follows: \[\begin{align} \mathop{\mathrm{Tie}}(L)&=\{i\in[n-1]:i,i+1\in\beta_j for some j\},\\ \mathop{\mathrm{Des}}(L)&=\{i\in[n-1]:i\in \beta_j and i+1\in \beta_m with m<j\},\\ \mathop{\mathrm{Asc}}(L)&=\{i\in[n-1]:i\in \beta_j and i+1\in \beta_m with m>j\}. \end{align}\]
We illustrate 6 in the following example.
Example 7. Consider the labeled Łukasiewicz path \[L=((2,0,1,0,-1,0,-1,-1),(\{2,4,6\},\{1\},\{3,5\},\{8\},\emptyset,\{7\},\emptyset,\emptyset)),\] which is illustrated in 2. The descent, ascent and tie sets of \(L\) are as follows: \[\begin{align} \mathop{\mathrm{Des}}(L)&=\{1,3,5,7\},\\ \mathop{\mathrm{Asc}}(L)&=\{2,4,6\},\\ \mathop{\mathrm{Tie}}(L)&=\emptyset. \end{align}\]
Notice that these sets agree with the descent, ascent, and tie set of the corresponding parking function \(\alpha=(2,1,3,1,3,1,6,4)\) of \(L\).
The observation made at the end of this example holds in general: the descent set of a labeled Łukasiewicz path coincides with the descent set of the corresponding parking function. First recall from 5 that, for a labeled Łukasiewicz path \(L=(\ell,\mathcal{B})\) of length \(n\), \(\alpha_L\) is the permutation arising from ordering the elements of each \(\beta_j\) in increasing order for \(j \in [n]\).
Proposition 6. The descent set of the parking function corresponding to a labeled Łukasiewicz path \(L=(\ell, \mathcal{B})\) is given by the inverse descent set of \(\alpha_L\) (descent set of \(\alpha_L^{-1}\)).
Proof. Let \(\alpha\) be the parking function corresponding to \(L\). By definition, \(\alpha_k = m\) if and only if \(k \in \beta_m\). Thus, \(\alpha\) has a descent at \(i\) exactly when \(i \in \beta_j\) and \(i+1 \in \beta_m\) for some \(m < j\), which is precisely the condition for \(L\) to have a descent at \(i\).
Since the elements of each \(\beta_j\) are listed in increasing order, the condition \(i \in \beta_j\) and \(i+1 \in \beta_m\) with \(m < j\) is equivalent to \(i+1\) appearing before \(i\) in \(\alpha_L\). That is, \(\alpha_L^{-1}(i) > \alpha_L^{-1}(i+1)\), meaning \(i\) is an inverse descent of \(\alpha_L\). ◻
Remark 6. As with descent sets, the ascent set of a labeled Łukasiewicz path and its corresponding parking function coincide. However, while in 6 we recover descents via \(\alpha_L^{-1}\), both ascents and ties in \(\alpha_L\) contribute to inverse ascents: \[\mathop{\mathrm{Asc}}(\alpha_L^{-1})=\mathop{\mathrm{Asc}}(\alpha)\,\cup\,\mathop{\mathrm{Tie}}(\alpha).\] Take, for example, \(\alpha_L=(1,2,6,4,3,5,8,7).\) Here \(\mathop{\mathrm{Des}}(L)=\{3,5,7\},\) \(\mathop{\mathrm{Asc}}(L)=\{2,4,6\},\) and \(\mathop{\mathrm{Tie}}(L)=\{1\},\) while ascent set of \(\alpha_L^{-1}=\{1, 2, 4, 6\}.\)
We conclude this section by noting that all of these results generalize to prime parking functions via prime Łukasiewicz paths.
5 \(\ell\)-forward differences↩︎
Denote the set of prime parking functions of length \(n\) by \(\mathop{\mathrm{PPF}}_n\). We use the circular rotation construction, due to Kalikow [3], to choose a prime parking function uniformly at random.
Pick at random an element \(\pi_0 \in (\mathbb{Z}/(n-1)\mathbb{Z})^n\), where the equivalence class representatives are taken in \(1,2, \dots, n-1\).
Let \((1,1, \dots, 1)\) be a vector of length \(n\). There is exactly one value of \(i \in \{0,1, \dots, n-2\}\), such that \(\pi=\pi_0+i(1,1, \dots, 1)\) (modulo \(n-1\)) is a prime parking function.
Thus, a random prime parking function can be generated by assigning \(n\) cars’ preferences independently on a circle of length \(n-1\) and then applying circular rotation. As an example, for \(n=4\) take \(\pi_0=(2,3,3,2).\) The unique parking function of the form \(\pi=\pi_0+i(1,1,1,1)\) is given by \((1,2,2,1)=(2,3,3,2)+2(1,1,1,1) \bmod{3}.\) For applications of this circular rotation perspective on parking functions, see Stanley and Yin [14].
Given a tuple \(\boldsymbol{x}=(x_1,x_2,\ldots,x_n)\), we say \(\boldsymbol{x}\) has an \(\ell\)-forward difference at \(i\) if \(x_{i+1}-x_{i}=\ell\pmod{n-1}\), for \(i=1,2,\ldots, n-1\) and \(\ell=0,1,\ldots, n-2\). Note, the \(0\)-forward differences are the ties of the parking function. We denote the number of \(\ell\)-forward differences in a parking function \(\pi\) by \(\Delta_{\ell} f(\pi).\)
Proof. We employ the circular rotation construction described above. For \(1\leq i\leq n-1\), note that if the \((i+1)\)th car prefers the spot that is (clockwise) \(\ell\)-distance away from that of the preference of the \(i\)th car, which happens with probability \(1/(n-1)\), then the count for \(\ell\)-distance adds 1. Otherwise, with probability \((n-2)/(n-1)\), the count stays the same.
Since the number of prime parking functions of length \(n\) is \((n-1)^{n-1}\), it follows that the number of prime parking functions of length \(n\) with exactly \(k\) \(\ell\)-forward differences is \(a_k=(n-1)^{n-1}\binom{n-1}{k}\left(\frac{1}{n-1}\right)^k\left(\frac{n-2}{n-1}\right)^{n-1-k}.\) Thus, \[\begin{align} \sum_{\pi \in \mathop{\mathrm{PPF}}_n} q^{\Delta_{\ell} f(\pi)}&=\sum_{k=0}^{n-1}a_kq^k=(n-1)^{n-1} \left(q\frac{1}{n-1}+\frac{n-2}{n-1}\right)^{n-1} =(q+n-2)^{n-1}.\qedhere \end{align}\] ◻
Using this generating function for the total number of \(\ell\)-forward differences in prime parking functions of length \(n\), we can calculate the expected number of descents \(\mathbb{E}[\mathrm{des}(\pi)|\pi\in\mathop{\mathrm{PPF}}_n].\)
Corollary 2. Take any integer \(\ell \in [0, n-2]\). Then we have \[\mathbb{E}[\Delta_{\ell} f(\pi)|\pi\in \mathop{\mathrm{PPF}}_n]=1.\] Moreover, \[\mathbb{E}[{\mathrm{des}}(\pi)|\pi\in\mathop{\mathrm{PPF}}_n]=\mathbb{E}[\mathrm{asc}(\pi)|\pi\in\mathop{\mathrm{PPF}}_n]=\frac{n-2}{2}.\]
Proof. Recall that \[\mathbb{E}[\Delta_{\ell} f(\pi)|\pi\in \mathop{\mathrm{PPF}}_n]= \frac{\sum_{\pi \in \mathop{\mathrm{PPF}}_n} \Delta_{\ell} f(\pi)}{|\mathop{\mathrm{PPF}}_n|}.\] We can use [prop:q95l-des] to calculate the expected number of \(\ell\)-forward differences. Differentiating both sides of \[\sum_{\pi\in\mathop{\mathrm{PPF}}_n}q^{\Delta_{\ell} f(\pi)}=(q+n-2)^{n-1},\] we have \[\sum_{\pi\in\mathop{\mathrm{PPF}}_n}\Delta_{\ell} f(\pi)q^{(\Delta_{\ell} f(\pi)) -1}=(n-1)(q+n-2)^{n-2}.\] Evaluating at \(q=1,\) \[\sum_{\pi\in\mathop{\mathrm{PPF}}_n}\Delta_{\ell} f(\pi)=(n-1)^{n-1}.\] Dividing by the total number of prime parking functions, we find \(\mathbb{E}[\Delta_{\ell} f(\pi)|\pi\in \mathop{\mathrm{PPF}}_n]=1\).
Given \(\pi=(\pi_1,\pi_2,\ldots,\pi_n)\in \mathop{\mathrm{PPF}}_n\), each \((\pi_i,\pi_{i+1})\) pair corresponds to an \(\ell\)-forward difference for some value of \(\ell\). When \(\ell=0\), we have \((\pi_i,\pi_{i+1})\) is a tie. When \(\ell\not=0\), \((\pi_i,\pi_{i+1})\) is either an ascent or a descent. Let \(\hat{\pi}\in \mathop{\mathrm{PPF}}_n\) be the reverse parking function, \(\hat{\pi}=(\pi_n,\ldots, \pi_2,\pi_1).\) Each ascent of \(\pi\) corresponds to a descent of \(\hat{\pi}\), and similarly, each descent to an ascent. Note that in the case \(\pi=\hat{\pi},\) \(\mathrm{des}(\pi)=\mathrm{asc}(\pi).\) Thus \[\sum_{\ell\not=0}\sum_{\pi\in\mathop{\mathrm{PPF}}_n}\Delta_{\ell} f(\pi)=\sum_{\pi\in\mathop{\mathrm{PPF}}_n}\mathrm{des}(\pi)+\sum_{\pi\in\mathop{\mathrm{PPF}}_n}\mathrm{asc}(\pi)=2\sum_{\pi\in\mathop{\mathrm{PPF}}_n}\mathrm{des}(\pi),\] and \[\mathbb{E}[\mathrm{des}(\pi)|\pi\in\mathop{\mathrm{PPF}}_n]=\frac{\sum_{\pi\in\mathop{\mathrm{PPF}}_n}\mathrm{des}(\pi)}{|\mathop{\mathrm{PPF}}_n|}=\frac{1}{2}\frac{\sum_{\ell=1}^{n-2}(n-1)^{n-1}}{(n-1)^{n-1}}=\frac{n-2}{2}.\qedhere\] ◻
6 Tie sets and quasisymmetric functions↩︎
In this section, we prove a link between sums of Gessel’s quasisymmetric functions indexed by tie sets and sums of Schur functions. Let \(S_{\Delta_{\ell}}(\pi)\) denote the set of indices where the prime parking function \(\pi\) has an \(\ell\)-forward difference. Thus \(S_{\Delta_{0}}(\pi)=\mathop{\mathrm{Tie}}(\pi).\) We start with the following count of prime parking functions with a given \(\ell\)-forward difference set, which is used in proving the main result of this section.
Theorem 7. Given a set \(S\subseteq[n-1]\), and fixed \(0\leq \ell\leq n-2,\) the number of prime parking functions \(\pi\in\mathop{\mathrm{PPF}}_n\) with \(S_{\Delta_{\ell}}(\pi)=S\) is \[|\{\pi \in \mathop{\mathrm{PPF}}_n : S_{\Delta_{\ell}}(\pi)=S\}| =(n-2)^{n-1-|S|}.\]
Proof. Consider the mapping \(\mathcal{L}:\mathop{\mathrm{PPF}}_n\rightarrow \left(\mathbb{Z}/(n-1)\mathbb{Z}\right)^{n-1}\) given by \[\mathcal{L}(\pi)=(\mathcal{L}_1,\mathcal{L}_2,\ldots,\mathcal{L}_{n-1})=(\pi_2-\pi_1, \pi_3-\pi_2,\ldots,\pi_n-\pi_{n-1})\pmod{n-1},\] i.e., \(\mathcal{L}_i\) is the \(\ell\)-forward difference of \(\pi\) at \(i.\) A consequence of Kalikow’s construction is that this mapping is a bijection. Given an arbitrary \(\mathcal{L}\in \left(\mathbb{Z}/(n-1)\mathbb{Z}\right)^{n-1},\) let \[\pi_0=(1,1+\mathcal{L}_1,1+\mathcal{L}_1+\mathcal{L}_2,\ldots,1+\sum_{j=1}^{n-1}\mathcal{L}_j)\pmod{n-1}.\] The prime parking function \(\pi\) of the form \(\pi_0+i(1,1,\ldots,1)\pmod{n-1}\) is the unique element of \(\mathop{\mathrm{PPF}}_n\) with \(\mathcal{L}(\pi)=\mathcal{L}.\)
Given a set \(S\subseteq [n-1],\) the set of \(\pi\in\mathop{\mathrm{PPF}}_n\) with \(S_{\Delta_{\ell}}(\pi)=S\) is precisely the set of prime parking functions that satisfy \(\mathcal{L}(\pi)_i=\ell\) for all \(i\in S\) and \(\mathcal{L}(\pi)_i\not=\ell\) for all \(i\not\in S.\) As there are exactly \((n-2)^{n-1-|S|}\) such \(\mathcal{L}\in \left(\mathbb{Z}/(n-1)\mathbb{Z}\right)^{n-1},\) it follows that \[|\{\pi \in \mathop{\mathrm{PPF}}_n : S_{\Delta_{\ell}}(\pi)=S\}| =(n-2)^{n-1-|S|}.\qedhere\] ◻
We are now ready to prove the following result on the sum, over all prime parking functions of length \(n,\) of quasisymmetric functions indexed by tie sets. The corresponding formula in the context of (classical) parking functions was derived earlier by Celano in [15].
Theorem 8. For \(n\geq 1\), \[\sum_{\pi\in\mathop{\mathrm{PPF}}_n}F_{n,\mathop{\mathrm{Tie}}(\pi)} =\sum_{i=1}^n (n-2)^{i-1}s_{(i,1^{n-i})}.\]
Here \(F_{n,S}\) is the Gessel’s quasisymmetric function defined as \[F_{n,S}= \sum_{\substack{1\leq b_1\leq \cdots\leq b_n \\ \\i\in S\Rightarrow b_i<b_{i+1}}} x_{b_1}\cdots x_{b_n},\] where \(S\subseteq[n-1],\) and \(s_{(i,1^{n-i})}\) is the Schur function corresponding to the partition \((i,1^{n-i})\).
We first illustrate this result with an example and then present the proof.
Example 8. When \(n=3\), \(\mathop{\mathrm{PPF}}_3=\{111,112,121,211\}\) and we have \[\begin{align} &\mathop{\mathrm{Tie}}(111)=\{1,2\}\rightarrow F_{3,\{1,2\}}(x_1, x_2, x_3)=x_1x_2x_3\tag{21}\\ &\mathop{\mathrm{Tie}}(121)=\emptyset\rightarrow \notag \\ & F_{3,\emptyset}(x_1, x_2, x_3)=x_1^3+x_2^3+x_3^3+x_1^2x_2+x_1x_2^2+x_1^2x_3+x_1x_3^2+x_2^2x_3+x_2x_3^2+x_1x_2x_3\tag{22}\\ &\mathop{\mathrm{Tie}}(112)=\{1\}\rightarrow F_{3,\{1\}}(x_1, x_2, x_3)=x_1x_2^2+x_1x_3^2+x_2x_3^2+x_1x_2x_3\tag{23}\\ &\mathop{\mathrm{Tie}}(211)=\{2\}\rightarrow F_{3,\{2\}}(x_1, x_2, x_3)=x_1^2x_2+x_1^2x_3+x_2^2x_3+x_1x_2x_3.\tag{24} \end{align}\] Taking the sum of 21 24 yields \[\begin{gather} \label{eqLHS} \sum_{\pi\in\mathop{\mathrm{PPF}}_n}F_{n,\mathop{\mathrm{Tie}}(\pi)} (x_1, x_2, x_3)\\ =x_1^3+x_2^3+x_3^3+2(x_1^2x_2+x_1x_2^2+x_1^2x_3+x_1x_3^2+x_2^2x_3+x_2x_3^2)+4x_1x_2x_3. \end{gather}\tag{25}\]
Now for the Schur functions side of the equation in 8: \[s_{(1,1^2)}+s_{(2,1)}+s_{(3)}.\] We want to construct all of the fillings which have numbers weakly increasing along the rows and strictly increasing down the columns of the Young diagram. For \(s_{(2,1)}(x_1, x_2, x_3)\) we have the following fillings: \[\begin{ytableau} 1 & 1 \\ 2\\ \end{ytableau},~\begin{ytableau} 1 & 1 \\ 3\\ \end{ytableau},~\begin{ytableau} 1 & 2 \\ 2\\ \end{ytableau},~\begin{ytableau} 1 & 2 \\ 3\\ \end{ytableau},~\begin{ytableau} 1 & 3 \\ 2\\ \end{ytableau} ,~ \begin{ytableau} 1 & 3\\ 3\\ \end{ytableau},~ \begin{ytableau} 2 & 2 \\ 3\\ \end{ytableau},~ \begin{ytableau} 2 & 3 \\ 3\\ \end{ytableau}.\] Now for each filling we construct a monomial, and this yields: \[\begin{align} \label{s21} s_{(2,1)}(x_1, x_2, x_3)=x_1^2x_2+x_1^2x_3+x_1x_2^2+2x_1x_2x_3+x_1x_3^2+x_2^2x_3+x_2x_3^2. \end{align}\tag{26}\] Similarly, we can construct \(s_{(1^3)}(x_1, x_2, x_3)\) from the filling \[\begin{ytableau} 1 \\ 2\\ 3\\ \end{ytableau}\] and so \[\begin{align} \label{s111} s_{(1^3)}(x_1, x_2, x_3)&=x_1x_2x_3. \end{align}\tag{27}\] Lastly, \(s_{(3)}(x_1, x_2, x_3)\) arises from the Young tableau: \[\begin{ytableau} 1 & 1 &1 \end{ytableau}, ~\begin{ytableau} 1 & 1 &2 \end{ytableau},~ \begin{ytableau} 1 & 1 &3 \end{ytableau},~\begin{ytableau} 1 & 2 &2 \end{ytableau}, ~\begin{ytableau} 1 & 2 &3 \end{ytableau},\] \[\begin{ytableau} 1 & 3 &3 \end{ytableau}, ~\begin{ytableau} 2 & 2 &2 \end{ytableau}, ~\begin{ytableau} 2 & 2 &3 \end{ytableau}, ~\begin{ytableau} 2 & 3 &3 \end{ytableau},~ \begin{ytableau} 3 & 3 &3 \end{ytableau}.\] Hence \[\begin{align} \label{s3} s_{(3)}(x_1, x_2, x_3)&=x_1^3+x_1^2x_2+x_1^2x_3+x_1x_2^2+x_1x_2x_3+x_1x_3^2+x_2^3+x_2^2x_3+x_2x_3^2+x_3^3. \end{align}\tag{28}\] Summing 26 , 27 , and 28 yields the right-hand side of the equation in 8: \[\begin{gather} \label{eqRHS} \sum_{i=1}^{3}(3-2)^{i-1}s_{(i,1^{n-i})}(x_1, x_2, x_3) \\ =x_1^3+x_2^3+x_3^3+2(x_1^2x_2+x_1x_2^2+x_1^2x_3+x_1x_3^2+x_2^2x_3+x_2x_3^2)+4x_1x_2x_3. \end{gather}\tag{29}\] Now note that the sum in 29 agrees with the sum in 25 . This confirms 8 for \(n=3\).
Proof of 8. The expansion of a Schur function into fundamental quasisymmetric functions is a well-known consequence of Stanley’s theory of \(P\)-partitions [3]. It is known that \[s_{(i,1^{n-i})}=\sum_{\substack{S\subseteq [n-1], |S|=n-i}}F_{n,S}.\] So, we have \[\label{eq:schur} \sum_{i=1}^n (n-2)^{i-1}s_{i,1^{n-i}}= \sum_{i=1}^n (n-2)^{i-1} \sum_{S\subseteq [n-1], |S|=n-i}F_{n,S}.\tag{30}\] By change of variables \(j=n-i\), we can rewrite 30 as follows: \[\begin{align} \sum_{j=0}^{n-1} (n-2)^{n-j-1} \sum_{S\subseteq [n-1], |S|=j} F_{n,S} =&\sum_{j=0}^{n-1} \sum_{S\subseteq [n-1], |S|=j} F_{n,S} ~|\pi \in \mathop{\mathrm{PPF}}_n : \mathop{\mathrm{Tie}}(\pi)=S|\\ =&\sum_{\pi \in \mathop{\mathrm{PPF}}_n} F_{n,\mathop{\mathrm{Tie}}(\pi)}, \end{align}\] where the first equality follows by 7. ◻
The following results are generalizations of [prop:q95l-des], [{thm:Tie95Set95count}], and 8.
Proposition 9. Let \(m \neq \ell\). Then we have \[\sum_{\pi \in \mathop{\mathrm{PPF}}_n} q^{ \Delta_{\ell} f(\pi)} t^{\Delta_{m} f(\pi)} = (q+t+n-3)^{n-1}.\]
Proof. The proof applies the circular rotation idea as in the proof of [prop:q95l-des]. We note that the number of prime parking functions of length \(n\) with exactly \(j\) \(\ell\)-forward differences and \(k\) \(m\)-forward differences is \(a_{j,k}=(n-1)^{n-1}\binom{n-1}{j, k}\left(\frac{1}{n-1}\right)^{j+k}\left(\frac{n-3}{n-1}\right)^{n-1-j-k}.\) Thus, \[\begin{align} \sum_{\pi \in \mathop{\mathrm{PPF}}_n} q^{ \Delta_{\ell} f(\pi)} t^{\Delta_{m} f(\pi)} &=\sum_{j=0}^{n-1} \sum_{k=0}^{n-1-j} a_{j, k} q^j t^k=(n-1)^{n-1} \left(q\frac{1}{n-1}+t\frac{1}{n-1}+\frac{n-3}{n-1}\right)^{n-1} \\ &=(q+t+n-3)^{n-1}.\qedhere \end{align}\] ◻
Theorem 10. Let \(m \neq \ell\). Given sets \(S\subseteq[n-1]\) and \(T\subseteq[n-1]\), and fixed \(0\leq m, \ell\leq n-2,\) the number of prime parking functions \(\pi\in\mathop{\mathrm{PPF}}_n\) with \(S_{\Delta_{m}}(\pi)=S\) and \(S_{\Delta_{\ell}}(\pi)=T\) is \[|\{\pi \in \mathop{\mathrm{PPF}}_n : S_{\Delta_{m}}(\pi)=S, S_{\Delta_{\ell}}(\pi)=T\}| =(n-3)^{n-1-|S|-|T|}.\]
Proof. The proof follows a similar line of reasoning as in the proof of [{thm:Tie95Set95count}]. We note that the set of \(\pi\in\mathop{\mathrm{PPF}}_n\) with \(S_{\Delta_{m}}(\pi)=S\) and \(S_{\Delta_{\ell}}(\pi)=T\) is precisely the set of prime parking functions that satisfy \(\mathcal{L}(\pi)_i=m\) for all \(i\in S\), \(\mathcal{L}(\pi)_j=\ell\) for all \(j\in T\), and \(\mathcal{L}(\pi)_k\not=m,\ell\) for all \(k\not\in S \cup T.\) ◻
Proof. We proceed as in the proof of 8. Observe that \[\label{eq:schur95mixed1} \sum_{i=1}^n q^{n-i}(n-2)^{i-1} s_{(i,1^{n-i})}= \sum_{i=1}^n q^{n-i}(n-2)^{i-1} \sum_{S\subseteq [n-1], |S|=n-i}F_{n,S}.\tag{31}\] By change of variables \(j=n-i\), we can rewrite 31 as follows: \[\begin{align} \sum_{j=0}^{n-1} q^j (n-2)^{n-j-1} \sum_{S\subseteq [n-1], |S|=j} F_{n,S} =&\sum_{j=0}^{n-1} \sum_{S\subseteq [n-1], |S|=j} q^{|S|} F_{n,S} ~|\pi \in \mathop{\mathrm{PPF}}_n : S_{\Delta_{\ell}}(\pi)=S|\\ =&\sum_{\pi \in \mathop{\mathrm{PPF}}_n} q^{\Delta_{\ell} f(\pi)} F_{n,S_{\Delta_{\ell}}(\pi)}, \end{align}\] where the first equality follows by 7.
Similarly, \[\label{eq:schur95mixed2} \sum_{i=1}^n (q+n-3)^{i-1}s_{i,1^{n-i}}= \sum_{i=1}^n (q+n-3)^{i-1} \sum_{S\subseteq [n-1], |S|=n-i}F_{n,S}.\tag{32}\] By change of variables \(j=n-i\), we can rewrite 32 as follows: \[\begin{align} &\sum_{j=0}^{n-1} (q+n-3)^{n-j-1} \sum_{S\subseteq [n-1], |S|=j} F_{n,S}\\ =&\sum_{j=0}^{n-1} \sum_{k=0}^{n-j-1} \binom{n-j-1}{k} q^k (n-3)^{n-j-k-1} \sum_{S\subseteq [n-1], |S|=j} F_{n,S}\\ =&\sum_{j=0}^{n-1} \sum_{k=0}^{n-j-1} \sum_{\substack{S\subseteq [n-1] \\ |S|=j}} \sum_{\substack{T \subseteq [n-1]\setminus S \\ |T|=k}} q^{|T|} F_{n,S} ~|\pi \in \mathop{\mathrm{PPF}}_n : S_{\Delta_{m}}(\pi)=S, S_{\Delta_{\ell}}(\pi)=T| \\ =&\sum_{\pi \in \mathop{\mathrm{PPF}}_n} q^{ \Delta_{\ell} f(\pi)} F_{n, S_{\Delta_{m}}(\pi)}, \end{align}\] where the first equality uses the binomial expansion and the second equality follows by 10. ◻
7 Conclusions and future work↩︎
Since the inception of the parking problem, researchers have found deep connections between parking functions and many other combinatorial structures, leading to applications in probability and statistics, algebraic geometry, interpolation theory, and representation theory. As pointed to in the introduction, the study of parking functions has found wide applications in data science through the alternative formulation of the parking problem as a hashing problem. Via this angle, the average displacement that we derived in prime parking functions provides insight into the efficiency of storing and retrieving data in the system. We study parking functions from multiple lenses, concentrating in particular on a subclass of parking functions termed prime parking functions. We expect that similar techniques may be extended to other subclasses of parking functions such as Stirling parking functions and tiered parking functions. In the last section, we display the intriguing link between parking functions and (quasi)symmetric functions. We hope to explore the interconnection between parking functions and other related topics in combinatorics in future work.
Acknowledgements↩︎
The authors benefited from participation in the Collaborative Workshop in Algebraic Combinatorics at the Institute for Advanced Study in June 2025. P. E. Harris and M. Yin were supported in part by an award from the Simons Travel Support for Mathematicians program. S. Kara was supported by NSF Grant DMS-2418805.