Parking functions

2026-08-23 Improve this page

#Parking functions

Definition

Let $(a_1, a_2, \dotsc, a_n)$ be a sequence of positive integers. We think of these as $n$ cars, where $a_i$ is the preferred parking spot for car $i.$ The parking spots are labeled $1, 2, \dotsc, n$ and the $n$ cars attempt to park according to the following rules:

Car $i$ attempts to park in spot $a_i .$
If that spot is taken, it proceeds to the next available empty spot to the right.

If all cars can park successfully, then the sequence $(a_1, \dotsc, a_n)$ is a parking function.

There are $(n+1)^{n-1}$ parking functions in total; see R. Pyke [Pyk59] and A. Konheim and B. Weiss [KW66]. Henry O. Pollak gave a neat proof for this formula by adding an extra $(n+1)$th spot; see J. Riordan [Rio69]. N. Wallace studies Schurifications of parking-function formulas through bijections with Young tableaux [Wal20].

Theorem

The sequence $(a_1, \dotsc, a_n)$ of positive integers is a parking function if and only if, when rearranged in nondecreasing order $(b_1 \leq b_2 \leq \dotsb \leq b_n),$ it satisfies \[b_i \leq i \quad \text{for all } i = 1, \dotsc, n.\]

Proof

First direction: If $(a_1, \dotsc, a_n)$ is a parking function, then $b_i \leq i$ for all $i.$

For any $k,$ there must be at least $k$ cars preferring spots among $1,2,\dotsc,k.$ This immediately gives that $b_k \leq k$ for all $k.$

Conversely: If $b_i \leq i$ for all $i = 1,2,\dotsc,n,$ then $(a_1, \dotsc, a_n)$ is a parking function.

Suppose this statement is not correct. We can then (by minimal counterexample) assume the first $n-1$ cars manage to park, but the last car fails to park. Then there must be some (smallest) $j$ such that spots $\{j,j+1,\dotsc,n\}$ are occupied after the first $n-1$ cars, and $a_n \geq j.$

Since the spot $j-1$ is empty, we know that there are $(n-j+1)+1$ cars that want to park at spot at least $j.$

But then, only (the remaining) $j-2$ cars want to park at spots $\{1,2,\dotsc,j-1\}.$ This implies that $b_{j-1} \gt{} j-1,$ violating our assumption.

The number of weakly increasing parking functions is given by the Catalan numbers. P. E. Harris, J. C. M. Mori, and A. N. Wilson give a Pollak-style proof of this enumeration [HMW25].

The descent polynomial \[D_n(t) \coloneqq \sum_{a\in\mathrm{PF}_n}t^{\des(a)}\] is real-rooted. Its coefficients form A333829; see parking-function descents for the descent-set transfer to words and the short interlacing proof.

#Bijection with labeled Dyck paths

There is a classical bijection between parking functions of length $n$ and labeled Dyck paths of order $n.$ A labeled Dyck path is a Dyck path from $(0,0)$ to $(n,n)$ where the $n$ North steps are labeled with $1,2,\dotsc,n,$ and labels within each column are arranged in strictly decreasing order from top to bottom.

Given a parking function $(a_1, \dotsc, a_n),$ place label $i$ in column $a_i.$ Within each column, arrange labels in decreasing order, then connect them with east steps to form a Dyck path. Conversely, reading which column each label appears in recovers the parking function; see [Yan15] and [Hag07] for details.

#Preference functions and square paths

A preference function of size $n$ is a map $f:[n]\to[n].$ Thus every parking function is a preference function, but not conversely. The same column construction sends $f$ to a path in the $n\times n$ square, without requiring the path to stay above the main diagonal. In column $i,$ write the labels in $f^{-1}(i),$ increasing from bottom to top, and draw the unique North-East path whose North steps have the labels immediately to their right. The preference function is a parking function exactly when this path is a Dyck path.

The reading word of a preference function is obtained by reading the cars diagonal by diagonal, from northeast to southwest, and within each diagonal from top to bottom. Equivalently, one first reads the highest diagonals $y=x+r,$ and in each diagonal reads from right to left.

The dinv statistic is the sum of three contributions:

