60
4 Permutations, partitions, et graphes
On dit que σ ∈ S n est un dérangement lorsqu’il n’a pas de point fixe :
σ(i) = i pour tout 1 i n. Les points fixes de σ sont les cycles de longueur
1 dans sa décomposition en cycles disjoints. La loi uniforme sur l’ensemble
D n ⊂ S n des dérangements peut être simulée avec l’algorithme du rejet, car
le rapport des cardinaux card(D n )/card(S n ) est élevé.
Théorème 4.2 (Loi uniforme sur les dérangements). Si σ est une permutation aléatoire de loi uniforme sur S n alors
p n := P(σ ∈ D n ) =
card(D n )
card(S n )
−→
n→∞
1
e
≈ 0.37.
Si (σ k ) k1 est une suite de permutations aléatoires indépendantes et identiquement distribuées de même loi uniforme sur S n et si
T := inf{k 1 : σ k ∈ D n }
alors la permutation aléatoire σ T suit la loi uniforme sur D n et la variable T
suit la loi géométrique de paramètre p n d’espérance 1/p n −→
n→∞
e ≈ 2.72.
On note parfois !n = card(D n ), et on a !(n + 1) = (n + 1)×!n + (−1)
n+1 ,
analogue de (n + 1)! = (n + 1) × n!.
On peut améliorer la performance en stoppant à chaque étape de proposition l’algorithme de Fisher-Yates-Knuth dès qu’un point fixe apparaît.
Démonstration. Si σ suit la loi uniforme sur S n alors {σ ∈ D n } = ∪
n
i=1 A i où
A i = {σ(i) = i}, et donc, grâce au principe d’inclusion-exclusion
P(σ ∈ D n ) = 1−P(∪ 1in A i ) = 1−
n
p=1
(−1)
p+1
1≤i1<··· P(A i1 ∩· · ·∩A ip ).
Or pour tout 1 p n,
1i1<···ipn
P(A i1 ∩ · · · ∩ A ip ) =
1i1<··· (n − p)!
n!
=
n
p
(n − p)!
n!
=
1
p!
d’où P(σ ∈ D n ) = 1 −
n
p=1
(−1)
p+1
p!
→ e
−1 .
4.3 Partitions aléatoires
Un appariement
5 de 2n points est une partition de {1, . . . , 2n} en n parties
de cardinal 2, chacune constituant un «couple de points appariés». On note
A 2n l’ensemble des appariements de 2n points. L’ensemble A 2n est en bijection avec l’ensemble des dérangements involutifs de {1, . . . , 2n}, c’est-à-dire
5. «Matching» en anglais.