Selma Mohamed: Parking functions and their applications in combinatorics

Abstract.

Parking functions are intriguing combinatorial objects originally introduced to model linear probing in hashing and data storage. A parking function is a sequence of integers that encodes the preferences of \(n\) cars attempting to park in \(n\) spots along a one-way street. The sequence is valid if each car can successfully park by proceeding to its preferred spot or the next available one. This paper investigates parking functions from multiple perspectives, including their definition, enumeration, and bijective relationships with other mathematical structures such as rooted labeled trees, Dyck paths, and hyperplane arrangements. It also explores generalizations of parking functions and presents Python code for generating both sorted and unsorted variants.

Abstrakt
Parkeringsfunktioner är fascinerande kombinatoriska objekt som ursprungligen introducerades för att modellera linjär probing inom hashing och datalagring. En parkeringsfunktion är en heltalsföljd som representerar preferenserna hos \(n\) bilar som försöker parkera på \(n\) platser längs en enkelriktad gata. Följden är giltig om varje bil lyckas parkera genom att börja vid sin önskade plats eller fortsätta till nästa lediga. Denna uppsats undersöker parkeringsfunktioner ur flera perspektiv, inklusive deras definition, uppräkning och bijektiva samband med andra matematiska strukturer såsom rotade märkta träd, Dyck-stigar och hyperplansarrangemang. Vidare behandlas generaliseringar av parkeringsfunktioner och Python-kod presenteras för att generera både sorterade och osorterade varianter.