a primary inversion: two cars on the same diagonal, where the left car has smaller label;
a secondary inversion: two cars on adjacent diagonals, where the northwest car has larger label than the southeast car;
the number of cars strictly below the main diagonal $y=x.$

For paths that stay above the diagonal, the last term vanishes and this agrees with the usual parking-function dinv statistic used in the Shuffle theorem.

Example (Reading word and dinv).

Let $f=(5,2,5,2,2,3).$ The nonempty columns are \[f^{-1}(2)=\{2,4,5\},\qquad f^{-1}(3)=\{6\},\qquad f^{-1}(5)=\{1,3\}.\] The corresponding square path is $P=\mathtt{ennneneennee},$ and its reading word is \[\mathrm{rw}(f)=365142.\] Here the cars $5$ and $6$ form a primary inversion, the pairs $\{1,5\}$ and $\{1,6\}$ form secondary inversions, and the car $2$ lies strictly below the main diagonal. Hence $\dinv(f)=1+2+1=4.$

A word preference function is the same square-path object, but with positive integer labels that may repeat globally, still strictly increasing from bottom to top in each column. Its monomial is \[\xvec_g \coloneqq \prod_{\text{cars } c} x_c.\] The standardized reading word is the permutation obtained by ordering smaller labels before larger labels, and breaking ties by their order in the reading word. A word parking function is a word preference function whose supporting path is a Dyck path. This word version is useful because it converts sums in Gessel fundamental quasisymmetric functions into monomial symmetric-function expansions.

#Bijection with rooted labeled trees

A rooted labeled tree is a tree whose vertices are labeled and in which one vertex is distinguished as the root. Since both parking functions and rooted labeled trees on $n+1$ vertices (with root labeled $0$) are counted by $(n+1)^{n-1},$ there exist natural bijections between them.

One such bijection goes via the labeled Dyck path: the root $0$ connects to all cars in the first column, and from each car $i,$ one traces a $45^\circ$ diagonal northeast to find children in subsequent columns, see [Hag07] for this construction.

A more direct bijection is as follows. Given a rooted labeled tree $T$ with vertices $0,1,\dotsc,n$ (root $0$), draw the children of each vertex in increasing order left to right. Read vertices level by level (BFS order) to produce a permutation $\pi$ of $\{1,\dotsc,n\}.$ Orient edges from child to parent. Then define $p_i = 1$ if $i \to 0,$ and $p_i = 1+j$ if $i \to \pi_j.$ This gives a parking function, and the map is invertible.

#Connection with hyperplane arrangements

The Shi arrangement $\mathcal{S}_n$ consists of the hyperplanes \[x_i - x_j = 0 \quad \text{and} \quad x_i - x_j = 1 \qquad \text{for all } 1 \leq i \lt{} j \leq n,\] introduced by J.-Y. Shi in the study of the affine Weyl group of type $A_{n-1}.$

Theorem ([AL99]).

The number of regions of $\mathcal{S}_n$ is $(n+1)^{n-1}.$ Moreover, there is an explicit bijection between regions of $\mathcal{S}_n$ and parking functions on $[n].$

Each parking function $f$ determines a partition of $[n]$ into chains (grouping $i,j$ whenever $f(i)=f(j)$), and these chains are braided into a permutation diagram that encodes a unique Shi region; see [AL99] for the full construction.

#Variations of parking functions

See [CCHJ+21] for many variations of parking functions.

L. Snider and C. Yan study two higher-dimensional generalizations: $U$-parking functions, which arise from Goncharov interpolation polynomials, and $(p,q)$-parking functions, which arise from recurrent configurations in the sandpile model for a complete bipartite graph with a root [SY22]. They show that $(p,q)$-parking functions are a specialization of $U$-parking functions and characterize them by pairs of weakly disjoint lattice paths.

K. Celano, J. Elder, K. P. Hadaway, P. E. Harris, A. Priestley, and G. Udell study inversions in parking functions [CEHH+25]. They obtain a $q$-exponential generating function by symmetric-function methods and by a direct bijection with rooted labeled forests, and extend the analysis to unit interval parking functions. K. Celano, J. Elder, K. P. Hadaway, P. E. Harris, J. L. Martin, A. Priestley, and G. Udell study $\ell$-interval parking functions, where every car has displacement at most $\ell$ [CEHH+25]. They enumerate these functions by inversion, displacement, and major index, and prove a cyclic sieving phenomenon for $1$-interval parking functions with fixed displacement.

