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.

DescriptionModifier

Il y a plusieurs manières d'encoder une permutation à l'aide d'une suite   de   nombres distincts tirés de   :

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

Si   alors

 
  • 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
 
en posant     là 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
 
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 précisément la correspondance fondamentale de Foata.

Exemple :
  • Toujours avec   on a
 
Ainsi la correspondance fondamentale de Foata associe à   la permutation   dont la décomposition en cycles disjoints est :
 
Par ailleurs l'écriture traditionnelle de   est :
 
  • D'un autre côté, la décomposition en cycles disjoints de   est :
 
Ainsi la correspondance fondamentale de Foata associe à   la suite   suivante :
 

BijectivitéModifier

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   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 donc de

 

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   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, bien que 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 fondamentale de Foata, à une permutation   alors chaque   est plus petit que tous les nombres entiers situé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, un peu plus loin, par un nombre qui est strictement plus petit. En d'autres termes, les   sont exactement 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 fondamentale 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  . En particulier 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 permet de retrouver les fins de cycles de la permutation encodée par la suite   et de vérifier ainsi que chaque suite possède un antécédent unique dans l'ensemble 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 :

 

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

 

indique comment inverser la correspondance fondamentale de Foata.

ApplicationsModifier

On peut considérer le groupe symétrique   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   de variables de Poisson indépendantes de paramètres respectifs 1, 1/2, 1/3, etc., 1/n, conditionnées à ce que :

 

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 cyclesModifier

Stick-breaking process et processus de Poisson-DirichletModifier

Le processus de Poisson-Dirichlet[1] de paramètre (0,θ) est une variable aléatoire   à valeurs dans le simplexe de dimension infinie :

 

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 bâton 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 manière à 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 seulement si

 

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

 

et les restes   sont donnés par

 

Lien avec les longueurs des cyclesModifier

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

Par exemple, pour   et   on a

 

Alors [2],[3]

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 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   (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 StirlingModifier

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 aussiModifier

NotesModifier

  1. (en) J. F. C. Kingman, « Random Discrete Distributions », Journal of the Royal Statistical Society. Series B (Methodological), vol. 37, no 1,‎ , p. 1-22 (lire en ligne)
  2. (en) A. M. Vershik et A. A. Shmidt, « Limit measures arising in the theory of groups I. », Theor. Probab. Appl., vol. 22,‎ , p. 79-85.
  3. (en) J. F. Kingman, « The population structure associated with the Ewens sampling formula », Theor Popul Biol., vol. 11, no 2,‎ , p. 274-283

BibliographieModifier

  • (en) M. Lothaire, Combinatorics on Words, Addison–Wesley, coll. « Encyclopedia of Mathematics and its Applications », (réimpr. 1997), 260 p., Section 10.2.
  • (en) Philippe Flajolet et Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, (ISBN 0-521-89806-4, lire en ligne), Section II.6.3.
  • (en) Jean Bertoin, Random Fragmentation and Coagulation Processes, Cambridge University Press, coll. « Cambridge Studies in Advanced Mathematics », , 1re éd., 288 p. (ISBN 0521867282), Section 2.2.4.
  • (en) Jim Pitman, Combinatorial Stochastic Processes: Ecole d'Eté de Probabilités de Saint-Flour XXXII - 2002, Springer, coll. « Lecture Notes in Mathematics », , 1re éd., 256 p. (ISBN 354030990X)

Article connexeModifier

Bijection de Joyal