Elementi di calcolo combinatorio

Materie:Appunti
Categoria:Matematica

Voto:

2 (2)
Download:251
Data:04.05.2000
Numero di pagine:7
Formato di file:.doc (Microsoft Word)
Download   Anteprima
elementi-calcolo-combinatorio_1.zip (Dimensione: 6.1 Kb)
trucheck.it_elementi-di-calcolo-combinatorio.doc     31.5 Kb
readme.txt     59 Bytes


Testo

ELEMENTI DI CALCOLO COMBINATORIO:
Avendo a disposizione un determinato numero di oggetti distinti, che possono eventualmente essere ripetuti, sorge la necessità di formare determinati gruppi.
Stabilita una legge di formazione di questi gruppi il calcolo combinatorio ci permette di determinare il numero dei gruppi che si possono di volta in volta formare.
Prendiamo in considerazione tre tipi di raggruppamenti che prendono il nome di disposizioni, permutazioni, combinazioni.
È necessario però distinguere i raggruppamenti costituiti da oggetti tutti distinti tra loro dai raggruppamenti costituiti da oggetti presenti più volte nello stesso gruppo, cioè ripetuti.
Nel primo caso, ovvero nel caso in cui gli oggetti siano tutti distinti tra loro abbiamo:
- disposizioni semplici;
- permutazioni semplici;
- combinazioni semplici;
Nel secondo caso, ovvero nel caso in cui gli oggetti possano essere ripetuti abbiamo:
- disposizioni con ripetizione;
- permutazioni con ripetizione;
- combinazioni con ripetizione.
Indichiamo in generale con:

n: in numero totale degli oggetti che si hanno a disposizione
k: il numero degli oggetti presi in considerazione per ogni gruppo.

Il numero n prende il nome di ordine del raggruppamento, mentre il numero k prende il nome di classe del raggruppamento.

- DEFINIZIONE DI DISPOSIZIONI SEMPLICI:
Si chiamano disposizioni semplici di n oggetti distinti tra loro di classe k tutti i possibili raggruppamenti che si possono formare prendendo k oggetti fra gli n dati, con la condizione che ciascun gruppo differisca da un altro o per l'ordine con cui gli oggetti sono collocati o per un oggetto medesimo.

Le disposizioni semplici si indicano con la sigla Dn,k.

La formula inerente alle disposizioni semplici è la seguente:

Dn,k=n! (stando attenti a fermarci quando lo sviluppo del fattoriale giunge alla pari con il numero degli oggetti presi in considerazione , ovvero k).

In altri termini la medesima formula inerente alle disposizioni semplici si indica nel modo seguente:

Dn,k=n*(n-1)*(n-2)*…..*(n-k+1)

In ogni caso è da preferirsi la prima di queste suddette due formule.

- Esempi
1)quante disposizioni semplici di 5 lettere si possono formare con le 21 lettere dell'alfabeto(N.B.: il numero totale degli oggetti a disposizione sono 21(ovvero,n) e il numero dei gruppi da formare con gli oggetti a disposizione sono 5(ovvero, k):
applicando la formula:
Dn,k=n!→D21,5=21*20*19*18*17=2.441.880

N.B.: a questo punto vediamo alcuni sviluppi del fattoriale , prima di proseguire: riferendoci alle serie , ovvero ad una somma continua di n elementi detta anche successione(che non è altro come visto che un caso particolare di funzione), alcune serie devono essere risolte con un metodo specifico che prende il nome di criterio del rapporto che si esprime in questo modo: Bn=n+1/n e che si utilizza prevalentemente nel caso in cui faccia parte della serie uno o più termini fattoriali.
Sviluppiamo i seguenti fattoriali:
a) 5!=5*4*3*2*1=120
b) n!=(n-1)*(n-2)*……*n
c) (n+1)!=(n)*(n-1)*(n-2)*….*(n)!

2)quante disposizioni di 2 vocali si possono formare con le 5 vocali dell'alfabeto:
Dn,k=n!→D5,2=5*4=20

