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
le factorielle
Re: le factorielle
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)
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)
Re: le factorielle
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 ?