On note
Surj(n,p) le nombre de surjections d'un ensemble a
n éléments vers un ensemble a
p éléments (
n≥p), et
S(n,p) le nombre de Stirling de seconde espece.
Montrer que le nombre total d'applications de {1,…,n} vers {1,…,p} est pn.
En utilisant la formule d'inclusion-exclusion, montrer que Surj(n,p)=∑k=0p(−1)k(kp)(p−k)n.
Vérifier pour n=3, p=2 : Surj(3,2)=6.
En déduire que le nombre de partitions de {1,…,n} en p blocs non vides vaut S(n,p)=p!Surj(n,p).
Application : de combien de facons peut-on répartir 5 boules dans 3 urnes non vides, selon que les boules et les urnes sont ou non discernables ? On distinguera les quatre cas.