3)sei persone possono sedersi sullo stesso lato di un tavolo dove sono disponibili solo 4 posti.
Di volta in volta come possono disporsi quattro di esse?
Queste sono disposizioni di 6 oggetti presi 4 a 4, dunque:
Dn,k=n!→D6,4==6*5*4*3=360

- DEFINIZIONE DI DISPOSIZIONI CON RIPETIZIONE:
Si chiamano disposizioni con ripetizione di n oggetti di classe k tutti i possibili raggruppamenti che si possono formare prendendo ogni volta k oggetti, con la condizione che ciascun gruppo differisca da un altro o per l'ordine in cui sono disposti gli oggetti, o per l'oggetto, o per il numero di volte in cui un oggetto viene ripetuto.

Le disposizioni con ripetizione si indicano con la sigla: D*n,k.

La formula da utilizzare per risolvere una disposizione con ripetizione è la seguente: D*n,k=n^k
(ovvero numero oggetti totali a disposizione elevato al numero dei gruppi che si vogliono formare).

- Esempi:
1) nel lancio di due dadi, in quanti modi diversi possono presentarsi le due facce superiori?
Sono le disposizioni con ripetizione di 6 numeri di classe 2:
D*n,k=6^2=36.

2) da due mazzi di 40 carte , estraendo una carta da ogni mazzo, quante possibilità diverse si possono avere?
D*n,k=40^2=1600

3) in due urne ci sono rispettivamente 30 palline di cui 10 rosse, 10 bianche e 10 verdi. Estraendole una alla volta da ciascuna (quindi due in tutto ogni estrazione) quante coppie diverse fra loro possono presentarsi, tenendo presente che le palline dello stesso colore sono indistinguibili?
In questo caso è come se avessi 3 oggetti distinti, cioè n=3; inoltre, poiché una pallina da ciascuna urna, è k=2. Gli oggetti sono ripetuti in quanto nelle due urne c'è la stessa varietà di palline, quindi il numero delle coppie è:
D*n,k=D*3,2=3^2=9

- DEFINIZIONE DI PERMUTAZIONI SEMPLICI:
Si chiamano permutazioni semplici di n oggetti distinti di classe k tutti i possibili raggruppamenti che si possono formare prendendo tutti gli n oggetti con la condizione che ogni gruppo differisca da un altro solamente per l'ordine con cui sono disposti gli oggetti.

Le permutazioni semplici si indicano con la sigla: Pn,k

La formula per risolvere una permutazione semplice è la seguente: Pn,k=n!

Questa formula differisce dalla formula utilizzate nelle disposizioni semplici in quanto non vi è nessun vincolo, non bisogna fermarci nello sviluppo del fattoriale giunti al numero dei gruppi che si vogliono formare, bensì bisogna sviluppare il fattoriale fino a quando n=k ovvero il numero totale degli oggetti a disposizione è uguale al numero dei gruppi che si volgiono formare.

- Esempi:
1) determinare il numero degli anagrammi che si possono formate con la parola FINE.
Questa è una permutazione di 4 oggetti che non si ripetono, allora si applica la formula tranquillamente.
Pn,k=P4,4=4!=4*3*2*1=24

È da notare che non essendoci nessun vincolo sullo sviluppo del fattoriale e dovendolo sviluppare fino a quando n=k la stessa formula può essere riscritta eliminando il k in quanto è sottointeso da n , dunque la formula per le permutazioni semplici è la seguente:
Pn=n!

2) in quanti modi diversi si possono disporre 5 quadri allineati su una parete: è la permutazione di 5 oggetti→P5=5!=5*4*3*2*1=120

3) calcolare in quanti modi si possono distribuire 8 regali diversi ad 8 bambini in modo che a ciascun bambino tocchi uno ed un solo regalo:
Pn=n!→P8=8!=40.320

- DEFINIZIONE DI PERMUTAZIONI CON RIPETIZIONE:
Si chiamano permutazioni con ripetizione di n oggetti , di cui alcuni uguali fra loro, tutti i vari raggruppamenti che si possono formare con gli n oggetti, con la condizione che ogni gruppo differisca da un altro solamente per l'ordine con cui sono disposti gli oggetti.

