Bijection de Joyal - Définition

Correspondance de Foata

Correspondance de Foata appliquée à la restriction τ de ƒ à C. Les deux points marqués de l'arbre de Cayley (associé à ƒ par la correspondance de Foata) sont ici 9 et 14.

L'ensemble C des éléments cycliques de ƒ est le plus grand sous-ensemble de ayant la propriété suivante:

• la restriction de ƒ à C est une bijection de C dans C.

On peut alors appliquer la correspondance de Foata à la restriction de ƒ à C, que nous noterons τ, et obtenir ainsi un arrangement (une suite ordonnée) ω de tous les éléments de C. La correspondance de Foata consiste à écrire la suite des cycles de la décomposition en cycles disjoints de τ, en prenant bien soin :

• de terminer chacun de ces cycles par son plus petit élément,
• d'écrire les dits cycles dans l'ordre croissant de leurs plus petits éléments.

Le premier et le dernier terme de l'arrangement ω ainsi obtenu sont destinés à être les deux sommets marqués de l'arbre de Cayley produit, à partir de ƒ, par la bijection de Joyal.

Distance entre deux points au hasard d'un arbre de Cayley aléatoire

Comme autre application, on peut citer le calcul de la loi de la distance entre deux points au hasard d'un arbre de Cayley aléatoire, qui, en vertu de la bijection de Joyal, est aussi la loi du nombre de points cycliques d'une application de dans . Notons le nombre d'éléments de tels que les deux points marqués soient à distance k l'un de l'autre. Pour on a :

où compte les choix possibles de l'ensemble des étiquettes des k+1 points sur le chemin entre les deux points marqués, où compte les manières d'ordonner ces k+1 étiquettes le long du chemin entre les deux points marqués, le facteur restant comptant les forêts de k+1 arbres comportant au total n-k-1 sommets (sans compter les k+1 racines) qu'on pourrait planter le long de ce chemin. Il suit que, toujours pour

Cette loi discrète apparaît aussi dans des problèmes d'allocations (boules et urnes), dont le fameux problème des anniversaires. On peut montrer, par exemple à l'aide du lemme de Scheffé, que converge en loi vers la loi de Rayleigh, ce qui indique que la distance "typique" entre deux points d'un arbre de taille n est de l'ordre de