PDFLINK |

# a Parking Function?

Communicated by *Notices* Associate Editor Emilie Purvine

Consider a one-way street with numbered parking spots, denoted A sequence of . cars enters the street one at a time, each with a preferred spot. Upon its arrival, car denoted , drives to its preferred spot , If spot . is unoccupied, car is *lucky* and parks there. Otherwise, car *displaces* further down the street until it finds the first unoccupied spot in which to park, if such a spot exists. If no such spot exists, car reneges the search process unable to park. Let be the encoding the cars’ parking preferences. If all cars are able to park, then -tuple is said to be a *parking function* of length .

Parking functions were first implicitly studied by Pyke *outcome*. If the of preferences is indeed a parking function, its outcome can be treated as a permutation of -tuple written in one-line notation. For example, as depicted in Figure 1, is a parking function of length with outcome .

Classical enumerative results about parking functions foreshadow their rich mathematical structure. There are

1parking functions of length (OEIS A000272)—this is Cayley’s formula

An elegant proof of 1, due to Pollak as credited by Riordan

Now, consider an arbitrary -tuple Can one tell whether it is a parking function of length . without explicitly considering its parking outcome? A classical inequality-based characterization of parking functions allows precisely this. Let be the weakly increasing rearrangement of Then, the following holds: .

2This characterization can be verified as follows. If there exists some for which then at least , cars attempt to park in the last spots This is more cars than spots available, so at least one of these cars will be unable to park. Conversely, if some car is unable to park, then there exists an earliest spot . left unoccupied, which can only be the case if .

Note that 2 has the following remarkable implication: parking functions are invariant under the action of the symmetric group which permutes their subscripts. In particular, the set of parking functions is obtained from the rearrangements of weakly increasing parking functions. For example, , , , and , are all parking functions of length each with a different parking outcome, whereas no rearrangement of , can possibly be a parking function of length .

Parking functions are also closely related to the Catalan numbers (OEIS A000108), which are given by the recurrence relation

3for with In particular, the set of weakly increasing parking functions of length . is enumerated by 3. To verify this, suppose you construct a weakly increasing parking function of length denoted , with your choice of , for the greatest index satisfying For any such choice of . the , -tuple must be a parking function of length the , -tuple must be a parking function of length and by induction there are , possibilities.

As a consequence, weakly increasing parking functions are in bijection with the wide variety of Catalan objects; refer to Stanley

Note that if is a weakly increasing parking function, then the car th (with preference parks in the ) spot th Therefore, the total displacement of a weakly increasing parking function . is given by

4This statistic has further combinatorial interpretations. For example, the number of full squares between a Dyck path and the main diagonal, which in the case of Figure 3 is is the same as the total displacement of its corresponding weakly increasing parking function. Lastly, note that the dependency of ,4 on reduces to the summation of its terms. This implies that the total displacement of a parking function is also preserved under rearrangements!

Despite first appearing in the literature more than six decades ago, the combinatorics of parking functions remains a vibrant area of research. Recent work ranges from the study of discrete statistics such as displacement *unit Fubini rankings*, and in particular their outcome map, to characterize and enumerate the Boolean intervals of rank in the weak order poset of

## References

[ AAH 23] - Yasmin Aguillon, Dylan Alvarenga, Pamela E. Harris, Surya Kotapati, J. Carlos Martínez Mori, Casandra D. Monroe, Zia Saylor, Camelle Tieu, and Dwight Anderson Williams II,
*On parking functions and the tower of Hanoi*, Amer. Math. Monthly**130**(2023), no. 7, 618–624, DOI 10.1080/00029890.2023.2206311. MR4623327,## Show rawAMSref

`\bib{aguillon2023parking}{article}{ author={Aguillon, Yasmin}, author={Alvarenga, Dylan}, author={Harris, Pamela E.}, author={Kotapati, Surya}, author={Mart\'{\i }nez Mori, J. Carlos}, author={Monroe, Casandra D.}, author={Saylor, Zia}, author={Tieu, Camelle}, author={Williams, Dwight Anderson, II}, title={On parking functions and the tower of Hanoi}, journal={Amer. Math. Monthly}, volume={130}, date={2023}, number={7}, pages={618--624}, issn={0002-9890}, review={\MR {4623327}}, doi={10.1080/00029890.2023.2206311}, }`

[ AW22] - Aruzhan Amanbayeva and Danielle Wang,
*The convex hull of parking functions of length*, Enumer. Comb. Appl.**2**(2022), no. 2, Paper No. S2R10, 10, DOI 10.54550/eca2022v2s2r10. MR4459984,## Show rawAMSref

`\bib{amanbayeva2022convex}{article}{ author={Amanbayeva, Aruzhan}, author={Wang, Danielle}, title={The convex hull of parking functions of length $n$}, journal={Enumer. Comb. Appl.}, volume={2}, date={2022}, number={2}, pages={Paper No. S2R10, 10}, review={\MR {4459984}}, doi={10.54550/eca2022v2s2r10}, }`

