Parking functions: What a mathematician thinks of when parking

Abstract

Základní parkovací problém je následující: Máme n aut postupně vjíždějících do ulice s n parkovacími místy a každé auto má nějaké preferované místo, kde se snaží zaparkovat. Pokud je místo obsazené, auto pokračuje v jízdě ulicí a hledá první volné místo (pokud takové existuje), na kterém parkuje. Pokud všechna auta zaparkují, nazýváme vektor jejich parkovacích preferencí parkovací funkce. Pokud auta mohou také couvat o k míst zpět, dostáváme k-Neapolské parkovací funkce. V práci představujeme charakterizaci k-Neapolských parkovacích funkcí formulovanou pomocí mřížových cest. Dále zavádíme unikátní k-Neapolské parkovací funkce, uvádíme jejich charakterizaci a vzorec, který je počítá. Nakonec zkoumáme případ, kdy mají auta různé délky. V tomto případě ro- zlišujeme mezi dvěma různými chováními aut, v prvním případě tak dostáváme parkovací sekvence a v druhém parkovací uspořádání. Zavádíme problém, kdy každé auto preferuje určité místo, ale není dáno pořadí, ve kterém auta vjíždějí do ulice. Na související otázky částečně odpovídáme. 1

The basic parking problem is the following: There are n cars entering a street with n empty parking spots and each car has a preferred spot where it tries to park. If the spot is occupied, the car continues driving and parks at the first empty spot (if any). If all cars are able to park, we call the vector of their preferences a parking function. If cars are allowed to drive also backwards up to k spots, we get the k-Naples parking functions. We present a characterization of k-Naples parking functions formulated in terms of lattice paths. We introduce unique-order k-Naples parking functions, present their characterization and a calculate their number. Further, we allow cars to have different sizes. We distinguish between two different behaviours of cars: in the first case, we get the parking sequences and in the second case, we get the parking assortments. We introduce a problem when the cars' preferences are given but the order in which the cars enter the street is not. We provide partial answers to certain related questions. 1