Calcolo combinatorio: differenze tra le versioni

Versione delle 23:13, 1 nov 2004

Versione delle 00:14, 2 nov 2004

Riga 1:

Il '''calcolo combinatorio''' è quellail termine che denota tradizionalmente la branca della matematica che studia i modi per raggruppare e/o ordinare secondo date regole gli elementi di un insieme finito di oggetti. UnI problemaIl di tipocalcolo combinatorio èsi legatointeressa al concettosoprattutto di contare tali modi, dettiovvero le '''configurazioni''' e viene solitamente postorisponde in termini dia domande quali "Quanti sono...", "In quanti modi...", "Quante possibili combinazioni..." ecc... .

Più formalmente, dato un insieme S di <math>n</math> oggetti si vuole contare le configurazioni che possono assumere <math>k</math> oggetti tratti da questo insieme.

Prima di affrontare un problema combinatorio bisogna capire due fatti importanti:

* Se l''''ordinamento''' è importante, ovvero se due configurazioni sono le stesse a meno di un riordinamento (Es.: <math>(x,y,z)</math> è uguale a <math>(z,x,y)</math> ? )

Riga 7:

=== Permutazioni ===

Una permutazione è un riodinamento di un insieme di oggetti ed ogni oggetto può essere considerato al più una volta. Per contare quante siano le permutazioni di un insieme con ''n'' oggetti si osservi che il primo elemento della configurazione può essere scelto in <math>n</math> modi diversi, il secondo in <math>(n-1)</math>, il terzo in <math>(n-2)</math> e così via sino all'ultimo che potrà essere preso in un solo modo essendo l'ultimo rimasto. Dunque, indicando con <math>P_{n}</math> il numero delle possibili permutazioni si ottiene che esse sono esattamente <math>n!</math> (<math>n</math> fattoriale):

Una permutazione è un riodinamento di un insieme di oggetti edè una presentazione ordinata, cioè una sequenza, dei suoi elementi nella quale ogni oggetto puòviene esserepresentato consideratouna al piùed una sola volta. Per contare quante siano le permutazioni di un insieme con ''n'' oggetti, si osservi che il primo elemento della configurazione può essere scelto in <math>n</math> modi diversi, il secondo in <math>(n-1)</math>, il terzo in <math>(n-2)</math> e così via sino all'ultimo che potrà essere preso in un solo modo essendo l'ultimo rimasto. Dunque, indicando con <math>P_{n}</math> il numero delle possibili permutazioni, si ottiene che esse sono esattamente <math>n!</math> (<math>n</math> fattoriale):

<math>P_{n} = n \times (n - 1) \times (n-2) \times \dots \times 1 = n!</math>

<math>P_{n} = n \timescdot (n - 1) \timescdot (n-2) \timescdot \dots \timescdot 1 = n!</math>

Esempio:

Ad esempio le permutazioni degli elementi dell'insieme {a,b,c} sono 3! = 6:

=== Disposizioni ===

<br>abc, acb, bac, bca, cab, cba.

==== Configurazioni ordinate di dimensione k senza ripetizioni ====

Una '''disposizione semplice''' è un ordinamento degli elementi nella quale non si possono avere ripetizioni di uno stesso oggetto.

=== Disposizioni senza ripetizioni ===

In questo caso si è interessati al numero di configurazioni che si possono creare prendendo <math>k</math> oggetti distinti da un insieme di <math>n</math> oggetti. Il primo può essere scelto in <math>n</math> modi diversi, il secondo in <math>(n-1)</math> e così via sino al <math>k-esimo</math> che può essere scelto in <math>(n-k+1)</math> modi diversi. Pertanto il numero di disposizioni semplici <math>D^{k}_{n}</math> di <math>k</math> oggetti su un insieme di <math>n</math> oggetti è dato dal numero di permutazioni totali da cui si devono togliere gli oggetti non presi in considerazione, ovvero:

Una '''disposizione semplice''' èdi lunghezza k di elementi di un ordinamentoinsieme degliS di n oggetti, con k &leq; n, è una presentazione ordinata di k elementi di S nella quale non si possono avere ripetizioni di uno stesso oggetto.

