Calcolo combinatorio: differenze tra le versioni

Versione delle 07:14, 2 mag 2006

Versione delle 16:17, 14 mag 2006

Riga 55:

Quando l'ordine non è importante ma è possibile avere componenti ripetute si parla di '''combinazioni con ripetizione'''. Nelle combinazioni con ripetizione di lunghezza k ogni elemento può essere ripetuto fino a <math>k</math> volte. Pensiamo in particolare alle combinazioni con ripetizione di lunghezza k dell'insieme dei primi n interi positivi

e più precisamente alle sequenze non decrescenti di lunghezza k di interi in {1,2,...,n}.

Consideriamo una di queste sequenze <math>m_1, m_2, \dots, m_k</math> e associamole la sequenza <math>m_1, m_2+1, \dots, m_k+k-1</math>. Si constata che 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|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>CR^{k}_{n} = C^{k}_{n+k-1} = {n + k -1 \choose k} =