Parking functions
The descent polynomial, the tieless descent polynomial and the weak left peak polynomial of parking functions of length $n$ are real-rooted.
Results
A parking function of length $n$ [DH17] is a word $w=w_0\dotsm w_{n-1}$ with letters in $\{0,\dots,n-1\}$ such that for every $k\le n$ at least $k$ letters are smaller than $k$. We set $\operatorname{des}(w)=\#\{i:w_i>w_{i+1}\}$ and $\operatorname{wlpk}(w)=\#\{i\ge1:w_{i-1}\le w_i>w_{i+1}\}$, with positions numbered from $0$. A parking function is tieless if no two adjacent letters are equal.
Theorem. For every $n\ge0$, each of the following polynomials over parking functions $w$ of length $n$ is real-rooted:
- $\sum_w x^{\operatorname{des}(w)}$;
- $\sum_w x^{\operatorname{des}(w)}$ over tieless parking functions;
- $\sum_w x^{\operatorname{wlpk}(w)}$.
Proposition. For $n\ge0$, $(n+1)$ times the descent polynomial of the parking functions of length $n$ equals the descent polynomial of all words of length $n$ over an alphabet of size $n+1$ (Pollak's cyclic action). Also, $(n+1)$ times the tieless descent polynomial equals the Brändén–Vecchi Chow polynomial of degree $n$ of the elementary Toeplitz matrix with $n+1$ entries equal to $1$.
References
[DH17]. The Chow polynomials appear on the Brändén–Vecchi page.
- [DH17] Persi Diaconis & Angela Hicks. Probabilizing parking functions. Advances in Applied Mathematics, 89, 125-155, 2017.
BibTeX
@article{DiaconisHicks2017,
author = {Persi Diaconis and Angela Hicks},
title = {Probabilizing parking functions},
journal = {Advances in Applied Mathematics},
volume = {89},
pages = {125--155},
year = {2017},
doi = {10.1016/j.aam.2017.05.004},
url = {https://doi.org/10.1016/j.aam.2017.05.004},
eprint = {1611.09821}
}
≔ Definitions
Parking functions
def IsParkingFunction (w : Fin n → Fin n) : Prop :=
∀ k : Fin (n + 1),
k.val ≤ (Finset.univ.filter fun i => (w i).val < k.val).card
Descent polynomial of parking functions
noncomputable def parkingDescentPolynomial : ℕ → ℝ[X]
| 0 => 1
| n + 1 => (parkingFunctions (n + 1)).genPoly fun w => (List.ofFn w).descentCount
Descent polynomial of tieless parking functions
def tielessParkingDescentPolynomial : ℕ → ℤ[X]
| 0 => 1
| n + 1 => (tielessParkingFunctions (n + 1)).genPoly fun w => (List.ofFn w).descentCount
Weak left peak polynomial of parking functions
def parkingWeakLeftPeakPolynomialInt (n : ℕ) : ℤ[X] :=
∑ w ∈ parkingFunctions n, X ^ wordWeakLeftPeakNumber w
⊢ Theorems
Parking function descent polynomials are real-rootedMain result
theorem parkingDescentPolynomial_splits (n : ℕ) :
(parkingDescentPolynomial n).Splits
Pollak's cyclic action: descents of parking functions and of words
theorem parkingDescentPolynomialInt_succ_nsmul
(n : ℕ) :
(n + 1) • parkingDescentPolynomialInt n =
literalWordDescentPolynomialInt (n + 1) n
Tieless parking function descent polynomials are real-rooted
theorem map_tielessParkingDescentPolynomial_splits (n : ℕ) :
((tielessParkingDescentPolynomial n).map
(Int.castRingHom ℝ)).Splits
Tieless descents and a Brändén–Vecchi Chow polynomial
theorem succ_nsmul_tielessParkingDescentPolynomial_eq_chowPolynomial
(n : ℕ) :
(n + 1) • tielessParkingDescentPolynomial n =
BrandenVecchi.chowPolynomial
(BrandenVecchi.finiteElementaryToeplitz
(R := ℤ) (fun _ : Fin (n + 1) => 1)) n
Parking function weak left peak polynomials are real-rooted
theorem map_parkingWeakLeftPeakPolynomialInt_splits (n : ℕ) :
((parkingWeakLeftPeakPolynomialInt n).map
(Int.castRingHom ℝ)).Splits
Lean source RealRooted/Challenges/Combinatorial/ParkingFunctions.lean at revision d6670742. Formalized 2026-09-13.