Aiuto calcolo combinatorio

Dobbiamo dimostrare che

Dn,k - k*Dn-1,k-1 = Dn-1, k

che può essere riscritta equivalentemente come

n*(n-1)*...*(n-k+1) = k*(n-1)(n-2)(n-k+1) + (n-1)*(n-2)*...*(n-k+1)(n-k)

Partiamo dall'espressione di destra

raccogliamo a fattore tutta la parte comune

(n-1)*...*(n-k+1) e l'altro termine é (k + n - k) = n

ottenendo n(n-1)*...*(n-k+1)

che riproduce esattamente Dn,k.

Le disposizioni semplici, ti conviene esprimerle come rapporto di due fattoriali.

Esegui il calcolo a membri separati e confronta alla fine i due risultati che devono essere espressi in un identico rapporto. E' più facile a farsi che a dirsi...

1° MEMBRO

D(n, k) = n!/(n - k)!

analogamente:

D(n - 1, k - 1) = (n - 1)!/(n - 1 - (k - 1))! = (n - 1)!/(n - k)!

Quindi , sempre a primo membro hai:

n!/(n - k)! - k·(n - 1)!/(n - k)! =

= (n! - k·(n - 1)!)/(n - k)!=

=(n·(n - 1)! - k·(n - 1)!)/(n - k)!=

=(n - 1)!/(-k + n - 1)!

2° MEMBRO

D(n - 1, k) = (n - 1)!/(n - 1 - k)!

Le due espressioni ottenute sono identiche, quindi l'uguaglianza di partenza è una identità