Le permutazioni con ripetizione si indicano e si risolvono nel seguente modo: P*=Dn,k/k!=n!/k1!*k2!*…
Dove il numeratore non è altro che una disposizione semplice e il denominatore sta ad indicare il numero delle volte che ogni oggetto distinto si ripete.

- Esempi:
1)determinare il numero degli anagrammi che si possono formare con la parola MATEMATICA.
P*=n!/K!=10!/2!*3!*2!=(10*9*8*7*6*5*4*3*2*1)/(2*6*2)=151.200

2)determinare il numero degli anagrammi che si possono formare con la parola ESAME:
P*=n!/k!=5!/2!=120/2=60

3)determinare il numero degli anagrammi che si possono formare con la parola DICIOTTO:
P*=n!/k!=8!/2!*2!*2!=(8*7*6*5*4*3*2*1)/(2*2*2)=(8*7*6*5*4*3*2*1)/(8)=7!=5040.

- DEFINIZIONE DI COMBINAZIONI SEMPLICI:
Si chiamano combinazioni semplici di n oggetti distinti tra loro di classe k tutti i possibili raggruppamenti che si possono formare prendendo k oggetti degli n dati, con la condizione che ogni gruppo differisca da un altro per almeno un oggetto.

Le combinazioni semplici si indicano con la sigli: Cn,k
La formula con la quale si risolvono le combinazioni semplici è la seguente:
Cn,k=Dn,k/k!
Dove il numeratore , analogamente alle permutazioni con ripetizione, è rappresentato dalla formula delle disposizioni semplici, mentre la differenza si ritrova nel denominatore che non esprime, come per le permutazioni con ripetizione, il numero delle volte che un oggetto distinto si ripete; il denominatore rappresenta semplicemente il numero dei gruppi che si vogliono formare fattoriale.

- Esempi:
1)nel gioco del lotto, quanti ambi si possono fare giocando sulla ruota di Bari?
L'ordine in cui vengono estratti i numeri non ha nessuna importanza e ricordando che su una ruota vengono estratti 5 numeri, allora i possibili ambi sono dati da:
Cn,k=Dn,k/k!=n!/k!=C5,2=(5*4)/(2*1)=20/2=10

2)avendo a disposizione 100 francobolli, tutti tra diversi tra loro, quante bustine contenenti 5 francobolli si possono formare?
L'ordine in cui vengono messi i francobolli non ha nessuna importanza , quindi si ha:
Cn,k=C100,5=n!/k!=(100*99*98*97*96)/(5*4*3*2*1)=75.287.520

- DEFINIZIONE DI COMBINAZIONI CON RIPETIZIONE:
Si chiamano combinazioni con ripetizione di n oggetti distinti tra loro di classe k, tutti i possibili raggruppamenti che si possono formare con gli n oggetti prendendone k alla volta, con la condizione che ciascuno di essi differisca da un altro per almeno un oggetto oppure per il numero di volte con cui uno stesso oggetto può essere ripetuto.

Le combinazioni con ripetizione si indicano con la sigla: C*n,k

La formula per risolvere una combinazione con ripetizione è la seguente:
C*n,k=[n*(n+1)*(n+2)*……*(n+k-1)]/[k*(k-1)*……*3*2*1]

- Esempi:
1)Un salumiere ha a disposizione un salame, una coppa, un prosciutto ed una bresaola. Determinare quanti sandwiches diversi può preparare mettendo in ognuno 6 fettine diverse o anche ripetute della stessa qualità:
C*n,k=C*4,6=(4*5*6*7*8*9)/(6*5*4*3*2*1)=84

3) un oste ha a disposizione 6 botti di vino di diversa qualità. Dovendo distribuire ad ognuno dei suoi clienti gruppi di 5 bottiglie, determinare quanti gruppi potrà formare ammettendo che in ciascuno di essi si trovino bottiglie di vino appartenente anche alla stessa botte.
Si tratta di una combinazione con ripetizione di 6 quantità prese 5 a 5:
C*6,5=(6*7*8*9*10)/(5*4*3*2*1)=252

____________________________________________________________________

Esempio