| 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 |
