Bac+1 |
Titre: denombrement
Texte Question: bonjour:Bonjour tous (sos) on note gamma(n,p)=g(n,p) le nombre de maniere de ranger p boules dans n tiroirs,chaque tiroir pouvant contenir autant de boules que l’on veut 1/j’ai calcule g(1,p) et g(2,p) 2/ j’ai montré que g(n,p)=g0,p)+g(1,p)+g(2,p)+,,,,,,,,,,+g(n-1,p) pouvez vous me donner une idée pour démontrer par récurrence que g(n,p)= p parmi n+p-1 merci de votre aide R |
Si on note xi le nombre de boules dans le tiroir d’indice i, cela revient à trouver le nombre ( g(n,p) ) de solutions en nombres entiers >= 0 de l’équation x(1)+x(2)+....x(n)=p. On voit notamment que g(1,p)=1 et g(2,p)=p+1. En faisant prendre à x(n+1) les valeurs possibles 0,1,,,,,p on obtient g(n+1,p)=g(n,0)+g(n,1)+....+g(n,p).(1) On a en particulier g(3,p)=(p+1)(p+2)/2 On peut penser que g(n,p)=C(p+n-1 , n-1).(2) ( C(n,p)=n!/((n-p)!p!) pour rappel ) On peut donc utiliser la relation (1) pour demontrer la relation (2) Puis on peut conclure en utilisant la realtion C(a+b,a)=C(a+b,b) pour ecrire que g(n,p)=C(p+n-1 , p) | Approbation le 28/12/2013 08:24:45 |