Fonction de parking

En mathématiques une fonction de parking est un objet combinatoire ayant des applications en théorie des groupes ainsi qu'en informatique théorique.

Définition

Définition intuitive

Considérons n places de parking disposées en ligne et numérotées de gauche à droite de 1 à n. Considérons que n voitures veulent se garer à tour de rôle sur ce parking. Quand la i-ième voiture veut se garer, elle va d'abord tenter de se garer sur sa place préférée p_i : si la place est libre, la voiture s'y gare et la prochaine arrive sur le parking ; si la place est déjà prise, alors la i-ième voiture va tenter de se garer à la place juste à droite de p_i à savoir p_i+1 ; si cette place est encore prise, alors la voiture se décale une fois de plus sur la droite pour tenter de se garer à la place p_i+2 ; ainsi de suite, jusqu'à ce que la i-ième voiture puisse se garer ou alors jusqu'à ce qu'elle arrive tout au bout du parking sans avoir pu se garer. Ce dernier cas signifie que toutes les places de p_i à n sont déjà prises lorsque la i-ième voiture rentre sur le parking.

Une fonction de parking est alors une suite (p₁ ,..., p_n) telle que les voitures arrivent toutes à se garer (si p_i désigne la place préférée de la i-ième voiture).

Définition formelle

Il existe une définition plus formelle et concise de fonction de parking :

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

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

Cela revient à dire que, si $(p_{1}',\dots ,p_{n}')$ est le réordonnement croissant de $(p_{1},\dots ,p_{n})$, 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.
• Une suite contenant deux n ou plus n'est jamais une fonction de parking de taille n.

Liste de toutes les fonctions de parking pour certaines tailles

	Fonctions de parking	Nombre de fonction de parking
n = 1	1	1
n = 2	11, 12, 21	3
n = 3	111, 112, 121, 211, 113, 131, 311, 122, 212, 221, 123, 132, 213, 231, 312, 321	16

Propriétés

Les fonctions de parking sont invariantes 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$.