Correspondance fondamentale de Foata

En mathématiques, et plus précisément en combinatoire, la correspondance fondamentale de Foata est une correspondance entre suites sans répétitions et permutations, différente de la correspondance classique où la suite sans répétitions est la suite des images, par la permutation, des éléments 1, 2, 3, etc. dans cet ordre. Cette correspondance facilite, par exemple, l'analyse combinatoire du nombre de cycles et de la taille des cycles d'une permutation.

Description

Il y a plusieurs manières d'encoder une permutation à l'aide d'une suite $\omega =({\omega }_1,{\omega }_2,\dots ,{\omega }_n)$ de $n$ nombres distincts tirés de $[[1,n]]$ :

• de la manière la plus classique, à partir de $\omega ,$ on obtient la permutation $T\omega =\sigma$ définie par $\sigma (i)={\omega }_i,$ $1\le i\le n$ ;

• d'une manière plus liée à la structure des cycles, à partir de $\omega ,$ on obtient la permutation $R\omega =\tau$ définie par $\tau (1)={\omega }_1,$ ${\tau }^2(1)={\omega }_2,$ … , ${\tau }^k(1)={\omega }_k,$ tant que $k$ est plus petit que la longueur ${\ell }_1$ du cycle de $\tau$ contenant 1 ( ${\ell }_1$ est la taille de l'orbite de 1) : la position de 1 dans la suite $\omega$ signale d'ailleurs la longueur de ce cycle : ${\omega }_{{\ell }_1}=1.$ Comment interpréter alors ${\omega }_{{\ell }_1+1}$ ? Foata propose d'utiliser la suite restante ${\omega }^{\prime }=({\omega }_{{\ell }_1+1},{\omega }_{{\ell }_1+2},\dots ,{\omega }_n),$ si elle n'est pas vide, pour encoder les images du plus petit élément $m_2$ de cette suite

en posant $\tau (m_2)={\omega }_{{\ell }_1+1},$ ${\tau }^2(m_2)={\omega }_{{\ell }_1+2},\dots ,{\tau }^k(m_2)={\omega }_{{\ell }_1+k},$ là encore, tant que $k$ est plus petit que la longueur ${\ell }_2$ du cycle de $\tau$ contenant $m_2$ : la position de $m_2$ dans la suite $\omega$ signale d'ailleurs la longueur de ce cycle : ${\omega }_{{\ell }_1+{\ell }_2}=m_2.$ On itère alors le procédé avec la suite ${\omega }^{\prime \prime }=({\omega }_{{\ell }_1+{\ell }_2+1},{\omega }_{{\ell }_1+{\ell }_2+2},\dots ,{\omega }_n),$ tant qu'elle n'est pas vide, pour encoder les images du plus petit élément de cette suite

Le nombre d'itérations de ce procédé est le nombre de cycles de la décomposition de $\tau$ en cycles disjoints.

Cette seconde correspondance entre suites sans répétitions et permutations est précisément la correspondance fondamentale de Foata.

Bijectivité

Cet encodage d'une permutation par une suite, attribué à Foata, est-il bijectif, c.-à-d. atteint-on toutes les permutations ? N'atteint-on pas plusieurs fois la même permutation ? En effet, un cycle de longueur $k$ donné s'écrit de $k$ manières différentes (123 s'écrit aussi 231 ou 312), et l'unique décomposition en cycles d'une permutation à $\ell$ cycles disjoints, de longueurs respectives $(k_j{)}_{1\le j\le \ell },$ s'écrit donc de Modèle:Centrer manières différentes, puisque des cycles disjoints commutent. De plus la séquence obtenue en juxtaposant les écritures des différents cycles est ambiguë, car on y perd la trace des séparations entre les cycles.

Cependant, on notera que la séquence obtenue à l'aide de la correspondance de Foata évite tous ces écueils. En effet on n'écrit pas chaque cycle n'importe comment, mais en terminant par son plus petit élément, ce qui fixe une manière unique d'écrire chaque cycle. Par ailleurs, on n'écrit pas les cycles dans n'importe quel ordre, mais rangés par ordre croissant du plus petit élément de chaque cycle. Il est ainsi clair que chaque permutation possède un seul encodage, bien défini, donné par le cycle contenant 1, écrit de sorte à se terminer par $m_1=1,$ suivi par le cycle contenant le plus petit élément, $m_2,$ n'appartenant pas au cycle de 1, s'il existe des éléments n'appartenant pas au cycle contenant 1, ce deuxième cycle écrit de sorte à se terminer par $m_2,$ etc.

Réciproquement, chaque encodage $\omega$ ne peut être associé qu'à une seule permutation : en effet, bien que la fin de chaque cycle ne soit pas indiquée par l'encodage (qui est une suite de $n$ nombres tous différents, mais sans marques qui puissent indiquer la fin de chaque cycle), on remarque que si $\omega$ est associé, via la correspondance fondamentale de Foata, à une permutation $\tau ,$ alors chaque $m_i$ est plus petit que tous les nombres entiers situés après lui dans la suite $\omega ,$ et que cette propriété est caractéristique des $m_i,$ puisque le plus petit élément du cycle apparaissant en dernier dans le cycle, les autres nombres du cycle sont suivis, un peu plus loin, par un nombre qui est strictement plus petit. En d'autres termes, les $m_i$ sont exactement les records vers le bas de la suite renversée $\tilde{\omega }=({\omega }_n,{\omega }_{n-1},\dots ,{\omega }_1)$. Ainsi

Cela permet de retrouver les fins de cycles de la permutation encodée par la suite $\omega ,$ et de vérifier ainsi que chaque suite possède un antécédent unique dans l'ensemble des permutations.

Applications

