Connecting parking functions to another classic car-related puzzle

Seacrest, Tyler

doi:10.2478/rmm-2025-0004

Abstract

Parking functions are a well-studied area of combinatorics that have connections to Cayley’s tree formula, Catalan numbers, Dyck paths, and much more. We connect parking functions to another classic car-related puzzle called the gas stations puzzle. Looking at it through this lens, we give two new proofs of results in this area that are natural extensions of the original connection.

References

[ALW16] Drew Armstrong, Nicholas A. Loehr, and Gregory S. Warrington. Rational parking functions and Catalan numbers. Ann. Comb., 20(1):21–58, 2016. doi: 10.1007/s00026-015-0293-6.
Search in Google Scholar Back to article
[Bol06] Béla Bollobás. The art of mathematics. Cambridge University Press, New York, 2006. Coffee time in Memphis. doi:10.1017/CBO9780511816574.
Search in Google Scholar Back to article
[KW66] Alan G. Konheim and Benjamin Weiss. An occupancy discipline and applications. SIAM Journal on Applied Mathematics, 14(6):1266–1274, 1966. URL: http://www.jstor.org/stable/2946240.
Search in Google Scholar Back to article
[LMS13] Linyuan Lu, Austin Mohr, and László Székely. Quest for negative dependency graphs. In Recent advances in harmonic analysis and applications, volume 25 of Springer Proc. Math. Stat., pages 243–258. Springer, New York, 2013. URL: https://doi.org/10.1007/978-1-4614-4565-4_21, doi:10.1007/978-1-4614-4565-4\_21.
Search in Google Scholar Back to article
[Lov79] L. Lovász. Combinatorial problems and exercises. North-Holland Publishing Co., Amsterdam-New York, 1979.
Search in Google Scholar Back to article
[Rio69] John Riordan. Ballots and trees. J. Combinatorial Theory, 6:408–411, 1969.
Search in Google Scholar Back to article
[Sei00] Charles Seife. Zero. Penguin Books, New York, 2000. The biography of a dangerous idea.
Search in Google Scholar Back to article
[/u/22] /u/bobjane. Catalan n-tuples v2, Jun 2022. URL: https://www.reddit.com/r/mathriddles/comments/vneoky/catalan_ntuples_v2/.
Search in Google Scholar Back to article
[Wil95] Andrew Wiles. Modular elliptic curves and Fermat’s last theorem. Ann. of Math. (2), 141(3):443–551, 1995. doi:10.2307/2118559.
Search in Google Scholar Back to article
[Win04] Peter Winkler. Mathematical puzzles: a connoisseur’s collection. A K Peters, Ltd., Natick, MA, 2004.
Search in Google Scholar Back to article
[Wä20] Johan Wästlund. Padlock solitaire: A martingale trick for combinatorial enumeration, 2020. URL: https://arxiv.org/abs/2008.13017, doi:10.48550/ARXIV.2008.13017.
Search in Google Scholar Back to article
[Yan15] Catherine H. Yan. Parking functions. In Handbook of enumerative combinatorics, Discrete Math. Appl. (Boca Raton), pages 835–893. CRC Press, Boca Raton, FL, 2015.
Search in Google Scholar Back to article

Connecting parking functions to another classic car-related puzzle

Abstract

Paradigm

My account