Fonction de parking

En mathématiques, et plus particulièrement en combinatoire, une fonction de parking est une suite finie de $n$ entiers compris entre 1 et $n$, tels qu'au moins $i$ de ces entiers soient inférieurs ou égaux à $i$ (pour tous les $i$ entre 1 et $n$). Autrement dit, c'est une suite de $n$ entiers compris entre 1 et $n$, telle qu'il y ait dans la suite au moins une fois le nombre 1, au moins deux fois des nombres inférieurs à 2, au moins trois fois des nombres inférieurs à 3, etc. Les fonctions de parking ont des applications en théorie des groupes ainsi qu'en informatique théorique, où elles servent en particulier à établir certaines tables de hachage.

Définition

Explication intuitive

Le nom attribué à ces fonctions vient de la situation suivante. Considérons qu'il y a $n$ places de parking disposées en ligne dans une rue à sens unique et numérotées successivement de 1 à $n$ et que $n$ voitures viennent se garer à tour de rôle dans cette rue. On imagine que leurs conducteurs ou conductrices ont une place de parking favorite. Quand la $i$-ème voiture veut se garer, elle va d'abord tenter de se garer sur sa place préférée, numérotée par exemple $p_{i}$ : si la place est libre, la voiture s'y gare ; si la place est déjà prise, la $i$-ème voiture se gare à la prochaine place libre, c'est-à-dire à la place $p_{i}+1$ si elle est libre, sinon, à la place $p_{i}+2$, et ainsi de suite, jusqu'à ce que la $i$-ème voiture puisse se garer ou alors jusqu'à ce qu'elle arrive tout au bout de la rue sans avoir trouvé de place. Ce dernier cas signifie que toutes les places de $p_{i}$ à $n$ sont déjà prises lorsque la $i$-ème voiture entre dans la rue pour se garer.

Une fonction de parking correspond alors à une suite de places préférées $(p_{1},p_{2},\ldots ,p_{n})$ telle que toutes les voitures arrivent à se garer (si $p_{i}$ désigne comme avant la place préférée de la $i$-ème voiture).

Définition formelle

La définition formelle d'une fonction de parking est alors :

Définition (fonction de parking) — Soit un entier $n\geq 1$. Une fonction de parking de taille $n$ est une suite finie $(p_{1},\ldots ,p_{n})$ telle que

$\#\{k:p_{k}\leq i\}\geq i~~~\forall i\in [\![1,n]\!]$.

Cela revient à dire que, si on réordonne $(p_{1},\ldots ,p_{n})$ de sorte que les termes aillent en croissant, en appaelant $(p_{1}',\ldots ,p_{n}')$ le résultat, alors, pour tout $1\leq i\leq n$, $p_{i}'\leq i$.

Exemples

• La suite (1, 1,..., 1) constituée uniquement de 1 est toujours une fonction de parking. En effet, elle correspond à la situation où la place favorite de toutes les voitures est la première place. La première voiture la prend, la deuxième prend la première place libre après, c'est-à-dire la deuxième place, la troisième voiture prend donc la troisième place, et ainsi de suite, donc tout le monde peut se garer.

• Une suite contenant deux $n$ ou plus n'est jamais une fonction de parking de taille $n$. En effet, dans ce cas, la première voiture qui a cette place favorite la prend (si elle est libre), mais la deuxième voiture la trouve occupée et comme c'est la dernière place, elle est obligée de sortir du parking sans pouvoir se garer.

• Les fonctions de parking qui permettent à chaque voiture de se garer à sa place favorite sont exactement les permutations. Il y en a donc $n!$.

Liste de toutes les fonctions de parking pour certaines tailles

	Fonctions de parking	Nombre de fonctions de parking
$n$ = 1	1	1
$n$ = 2	(1,1), (1,2), (2,1)	3
$n$ = 3	(1,1,1), (1,1,2), (1,2,1), (2,1,1), (1,1,3), (1,3,1), (3,1,1), (1,2,2), (2,1,2), (2,2,1), (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)	16

Propriétés

L'ensemble des fonctions de parking est invariant par permutations, autrement dit :

Proposition (invariance par permutation) — Soit un entier $n\geq 1$ et une permutation $\sigma \in {\mathfrak {S}}_{n}$. La fonction

$(p_{1},\dots ,p_{n})\mapsto (p_{\sigma (1)},\dots ,p_{\sigma (n)})$

est une bijection sur l'ensemble des fonctions de parking de taille $n$.

Le nombre de fonctions de parking est connu depuis 1966:

Théorème (Konheim et Weiss, 1966) — Soit un entier $n\geq 1$. Il existe alors $(n+1)^{n-1}$ fonctions de parking de taille $n$.

Références

(en) Cet article est partiellement ou en totalité issu de la page de Wikipédia en anglais intitulée « Parking function » (voir la liste des auteurs).

Liens externes

• (en) Richard Stanley, « Parking Functions », sur MIT, 1999 (consulté le 9 juillet 2024).