196
14 Restaurants chinois
n
k
=
n − 1
k − 1
+ k
n − 1
k
avec conditions au bord
n
1
= 1 et
n
n
= 1
car pour choisir une partition de {1, . . . , n} ayant k blocs il faut et il suffit soit
de choisir une partition de {1, . . . , n − 1} ayant k − 1 blocs et de la compléter
avec le bloc singleton {n}, soit d’ajouter l’élément n à l’un des k blocs d’une
partition de {1, . . . , n − 1} ayant k blocs. Si X est une variable aléatoire de
loi de Poisson de paramètre λ alors
E(X
n ) =
n
k=1
n
k
λ
k
en particulier E(X
n ) = B n si λ = 1.
On dispose également de la formule explicite suivante :
n
k
=
1
k!
k
j=1
(−1)
k−j
k
j
j
n
qui peut s’obtenir grâce au principe d’inclusion-exclusion car le nombre de
Stirling de seconde espèce est égal au nombre de surjections de {1, . . . , n}
dans {1, . . . , k} divisé par k!.
Une partition de {1, . . . , n} prescrit le support des cycles mais ne précise
pas la structure interne de chaque cycle. Il peut donc y avoir plusieurs permutations pour chaque partition. Le nombre de permutations de {1, . . . , n} qui
possèdent exactement k cycles est donné par le nombre de Stirling de première
espèce non signé, noté
n
k
,
égal au coefficient de x
k dans le polynôme de Pochhammer
x (n) = x(x + 1) · · · (x + n − 1).
14.5 Pour aller plus loin
L’essentiel de ce chapitre est tiré de l’article didactique [CDM13]. Warren
Ewens est un professeur de biologie mathématique né en 1937 en Australie.
C’est à la fin des années 1960 qu’il découvre la loi qui porte aujourd’hui son
nom, en étudiant un problème d’échantillonnage en génétique des populations,
lié au modèle de Wright-Fisher, abordé dans le chapitre 12. Le paramètre θ