Bonjour,
Je cherche à dénombrer le nombre de feuilles et de noeuds d'un arbre. (b étant le facteur de branchement, et p la profondeur de l'arbre).
Trivialement, le nombre de feuilles est b^p.
De même, le nombre de noeuds est égal à la somme pour i variant de 0 à p de b^i.
Ce que je voudrais c'est exprimer ceci sans utiliser de somme (ou du moins une somme dont l'arité ne dépendrait pas des paramètres b et p). C'est possible ? Je suis pas certain d'être clair :-S
Posted by: fahr451
bonsoir
calcule (1-b) S
déduis en S
Posted by: Sinus
Heu, désolé mais c'est pas clair pour moi. Tu pourrais m'en dire un peu plus STP ?
Posted by: kazeriahm
tu cherches un moyen d'exprimer simplement S=somme(b^i,i=0..p).
C'est la somme d'une suite géomètrique vue au lycée normalement mais si tu veux le retrouver fais ce que te dis fahr, simplifie (1-b)*S.
Posted by: fahr451
je pense qu'on voit ça au lycée mais sinon fais ce que je te dis
développe
(1-b) S presque tous les termes se télescopent
Posted by: Sinus
(1-b^(p+1))/(1-b).
Merci à vous pour le tuyau. (Effectivement j'ai probablement vu ça au lycée ^^)
