Calcolo combinatorio: differenze tra le versioni

Versione delle 16:56, 10 dic 2005

Versione delle 11:58, 3 gen 2006

Riga 41:

== Combinazioni senza ripetizioni ==

Si chiama '''combinazione semplice''' una presentazione di elementi di un insieme nella quale non ha importanza l'ordine dei componenti e non si può ripetere lo stesso elemento più volte. La collezione delle combinazioni di <math>k</math> elementi estratti da un insieme S di <math>n</math> oggetti distinti si può considerare ottenuta dalla collezione delle disposizioni semplici di lunghezza k degli elementi di S ripartendo tali sequenze nelle '''[[Classe_di_equivalenza|classi]]''' delle sequenze che presentano lo stesso sottoinsieme di S e scegliendo una sola sequenza da ciascuna di queste classi. Si osserva che ciascuna delle suddette classi di sequenza di lunghezza k contiene k! sequenze, in quanto accanto a una sequenza &sigma; si hanno tutte e sole quelle ottenibili permutando i componenti della &sigma;. Quindi il numero delle combinazioni semplici di n elementi di lunghezza k si ottiene dividendo per k! il numero delle disposizioni semplici di n elementi di lunghezza k:

:<math>C^{k}_{n} = \frac{D^{k}_{n}}{k!} = \frac{n!}{k!(n-k)!} = {n \choose k}</math>

Riga 52:

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} =