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  :

Exemple :

Si alors

 \begin{align}
\sigma(1)&=2
\\
\sigma(2)&=8
\\
\sigma(3)&=10
\\
\sigma(4)&=6
\\
\dots&=\dots
\end{align}
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  :

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.

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

Bibliographie

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.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu