4.3 Partitions aléatoires
61
l’ensemble des éléments de S 2n sans point fixe et qui sont leur propre inverse,
autrement dit l’ensemble des éléments de S 2n obtenus en faisant le produit de
n transpositions à supports deux à deux disjoints. On a la formule d’Isserlis
card(A 2n ) =
(2n)!
2 n n!
.
C’est aussi le produit des nombres impairs inférieurs ou égaux à 2n − 1, noté
(2n − 1)!! (double factorielle). Le rapport card(A 2n )/card(S 2n ) est petit, ce
qui incite à trouver une alternative à la méthode de simulation par rejet. Voici
donc un algorithme de simulation de la loi uniforme sur A 2n .
Théorème 4.3 (Loi uniforme sur les appariements). Si σ suit la loi uniforme
sur S 2n alors l’appariement aléatoire {{σ(1), σ(n + 1)}, . . . , {σ(n), σ(n + n)}}
suit la loi uniforme sur A 2n .
2
4
1
3
6
5
2
4
1
3
6
5
Fig. 4.1. Appariement de {1, . . . , 6} obtenu avec un élément de S6 (ici n = 3).
Démonstration. Pour tout appariement {{a 1 , a n+1 }, . . . , {a n , a n+n }} on a n!
façons de permuter les n blocs et 2
n façons de permuter leur contenu, d’où
P({{σ(1), σ(n + 1)}, . . . , {σ(n), σ(n + n)}} = {{a 1 , a n+1 }, . . . , {a n , a n+n }})
= 2
n n!P(σ(1) = a 1 , . . . , σ(2n) = a 2n ) =
2
n n!
(2n)!
qui ne dépend pas de l’appariement et qui vaut précisément 1/card(A 2n ).
La décomposition en cycles d’une permutation aléatoire de loi uniforme
sur S n fournit une partition aléatoire de {1, . . . , n}. La loi de cette partition
n’est pas uniforme sur l’ensemble des partitions Π n de {1, . . . , n} (remarque
14.6). Intéressons-nous à la simulation de la loi uniforme sur Π n . Cette loi
affecte le même poids 1/B n à chaque élément de Π n , où B n = card(Π n ). En
combinatoire, la suite (B n ) n1 constitue les nombres de Bell. On a B 1 = 1,
B 2 = 2, et plus généralement, en utilisant la convention B 0 = 1, on a la
formule de récurrence triangulaire
B n+1 =
n
k=0
n
k
B k ,
où k s’interprète comme le nombre d’éléments qui ne sont pas dans le bloc
de n + 1. Il en découle que la série formelle G(X) =
∞
n=0
Bn
n! X
n vérifie