Fonction de parking
Cet article est orphelin. Moins de trois articles lui sont liés ().
Vous pouvez aider en ajoutant des liens vers [[Fonction de parking]]
dans les articles relatifs au sujet.
En mathématiques, et plus particulièrement en combinatoire, une fonction de parking est une suite finie de entiers compris entre 1 et , tels qu'au moins de ces entiers soient inférieurs ou égaux à (pour tous les entre 1 et ). Autrement dit, c'est une suite de entiers compris entre 1 et , 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[1], où elles servent en particulier à établir certaines tables de hachage[2].
Définition
Explication intuitive
Le nom attribué à ces fonctions vient de la situation suivante. Considérons qu'il y a places de parking disposées en ligne dans une rue à sens unique et numérotées successivement de 1 à et que 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 -è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 : si la place est libre, la voiture s'y gare ; si la place est déjà prise, la -ème voiture se gare à la prochaine place libre, c'est-à-dire à la place si elle est libre, sinon, à la place , et ainsi de suite, jusqu'à ce que la -è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 à sont déjà prises lorsque la -ème voiture entre dans la rue pour se garer.
Une fonction de parking correspond alors à une suite de places préférées telle que toutes les voitures arrivent à se garer (si désigne comme avant la place préférée de la -ème voiture).
Définition formelle
La définition formelle d'une fonction de parking est alors[1] :
Définition (fonction de parking) — Soit un entier . Une fonction de parking de taille est une suite finie telle que
Cela revient à dire que, si on réordonne de sorte que les termes aillent en croissant, en appaelant le résultat, alors, pour tout , .
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 ou plus n'est jamais une fonction de parking de taille . 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 .
Fonctions de parking | Nombre de fonctions de parking | |
---|---|---|
= 1 | 1 | 1 |
= 2 | (1,1), (1,2), (2,1) | 3 |
= 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 et une permutation . La fonction
est une bijection sur l'ensemble des fonctions de parking de taille .
Le nombre de fonctions de parking est connu depuis 1966[2]:
Théorème (Konheim et Weiss, 1966) — Soit un entier . Il existe alors fonctions de parking de taille .
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).
- ↑ a et b (en) Persi Diaconis et Angela Hicks, « Probabilizing parking functions », Advances in Applied Mathematics, vol. 89, , p. 125-155 (ISSN 0196-8858, lire en ligne).
- ↑ a et b (en) Alan G. Konheim et Benjamin Weiss, « An occupancy discipline and applications », SIAM J. Appl. Math., vol. 14, , p. 1266–1274 (lire en ligne).
Liens externes
- (en) Richard Stanley, « Parking Functions », sur MIT, (consulté le ).
- Portail des mathématiques
- Portail de l'informatique théorique