Bijection de Joyal - Définition et Explications

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

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 (En théorie des ensembles, un ensemble désigne intuitivement une collection...) C des éléments cycliques de ƒ est le plus grand sous-ensemble (En mathématiques, un ensemble A est un sous-ensemble ou une partie d’un ensemble B, ou...) de \scriptstyle\ [\![1,n]\!] ayant la propriété suivante:

  • la restriction de ƒ à C est une bijection (Une fonction f: X → Y est dite bijective ou est une bijection si pour tout y...) de C dans C.

On peut alors appliquer la correspondance (La correspondance est un échange de courrier généralement prolongé sur une longue période. Le...) de Foata à la restriction de ƒ à C, que nous noterons τ, et obtenir ainsi un arrangement (La notion d'arrangement est utilisée en probabilités, et notamment pour les...) (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 biologie, la décomposition est le processus par lequel des corps organisés, qu'ils...) 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 (Un arbre est une plante terrestre capable de se développer par elle-même en hauteur, en...) 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 \scriptstyle\ D_n 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 (La notion de nombre en linguistique est traitée à l’article « Nombre...) de points cycliques d'une application de \scriptstyle\ [\![1,n]\!] dans \scriptstyle\ [\![1,n]\!]. Notons \scriptstyle\ d_{n,k} le nombre d'éléments de tels que les deux points marqués soient à distance k l'un de l'autre. Pour \scriptstyle\ 0\ \le\ k\ \le\ n-1,\ on a :

d_{n,k}\ =\ {n\choose k+1}\times (k+1)!\times n^{n-k-1}\times \frac{k+1}n,

\scriptstyle\ {n\choose k+1}\ compte les choix possibles de l'ensemble des étiquettes des k+1 points sur le chemin entre les deux points marqués, où \scriptstyle\ (k+1)!\ 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 ( Total est la qualité de ce qui est complet, sans exception. D'un point de vue comptable, un...) n-k-1 sommets (sans compter les k+1 racines) qu'on pourrait planter le long de ce chemin. Il suit que, toujours pour \scriptstyle\ 0\ \le\ k\ \le\ n-1,\

\mathbb{P}\left(D_n=k\right)\ =\ n^{-n}d_{n,k}\ =\ \frac{(k+1)\times(n)_{\downarrow k+1}}{n^{k+2}}.

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é (Le lemme de Scheffé est un critère de convergence en loi concernant les suites de...), que \scriptstyle\ D_n/\sqrt{n} converge en loi vers la loi de Rayleigh (En probabilités et en statistiques, la loi de Rayleigh est une loi de probabilité à...), ce qui indique que la distance "typique" entre deux points d'un arbre de taille n est de l'ordre de \scriptstyle\ \sqrt{n}.

Page générée en 0.035 seconde(s) - site hébergé chez Contabo
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique