62
4 Permutations, partitions, et graphes
G
(X) = exp(X)G(X), d’où la formule G(X) = exp(exp(X)−1). On reconnaît
la transformée de Laplace de la loi Poi(1). Les nombres de Bell sont donc les
moments de cette loi, d’où la formule dite de Dobinski :
B n =
1
e
∞
k=1
k
n
k!
.
Elle intervient dans un algorithme de simulation de la loi uniforme sur Π n .
Théorème 4.4 (Algorithme de Stam). Soit n 1. Soit K un entier aléatoire
valant k avec probabilité k
n /(k!eB n ) pour tout k 0. Sachant K, soient
C 1 , . . . , C n des variables aléatoires i.i.d. de loi uniforme sur {1, . . . , K}. Soit
P la partition aléatoire de {1, . . . , n} obtenue en décidant que i, j sont dans
le même bloc ssi C i = C j . Alors P suit la loi uniforme sur Π n .
La loi de K est bien définie grâce à la formule de Dobinski. Il est commode
d’interpréter C 1 , . . . , C n comme des couleurs, les blocs de P regroupant donc
les éléments par couleur. L’entier aléatoire K peut être simulé avec l’algorithme basique pour les lois discrètes.
Démonstration. Si p ∈ Π n possède b blocs alors
P(P = p) =
∞
k=b
P(P = p | K = k)P(K = k)
=
∞
k=b
k(k − 1) · · · (k − b + 1)
k n
k
n
k!eB n
=
1
B n
.
4.4 Graphes aléatoires
Dans toute cette section on pose V = {1, . . . , n}. Un graphe fini
G = (V, E)
est un couple où E ⊂ {{i, j} : i, j ∈ V, i = j}. Les éléments de V sont les
sommets
6 du graphe tandis que les éléments de E sont les arêtes
7 du graphe.
Il existe au plus une arête entre deux sommets distincts (absence d’arêtes
multiples), et aucune entre un sommet et lui même (absence de boucles).
Les arêtes ne sont pas orientées. On reprend la terminologie concernant les
graphes finis introduite dans le chapitre 16 : chemins, boucles, etc. La matrice
d’adjacence A de G est la matrice symétrique n×n définie par A j,k = 1 {j,k}∈E .
6. On dit aussi sites, «vertices» en anglais, d’où la notation V .
7. On dit aussi liens, et en anglais «edges», d’où la notation E.