InPer questoavere caso si è interessati alil numero di queste configurazioni che si possonoconsidera creareche prendendoil <math>k</math>primo oggetti distinti da un insiemecomponente di <math>n</math>una oggetti.tale Il primosequenza può essere scelto in <math>n</math> modi diversi, il secondo in <math>(n-1)</math> e così via sino al <math>k-esimo</math> che può essere scelto in <math>(n-k+1)</math> modi diversi. Pertanto il numero di disposizioni semplici <math>D^{k}_{n}</math> di disposizioni semplici di <math>k</math> oggetti suestratti da un insieme di <math>n</math> oggetti è dato dal numero di permutazioni totali da cui si devono togliere gli oggetti non presi in considerazione, ovveroprodotto:

<math>

D^{k}_{n} = P^{k}_{n} = n \timescdot (n-1) \timescdot \dots \timescdot (n-k+1)

= \frac{n \timescdot (n-1) \timescdot \dots \timescdot 1}{(n-k) \timescdot (n-k-1) \timescdot \dots \timescdot 1}

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

</math>

Ad esempio le disposizioni semplici di lunghezza 2 degli elementi dell'insieme {1,2,3,4,5} sono <math>5\cdot 4 = 20</math>:

A titolo di ossservazione si noti come il numero di permutazioni di un insieme di oggetti sia effettivamente il numero di disposizioni semplici che si possono operare sugli stessi prendendoli <math>n</math> per volta:

<br>12, 13, 14, 15, 21, 23, 24, 25, 31, 32, 34, 35, 41, 42, 43, 45, 51, 52, 53, 54.

Si osserva che le permutazioni sono casi particolari delle disposizioni semplici: le permutazioni di un insieme di n oggetti sono le disposizioni semplici di tali oggetti di lunghezza n. In effetti per il loro numero:

<math>P_{n} = D^{n}_{n} = \frac{n!}{(n-n)!} = \frac{n!}{0!} = \frac{n!}{1} = n!</math>

<math>P_{n} = D^{n}_{n} = \frac{n!}{(n-n)!} = \frac{n!}{0!} = \frac{n!}{1} = n!</math>

Esempio:

==== Configurazioni ordinate di dimensione kDisposizioni con ripetizioni ====

SeUna l'ordinepresentazione èordinata rilevantedi nellaelementi configurazionedi edun èinsieme nella quale si possibilepossono avere ripetizioni di uno stesso elemento si parla didice '''disposizionidisposizione con ripetizioneripetizioni'''. Quello che si sta cercando èCerchiamo il numero delle possibili sequenze di <math>k</math> oggetti che riproducono gli elementi scegliendoli dadi un insieme di <math>n</math> oggetti e ognuno didei essiquali può essere preso più volte. Si hanno dunque <math>n</math> possibilità per scegliere il primo elementocomponente, <math>n</math> per il secondo ed altrettante per il terzo e così via sino al <math>k-esimo</math> che completa la configurazione. Il numero di disposizioni con ripetizionicercato è pertanto:

<math>

DR^{k}_{n}

= {\underbrace{n_{1}n_1 \timescdot n_{2}n_2 \timescdot \dots \times n_{k}n_k} \atop {k-volte}}

= n^{k}

</math>

Ad esempio le disposizioni con ripetizione di lunghezza 2 degli elementi di {1,2,3,4,5} sono <math>5\cdot 5 = 25</math>:

Esempio:

<br>11, 12, 13, 14, 15, 21, 22, 23, 24, 25, 31, 32, 33, 34, 35, 41, 42, 43, 44, 45, 51, 52, 53, 54, 55.

=== Combinazioni senza ripetizioni ===

==== Configurazioni non ordinate di dimensione k senza ripetizioni ====

Si chiama '''combinazione semplice''' una configurazione in cui non ha importanza l'ordine degli elementi e non si può riperete lo stesso elemento più volte. Potendo scegliere <math>k</math> elementi da <math>n</math> oggetti distintiti si devono calcolare le permutazioni dei <math>k</math> oggetti e togliere tutte le sequenze uguali a meno di un ordinamento. Le prime sono esattamente le disposizioni semplici mentre le ultime sono le permutazioni possibili della sequenza, ovvero <math>k!</math>:

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

Ad esempio le combinazioni semplici di :

Esempio:

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

Riga 67 ⟶ 69:

</math>

Ad esempio le combinazioni con ripetizione di :

Esempio:

[[Categoria:Combinatorica]]