Calcolo combinatorio: differenze tra le versioni

Versione delle 00:14, 2 nov 2004

Versione delle 01:40, 2 nov 2004

Riga 37:

<math>

DR^{k}_{n}

= {\underbrace{n_1n \cdot n_2n \cdot \dots \timescdot n_kn} \atop {k-volte}}

= n^k

</math>

Riga 45:

=== Combinazioni senza ripetizioni ===

Si chiama '''combinazione semplice''' una configurazionepresentazione indi cuielementi di un insieme nella quale non ha importanza l'ordine deglidei elementicomponenti e non si può ripereteripetere lo stesso elemento più volte. PotendoLa sceglierecollezione delle combinazioni di <math>k</math> elementi estratti da un insieme S di <math>n</math> oggetti distintitidistinti si devonopuò calcolareconsiderare leottenuta permutazionidalla deicollezione delle disposizioni semplici di lunghezza <math>k</math> oggettidegli eelementi toglieredi tutteS leripartendo tali sequenze ugualinelle aclassi menodelle sequenze che presentano lo stesso sottoinsieme di unS ordinamento.e Lescegliendo primeuna sonosola esattamentesequenza leda disposizioniciascuna semplicidi mentrequeste leclassi. ultimeSi sonoosserva leche permutazioniciascuna possibilidelle dellasuddette classi di sequenza di lunghezza k contiene k! sequenze, ovveroin 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 <math>k!</math> il numero delle disposizioni semplici di n elementi di lunghezza k:

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

Di solito tra le diverse disposizioni semplici di una classe si scieglie come combinazione rappresentativa

Ad esempio le combinazioni semplici di :

la sequenza nella quale i componenti compaiono in ordine crescente (tutti gli insiemi finiti possono avere

gli elementi ordinati totalmente, ovvero associati biunivocamente ai primi interi positivi).

Ad esempio le combinazioni semplici di lunghezza 4 degli elementi di {1,2,3,4,5,6} sono 6! / (4! 2!) = 15:

<br>1234, 1235, 1236, 1245, 1246, 1256, 1345, 1346, 1356, 1456, 2345, 2346, 2356, 2456, 3456.

==== Configurazioni non ordinate di dimensione kCombinazioni con ripetizioni ====

Quando l'ordine non è importante ma è possibile avere ripetizione deglicomponenti elementiripetute si parla di '''combinazioni con ripetizione'''. In questo caso un elemento <math>n</math> può essere ripetuto fino a <math>k</math> volte ma bisogna sempre eliminare tutte le sequenze simili a meno di un ordinamento:

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 k 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 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} = \fracC^{k}_{(n+k-1)!} = {k!(n + k -1)! \choose k} = \frac{(n+k-1)!}{k!(n+k-1-k)!}</math>

<math>

CR^{k}_{n} = \frac{DR^{k}_{n}}{k!}

= \frac{ {\underbrace{n_{1} \times \dots \times n_{k}} \atop {k-volte}} } {k!}

= \frac{ n \times [(n-1)+1] \times [(n-2)+2] \times \dots \times [(n-k)+k]} {k!} =</math>

Ad esempio le combinazioni con ripetizione di lunghezza 2 degli elementi di {1,2,3,4,5} sono 6! / (2! 4!) = 15:

<math>

<br>11, 12, 13, 14, 15, 22, 23, 24, 25, 33, 34, 35, 44, 45, 55.

= \frac{(n+k-1)!}{k!(n-1)!} = \frac{(n+k-1)!}{k!(n+k-1-k)!}

</math>

riscrivibile quindi come

<math>

CR^{k}_{n} = {n + k -1 \choose k}

</math>

=== Osservazione linguistica ===

Ad esempio le combinazioni con ripetizione di :

Osserviamo che le locuzioni ''disposizioni con ripetizione'' e ''combinazioni con ripetizione''

sono locuzioni idiomatiche per la matematica: non si devono interpretare in senso letterale;

Locuzioni più precise, ma pesanti, sarebbero ''disposizioni che possono presentare ripetizioni'' e la

corrispondente per le combinazioni. Siamo quindi in presenza di un certo conflitto fra

convenzioni matematiche e significato letterale.

[[Categoria:Combinatorica]]