Correspondance fondamentale de Foata

Sommaire

1 Description de la correspondance fondamentale de Foata
2 Bijectivité
- 2.1 Exemple
3 Applications
- 3.1 Stick-breaking process, processus de Poisson-Dirichlet et longueurs des cycles
  - 3.1.1 Stick-breaking process et processus de Poisson-Dirichlet
  - 3.1.2 Lien avec les longueurs des cycles
- 3.2 Interprétations du nombre de Stirling
4 Voir aussi

Description de la correspondance fondamentale de Foata

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

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

Exemple :

Si $\scriptstyle\ \omega{=}(2,8,10,6,1,3,12,5,4,9,7,15,11,14,13),\$ 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 $\scriptstyle\ \omega,\$ on obtient la permutation $\scriptstyle\ R\omega=\tau$ définie par $\scriptstyle\ \tau(1)=\omega_{1},\$ $\scriptstyle\ \tau^2(1)=\omega_{2},\$ ... , $\scriptstyle\ \tau^k(1)=\omega_{k},\$ tant que $\scriptstyle\ k$ est plus petit que la longueur $\scriptstyle\ \ell_{1}$ du cycle de $\scriptstyle\ \tau$ contenant 1 ( $\scriptstyle\ \ell_{1}$ est la taille de l'orbite de 1) : la position de 1 dans la suite $\scriptstyle\ \omega$ signale d'ailleurs la longueur de ce cycle : $\scriptstyle\ \omega_{\ell_{1}}=1.\$ Comment interpréter alors $\scriptstyle\ \omega_{\ell_{1}+1}$ ? Foata propose d'utiliser la suite restante $\scriptstyle\ \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 $\scriptstyle\ m_{2}$ de cette suite

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

en posant $\scriptstyle\ \tau(m_{2})=\omega_{\ell_1+1},\$ $\scriptstyle\ \tau^2(m_{2})=\omega_{\ell_1+2},\ \dots ,\ \tau^k(m_{2})=\omega_{\ell_1+k},\$ là encore, tant que $\scriptstyle\ k$ est plus petit que la longueur $\scriptstyle\ \ell_{2}$ du cycle de $\scriptstyle\ \tau$ contenant $\scriptstyle\ m_{2}$ : la position de $\scriptstyle\ m_{2}$ dans la suite $\scriptstyle\ \omega$ signale d'ailleurs la longueur de ce cycle : $\scriptstyle\ \omega_{\ell_{1}+\ell_{2}}=m_{2}.\$ On itère alors le procédé avec la suite $\scriptstyle\ \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

$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 $\scriptstyle\ \tau$ 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 $\scriptstyle\ \ \omega{=}(2,8,10,6,1,3,12,5,4,9,7,15,11,14,13),\$ 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 fondamentale de Foata associe à $\scriptstyle\ \omega$ la permutation $\scriptstyle\ \tau$ 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).$

Par ailleurs l'écriture traditionnelle de $\scriptstyle\ \tau$ 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 $\scriptstyle\ \sigma$ est :

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

Ainsi la correspondance fondamentale de Foata associe à $\scriptstyle\ \sigma$ la suite $\scriptstyle\ \tilde{\omega}$ 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, c.-à-d. atteint-on toutes les permutations ? N'atteint-on pas plusieurs fois la même permutation ? En effet, un cycle de longueur $\scriptstyle k$ donné s'écrit de $\scriptstyle k$ manières différentes (123 s'écrit aussi 231 ou 312), et l'unique décomposition en cycles d'une permutation à $\scriptstyle \ell$ cycles disjoints, de longueurs respectives $\scriptstyle (k_{j})_{1\le j\le\ell},\$ s'écrit donc 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 ambigüe, 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 $\scriptstyle m_{1}=1,\$ suivi par le cycle contenant le plus petit élément, $\scriptstyle 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 $\scriptstyle m_{2},\$ etc ...

Réciproquement, chaque encodage $\scriptstyle \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 $\scriptstyle n$ nombres tous différents, mais sans marques qui puissent indiquer la fin de chaque cycle), on remarque que si $\scriptstyle \omega$ est associé, via la correspondance fondamentale de Foata, à une permutation $\scriptstyle \tau,\$ alors chaque $\scriptstyle m_{i}$ est plus petit que tous les nombres entiers situés après lui dans la suite $\scriptstyle \omega,\$ et que cette propriété est caractéristique des $\scriptstyle 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 $\scriptstyle m_{i}$ sont exactement les records vers le bas de la suite renversée $\scriptstyle \tilde{\omega}=(\omega_{n}, \omega_{n-1}, \dots, \omega_{1})$ . Ainsi

