Correspondance fondamentale de Foata

Il y a plusieurs manières d'encoder une permutation avec une suite de nombres différents tirés de ...

Catégories :

Analyse combinatoire - Probabilités

Page(s) en rapport avec ce sujet :

transformation principale donnée par CARTIER et FOATA qui faisait.... Soit l le nombre d'inversions de w. La suite r = r1r2... rl ∈ {1, 2, ..., m−..... cycles disjoints. On généralise cette décomposition au cas des bimots. Un bimot (u..... Distribution Euler-mahonienne : une correspondance, C. R. Acad.... (source : www-irma.u-strasbg)
La correspondance de rotation (arbres géneraux binaires).... Cycles dans les permutations : le nombre de cycles vaut en moyenne H (n), le nombre harmonique... Application au nombre de maxima via la bijection principale de Foata.... (source : algo.inria)
d'après sa factorisation en cycles, mais central dans la suite, ... fix (σ) (resp. trans (σ) ) est le nombre de points fixes (resp. de .... k ≤ n et que la correspondance doit ainsi être, non pas terme à terme, mais bien suite à ... Le théorème combinatoire essentiel de D. Foata est alors ce dernier, en forme de ... (source : ehess)

Il y a plusieurs manières d'encoder une permutation avec une suite de nombres différents tirés de :

de la manière la plus classique, à partir de on obtient la permutation définie par ;

Exemple :

Si alors

$\begin{align} \sigma(1)&=2 \\ \sigma(2)&=8 \\ \sigma(3)&=10 \\ \sigma(4)&=6 \\ \dots&=\dots \end{align}$

d'une manière plus liée à la structure des cycles, à partir de on obtient la permutation définie par..., tant que est plus petit que la longueur du cycle de contenant 1 (est la taille de l'orbite de 1) : la position de 1 dans la suite signale d'ailleurs la longueur de ce cycle : Comment interpréter alors ? Foata propose d'utiliser la suite restante si elle n'est pas vide, pour encoder les images du plus petit élément de cette suite

$m_{2}=\min\{\omega_{k}\ |\ell_1+1\le k\le n\},$

en posant ici encore, tant que est plus petit que la longueur du cycle de contenant : la position de dans la suite signale d'ailleurs la longueur de ce cycle : On itère alors le procédé avec la suite tant qu'elle n'est pas vide, pour encoder les images du plus petit élément de cette suite

$m_{3}=\min\{\omega_{k}\ |\ell_{1}+\ell_{2}+1\le k\le n\}.$

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

Cette seconde correspondance entre suites sans répétitions et permutations est exactement la correspondance principale de Foata.

Exemple :

Toujours avec on a

$\begin{align} m_{1}&=1,\ \ell_{1}=5,\ \tau(1)=2,\ \tau(2)=8,\ \tau(8)=10,\ \tau(10)=6,\ \tau(6)=1, \\ m_{2}&=3,\ \ell_{2}=1,\ \tau(3)=3, \\ m_{3}&=4,\ \ell_{3}=3,\ \tau(4)=12,\ \tau(12)=5,\ \tau(5)=4, \\ m_{4}&=7,\ \ell_{4}=2,\ \tau(7)=9,\ \tau(9)=7, \\ m_{5}&=11,\ \ell_{5}=2,\ \tau(11)=15,\ \tau(15)=11, \\ m_{6}&=13,\ \ell_{6}=2,\ \tau(13)=14,\ \tau(14)=13. \end{align}$

Ainsi la correspondance principale de Foata associe à la permutation dont la décomposition en cycles disjoints est :

$\tau=(2,8,10,6,1)\ (3)\ (12,5,4)\ (9,7)\ (15,11)\ (14,13)\ =\ R(\omega).$

D'autre part l'écriture respectant les traditions de est :

$Tˆ{-1}\circ R(\omega)=(2,8,3,12,4,1,9,10,7,6,15,5,14,13,11).$

D'un autre côté, la décomposition en cycles disjoints de est :

$\sigma=(2,8,5,1)\ (10,9,4,6,3)\ (12,15,13,11,7)\ (14).$

Ainsi la correspondance principale de Foata associe à la suite suivante :

$\tilde{\omega}=Rˆ{-1}\circ T(\omega)=(2,8,5,1,10,9,4,6,3,12,15,13,11,7,14).$

