Nombre de surjections

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: olivercat

Bonjour à tous.

Soit En = {1,2,...,n} et p un nombre entier.
On note Sn,p le nombre de surjections de En vers Ep.

Je voudrais montrer que:

1) p^n = SOMME(q=0 à p) C(p,q).Sn,q
avec C=combinaison

2) puis en déduire que:

Sn,p = (-1)^p SOMME(k=0 à p) (-1)^k C(p,k) k^n

Un grand merci d'avance pour ceux qui arriveront à m'aider !
Bon courage...


Posted by: busard_des_roseaux

bonsoir,

le nombre d'applications f de E_{n} vers E_{p}
est p^{n}
en effet, il y a p choix pour f(1), p choix pour f(2), .., p choix pour f(n).

Maintenant, on partitionne l'ensemble des applications de E_{n} vers E_{p} en:
1) les applications telles que Card(Im(f))=1
2) les applications telles que Card(Im(f))=2
...
k)les applications telles que Card(Im(f))=k
...
p) les applications telles que Card(Im(f))=p

Pour le cas (k), on choisit un ensemble image Im(f) , donc C_{p}^{k} choix et pour chaque choix, il y a S_{n,k} choix d'applications de E_{n} sur Im(f).

d'où la formule:

\displaystyle p^{n}=\sum_{k=0}^{p} \quad C_{p}^{k} \, S_{n,k}


Posted by: ThSQ

Ca a été posé il y a pas très longtemps (< semaine) avec un lien vers un pdf très intéressant. Cherche dans l'historique.










-