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:

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.

  1. [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

    ParkingFunction.IsParkingFunctionsource
    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

    RealRooted.ParkingFunctions.parkingDescentPolynomialsource
    noncomputable def parkingDescentPolynomial : ℕ → ℝ[X]
      | 0 => 1
      | n + 1 => (parkingFunctions (n + 1)).genPoly fun w => (List.ofFn w).descentCount
  • Descent polynomial of tieless parking functions

    RealRooted.ParkingFunctions.tielessParkingDescentPolynomialsource
    def tielessParkingDescentPolynomial : ℕ → ℤ[X]
      | 0 => 1
      | n + 1 => (tielessParkingFunctions (n + 1)).genPoly fun w => (List.ofFn w).descentCount
  • Weak left peak polynomial of parking functions

    RealRooted.ParkingFunctions.parkingWeakLeftPeakPolynomialIntsource
    def parkingWeakLeftPeakPolynomialInt (n : ℕ) : ℤ[X] :=
      ∑ w ∈ parkingFunctions n, X ^ wordWeakLeftPeakNumber w

Theorems

  • Parking function descent polynomials are real-rootedMain result

    RealRooted.ParkingFunctions.parkingDescentPolynomial_splitssourcestatement on symmetricfunctions.com
    theorem parkingDescentPolynomial_splits (n : ℕ) :
        (parkingDescentPolynomial n).Splits
  • Pollak's cyclic action: descents of parking functions and of words

    RealRooted.ParkingFunctions.parkingDescentPolynomialInt_succ_nsmulsource
    theorem parkingDescentPolynomialInt_succ_nsmul
        (n : ℕ) :
        (n + 1) • parkingDescentPolynomialInt n =
          literalWordDescentPolynomialInt (n + 1) n
  • Tieless parking function descent polynomials are real-rooted

    RealRooted.ParkingFunctions.map_tielessParkingDescentPolynomial_splitssource
    theorem map_tielessParkingDescentPolynomial_splits (n : ℕ) :
        ((tielessParkingDescentPolynomial n).map
          (Int.castRingHom ℝ)).Splits
  • Tieless descents and a Brändén–Vecchi Chow polynomial

    RealRooted.ParkingFunctions.succ_nsmul_tielessParkingDescentPolynomial_eq_chowPolynomialsource
    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

    RealRooted.ParkingFunctions.map_parkingWeakLeftPeakPolynomialInt_splitssource
    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.