le factorielle

Aide sur les questions d'analyses.
mt2sr
Membre
Messages : 39
Inscription : 09 septembre 2013, 23:01

le factorielle

Message par mt2sr » 24 octobre 2013, 12:25

bonjour,
je n'arrive pas à démontrer par récurrence la relation suivantes $n!=\sum_{k=1}^{n}(-1)^{n-k}\binom{n}{k}k^{n}$
merci

JPB
Membre
Messages : 23
Inscription : 30 juin 2013, 12:18

Re: le factorielle

Message par JPB » 03 novembre 2013, 12:44

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)

mt2sr
Membre
Messages : 39
Inscription : 09 septembre 2013, 23:01

Re: le factorielle

Message par mt2sr » 03 novembre 2013, 23:53

merci pour votre réponse, c'est à partir de ce résultat que j'ai remarquer la formule du factoriel et j'ai voulais la démontrer directement en utilisant la récurrence et la je suis coincé ... donc c'est pas possible ?

Répondre