UN ORDRE PARTIEL DES FONCTIONS DE PARKING

De nition IV.2.4. Une fonction de parking est une suite (a1; : : : ; an) d’entiers strictement positifs telle que, si (a01; : : : ; a0n) est le rearrangement croissant de la suite, alors pour tout i, a0i i.

L’origine du nom vient de la visualisation suivante. Considerons une rue a sens unique avec n places de parking, ainsi que n voitures qui successivement souhaitent s’y garer. La i-eme voiture souhaite se garer a la place ai, si cette place est occupee elle avance jusqu’a trouver une place vide et s’y garer, ou bien sortir de la rue sans avoir trouve de place. La suite (a1; : : : ; an) est alors de parking si toutes les voitures trouvent a se garer.

Le nombre de fonctions de parking de taille n est (n + 1)n 1, par exemple pour n = 3 on a les 16 fonctions suivantes, 111; 112; 121; 211; 122; 212; 221; 113; 131; 311; 123; 132; 213; 231; 312; 321:

On donne maintenant la de nition d’une espece, ainsi que la de nition de l’espece des fonctions de parking.

De nition IV.2.5. Une espece F est un foncteur de la categorie des ensembles nis et bijections vers elle m^eme. Autrement dit, c’est une application F qui | a tout ensemble ni V associe un ensemble F(V ), | a toute bijection   : V ! U entre les ensembles V et un autre ensemble U associe une application F( ) : F(V ) ! F(U) et telle que F(idV ) = idF(V ) pour tout ensemble ni V , et F( ) = F( ) F( ) pour toutes bijections : V ! U et : U ! W .

On a les operations usuelles sur les especes, comme l’addition qui se traduit par l’union disjointe des ensembles, et le produit (F:G)(A) = X

F(B)  G(C). Pour

A=BtC

plus de details sur les especes, voir [BLL98].

Il y a une action naturelle du groupe symetrique sur les fonctions de parking, que l’on obtient en permutant les lettres de la fonction de parking, on peut donc naturellement construire une espece de parking qui respect cette action.

De nition IV.2.6. Un arbre de parking d’un ensemble L est un couple (V; E), ou | V est une partition de L en jLj + 1 parts, certaines pouvant ^etre vides,

| E est une application injective de V vers les couples (v; i), ou v 2 V et  1 i v , telle que l’application E induite de V vers V de nit les ar^etes d’un arbre sur V .

L’espece des fonctions de parking (ou espece de parking) est l’espece qui a tout ensemble ni V associe l’ensemble des arbres de parking sur V .

Un sommet v d’un arbre de parking a autant d’ar^etes sortantes qu’il y a d’elements dans v, donc les sommets qui correspondent aux parts vides de la partition sont les feuilles de l’arbre.

y. Avec le Lemme IV.2.3, on a que pour tout k, z(k) x(k) \ y(k). Comme les x(k) et y(k) forment deux partitions de [n], les x(k) \ y(k), a egalite pres, sont tous disjoint. Or les z(k) forment aussi une partition de [n], cela implique que les x(k) \ y(k) forment une partition de [n]. On peut donc trouver un element v dans l’ensemble tel que v = x \ y, qui est plus grand que x et y, et qui est plus petit que z. Donc x _ y = v, et 2 est un join-semi treillis.

Dans cette section, on s’interesse a di erents objets en bijection avec les fonctions de parking de taille n ayant un rang r dans l’ensemble partiellement ordonne 2 . En remarquant qu’un element de rang r correspond a une fonction de parking ayant exactement r + 1 valeurs distinctes, on a la proposition suivante.

Proposition IV.2.11. Le nombre de fonctions de parking de taille n a r + 1 valeurs distinctes est An;r = r S(n; r + 1)r!;

Remarquons que pour l’arbre de parking associe, r + 1 est le nombre de sommets de l’arbre. Cette sequence fAn;rg est la sequence OEIS A141618. Edelman retrouve cette sequence dans [Ede80] en comptant le nombre de 2-partitions de taille n a r + 1 blocs.

Preuve de la Proposition IV.2.11. En raisonnant en matiere d’arbres de parking, S(n; r + 1) correspond au choix des sommets et de leurs etiquettes, et nombre d’agencements possibles pour former un arbre a partir de ces sommets.

Cette sequence correspond aussi au nombre de fonctions nilpotentes partielles de taille n dont l’image est de taille r.

De nition IV.2.12. Une fonction nilpotente partielle est une fonction f partielle-ment de nie de [n] dans [n], telle que fn([n]) = ?.

De maniere equivalente, on peut representer une fonction partielle nilpotente comme un mot de longueur n sur l’alphabet f0; : : : ; ng, avec les 0 correspondant aux elements sur lesquels la fonction n’est pas de nie. On remarque que si le mot ne contient pas de 0, alors la fonction n’est pas partielle, et donc n’est pas nilpotente.

Exemple IV.2.13. Le mot 010134 correspond a la fonction f non de nie sur 1 et 3, et telle que f(4) = f(2) = 1, f(6) = 4 et f(5) = 3. On a que f2 = 000001 et f3 = 000000, ce qui est equivalent a dire que f3([n]) = ?, donc f est bien nilpotente.

L’ensemble des fonctions partielles nilpotentes sur [n] telles que j Im(f)j = r + 1 est aussi de cardinalite An;r, leur enumeration est due a Laradji et Umar dans [LU04]. On peut donc donner une bijection entre ces fonctions et les fonctions de parking.

Bijection entre fonctions de parking et fonctions nilpotentes partielles.

On va associer bijectivement un arbre de parking a une fonction partielle nilpotente.

Les sommets de l’arbre sont les classes d’equivalence par l’image de f, c’est-a-dire les f 1(i) pour i 2 Im(f). La racine de l’arbre est f 1(?), et pour toute ar^ete sortante d’une etiquette i, on attache f 1(i). On remarque que cette construction est valide et forme un arbre si et seulement si f est nilpotente. De plus, cette construction est inversible, d’ou la bijection.

Exemple IV.2.14. La Figure IV.2.5 montre un exemple d’arbre de parking obtenu a partir de la fonction partielle nilpotente (10; 0; 11; 11; 4; 10; 2; 0; 7; 2; 0) avec la bijection. La fonction de parking correspondante est alors (3; 1; 9; 9; 11; 3; 2; 1; 6; 2; 1). On remarque sans surprise que les classes d’equivalence des deux fonctions sont egales. On remarque de plus que l’operation d’iteration sur la fonction partielle nilpotente se traduit sur l’arbre par la fusion de la racine avec ses enfants, et en iterant un nombre su sant de fois, on obtient l’arbre a un seul n ud, qui correspond a la fonction nulle. Notons en n qu’on peut appliquer la bijection a une fonction qui n’est pas partielle, mais le resultat contiendra forcement un cycle.