[ ALW16] - Drew Armstrong, Nicholas A. Loehr, and Gregory S. Warrington,
*Rational parking functions and Catalan numbers*, Ann. Comb.**20**(2016), no. 1, 21–58, DOI 10.1007/s00026-015-0293-6. MR3461934,## Show rawAMSref

`\bib{armstrong2016rational}{article}{ author={Armstrong, Drew}, author={Loehr, Nicholas A.}, author={Warrington, Gregory S.}, title={Rational parking functions and Catalan numbers}, journal={Ann. Comb.}, volume={20}, date={2016}, number={1}, pages={21--58}, issn={0218-0006}, review={\MR {3461934}}, doi={10.1007/s00026-015-0293-6}, }`

[ CCH 21] - Joshua Carlson, Alex Christensen, Pamela E. Harris, Zakiya Jones, and Andrés Ramos Rodríguez,
*Parking functions: choose your own adventure*, College Math. J.**52**(2021), no. 4, 254–264, DOI 10.1080/07468342.2021.1943115. MR4309295,## Show rawAMSref

`\bib{carlson2021parking}{article}{ author={Carlson, Joshua}, author={Christensen, Alex}, author={Harris, Pamela E.}, author={Jones, Zakiya}, author={Ramos Rodr\'{\i }guez, Andr\'{e}s}, title={Parking functions: choose your own adventure}, journal={College Math. J.}, volume={52}, date={2021}, number={4}, pages={254--264}, issn={0746-8342}, review={\MR {4309295}}, doi={10.1080/07468342.2021.1943115}, }`

[ Cay89] - Arthur Cayley,
*A theorem on trees*, Quarterly Journal of Pure and Applied Mathematics**23**(1889), 376–378.,## Show rawAMSref

`\bib{cayley1889theorem}{article}{ author={Cayley, Arthur}, title={A theorem on trees}, date={1889}, journal={Quarterly Journal of Pure and Applied Mathematics}, volume={23}, pages={376\ndash 378}, }`

[ EHKMM23] - Jennifer Elder, Pamela E. Harris, Jan Kretschmann, and J. Carlos Martínez Mori,
*Cost-sharing in parking games*, Preprint, arXiv:2309.12265, 2023.,## Show rawAMSref

`\bib{elder2023cost}{eprint}{ author={Elder, Jennifer}, author={Harris, Pamela~E.}, author={Kretschmann, Jan}, author={Mart\'{\i }nez~Mori, J.~Carlos}, title={Cost-sharing in parking games}, date={2023}, arxiv={2309.12265}, }`

[ EHKMM24] - Jennifer Elder, Pamela E. Harris, Jan Kretschmann, and J. Carlos Martínez Mori,
*Parking functions, fubini rankings, and Boolean intervals in the weak order of*, To appear in Journal of Combinatorics (2024).,## Show rawAMSref

`\bib{elder2024boolean}{article}{ author={Elder, Jennifer}, author={Harris, Pamela~E.}, author={Kretschmann, Jan}, author={Mart\'{\i }nez~Mori, J.~Carlos}, title={Parking functions, fubini rankings, and {B}oolean intervals in the weak order of $\mathfrak {S}_n$}, date={2024}, journal={To appear in Journal of Combinatorics}, }`

[ GS04] - Ira M. Gessel and Seunghyun Seo,
*A refinement of Cayley’s formula for trees*, Electron. J. Combin.**11**(2004/06), no. 2, Research Paper 27, 23, DOI 10.37236/1884. MR2224940,## Show rawAMSref

`\bib{gessel2006refinement}{article}{ author={Gessel, Ira M.}, author={Seo, Seunghyun}, title={A refinement of Cayley's formula for trees}, journal={Electron. J. Combin.}, volume={11}, date={2004/06}, number={2}, pages={Research Paper 27, 23}, review={\MR {2224940}}, doi={10.37236/1884}, }`

[ HLVM24] - Mitsuki Hanada, John Lentfer, and Andrés R. Vindas-Meléndez,
*Generalized Parking Function Polytopes*, Ann. Comb.**28**(2024), no. 2, 575–613, DOI 10.1007/s00026-023-00671-1. MR4747488,## Show rawAMSref

`\bib{hanada2023generalized}{article}{ author={Hanada, Mitsuki}, author={Lentfer, John}, author={Vindas-Mel\'{e}ndez, Andr\'{e}s R.}, title={Generalized Parking Function Polytopes}, journal={Ann. Comb.}, volume={28}, date={2024}, number={2}, pages={575--613}, issn={0218-0006}, review={\MR {4747488}}, doi={10.1007/s00026-023-00671-1}, }`

[ HKMM24] - Pamela E. Harris, Jan Kretschmann, and J. Carlos Martínez Mori,
*Lucky Cars and the Quicksort Algorithm*, Amer. Math. Monthly**131**(2024), no. 5, 417–423, DOI 10.1080/00029890.2024.2309103. MR4739576,## Show rawAMSref

