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[1].

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[1] :

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 1\leq i\leq 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[2] :

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) Persi Diaconis et Angela Hicks, « Probabilizing parking functions », Advances in Applied Mathematics, vol. 89,‎ 2017, p. 125-155 (ISSN 0196-8858, lire en ligne)
(en) A G Konheim et B Weiss, « An occupancy discipline and applications », SIAM J. Appl. Math., vol. 14,‎ 1966, p. 1266–1274 (lire en ligne)

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.