# a Parking Function?

J. Carlos Martínez Mori

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 -tuple encoding the cars’ parking preferences. If all cars are able to park, then is said to be a parking function of length .

Parking functions were first implicitly studied by Pyke Pyk59 in his study of Poisson processes and later on by Konheim and Weiss KW66 in their study of hashing with linear probing. Parking functions can be seen as functions in the sense that the “parking experiment” narrated above assigns, to each -tuple of parking preferences, a single -tuple encoding its parking outcome. If the -tuple of preferences is indeed a parking function, its outcome can be treated as a permutation of 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

parking functions of length (OEIS A000272)—this is Cayley’s formula Cay89 for the number of labeled trees on vertices. This count was established independently by Pyke Pyk59 and Konheim and Weiss KW66, and has been recovered bijectively by numerous authors; refer to Yan Yan15, Section 13.2 and the references therein.

An elegant proof of 1, due to Pollak as credited by Riordan Rio69, is as follows. Consider a circular one-way street with numbered parking spots, denoted . Say, it is a roundabout with no exits and a single entry between spots and . There are cars attempting to park, so that each -tuple encodes a possibility for the cars’ parking preferences. How many of these -tuples are in fact parking functions of length ? Since there are spots but only cars, there will always be one spot left unoccupied; which exact spot this is depends on the preferences. Note that the preference tuples form a group under component-wise addition modulo , and consider the subgroup generated by the all-ones preference tuple . As depicted in Figure 2, the cosets for form equivalence classes of order , each of which contains exactly one parking function, namely whichever tuple leaves spot unoccupied in its outcome. Therefore, there are parking functions of length .

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:

This 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

for 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 Sta15 for a survey. For example, weakly increasing parking functions of length are in bijection with Dyck paths of length ; these are lattice paths from to using only north steps and east steps , denoted “N” and “E” respectively, and which do not cross below the main diagonal. Armstrong, Loehr, and Warrington ALW16, Section 2.2 describe the following bijection: given a Dyck path of length , obtain a weakly increasing parking function of length by letting be one plus the total number of E steps appearing before the th N step for all . Figure 3 illustrates this construction using the weakly increasing parking function ; the weakly increasing rearrangement of the example in Figure 1.

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

This 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 KY23EHKMM23 or the number of lucky cars GS04SV24SY23, the introduction of new variants and/or generalizations on the classical “parking experiment” rule (refer to Carlson et al. CCH21 for an accessible tour of endless possibilities in the style of “choose your own adventure”), polyhedral aspects AW22HLVM24, and surprising connections to seemingly unrelated objects AAH23HKMM24, to mention just a few. In recent work, my collaborators and I use a subset of parking functions we call unit Fubini rankings, and in particular their outcome map, to characterize and enumerate the Boolean intervals of rank in the weak order poset of EHKMM24. Figure 4 illustrates our construction.

## References

[AAH23]
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}, } 
[CCH21]
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.