Fixed points and cycles of parking functions
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917875815546880 |
|---|---|
| author | Rubey, Martin Yin, Mei |
| author_facet | Rubey, Martin Yin, Mei |
| contents | A parking function of length $n$ is a sequence $π=(π_1,\dots, π_n)$ of positive integers such that if $λ_1\leq\cdots\leq λ_n$ is the increasing rearrangement of $π_1,\dots,π_n$, then $λ_i\leq i$ for $1\leq i\leq n$. The index $i$ is a fixed point of the parking function $π$ if $π_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 $π$ if $π_{i_1}=i_2, π_{i_2}=i_3, \dots, π_{i_{m-1}}=i_m, π_{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_17110 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fixed points and cycles of parking functions Rubey, Martin Yin, Mei Combinatorics 05A15, 05A19, 60C05 A parking function of length $n$ is a sequence $π=(π_1,\dots, π_n)$ of positive integers such that if $λ_1\leq\cdots\leq λ_n$ is the increasing rearrangement of $π_1,\dots,π_n$, then $λ_i\leq i$ for $1\leq i\leq n$. The index $i$ is a fixed point of the parking function $π$ if $π_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 $π$ if $π_{i_1}=i_2, π_{i_2}=i_3, \dots, π_{i_{m-1}}=i_m, π_{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. |
| title | Fixed points and cycles of parking functions |
| topic | Combinatorics 05A15, 05A19, 60C05 |
| url | https://arxiv.org/abs/2403.17110 |