a) Tracer un arbre a trois niveaux. Combien de chemins possède cet arbre?
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
... etc
En deduire la valeur de
(3 0) + (3 1) + (3 2) + (3 3)
=1+3+3+1
=8=2³
b) Si on prolonge l'arbre précédent d'un niveau supérieur, combien y
aura t-il de chemins ? 2^4=16 chemins
En déduire la valeur de
(4 0) + (4 1) + (4 2) +
(4 3) + (4 4)
=1+4+6+4+1
=16=2^4
c) Combien de chemins possède un arbre a n niveaux ?
N=2^n chemins
En déduire
(n 0) + (n 1) +....+ (n n)
=1+n+n(n-1)/2+...+n(n-1)/2+1
=2^n