Matematica Discreta I Lezione del giorno 11 dicembre 2008 Calcoleremo ora la cardinalità di C

(1)

Matematica Discreta I

Lezione del giorno 11 dicembre 2008

Calcoleremo ora la cardinalità di C

^rn

,

m

ossia il numero delle combinazioni con ripetizione di n degli elementi a

1

,a

2

,…,a

n

presi ad m ad m.

Una generica combinazione con ripetizione di C

^rn,m

si può rappresentare nella forma:

a

1

,a

1,

….,a

1

,a

2

,a

2

,…,a

2

,……..,a

n

,a

n

,…,a

n

dove a

1

compare m

1

volte (anche 0 volte, se non compare), a

2

compare m

2

volte,…. , a

n

compare m

n

volte, e dove ovviamente la somma m

1

+m

2

+….+m

n

coincide con m (visto che la combinazione coinvolge esattamente m elementi fra gli n elementi dati). Possiamo costruire, a partire da tale combinazione con ripetizione, una opportuna parola sull’alfabeto {0,1} nel modo seguente:

00….0100….01………..100…0

dove gli zeri consecutivi all’inizio della parola sono in numero di m

1

, dopo di essi vi è un 1 che funge da “separatore”, il secondo settore di zeri consecutivi contiene un numero m

2

di zeri, di seguito vi è un altro 1 che funge da “separatore”, e così procedendo fino all’ultimo “separatore” 1 seguito da altri zeri consecutivi in numero di m

n

.

Per esempio se n=4, se gli elementi sono a

1

,a

2

,a

3

,a

4

e se m=10, a partire dalla seguente combinazione con ripetizione dei 4 elementi presi a 10 a 10 :

a

1

a

1

a

2

a

3

a

3

a

3

a

4

a

4

a

4

a

4

si può costruire la seguente parola sull’alfabeto {0,1}:

0010100010000

La parola costruita ha un numero di 1 (separatori) uguale ad (n-1), ed un numero di 0 uguale alla somma m

1

+m

2

+….+m

n

, cioè uguale ad m. In totale la lunghezza della parola è (n-1)+m=n+m-1.

Se indichiamo con B l’insieme di tutte le parole sull’alfabeto {0,1} di lunghezza (n+m-1) in cui la lettera 1 compare esattamente (n-1) volte, il procedimento precedente permette di costruire una funzione f: C

^rn,m

 B. Dal ragionamento fatto nella lezione precedente sappiamo che B ha

cardinalità

 

 









1n 1m n

.

Ora dimostriamo che la funzione f è biunivoca.

Per dimostrare che f è iniettiva basta osservare che, date due combinazioni diverse in C

^rn,m

, in esse vi sarà qualche elemento a

i

che compare un numero diverso di volte nelle 2 combinazioni, quindi le 2 parole corrispondenti sull’alfabeto {0,1} saranno diverse, perché nel “settore” corrispondente all’elemento a

i

vi sarà un numero diverso di 0.

Per dimostrare che f è surgettiva, data una parola qualunque in B, è facile (invertendo la costruzione precedente) trovare una combinazione di C

^rn,m

di cui la parola data sia la corrispondente mediante la funzione f: basta cominciare a “leggere” la parola da sinistra verso destra, isolare il primo “settore”

di 0 consecutivi (seguiti da un 1), e prendere nella combinazione un numero di a

1

uguale al numero di tali 0 e così via.

Possiamo allora concludere che il numero delle combinazioni con ripetizione di n elementi a

1

,a

2

,

…,a

n

presi ad m ad m è il seguente:

(2)

 C

^rn,m

= B=

 

 









1n 1m n

.

Combinazioni semplici come sottoinsiemi

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).