k entiers consécutifs
Pierre Capdevila
toujours divisible par k!
C'est pourquoi la formule donnant le nombre C(n,k) de combinaisons possibles
de k éléments pris dans un ensemble cardinal n tombe bien sur un entier (je
vous rappelle que C(n,k) est égal au produit de k entiers consécutifs divisé
par k!).
Comment peut-on démontrer cette propriété ?
Cordialement,
Pierre
Gilles Radenne
On peut bêtement démontrer que la définition de C(n,k) par récurrence
coïncide avec la définition par les factorielles, et la déf. par
récurrence montre bien que C(n,k) est entier.
--
Gilles
Laurent Demonet
En démontrant que C(n,k) est le nombre de choix de k objets parmi n et est donc
entier.
Sinon, on peut (ce qui revient au même) voir que C(n, k) = C(n-1, k) + C(n-1,
k-1) et
y appliquer une récurrence pour montrer que C(n, k) est entier. Ces
démonstrations sont
les plus simples. Sinon, on peut en faire une démonstration arithmétique en
calculant la valuation
p-adique du produit de k nombres consécutifs pour voir qu'elle est plus grande
que celle de k!.
Cela revient à montrer que pour tout p premier et pour tout a, il y a toujours
plus (au sens large du
terme) de nombres entre n - k + 1 et n qui sont divisibles par p^a qu'entre 1 et
k : il y a [k / p^a]
nombres entre 1 et n divisibles par p^a et il y en a [n / p^a] - [(n-k) / p^a]
entre n - k + 1 et n et on
conclut par [a+b] >= [a] + [b].
NB : [.] désigne la partie entière.
Laurent
Pierre Capdevila
Cordialement, Pierre.
"Laurent Demonet" <ldem...@noos.fr> a écrit dans le message news:
3AE730EA...@noos.fr...
j-p boucheron
> Vous avez probablement remarqué que le produit de k entiers consécutifs est
> toujours divisible par k!
Pour tout n entier, n*(n-1)*...*(n-k+1) est le cardinal de l'ensemble X
des k-uplets (u_1,...,u_k) d'éléments distincts de {1,2,...,n}.
La relation binaire ~ sur X définie par :
(u_1,...,u_k) ~ (v_1,...,v_k)
ssi
{u_1,...,u_k}={v_1,...,v_k}
est une relation d'équivalence dont toutes les classes ont k! éléments.
(Bon d'accord, c'est la preuve que C(n,k) est entier, à peine
déguisée...)
--
jpb
Pierre Capdevila
Cordialement, Pierre.
"j-p boucheron" <jean_philip...@noos.fr> a écrit dans le message
news: 1esh3sv.v3k2f5d1l8a2N%jean_philip...@noos.fr...
Stéphane Ménart
> Vous avez probablement remarqué que le produit de k entiers
consécutifs est
> toujours divisible par k!
Pour n entier >= 0 et k entier > 0, appelons P(n,k) la proposition
"(n+1)(n+2)...(n+k) est divisible par k!"
On a l'identité :
(n+1)(n+2)...(n+k) = n(n+1)(n+2)...(n+k-1) + k(n+1)(n+2)...(n+k-1)
Par conséquent, pour démontrer P(n,k), il suffit de prouver que
n(n+1)(n+2)...(n+k-1) est divisible par k! et que (n+1)(n+2)...(n+k-1)
est divisible par (k-1)!, autrement dit de prouver P(n-1,k) et
P(n,k-1).
On est donc ramené de proche en proche à prouver les propositions
P(0,k) et P(n,1), qui sont évidentes.
Cordialement
Stéphane
Pierre Capdevila
Ce qui me chiffonne, c'est que lorsqu'on poursuit le raisonnement au
deuxième puis au troisième niveau, on s'aperçoit qu'un arbre se construit,
et que le nombre de P(i,j) à démontrer croît.
Saurait-on faire la démonstration de récurrence directe à partir de ton idée
? Il faudrait je pense appliquer le principe de récurrence totale sur les
deux indices n et k. On pourrait par exemple admettre que P(n,k) est
vérifiée pour toutes les valeurs inférieures ou égales à p et à k et
démontrer que P(n+1,k), P(n,k+1) et P(n+1,k+1) sont alors vérifiées. Qu'en
penses-tu ?
Cordialement, Pierre.
Laurent Demonet
On peut tout à fait présenter cela comme une récurrence sur n+k.