Parking functions and Łukasiewicz paths

Thomas Selig; Haoyue Zhu

doi:10.47443/dml.2024.070

Author(s)

Thomas Selig Department of Computing, School of Advanced Technology, Xi'an Jiaotong-Liverpool University,Suzhou,China

Haoyue Zhu Department of Computing, School of Advanced Technology, Xi'an Jiaotong-Liverpool University,Suzhou,China

Abstract

We present a bijection between two well-known objects in the ubiquitous Catalan family: non-decreasing parking functions and Lukasiewicz paths. This bijection maps the maximum displacement of a parking function to the height of the corresponding Lukasiewicz path, and the total displacement to the area of the path. We also study this bijection restricted to two specific families of parking functions: unit-interval parking functions and prime parking functions.

Publication Details

Page(s) 77-84

DOI 10.47443/dml.2024.070

Published Journal: Discrete Mathematics Letters, Volume: 14, Issue: 0, Year: 2024

Request the full text from PASTIC

Keywords

bijection, parking functions, Lukasiewicz paths, Catalan numbers, displacement statistic

References

Aguilar-Fraga T.,Elder J.,Garcia R. E.,Hadaway K. P.,Harris P. E.,Harry K. J.,Hogan I. B.,Johnson J.,Lawson-Chavanu K.,Monroe C. D.,Tolson III,D. A. Williams II .2023 .-interval rational parking functions. ArXiv:2311.14055 [math.CO], : .

Barcucci E.,Pinzani R.,Sprugnoli R. .1992 .The Motzkin family. Pure Math. Appl, 2(3) : 249-279.

Bradt S. A.,Elder J.,Harris P. E.,Kirby G. R.,Wang Y. S.,Whidden J. .2024 .Unit interval parking functions and the r-Fubini numbers. Mathematica, 3 : 370-384.

Colmenarejo L.,Harris P. E.,Jones Z.,A. R. Z. .2021 .Vindas-Mele´ndez, Counting k-Naples parking functions through permutations and the k-Naples area statistic. Enumer. Comb. Appl, 1(2) : S2R11.

Cori R.,Rossin D. .2000 .On the sandpile group of dual graphs. European J. Combin, 21(4) : 447-459.

Delcroix-Oger B.,M. B. .2022 .Josuat-Verge`s, L. Randazzo, Some properties of the parking function poset. Electron. J. Combin, 29(4) : 42.

Duarte R.,A R. .2024 .The number of prime parking functions. Math. Intelligencer, 46 : 222-224.

Elder J.,Harris P. E.,Kretschmann J.,J. C. J. .2023 .Mart´ınez Mori, Parking functions, Fubini rankings, and Boolean intervals in the weak order of Sn. , 2306 : .

Flajolet P.,Sedgewick R. .2009 .. , : .

Hadaway K. .2021 .On combinatorial problems of generalized parking functions. BA Thesis, : .

Harris P. E.,Kamau B. M.,Tian R. .2023 .On the outcome map of MVP parking functions: permutations avoiding 321 and 3412. Enumer. Comb. Appl, 3(2) : S2R11.

Konheim A. G.,Weiss B. .1996 .An occupancy discipline and applications. SIAM J. Appl. Math, 14(6) : 1266-1274.

Kreweras G. .1980 .Une famille de polynoˆmes ayant plusieurs proprie´te´s enumeratives, Period. , 11 : 309-320.

Meyles L. C.,Harris P. E.,Jordaan R.,Kirby G. R.,Sehayek S. .2023 .Unit-interval parking functions and the permutohedron. ArXiv:2305.15554 [math.CO], : .

Selig T.,Zhu H. .2023 .New combinatorial perspectives on MVP parking functions and their outcome map. ArXiv:2309.11788 [math.CO], : .

Stanley R. P. .1996 .Hyperplane arrangements, interval orders, and trees. Proc. Natl. Acad. Sci. USA, 93(6) : 2620-2625.

Stanley R. P. .1999 .. , 2 : .

Stanley R. P. .2015 .. , : .

. .The OEIS Foundation Inc. The On-line Encyclopedia of Integer Sequences, : .

Yan C. H.,Bona C. H. .2015 .Parking functions. , : 835-893.