DM sur le dénombrement

[cassou44770]

Bonjour,
je n'arrive pas du tout à résoudre cet exercice et j'espère que vous pourrez me donner quelques pistes.


Soient n, p apprtiennet à IN tels que n >= 2 et p=< n. Le but de ce problème est de démontrer la formule suivante avec plusieurs méthodes, puis de l’utiliser :
somme de k allant de 0 à p comb (n,k)comb(n-k,p-k)=2 puissance p x comb(n,p)
-> x veut dire multiplier par

1. Méthode algébrique.
(a) Montrer que : pout tout k appartient à [0;p] comb(n,k)comb(n-k,p-k)=comb(n,p)comb(p,k)
-> Comb(n,k) veut dire coefficient binomial (n,p)
(b) En déduire la relation recherchée.

2. Méthode combinatoire. On considère l’ensemble
E = {(X; Y)|X appartient à P indice p(Nn) et Y appartient à P(X)} .
Nous allons dénombrer E de deux manières différentes puis l’identification des résultats fournira la formule souhaitée.
(a) On raisonne par décomposition en commençant par le choix de l’ensemble X appartient à P indice p(Nn).
• Combien existe-t-il de parties de N indice n à p éléments ?
• Combien existe-t-il de parties de N indice p ?
• En déduire que Card(E ) = 2 puissance p x comb(n,p)
(b) On raisonne par décomposition en commençant par le choix de Y.
• Soit k appartient à [0;p]. On note E indice k = {Y appartient à P(N indice n)|Card(Y) = k}. Dénombrer Ek.
• Après avoir fabriqué Y, et pour constituer X il nous faut compléter Y avec p ;) k éléments parmi les
éléments restants de N indice n. Combien de choix existe-t-il ?
• En déduire que Card(E ) = Somme de k allant de 0 à p comb(n,k)comb(n-k,p-k)
(c) Conclure.

3. Applications.
(a) Montrer que Somme de k allant de 0 à p k x comb(n,k)=n2(puissance n-1)
(b) Calculer somme de k allant de 0 à n kpuissance2 x comb (n,k) en appliquant la formule du début avec p = n ;) 2 et en utilisant la réponse précédente.

J'espère que vous comprendrez ce que j'ai écrit malgré les erreurs et mon incapacité à écrire avec les symboles.
Merci d'avance :we:

[Manny06]

Bonjour,
je n'arrive pas du tout à résoudre cet exercice et j'espère que vous pourrez me donner quelques pistes.


Soient n, p apprtiennet à IN tels que n >= 2 et p= x veut dire multiplier par

1. Méthode algébrique.
(a) Montrer que : pout tout k appartient à [0;p] comb(n,k)comb(n-k,p-k)=comb(n,p)comb(p,k)
-> Comb(n,k) veut dire coefficient binomial (n,p)
(b) En déduire la relation recherchée.

2. Méthode combinatoire. On considère l’ensemble
E = {(X; Y)|X appartient à P indice p(Nn) et Y appartient à P(X)} .
Nous allons dénombrer E de deux manières différentes puis l’identification des résultats fournira la formule souhaitée.
(a) On raisonne par décomposition en commençant par le choix de l’ensemble X appartient à P indice p(Nn).
• Combien existe-t-il de parties de N indice n à p éléments ?
• Combien existe-t-il de parties de N indice p ?
• En déduire que Card(E ) = 2 puissance p x comb(n,p)
(b) On raisonne par décomposition en commençant par le choix de Y.
• Soit k appartient à [0;p]. On note E indice k = {Y appartient à P(N indice n)|Card(Y) = k}. Dénombrer Ek.
• Après avoir fabriqué Y, et pour constituer X il nous faut compléter Y avec p k éléments parmi les
éléments restants de N indice n. Combien de choix existe-t-il ?
• En déduire que Card(E ) = Somme de k allant de 0 à p comb(n,k)comb(n-k,p-k)
(c) Conclure.

3. Applications.
(a) Montrer que Somme de k allant de 0 à p k x comb(n,k)=n2(puissance n-1)
(b) Calculer somme de k allant de 0 à n kpuissance2 x comb (n,k) en appliquant la formule du début avec p = n 2 et en utilisant la réponse précédente.

J'espère que vous comprendrez ce que j'ai écrit malgré les erreurs et mon incapacité à écrire avec les symboles.
Merci d'avance :we:

Pour le 1)a) ecris les deux formules avec les factorielles et après simplification tu constateras qu'elles sont égales

[cassou44770]

Pour le 1)a) ecris les deux formules avec les factorielles et après simplification tu constateras qu'elles sont égales

Merci beaucoup ça marche bien! Et dire que je cherchais un truc compliqué...

[cassou44770]

Ce que j'ai surtout beaucoup de mal c'est la qsuestion 2b, tout le reste ça va à peu près.
Si quelqu'un peut m'éclairer..

[cassou44770]

En fait je comprends pas trop comment faire la 3 non plus...