Matematica Discreta Lezione del giorno 26 ottobre 2011

(1)

Matematica Discreta

Lezione del giorno 26 ottobre 2011

Esaminiamo alcune terminologie particolari relative alla teoria delle disposizioni.

1) Permutazioni.

Nel caso particolare n=m, le disposizioni semplici di n elementi presi ad n ad n sono dette permutazioni degli n elementi dati: esse rappresentano in pratica tutti i modi diversi di disporre in ordine gli n elementi dati.

Il numero delle permutazioni di n elementi si ricava come caso particolare dalla formula della disposizioni semplici ponendo n=m: le permutazioni di n elementi sono dunque in numero di

n(n-1)(n-2)….. 1 = n!

Esempio: se A={1,2,3,4}, le permutazioni di 1,2,3,4 sono in numero di 4!=24, ed esse costituiscono l’insieme D

4,4

={1234, 1432, 2341, 4132, ……..} contenente appunto i 24 modi diversi di disporre in ordine gli elementi 1,2,3,4 .

2) Parole.

Nel linguaggio informatico, le disposizioni con ripetizione degli n elementi a

1

,a

2

,…,a

n

presi ad m ad m sono spesso chiamate parole di lunghezza m sull’alfabeto a

1

,a

2

,…,a

n

(gli elementi a

1

,a

2

,…,a

n

sono dette lettere dell’alfabeto): secondo quanto dimostrato quando abbiamo calcolato il numero delle disposizioni di n elementi presi ad m ad m, il numero delle parole di lunghezza m su un alfabeto di n lettere è n

^m

.

Esempio: le parole di lunghezza 4 sull’alfabeto {0,1} sono le seguenti 2

⁴

=16 disposizioni con ripetizione dei 2 elementi 0,1 presi a 4 a 4:

{0000,1111,0001,0010,0100,1000,0011,0101,0110,1010,1100, 1001,1110,1101,1011,0111}

Combinazioni

Siano n,m due numeri naturali qualunque. Sia poi A un insieme di cardinalità n, contenente gli n elementi distinti a

1

,a

2

,…,a

n

.

Chiamiamo combinazione di classe m degli n elementi (o combinazione degli n elementi presi ad m ad m) un qualunque modo di scegliere m fra gli n elementi, non tenendo conto dell’ordine di scelta (quindi 2 combinazioni si distinguono fra loro solo per gli m elementi scelti e non per il loro ordine). Una combinazione è semplice se gli elementi scelti sono tutti distinti (e in questo caso necessariamente deve essere nm) oppure con ripetizione se è possibile ripetere qualche elemento più volte.

Indicheremo con C

n,m

l’insieme di tutte le possibili combinazioni semplici di classe m degli n elementi, e con C

^rn,m

l’insieme di tutte le possibili combinazioni con ripetizione di classe m degli n elementi. Ovviamente ogni combinazione semplice è una particolare combinazione con ripetizione, quindi si ha C

n,m

 C

^rn,m

.

Esempio: Se A={a,b,c,d}(quindi n=4) e se fissiamo m=3 si ha:

C

4,3

= {abc, abd, acd, bcd} ; C

^r4,3

= {abc, abd, acd, bcd, aab, aac, aad, bbc, bba, bbd, cca, ccb, ccd,

dda, ddb, ddc, aaa, bbb, ccc, ddd}.

(2)

Numero delle combinazioni semplici

Calcoliamo la cardinalità di C

n

,

m

ossia il numero delle combinazioni semplici di n elementi a

1

,a

2

,

…,a

n

presi ad m ad m.

Ragionando come nel caso delle disposizioni semplici, si deduce che nel caso n<m non esiste nessuna di tali combinazioni semplici :

C

^rn,m

=  nel caso n<m Quindi supponiamo di essere nel caso nm.

Consideriamo l’insieme D

n,m

delle disposizioni semplici degli n elementi presi ad m ad m:

sappiamo che ha cardinalità n(n-1)(n-2)….. (n-m+1).

Poiché nelle combinazioni l’ordine degli elementi non conta, possiamo suddividere l’insieme delle disposizioni D

n,m

in sottoinsiemi, ponendo in ciascun sottoinsieme le disposizioni che coinvolgono m elementi fissati fra gli n elementi dati: è ovvio che le diverse disposizioni poste nello stesso sottoinsieme corrispondono ad 1 sola combinazione.

(Per esempio se A={a,b,c,d}, n=4, m=3 potremmo fissare i 3 elementi a,b,c e considerare le disposizioni che coinvolgono solo a,b,c, cioè abc, acb, bac, bca, cab, cba: esse sono 6 diverse disposizioni ma rappresentano 1 sola combinazione).

Contare il numero delle combinazioni equivale a contare il numero dei sottoinsiemi in cui abbiamo suddiviso D

n,m

. Ma in ognuno di tali sottoinsiemi vi sono le disposizioni che coinvolgono m elementi fissati e queste non sono altro che le permutazioni di questi m elementi: sappiamo già che esse sono in numero di m!.

Dunque ognuno dei sottoinsiemi in cui abbiamo ripartito D

n,m

contiene lo stesso numero m! di disposizioni.

In totale il numero delle combinazioni semplici di n elementi a

1

,a

2

,…,a

n

presi ad m ad m si otterrà dividendo la cardinalità di D

n,m

per m!, ottenendo alla fine:

C

n

,

m

 =

m!

1) m 2)....(n 1)(n

n(n    

(sempre nell’ipotesi nm)

Tale numero (intero nonostante la rappresentazione sotto forma di frazione) è detto coefficiente binomiale ed è indicato con il simbolo:

 

 



 m n

= m!

1) m 2)....(n 1)(n

n(n    

(sempre nell’ipotesi nm)

Esempio: Se A={a,b,c,d,e,f} (quindi n=6) e se m=3, le combinazioni semplici dei 6 elementi presi

a 3 a 3 sono in numero di

 

 



 3 6

= (654)/3! = 20.

(3)

Esempio: Le combinazioni del Superenalotto sono le combinazioni semplici di 90 numeri presi a 6 a 6, quindi sono in numero di 90

6    

  =(908988878685)/6! = 622.614.630 Significato insiemistico del coefficiente binomiale

Se A = { a

1

,a

2

,….,a

n

}, possiamo notare che sostanzialmente il concetto di combinazione semplice degli n elementi a

1

,a

2

,….,a

n

presi ad m ad m coincide con quello di sottoinsieme di cardinalità m contenuto nell’insieme A di cardinalità n (essendo gli elementi scelti nella combinazione tutti distinti e non tenendo conto del loro ordine).