Bijectivité

Cet encodage d'une permutation par une suite, attribué à Foata, est-il bijectif, i. e. atteint-on l'ensemble des permutations ? N'atteint-on pas plusieurs fois la même permutation ? En effet, un cycle de longueur donné s'écrit de manières différentes (123 s'écrit aussi 231 ou 312), et l'unique décomposition en cycles d'une permutation à cycles disjoints, de longueurs respectives s'écrit par conséquent de

$\ell !\prod_{1\le j\le\ell}k_{j}$

manières différentes, puisque des cycles disjoints commutent. De plus la séquence obtenue en juxtaposant les écritures des différents cycles est ambigue, car on y perd la trace des séparations entre les cycles.

Cependant, on notera que la séquence obtenue avec 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. D'autre part, 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 suivi par le cycle contenant le plus petit élément, 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 etc...

Réciproquement, chaque encodage ne peut être associé qu'à une seule permutation : en effet, quoique la fin de chaque cycle ne soit pas indiquée par l'encodage (qui est une suite de nombres tous différents, mais sans marques qui puissent indiquer la fin de chaque cycle), on remarque que si est associé, via la correspondance principale de Foata, à une permutation alors chaque est plus petit que l'ensemble des nombres entiers localisés après lui dans la suite et que cette propriété est caractéristique des puisque le plus petit élément du cycle apparaissant en dernier dans le cycle, les autres nombres du cycle sont suivis, légèrement plus loin, par un nombre qui est strictement plus petit. En d'autres termes, les sont précisément les records vers le bas de la suite renversée. Ainsi

Propriété — Les cycles de la permutation associée à la suite par la correspondance principale de Foata sont décrits par les fragments de cette suite qui se terminent par les records vers le bas de la suite renversée. Surtout le nombre de cycles dans la décomposition de la permutation est égal au nombre de records vers le bas de la suite renversée.

Cela sert à retrouver les fins de cycles de la permutation encodée ensuite et de vérifier mais aussi chaque suite possède un antécédent unique dans la totalité des permutations.

Exemple

Dans l'exemple de la section précédente, les records vers le bas de la suite renversée apparaissent ci-dessous en gras et soulignés :

$\ \tilde{\omega}{=}(\underline{\bold{13}},14,\underline{\bold{11}},15,\underline{\bold{7}},9,\underline{\bold{4}},5,12,\underline{\bold{3}},\underline{\bold{1}},6,10,8,2),$

ce qui, comparé à la décomposition en cycles disjoints de la permutation :

$\tau{=}(2,8,10,6,1)\ (3)\ (12,5,4)\ (9,7)\ (15,11)\ (14,13),$

indique comment inverser la correspondance principale de Foata.

Applications

On considère généralement le groupe 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. A titre d'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 de variables de Poisson indépendantes de paramètres respectifs 1, 1/2, 1/3, etc..., 1/n, conditionnées à ce que la somme de ces variables soit n. 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 processus de Poisson-Dirichlet de paramètre (0, θ) est une variable aléatoire à valeurs dans le simplexe de dimension illimitée :

$S=\left\{x=(x_k)_{k\ge1}\,\left|\ x_i\ge0, \forall i\ge1\text{ et } \sum_{i\ge1}x_i=1\right.\right\}.$

La description la plus parlante du processus de Poisson-Dirichlet est donnée par l'«algorithme» suivant, qui produit le processus de Poisson-Dirichlet :

casser un baton de longueur 1, en deux morceaux de tailles aléatoires respectives et puis casser à nouveau le morceau restant en deux morceaux aléatoires et puis casser à nouveau le morceau restant en deux morceaux aléatoires et etc... de façon à produire une suite à valeurs dans ;

ordonner la suite dans l'ordre décroissant pour obtenir une suite décroissante à valeurs dans

Si les variables aléatoires réelles sont indépendantes et suivent toutes la loi Bêta de paramètre (1, θ) , alors suit la loi de Poisson-Dirichlet de paramètre (0, θ) .

Nota. appartient à si et uniquement si

$\ \sum_{i\ge 1}U_i(\omega)=+\infty,\$

ce qui se produit avec probabilité 1 dans le cas du processus de Poisson-Dirichlet. Les sont donnés par la formule explicite

$\ Y_i(\omega)=U_i(\omega)\ \prod_{1\le k\le i-1}\,(1-U_k(\omega)),\$

et les restes sont donnés par

$\ R_i(\omega)=\ \prod_{1\le k\le i}\,(1-U_k(\omega)).\$

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 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 illimitée de zéros.

A titre d'exemple, pour et on a

$Xˆ{(15)}(\omega)=\left(\frac13,\ \frac15,\ \frac2{15},\ \frac2{15},\ \frac2{15},\ \frac1{15},\ 0,\ 0,\ 0,\ 0,\ \dots\right).$

Alors

Théorème — est une suite de variables aléatoires à valeurs dans le simplexe, suite qui converge faiblement vers une distribution de Poisson-Dirichlet de paramètre (0, 1) (i. e. les variables aléatoires réelles intervenant dans la définition du processus de Poisson-Dirichlet suivent toutes la loi Bêta de paramètre (1, 1), qui n'est autre que la loi uniforme sur l'intervalle [0, 1]).

Grâce à la correspondance de Foata, on voit que les longueurs des cycles sont dictées par les positions des nombres (les records successifs) lesquelles positions sont uniformément distribuées sur la place laissée par les cycles qui ont précédé, 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.

Démonstration

Il est facile de voir que le nombre de suites ω de n nombres différents pris dans et vérifiant est (n-1) !. Par conséquent la longueur, que nous noterons du cycle contenant 1 dans la décomposition en cycles disjoints de vérifie

$\forall k\in[\![1,n]\!],\qquad \mathbb{P}\left(nY_1ˆ{(n)}=k\right)=\frac1n.$

Or, si on pose

$\widehat{Y}_1ˆ{(n)} \ =\ \frac{\lceil nU_1\rceil}n,$

on constate que et ont la même loi. D'autre part

$U_1\ \le\ \widehat{Y}_1ˆ{(n)}\ <\ U_1\ +\ \frac1n.$

Comme la suite converge presque sûrement vers on en déduit que la suite converge en loi vers

Examinons désormais la longueur, que nous noterons du cycle contenant dans la décomposition en cycles disjoints de On voit aisément que la loi conditionnelle de sachant que est la loi uniforme sur en effet, sachant que la suite ω débute par une suite de k-1 nombres bien précis, suivis du nombre 1, les n-k! manières de terminer la suite ω sont équiprobables, et la position du plus petit nombre restant, est par conséquent uniformément répartie sur les n-k positions de cette suite, pour la même raison que auparavant : ainsi la loi conditionnelle de sachant tout sur les k premiers termes de la suite, est la loi uniforme sur et ne dépend par conséquent pas vraiment des k-1 premiers termes de cette suite, mais seulement du fait que le nombre 1 apparaît à la k-ème position. La loi uniforme sur est par conséquent aussi la loi conditionnelle de sachant que

Posons

$\widehat{Y}_2ˆ{(n)} \ =\ \frac{\left\lceil n(1-\widehat{Y}_1ˆ{(n)})U_2\right\rceil}n.$

Alors les couples et ont même loi, mais le second couple converge presque sûrement vers En effet :

$(1-U_1)U_2\ -\frac{U_2}n\ \le \widehat{Y}_2ˆ{(n)} \ =\ \frac{\left\lceil \lfloor n(1-U_1)\rfloor U_2\right\rceil}n\ \le\ (1-U_1)U_2\ +\frac{1}n.$

Donc le couple converge en loi vers De manière légèrement fastidieuse, mais sans grande difficulté, on obtiendra ainsi, pour tout k, la convergence en loi de vers ; une méthode plus élégante, consistant à étudier la convergence des restes, est esquissée plus bas. Cela entraîne la convergence en loi de la suite vers la suite Sur le simplexe, l'opération consistant à ordonner une suite de manière décroissante est une opération continue pour la topologie de la convergence terme à terme (qui est métrisable). Ainsi les suites obtenues en réordonnant de manière décroissante les suites à savoir les suites convergent en loi aussi, vers la réordonnée décroissante de la suite Y, qui, par définition, est un processus de Poisson-Dirichlet de paramètre (0, 1).

Nota : une suite ne peut pas forcément être réordonnée de manière décroissante (par exemple l'énumération de l'ensemble des rationnels ne peut pas être réordonnée ainsi), mais une suite appartenant au simplexe peut toujours être réordonnée de manière décroissante, car la totalité des termes de cette suite supérieurs à ε>0 est un ensemble fini, par conséquent bien ordonné.

Etude des restes. Etant donné un début de suite quelconque de longueur n-k, la fin de la suite, de longueur k, est uniformément distribuée parmi les k! fins de suites envisageables. Il est alors commode d'étudier les restes successifs :

$Rˆ{(n)}_{0}=n,\ Rˆ{(n)}_{1}\ =\ n-nYˆ{(n)}_{1},\ Rˆ{(n)}_{2}\ =\ n-nYˆ{(n)}_{1}-nYˆ{(n)}_{2},\ Rˆ{(n)}_{3}\ =\ n-nYˆ{(n)}_{1}-nYˆ{(n)}_{2}-nYˆ{(n)}_{3},\ \dots$

L'uniformité des suites résiduelles, remarquée légèrement plus haut, entraîne que la loi conditionnelle de sachant que est la loi uniforme sur (la position du minimum de la suite résiduelle, de longueur k, étant uniformément distribuée sur il suit que le nombre de termes de la suite apparaissant après le minimum est uniformément distribué sur Cela fait de la suite une chaîne de Markov, partant de n, de noyau de transition particulièrement simple

$p_{k,j}\ =\ \frac1k\ 1\!\!\!\ \text{I}_{0\le j<k},\qquad k,j\in\N.$

Or on peut génèrer une telle chaîne de Markov avec une suite de variables aléatoires indépendantes uniformes sur [0, 1], via la relation de récurrence

$\widehat{R}ˆ{(n)}_{j}\ =\ \left\lfloor \widehat{R}ˆ{(n)}_{j-1}(1-U_{j})\right\rfloor,\qquad j\ge 1,\qquad\text{ et }\widehat{R}ˆ{(n)}_{0}\ =\ n.$

Posons

$r_{j}\ =\ \prodˆ{j}_{k=1}(1-U_{k}),\qquad j\ge 1,\qquad\text{ et }r_{0}\ =\ 1.$

On montre aisément que

$0\ \le\ nr_{j}-\widehat{R}ˆ{(n)}_{j}\ \le\ j,\qquad j\ge 0,$

donc la suite converge presque sûrement, terme à terme, vers la suite Donc, la suite converge en loi vers la suite r. La suite des longueurs des cycles, tels qu'ils apparaissent dans la correspondance de Foata, est déduite de la suite des restes avec la relation

$nYˆ{(n)}_{j}\ =\ Rˆ{(n)}_{j-1}\ -\ Rˆ{(n)}_{j},\qquad j\ge 1.$

Ainsi la suite converge en loi vers la suite et d'autre part

$r_{j-1}-r_{j}\ =\ Y_{j},\qquad j\ge 1.$

Notons que la loi de (premier terme de la suite X) est nommé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 polynome 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 précisément k cycles, mais également le nombre de permutations de n objets ayant précisément k records. A l'aide du code de Lehmer d'une permutation, le nombre de records, et par conséquent le nombre de cycles aussi, 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 Hœffding, ou bien à l'aide du théorème central limite).

Voir aussi

Pages liées

Permutation
Groupe symétrique
Nombre de Stirling

Distribution de Dickman
Bijection de Joyal
Code de Lehmer

Bibliographie

(en) Lothaire, Combinatorics on Words, Addison–Wesley, coll. «Encyclopedia of Mathematics and its Applications», 1983 (réimpr. 1997), 260 p. , Section 10.2.
(en) [ Flajolet] et [ Sedgewick], Analytic Combinatorics, Cambridge University Press, 15 janvier 2009, 1^re éd. , 824 p. (ISBN 0521898064) , Section II. 6.3.
(en) [ Bertoin], Random Fragmentation and Coagulation Processes, Cambridge University Press, coll. «Cambridge Studies in Advanced Mathematics», 28 août 2006, 1^re éd. , 288 p. (ISBN 0521867282) , Section 2.2.4.
(en) [ Pitman], Combinatorial Stochastic Processes : Ecole d'Eté de Probabilités de Saint-Flour XXXII - 2002, Springer, coll. «Lecture Notes in Mathematics», 6 juillet 2006, 1^re éd. , 256 p. (ISBN 354030990X)

Recherche sur Amazon (livres) :

Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Correspondance_fondamentale_de_Foata.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 10/03/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.