Differenze tra le versioni di "Combinazione"

 
=== Prima dimostrazione ===
Dato un qualsiasi insieme finito di ''n'' elementi, questo può essere posto in [[corrispondenza biunivoca]] con l'insieme {1, 2, ... , ''n''}; ci si può quindi chiedere quanti sono i sottoinsiemi di cardinalità ''k'' di questo.
 
A tal fine, si considerano le sequenze non decrescenti, di lunghezza ''k'', di interi appartenenti a {1, 2, ... , ''n''}. Consideriamo una di queste sequenze:
:<math>m_1,m_2,\dots,m_k</math>
 
:<math>m_1,m_2+1,\dots,m_k+k-1</math>
 
La nuova sequenza è strettamente crescente, non presenta ripetizioni e quindi individua una combinazione semplice di lunghezza ''k'' degli interi in {1, 2, ... , ''n''+''k''–1}. La precedente associazione pone in [[corrispondenza biunivoca]] le combinazioni con ripetizioni di lunghezza k degli elementi di {1, 2, ... , ''n''} con le combinazioni semplici di lunghezza ''k'' degli interi in {1, 2, ... , ''n''+''k''-1}. Quindi il numero delle combinazioni con ripetizioni di lunghezza ''k'' dei primi ''n'' interi positivi coincide con il numero delle combinazioni semplici di lunghezza ''k'' dei primi ''n''+''k''-1 interi positivi:
 
:<math>C'_{n,k} = C_{n+k-1,k} = {n + k -1 \choose k} = \frac{(n+k-1)!}{(n-1)!k!}</math>
Utente anonimo