Bonjour.
Cette formule est un cas particulier de la formule plus générale $S_{p,n}=\sum_{k=1}^n(-1)^{n-k}\binom nkk^p$, où $S_{p,n}$ désigne le nombre de surjections de $\{1,2,\ldots,p\}$ vers $\{1,2,\ldots,n\}$. En effet, lorsque $n=p$, $S_{n,n}$ est aussi le nombre de bijections de $\{1,2,\ldots,n\}$ dans lui-même, soit $n!$.
Pour démontrer cette formule par récurrence, on part de la relation : $S_{p,n}=n(S_{p-1,n}+S_{p-1,n-1})$ (qui se justifie par des arguments combinatoires) et on raisonne par récurrence sur $p$. En effet, si la formule est supposée vraie au rang $p-1$, alors :
$S_{p,n}=n\Bigl(\sum_{k=1}^n(-1)^{n-k}\binom nkk^{p-1}+\sum_{k=1}^{n-1}(-1)^{n-1-k}\binom{n-1}kk^{p-1}\Bigr)$.
On regroupe les deux sommes :
$S_{p,n}=n\Bigl(\sum_{k=1}^{n-1}(-1)^{n-k}\Bigl(\binom nk-\binom{n-1}k\Bigr)k^{p-1}+n^{p-1}\Bigr)$.
On simplifie à l'aide de la formule de Pascal :
$S_{n,p}=n\sum_{k=1}^{n-1}(-1)^{n-k}\binom{n-1}{k-1}k^{p-1}+n^p=\sum_{k=1}^{n-1}(-1)^{n-k}\binom nkk^p+n^p$
et le tour est joué.
Cette formule peut aussi se démontrer à l'aide de la formule d'inversion de Pascal (voir le lien wikipedia suivant :
http://fr.wikipedia.org/wiki/Formule_d' ... _de_Pascal)