TD 2, n°20 : calcul combinatoire

a) C(n,p) = n!/(p! (n-p)!) mais n! = n (n-1)! et p!= p (p-1)! Or :

(n-1)! / (p-1)! (n-p)! = C(n-1,p-1) ainsi : C(n,p) = n/p  C(n-1,p-1). Cette règle est parfois appelée "règle d'Euler". Si on la réapplique à

C(n-1,p-1), il vient C(n-1,p-1) = (n-1)/(p-1)  C(n-2,p-2). Au final, vient que : C(n,p)=n(n-1)/p(p-1)  C(n-2,p-2).

b) On a vu démontré en cours la règle dite de Pascal :

C(n+1,p+1) = C(n,p) + C(n,p+1) ou encore :

C(n,p) = C(n-1,p-1) + C(n-1,p)

 Si on réapplique cette règle à C(n-1,p-1) et à C(n-1,p), il vient que :

C(n-1,p-1) = C(n-2,p-2) + C(n-2,p-1)

et C(n-1,p) = C(n-2,p-1) + C(n-2,p). En ajoutant, on obtient bien que : C(n,p) = C(n-2,p) + 2 C(n-2,p-1)+ C(n-2,p-2).

CQFD