Propriété — Les cycles de la permutation $\scriptstyle R\omega$ associée à la suite $\scriptstyle \omega$ par la correspondance fondamentale de Foata sont décrits par les fragments de cette suite $\scriptstyle \omega$ qui se terminent par les records vers le bas de la suite renversée $\scriptstyle \tilde{\omega}=(\omega_{n}, \omega_{n-1}, \dots, \omega_{1})$ . En particulier le nombre de cycles dans la décomposition de la permutation $\scriptstyle R\omega$ est égal au nombre de records vers le bas de la suite renversée $\scriptstyle \tilde{\omega}=(\omega_{n}, \omega_{n-1}, \dots, \omega_{1})$ .

Cela permet de retrouver les fins de cycles de la permutation encodée par la suite $\scriptstyle \omega,\$ 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 :

$\ \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 $\scriptstyle\ \tau\$ :

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

indique comment inverser la correspondance fondamentale de Foata.

Applications

On peut considérer le groupe $\scriptstyle\ \mathfrak{S}_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 $\scriptstyle\ (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 :

$\sum_{k\ge1}\ k\,Y_k\ =\ 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^[1] de paramètre (0,θ) est une variable aléatoire $\scriptstyle\ X=(X_k)_{k\ge1}\$ à valeurs dans le simplexe de dimension infinie :

$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 $\scriptstyle\ X=(X_k)_{k\ge1}\$ :

casser un bâton de longueur 1, en deux morceaux de tailles aléatoires respectives $\scriptstyle\ Y_1=U_1\$ et $\scriptstyle\ R_1=1-Y_1,\$ puis casser à nouveau le morceau restant $\scriptstyle\ R_1=1-Y_1\$ en deux morceaux aléatoires $\scriptstyle\ Y_2=R_1U_2,\$ et $\scriptstyle\ R_2=R_1(1-U_2),\$ puis casser à nouveau le morceau restant $\scriptstyle\ R_2\$ en deux morceaux aléatoires $\scriptstyle\ Y_3=R_2U_3,\$ et $\scriptstyle\ R_3=R_2(1-U_3),\$ etc ... de manière à produire une suite $\scriptstyle\ Y=(Y_k)_{k\ge1}\$ à valeurs dans $\scriptstyle\ S\$ ;

ordonner la suite $\scriptstyle\ Y=(Y_k)_{k\ge1}\$ dans l'ordre décroissant pour obtenir une suite décroissante $\scriptstyle\ X=(X_k)_{k\ge1}\$ à valeurs dans $\scriptstyle\ S.\$

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

Nota. $\scriptstyle\ Y(\omega)\$ appartient à $\scriptstyle\ S\$ si et seulement 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 $\scriptstyle\ Y_i(\omega)\$ 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 $\scriptstyle\ R_i(\omega)\$ 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 $\scriptstyle\ X^{(n)}(\omega)=\left(X^{(n)}_k(\omega)\right)_{k\ge1}\$ 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 $\scriptstyle\ \ \omega=(2,8,10,6,1,3,12,5,4,9,7,15,11,14,13)\$ et $\scriptstyle\ \tau=(2,8,10,6,1)\ (3)\ (12,5,4)\ (9,7)\ (15,11)\ (14,13),$ on a

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

Alors ^[2] ^[3]

Théorème — $\scriptstyle\ \left(X^{(n)}\right)_{n\ge1}\$ est une suite de variables aléatoires à valeurs dans le simplexe $\scriptstyle\ S\$ , suite qui converge faiblement vers une distribution de Poisson-Dirichlet de paramètre (0,1) (i.e. les variables aléatoires réelles $\scriptstyle\ (U_k)_{k\ge1}\$ 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 $\scriptstyle\ 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.

Démonstration

Il est facile de voir que le nombre de suites ω de n nombres différents pris dans $\scriptstyle\ [\![1,n]\!]\$ et vérifiant $\scriptstyle\ \omega_k=1\$ est (n-1)!. Donc la longueur, que nous noterons $\scriptstyle\ nY_1^{(n)}(\omega),\$ du cycle contenant 1 dans la décomposition en cycles disjoints de $\scriptstyle\ \tau=R(\omega),\$ 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 $\scriptstyle\ Y_1^{(n)}\$ et $\scriptstyle\ \widehat{Y}_1^{(n)}\$ ont la même loi. Par ailleurs

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

Comme la suite $\scriptstyle\ \left(\widehat{Y}_1^{(n)}\right)_{n\ge 1}\$ converge presque sûrement vers $\scriptstyle\ U_1,\$ on en déduit que la suite $\scriptstyle\ \left({Y}_1^{(n)}\right)_{n\ge 1}\$ converge en loi vers $\scriptstyle\ U_1.\$

Examinons maintenant la longueur, que nous noterons $\scriptstyle\ nY_2^{(n)}(\omega),\$ du cycle contenant $\scriptstyle\ m_2\$ dans la décomposition en cycles disjoints de $\scriptstyle\ \tau=R(\omega).\$ On voit facilement que la loi conditionnelle de $\scriptstyle\ nY_2^{(n)},\$ sachant que $\scriptstyle\ nY_1^{(n)}=k,\$ est la loi uniforme sur $\scriptstyle\ [\![1,n-k]\!]:\$ en effet, sachant que la suite ω commence 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, $\scriptstyle\ m_2,\$ est donc uniformément répartie sur les n-k positions de cette suite, pour la même raison que précédemment : ainsi la loi conditionnelle de $\scriptstyle\ nY_2^{(n)},\$ sachant tout sur les k premiers termes de la suite, est la loi uniforme sur $\scriptstyle\ [\![1,n-k]\!],\$ et ne dépend donc pas vraiment des k-1 premiers termes de cette suite, mais uniquement du fait que le nombre 1 apparaît à la k-ème position. La loi uniforme sur $\scriptstyle\ [\![1,n-k]\!]\$ est donc aussi la loi conditionnelle de $\scriptstyle\ nY_2^{(n)},\$ sachant que $\scriptstyle\ nY_1^{(n)}=k.\$

Posons

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

Alors les couples $\scriptstyle\ (Y_1^{(n)},Y_2^{(n)})\$ et $\scriptstyle\ (\widehat{Y}_1^{(n)},\widehat{Y}_2^{(n)})\$ ont même loi, mais le second couple converge presque sûrement vers $\scriptstyle\ \left(U_1,(1-U_1)U_2\right)=(Y_1,Y_2).\$ 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 $\scriptstyle\ (Y_1^{(n)},Y_2^{(n)})\$ converge en loi vers $\scriptstyle\ (Y_1,Y_2).\$ De manière un peu fastidieuse, mais sans grande difficulté, on obtiendra ainsi, pour tout k, la convergence en loi de $\scriptstyle\ (Y_i^{(n)})_{1\le i\le k}\$ vers $\scriptstyle\ (Y_i)_{1\le i\le k}\$ ; 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 $\scriptstyle\ Y^{(n)}\$ vers la suite $\scriptstyle\ Y.\$ 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 $\scriptstyle\ Y^{(n)},\$ à savoir les suites $\scriptstyle\ X^{(n)},\$ convergent en loi également, 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 toujours être réordonnée de manière décroissante (par exemple l'énumération de tous les 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 l'ensemble des termes de cette suite supérieurs à ε>0 est un ensemble fini, donc 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 possibles. 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 un peu plus haut, entraîne que la loi conditionnelle de $\scriptstyle\ R^{(n)}_{\ell+1}$ sachant que $\scriptstyle\ \left(R^{(n)}_{j}\right)_{1\le j\le \ell}=(r_{1},r_{2},\dots,r_{\ell-1},k),\$ est la loi uniforme sur $\scriptstyle\ [\![0,k-1]\!]\$ (la position du minimum de la suite résiduelle, de longueur k, étant uniformément distribuée sur $\scriptstyle\ [\![1,k]\!],\$ il suit que le nombre de termes de la suite apparaissant après le minimum est uniformément distribué sur $\scriptstyle\ [\![0,k-1]\!]).$ Cela fait de la suite $\scriptstyle\ \left(R^{(n)}_{j}\right)_{j\ge 0}\$ une chaîne de Markov, partant de n, de noyau de transition très simple

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

Or on peut engendrer une telle chaîne de Markov à l'aide d'une suite $\scriptstyle\ \left(U_{j}\right)_{j\ge 1}\$ 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 facilement que

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

donc la suite $\scriptstyle\ \left(\widehat{R}^{(n)}_{j}/n\right)_{j\ge 1}\$ converge presque sûrement, terme à terme, vers la suite $\scriptstyle\ r=\left(r_{j}\right)_{j\ge 1}.\$ Par conséquent, la suite $\scriptstyle\ \left(R^{(n)}_{j}/n\right)_{j\ge 0}\$ converge en loi vers la suite r. La suite des longueurs des cycles, tels qu'ils apparaissent dans la correspondance de Foata, $\scriptstyle\ \left(nY^{(n)}_{j}\right)_{j\ge 1},\$ est déduite de la suite des restes à l'aide de la relation

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

Ainsi la suite $\scriptstyle\ \left(Y^{(n)}_{j}\right)_{j\ge 1},\$ converge en loi vers la suite $\scriptstyle\ \left(r_{j-1}-r_{j}\right)_{j\ge 1},\$ et par ailleurs

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

Notons que la loi de $\scriptstyle\ 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 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 exactement k cycles, mais aussi le nombre de permutations de n objets ayant exactement k records. A 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

Notes

↑ (en) J. F. C. Kingman, « Random Discrete Distributions », dans Journal of the Royal Statistical Society. Series B (Methodological), vol. 37, n^o 1, 1975, p. 1-22 [texte intégral]
↑ (en) A. M. Vershik et A. A. Shmidt, « Limit measures arising in the theory of groups I. », dans Theor. Probab. Appl., vol. 22, 1977, p. 79-85 .
↑ (en) J. F. Kingman, « The population structure associated with the Ewens sampling formula », dans Theor Popul Biol., vol. 11, n^o 2, avril 1977, p. 274-283

Pages liées

Bibliographie

(en) M. Lothaire, Combinatorics on Words, Addison–Wesley, coll. « Encyclopedia of Mathematics and its Applications », 1983 (réimpr. 1997), 260 p. , Section 10.2.
(en) Philippe Flajolet et Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, 15 janvier 2009, 1^re éd., 824 p. (ISBN 0521898064) , Section II.6.3.
(en) Jean 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) Jim 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)

Portail des mathématiques

Catégories :

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Correspondance fondamentale de Foata de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

Bijection de Joyal — La bijection de Joyal consiste à déplier , à l aide de la correspondance fondamentale de Foata, la partie cyclique d une application de dans pour en faire un arbre de Cayley. La bijection de Joyal permet de donner une démonstration élégante de la … Wikipédia en Français
Permutable — Permutation En mathématiques, la notion de permutation exprime l idée de réarrangement d objets discernables. Une permutation de n objets distincts rangés dans un certain ordre, correspond à un changement de l ordre de succession de ces n objets … Wikipédia en Français
Permutation — En mathématiques, la notion de permutation exprime l idée de réarrangement d objets discernables. Une permutation de n objets distincts rangés dans un certain ordre, correspond à un changement de l ordre de succession de ces n objets. La… … Wikipédia en Français
Code de Lehmer — Pour les articles homonymes, voir Lehmer. Sommaire 1 Définition 2 Décodage 2.1 Un algorithme … Wikipédia en Français
Nombre de Stirling — En mathématiques, les nombres de Stirling apparaissent dans plusieurs problèmes combinatoires. Ils tirent leur nom de James Stirling, qui les a introduits au XVIIIe siècle. Il en existe deux sortes, nommés les nombres de Stirling de première … Wikipédia en Français
Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… … Wikipédia en Français
Loi de Bernoulli — Pour les articles homonymes, voir Théorème de Bernoulli. Bernoulli Paramètres (nombre réel) Support … Wikipédia en Français
Nombre De Stirling — En mathématiques, les nombres de Stirling apparaissent dans plusieurs problèmes combinatoires. Ils tirent leur nom de James Stirling, qui les a introduits au XVIIIe siècle. Il en existe deux sortes, nommés les nombres de Stirling de première … Wikipédia en Français
Nombre de stirling — En mathématiques, les nombres de Stirling apparaissent dans plusieurs problèmes combinatoires. Ils tirent leur nom de James Stirling, qui les a introduits au XVIIIe siècle. Il en existe deux sortes, nommés les nombres de Stirling de première … Wikipédia en Français
Permutation aléatoire — Une permutation aléatoire de taille N est une permutation prise de manière uniforme dans l ensemble des permutations de taille N. Par exemple pour N=5, nous pouvons obtenir (15423) ou encore (34125). Les permutations aléatoires peuvent être mises … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Correspondance fondamentale de Foata

Sommaire

Description de la correspondance fondamentale de Foata