Dimostrare con doppio conteggio la seguente identità
$$
k \times\left(\begin{array}{l}
n \\
k
\end{array}\right)=n \times\left(\begin{array}{l}
n-1 \\
k-1
\end{array}\right) .
$$
Qualcuno può spiegarmi come fare? So cos’è il doppio conteggio ma non ho capito quale sia la dimostrazione da effettuare
14
punti
Livello 0
La dimostrazione classica (senza l'induzione ) é
k*C(n,k) =
= k * n!/(k! (n-k)!) = n!/((k-1)!(n-k)!) = n * (n-1)!/((k-1)! * ((n-1)-(k-1)!)) =
= n* C(n-1,k-1)
Quella col "doppio conteggio" non la tengo presente, ma forse una possibile interpretazione é la seguente.
Se formo un sottoinsieme di k elementi presi da n il numero di modi in cui si può estrarre il primo come singolo
e poi in blocco gli altri k-1 dai restanti n-1 é n C (n-1, k-1).
Questi modi coprono diverse volte i modi in cui si potrebbero estrarre i k elementi tutti in una volta.
Infatti il primo elemento - per appartenere a quel gruppo - potrebbe presentarsi in k modi.
Pertanto k C (n,k) = n C(n-1,k-1).
38026
punti
Livello 6
Legge dei tre fattoriali:
Primo membro=
=k*n!/((n-k)!k!)=n!/((n-k)!(k-1)!)
Secondo membro=
=n*(n-1)!/((n-1-k+1)!(k-1)!)=n!/((n-k)!((k-1)!)
78233
punti
Genius II
