Matematica Discreta I
Lezione del giorno 16 novembre 2007 Calcolo combinatorio
Il calcolo combinatorio studia le tecniche per contare la cardinalità di alcuni insiemi finiti, costruiti a partire da altri insiemi finiti.
Disposizioni semplici e con ripetizione
Sia A un insieme di cardinalità n, contenente gli n elementi distinti a1,a2,…,an , e fissiamo un numero naturale m.
Chiamiamo disposizione degli n elementi presi ad m ad m (o disposizione di classe m degli n elementi) un qualunque modo di disporre ordinatamente m fra gli n elementi (quindi 2 disposizioni si distinguono non solo per gli m elementi disposti ma anche per il loro ordine).
Una disposizione è semplice se gli m elementi scelti sono tutti distinti (e in questo caso necessariamente deve essere nm) oppure con ripetizione se è possibile ripetere qualche elemento più volte (e in questo caso n,m possono essere arbitrari) .
Indicheremo con Dn,m l’insieme di tutte le possibili disposizioni semplici di classe m degli n elementi, e con Drn,m l’insieme di tutte le possibili disposizioni con ripetizione di classe m degli n elementi (sottintendendo nel simbolo l’insieme A degli elementi). Ovviamente ogni disposizione semplice è una particolare disposizione con ripetizione (nelle disposizioni con ripetizione è possibile ripetere qualche elemnto, ma non obbligatorio), quindi si ha Dn,m Drn,m .
Esempio: Se A={a,b,c}(quindi n=3) e se fissiamo m=2 si ha:
D3,2 = {ab, ba, ac, ca, bc, cb} ; Dr3,2 = { ab, ba, ac, ca, bc, cb, aa, bb, cc}
Contiamo le disposizioni con ripetizione di classe m di n elementi; ognuna di tali disposizioni dipende dai valori di m variabili:
x1=valore dell’elemento da sistemare nella prima posizione della disposizione;
x2= valore dell’elemento da sistemare nella seconda posizione della disposizione;
…..
xm= valore dell’elemento da sistemare nell’ ultima posizione della disposizione (la numero m). La variabile x1 ha n valori possibili (gli n elementi di A); fissato un valore di x1, la variabile x2 ha n valori possibili (gli n elementi di A); ..…. ; fissato un valore di x1, uno di x2,…, uno di xm-1, la variabile xm ha n valori possibili (gli n elementi di A). Per il principio delle scelte multiple, il numero delle possibili disposizioni con ripetizione di Drn,m è il prodotto nn…..n (con m fattori), quindi è la potenza nm.
Contiamo le disposizioni semplici di classe m degli n elementi (nel caso nm); ognuna di esse dipende dai valori di m variabili:
x1=valore dell’elemento da sistemare nella prima posizione della disposizione;
x2= valore dell’elemento da sistemare nella seconda posizione della disposizione;
…..
xm= valore dell’elemento da sistemare nell’ ultima posizione della disposizione (la numero m). La variabile x1 ha n valori possibili (gli n elementi di A); fissato un valore di x1, la variabile x2 ha (n-1) valori possibili (gli n elementi di A meno quello sistemato nella prima posizione); ..…. ; fissato un valore di x1, uno di x2,…, uno di xm-1, la variabile xm ha n-(m-1)=n-m+1 valori possibili (gli n elementi di A meno quelli sistemati nelle prime m-1 posizioni).
Per il principio delle scelte multiple, il numero delle possibili disposizioni semplici di Dn,m è il prodotto n(n-1)(n-2)…..(n-m+1) (sempre nell’ipotesi che sia nm).
Permutazioni
Nel caso particolare n=m , le disposizioni semplici di n elementi presi ad n ad n sono dette permutazioni degli n elementi dati (concetto già incontrato nella costruzione del determinante di una matrice). Il loro numero si ricava dalla formula della disposizioni semplici ponendo n=m: e le permutazioni di n elementi sono 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 D4,4 ={1234, 1432, 2341, 4132, ……..} contenente appunto 24 permutazioni degli elementi 1,2,3,4 .
Parole
Nel linguaggio informatico, le disposizioni con ripetizione degli n elementi a1,a2,…,an presi ad m ad m sono dette anche parole di lunghezza m sull’alfabeto a1,a2,…,an (gli elementi a1,a2,…,an sono dette lettere dell’alfabeto): secondo la teoria delle disposizioni con ripetizione, il numero delle parole di lunghezza m sull’alfabeto a1,a2,…,an è quindi nm.
Esempio: le parole di lunghezza 4 sull’alfabeto {0,1} sono le seguenti 24=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
Sia A un insieme di cardinalità n, contenente gli n elementi distinti a1,a2,…,an , e fissiamo un numero naturale m.
Chiamiamo combinazione degli n elementi presi ad m ad m (o disposizione di classe m degli n elementi) un qualunque modo di scegliere m fra gli n elementi, non tenendo conto dell’ordine di scelta (quindi 2 combinazioni si distinguono 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 nm) oppure con ripetizione se è possibile ripetere qualche elemento più volte.
Indicheremo con Cn,m l’insieme di tutte le possibili combinazioni semplici di classe m degli n elementi, e con Crn,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 Cn,m Crn,m .
Esempio: Se A={a,b,c,d}(quindi n=4) e se fissiamo m=3 si ha:
C4,3 = {abc, abd, acd, bcd} ; Cr4,3 = {abc, abd, acd, bcd, aab, aac, aad, bbc, bba, bbd, cca, ccb, ccd, dda, ddb, ddc, aaa, bbb, ccc, ddd}.
Osservazione: Possiamo notare che sostanzialmente il concetto di combinazione semplice di n elementi 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).
Calcoliamo la cardinalità di Cn,m ossia il numero delle combinazioni semplici di n elementi a1,a2,
…,an presi ad m ad m (dove si suppone nm).
Consideriamo l’insieme Dn,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 ripartire le disposizioni di Dn,m in sottoinsiemi, ponendo in ciascun sottoinsieme le disposizioni che coinvolgono m elementi fissati fra gli n elementi dati: è ovvio che le disposizioni di uno stesso sottoinsieme corrispondono ad 1 sola combinazione. Ma le disposizioni che coinvolgono m elementi fissati non sono altro che le permutazioni di questi elementi, ed esse sono quindi in numero di m!.
In totale il numero delle combinazioni semplici di n elementi a1,a2,…,an presi ad m ad m si otterrà dividendo la cardinalità di Dn,m per m!, ottenendo alla fine:
Cn,m =
m!
1) m 2)....(n 1)(n
n(n
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 nm)
Per quanto detto sopra, il coefficiente binomiale rappresenta anche il numero dei sottoinsiemi di cardinalità m che sono contenuti un insieme A di cardinalità n.
Esempio: se gli elementi sono 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
= (654)/3! = 20, e tale numero rappresenta il
numero dei sottoinsiemi di cardinalità 3 contenuti nell’insieme {a,b,c,d,e,f} di cardinalità 6.
Per calcolare la cardinalità di Crn,m ossia il numero delle combinazioni con ripetizione di n elementi a1,a2,…,an presi ad m ad m, abbiamo bisogno di alcuni risultati preliminari.
Fissiamo un naturale r e consideriamo tutte le parole di lunghezza r sull’alfabeto {0,1}: sappiamo che esse sono in numero di 2r. Fissiamo poi un naturale sr e contiamo le parole di lunghezza r sull’alfabeto {0,1} che contengono la lettera 1 esattamente s volte. Ognuna di tali parole dipende da due variabili:
x=scelta delle s posizioni (fra le r disponibili) in cui inserire la lettera 1 y=scelta del contenuto delle rimanenti (r-s)
I valori possibili di x corrispondono alle combinazioni semplici di r posizioni prese ad s ad s, quindi
sono in numero di
s r
. Fissato un valore per x, cioè fissata una scelta delle s posizioni (fra le r
disponibili) in cui inserire la lettera 1, per il valore di y vi è una scelta “obbligata” (le rimanenti (r-s) posizioni devono tutte contenere 0) ossia il numero dei valori possibili di y è 1.
Per il principio delle scelte multiple, il numero delle parole di lunghezza r sull’alfabeto {0,1} che
contengono la lettera 1 esattamente s volte coincide con il coefficiente binomiale
s r
.
