Fixed points and cycles of parking functions

Martin Rubey; Mei Yin

paper

Fixed points and cycles of parking functions

arXiv:2403.17110

Abstract

A parking function of length $n$ is a sequence $I ¨ = (I ¨ _{1}, \dots, I ¨ _{n})$ of positive integers such that if $I^»_{1} \leq \dots \leq I^»_{n}$ is the increasing rearrangement of $I ¨ _{1}, \dots, I ¨ _{n}$ , then $I^»_{i} \leq i$ for $1 \leq i \leq n$ . The index $i$ is a fixed point of the parking function $I ¨ $ if $I ¨ _{i} = i$ . More generally, for $m \geq 1$ , the indices $(i_{1}, \dots, i_{m})$ where the $i_{j}$ 's are all distinct constitute an $m$ -cycle of the parking function $I ¨ $ if $I ¨ _{i_{1}} = i_{2}, I ¨ _{i_{2}} = i_{3}, \dots, I ¨ _{i_{m - 1}} = i_{m}, I ¨ _{i_{m}} = i_{1}$ . In this paper we obtain some exact results on the number of fixed points and cycles of parking functions. Our derivations are based on generalizations of Pollak's argument and the symmetry of parking coordinates. Extensions of our techniques are discussed.

11 pages, updated version contains expanded proof details and connections to other research areas through OEIS entries