P. E. Harris, S. Kara, E. McNicholas, K. Nyman, and M. Yin study statistics of prime parking functions, Łukasiewicz paths, and quasisymmetric functions [HKMN+26].

Bibliography

[AL99]Christos A. Athanasiadis and Svante Linusson. A simple bijection for the regions of the Shi arrangement of hyperplanes. Discrete Mathematics, 204(1–3):27–39, 1999.

.bib

@article{AthanasiadisLinusson1999,
  author  = {Christos A. Athanasiadis and Svante Linusson},
  title   = {A simple bijection for the regions of the {S}hi arrangement of hyperplanes},
  journal = {Discrete Mathematics},
  volume  = {204},
  number  = {1--3},
  pages   = {27--39},
  year    = {1999},
  doi     = {10.1016/S0012-365X(98)00365-3}
}

[CCHJ+21]Joshua Carlson, Alex Christensen, Pamela E. Harris, Zakiya Jones and Andrés Ramos Rodrı́guez. Parking Functions: Choose Your Own Adventure. The College Mathematics Journal, 52(4):254–264, August 2021.

.bib

@article{CarlsonChristensenHarrisJonesRodriguez2021,
  doi = {10.1080/07468342.2021.1943115},
  url2 = {https://doi.org/10.1080/07468342.2021.1943115},
  year = {2021},
  month = aug,
  publisher = {Informa {UK} Limited},
  volume = {52},
  number = {4},
  pages = {254--264},
  author = {Joshua Carlson and Alex Christensen and Pamela E. Harris and Zakiya Jones and Andr{\'{e}}s Ramos Rodr{\'{\i}}guez},
  title = {Parking {F}unctions: {C}hoose {Y}our {O}wn {A}dventure},
  journal = {The College Mathematics Journal}
}

[CEHH+25]Kyle Celano, Jennifer Elder, Kimberly P. Hadaway, Pamela E. Harris, Jeremy L. Martin, Amanda Priestley and Gabe Udell. Statistics on $\ell$-interval parking functions. arXiv:2507.07243, 2025.

.bib

@article{CelanoElderHadawayHarrisMartinPriestleyUdell2025x,
  author = {Kyle Celano and Jennifer Elder and Kimberly P. Hadaway and
    Pamela E. Harris and Jeremy L. Martin and Amanda Priestley and
    Gabe Udell},
  title = {Statistics on {$\ell$}-interval parking functions},
  year = {2025},
  eprint = {2507.07243},
  url = {https://arxiv.org/abs/2507.07243},
  journal = {arXiv e-prints}
}

[CEHH+25]Kyle Celano, Jennifer Elder, Kimberly P. Hadaway, Pamela E. Harris, Amanda Priestley and Gabe Udell. Inversions in parking functions. arXiv:2508.11587, 2025.

.bib

@article{CelanoElderHadawayHarrisPriestleyUdell2025x,
  author = {Kyle Celano and Jennifer Elder and Kimberly P. Hadaway and
    Pamela E. Harris and Amanda Priestley and Gabe Udell},
  title = {Inversions in parking functions},
  year = {2025},
  eprint = {2508.11587},
  url = {https://arxiv.org/abs/2508.11587},
  journal = {arXiv e-prints}
}

[HKMN+26]Pamela E. Harris, Selvi Kara, Erin McNicholas, Kathryn Nyman and Mei Yin. On statistics of prime parking functions, Łukasiewicz paths, and quasisymmetric functions. arXiv:2601.20770, 2026.

.bib

@article{HarrisKaraMcNicholasNymanYin2026x,
  author = {Pamela E. Harris and Selvi Kara and Erin McNicholas and
    Kathryn Nyman and Mei Yin},
  title = {On statistics of prime parking functions, {\L}ukasiewicz paths, and
    quasisymmetric functions},
  year = {2026},
  eprint = {2601.20770},
  url = {https://arxiv.org/abs/2601.20770},
  journal = {arXiv e-prints}
}

[HMW25]Pamela E. Harris, J. Carlos Martínez Mori and Alexander N. Wilson. A Pollak Proof for the Number of Weakly Increasing Parking Functions. arXiv:2511.20796, 2025.

.bib

@article{HarrisMoriWilson2025x,
  author = {Pamela E. Harris and J. Carlos Mart{\'i}nez Mori and
    Alexander N. Wilson},
  title = {A {P}ollak {P}roof for the {N}umber of {W}eakly {I}ncreasing
    {P}arking {F}unctions},
  year = {2025},
  eprint = {2511.20796},
  url = {https://arxiv.org/abs/2511.20796},
  journal = {arXiv e-prints}
}

[KW66]Alan G. Konheim and Benjamin Weiss. An occupancy discipline and applications. SIAM Journal on Applied Mathematics, 14(6):1266–1274, 1966.

.bib

@article{KonheimWeiss1966,
  author  = {Alan G. Konheim and Benjamin Weiss},
  title   = {An occupancy discipline and applications},
  journal = {SIAM Journal on Applied Mathematics},
  volume  = {14},
  number  = {6},
  pages   = {1266--1274},
  year    = {1966},
  doi     = {10.1137/0114101}
}

[Pyk59]Ronald Pyke. The supremum and infimum of the Poisson process. The Annals of Mathematical Statistics, 30(2):568–576, 1959.

.bib

@article{Pyke1959,
  author = {Ronald Pyke},
  title = {The supremum and infimum of the {Poisson} process},
  journal = {The Annals of Mathematical Statistics},
  volume = {30},
  number = {2},
  pages = {568--576},
  year = {1959},
  doi = {10.1214/aoms/1177706269}
}

[Rio69]John Riordan. Ballots and trees. Journal of Combinatorial Theory, 6:408–411, 1969.

.bib

@article{Riordan1969,
  author = {John Riordan},
  title = {Ballots and trees},
  journal = {Journal of Combinatorial Theory},
  volume = {6},
  pages = {408--411},
  year = {1969}
}

[SY22]Lauren Snider and Catherine Yan. $U$-parking functions and $(p,q)$-parking functions. Advances in Applied Mathematics, 134:102309, 2022.

.bib

@article{SniderYan2022,
  author = {Snider, Lauren and Yan, Catherine},
  title = {{$U$}-parking functions and $(p,q)$-parking functions},
  year = {2022},
  journal = {Advances in Applied Mathematics},
  volume = {134},
  pages = {102309},
  publisher = {Elsevier BV},
  doi = {10.1016/j.aam.2021.102309},
  url = {http://dx.doi.org/10.1016/j.aam.2021.102309},
  issn = {0196-8858}
}

[Wal20]Nancy Wallace. Toward a Schurification of parking function formulas via bijections with Young tableaux. arXiv:2003.00062, 2020.

.bib

@article{Wallace2020x,
  author = {Nancy Wallace},
  title = {Toward a {S}churification of parking function formulas via
    bijections with {Y}oung tableaux},
  year = {2020},
  eprint = {2003.00062},
  archivePrefix = {arXiv},
  primaryClass = {math.CO}
}

[Yan15]Catherine H. Yan. Parking functions. Handbook of enumerative combinatorics:835–893, March 2015.

.bib

@incollection{Yan2015,
  doi = {10.1201/b18255-14},
  url2 = {https://doi.org/10.1201/b18255-14},
  year = {2015},
  month = mar,
  publisher = {Chapman and Hall/{CRC}},
  pages = {835--893},
  author = {Catherine H. Yan},
  title = {Parking Functions},
  booktitle = {Handbook of Enumerative Combinatorics}
}

[Hag07]James Haglund. The $q,t$-Catalan numbers and the space of diagonal harmonics (University lecture series). American Mathematical Society, 2007.

.bib

@book{qtCatalanBook,
  Author = {James Haglund},
  Title = {The $q,t$-{C}atalan numbers and the space of diagonal harmonics ({U}niversity lecture series)},
  Publisher = {American Mathematical Society},
  Year = {2007},
  ISBN = {0821844113},
  url = {https://www.math.upenn.edu/~jhaglund/books/qtcat.pdf}
}