`\bib{harris2024lucky}{article}{ author={Harris, Pamela E.}, author={Kretschmann, Jan}, author={Mart\'{\i }nez Mori, J. Carlos}, title={Lucky Cars and the Quicksort Algorithm}, journal={Amer. Math. Monthly}, volume={131}, date={2024}, number={5}, pages={417--423}, issn={0002-9890}, review={\MR {4739576}}, doi={10.1080/00029890.2024.2309103}, }`

[ KY23] - Richard Kenyon and Mei Yin,
*Parking functions: from combinatorics to probability*, Methodol. Comput. Appl. Probab.**25**(2023), no. 1, Paper No. 32, 30, DOI 10.1007/s11009-023-10022-5. MR4549917,## Show rawAMSref

`\bib{kenyon2023parking}{article}{ author={Kenyon, Richard}, author={Yin, Mei}, title={Parking functions: from combinatorics to probability}, journal={Methodol. Comput. Appl. Probab.}, volume={25}, date={2023}, number={1}, pages={Paper No. 32, 30}, issn={1387-5841}, review={\MR {4549917}}, doi={10.1007/s11009-023-10022-5}, }`

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

`\bib{konheim1966occupancy}{article}{ author={Konheim, Alan~G.}, author={Weiss, Benjamin}, title={An occupancy discipline and applications}, date={1966}, journal={SIAM Journal on Applied Mathematics}, volume={14}, number={6}, pages={1266\ndash 1274}, }`

[ Pyk59] - Ronald Pyke,
*The supremum and infimum of the Poisson process*, Ann. Math. Statist.**30**(1959), 568–576, DOI 10.1214/aoms/1177706269. MR107315,## Show rawAMSref

`\bib{pyke1959supremum}{article}{ author={Pyke, Ronald}, title={The supremum and infimum of the Poisson process}, journal={Ann. Math. Statist.}, volume={30}, date={1959}, pages={568--576}, issn={0003-4851}, review={\MR {107315}}, doi={10.1214/aoms/1177706269}, }`

[ Rio69] - John Riordan,
*Ballots and trees*, J. Combinatorial Theory**6**(1969), 408–411. MR234843,## Show rawAMSref

`\bib{riordan1969ballots}{article}{ author={Riordan, John}, title={Ballots and trees}, journal={J. Combinatorial Theory}, volume={6}, date={1969}, pages={408--411}, issn={0021-9800}, review={\MR {234843}}, }`

[ SV24] - Antonín Slavík and Marie Vestenická,
*Lucky cars: expected values and generating functions*, Amer. Math. Monthly**131**(2024), no. 4, 343–348, DOI 10.1080/00029890.2023.2293616. MR4723560,## Show rawAMSref

`\bib{slavik2023lucky}{article}{ author={Slav\'{\i }k, Anton\'{\i }n}, author={Vestenick\'{a}, Marie}, title={Lucky cars: expected values and generating functions}, journal={Amer. Math. Monthly}, volume={131}, date={2024}, number={4}, pages={343--348}, issn={0002-9890}, review={\MR {4723560}}, doi={10.1080/00029890.2023.2293616}, }`

[ Sta15] - Richard P. Stanley,
*Catalan numbers*, Cambridge University Press, New York, 2015, DOI 10.1017/CBO9781139871495. MR3467982,## Show rawAMSref

`\bib{stanley2015catalan}{book}{ author={Stanley, Richard P.}, title={Catalan numbers}, publisher={Cambridge University Press, New York}, date={2015}, pages={viii+215}, isbn={978-1-107-42774-7}, isbn={978-1-107-07509-2}, review={\MR {3467982}}, doi={10.1017/CBO9781139871495}, }`

[ SY23] - Richard P. Stanley and Mei Yin,
*Some enumerative properties of parking functions*, Preprint, arXiv:2306.08681, 2023.,## Show rawAMSref

`\bib{stanley2023some}{eprint}{ author={Stanley, Richard~P.}, author={Yin, Mei}, title={Some enumerative properties of parking functions}, date={2023}, arxiv={2306.08681}, }`

[ Yan15] - Catherine H. Yan,
*Parking functions*, Handbook of enumerative combinatorics, Discrete Math. Appl. (Boca Raton), CRC Press, Boca Raton, FL, 2015, pp. 835–893. MR3409354,## Show rawAMSref

`\bib{yan2015parking}{article}{ author={Yan, Catherine H.}, title={Parking functions}, conference={ title={Handbook of enumerative combinatorics}, }, book={ series={Discrete Math. Appl. (Boca Raton)}, publisher={CRC Press, Boca Raton, FL}, }, date={2015}, pages={835--893}, review={\MR {3409354}}, }`

## Credits

All figures are courtesy of J. Carlos Martínez Mori.

Author photo is courtesy of Nicole Sempértegui.