On peut considérer le groupe symétrique ${𝔖}_n$ des permutations de n symboles comme un univers probabiliste, chaque permutation étant équiprobable. Alors la longueur des cycles, le nombre de cycles de la décomposition d'une permutation en cycles disjoints, le nombre de montées, le nombre d'inversions, etc. sont des variables aléatoires, dont la loi est intéressante. Par exemple, une formule due à Cauchy indique que la loi jointe du nombre de cycles de longueur respectivement 1,2,3, etc. est la loi d'une suite $(Y_1,Y_2,Y_3,\dots )$ de variables de Poisson indépendantes de paramètres respectifs 1, 1/2, 1/3, etc., 1/n, conditionnées à ce que : Modèle:Centrer Cela entraîne (mais pas immédiatement) que la loi jointe du nombre de cycles de longueur respectivement 1, 2, etc. converge vers une suite de variables de Poisson indépendantes de paramètres respectifs 1, 1/2, 1/3, etc., non conditionnées, mais cela ne permet pas de dire grand chose sur la loi limite des longueurs des plus grands cycles d'une permutation tirée au hasard. C'est là, entre autres, que la correspondance de Foata montre son utilité.

Stick-breaking process, processus de Poisson-Dirichlet et longueurs des cycles

Stick-breaking process et processus de Poisson-Dirichlet

Le Modèle:Lien de paramètre (0, θ) est une variable aléatoire $X=(X_k{)}_{k\ge 1}$ à valeurs dans le simplexe de dimension infinie : Modèle:Centrer La description la plus parlante du processus de Poisson-Dirichlet est donnée par l'« algorithme » suivant, qui produit le processus de Poisson-Dirichlet $X=(X_k{)}_{k\ge 1}$ :

• casser un bâton de longueur 1, en deux morceaux de tailles aléatoires respectives $Y_1=U_1$ et $R_1=1-Y_1$, puis casser à nouveau le morceau restant $R_1=1-Y_1$ en deux morceaux aléatoires $Y_2=R_1{U}_2$ et $R_2=R_1(1-U_2)$, puis casser à nouveau le morceau restant $R_2$ en deux morceaux aléatoires $Y_3=R_2{U}_3$ et $R_3=R_2(1-U_3)$Modèle:Etc. de manière à produire une suite $Y=(Y_k{)}_{k\ge 1}$ à valeurs dans $S$ ;
• ordonner la suite $Y=(Y_k{)}_{k\ge 1}$ dans l'ordre décroissant pour obtenir une suite décroissante $X=(X_k{)}_{k\ge 1}$ à valeurs dans $S$.

Si les variables aléatoires réelles $(U_k{)}_{k\ge 1}$ sont indépendantes et suivent toutes la loi bêta de paramètre (1, θ), alors $X=(X_k{)}_{k\ge 1}$ suit la loi de Poisson-Dirichlet de paramètre (0, θ).

Nota. $Y(\omega )$ appartient à $S$ si et seulement si Modèle:Centrer ce qui se produit avec probabilité 1 dans le cas du processus de Poisson-Dirichlet. Les $Y_i(\omega )$ sont donnés par la formule explicite Modèle:Centrer et les restes $R_i(\omega )$ sont donnés par Modèle:Centrer

Lien avec les longueurs des cycles

Considérons une permutation au hasard sur n symboles, τ, ou encore la suite ω de n nombres tous différents qui lui est associée par la correspondance de Foata. Notons $X^{(n)}(\omega )={(X_k^{(n)}(\omega ))}_{k\ge 1}$ la suite finie des longueurs des cycles de la décomposition de τ, rangées par ordre décroissant, longueurs toutes divisées par n, et suite finie complétée par une suite infinie de zéros.

Par exemple, pour $\omega =(2,8,10,6,1,3,12,5,4,9,7,15,11,14,13)$ et $\tau =(2,8,10,6,1)(3)(12,5,4)(9,7)(15,11)(14,13),$ on a Modèle:Centrer

Alors Modèle:, Modèle:Théorème

Grâce à la correspondance de Foata, on voit que les longueurs des cycles sont dictées par les positions des nombres $m_i$ (les records successifs) lesquelles positions sont uniformément distribuées sur la place laissée par les cycles précédents, ce qui fait apparaître naturellement une version discrète du stick-breaking process. On peut alors sans peine formaliser une démonstration rigoureuse du résultat de convergence en loi ci-dessus.

Notons que la loi de $X_1$ (premier terme de la suite X) est appelée distribution de Dickman et est omniprésente dans l'analyse probabiliste d'objets algébriques (taille du plus grand facteur premier d'un nombre entier tiré au hasard, degré du facteur premier de plus haut degré d'un polynôme tiré au hasard, taille du plus long cycle d'une permutation tirée au hasard, etc.).

Interprétations du nombre de Stirling

Les nombres de Stirling de première espèce comptent le nombre de permutations de n objets ayant exactement k cycles, mais aussi le nombre de permutations de n objets ayant exactement k records. À l'aide du code de Lehmer d'une permutation, le nombre de records, et donc le nombre de cycles également, peuvent être vus comme des sommes de variables de Bernoulli indépendantes, ce qui explique la forme multiplicative de la série génératrice des nombres de Stirling, et ouvre la voie à des estimées précises sur la concentration de la loi du nombre de cycles (estimations via l'inégalité de Hoeffding, ou bien à l'aide du théorème central limite).

Voir aussi

Bibliographie

• Modèle:Ouvrage, Section 10.2.
• Modèle:Analytic Combinatorics, Section II.6.3.
• Modèle:Ouvrage, Section 2.2.4.
• Modèle:Ouvrage

Article connexe

Bijection de Joyal