Matematica Discreta Lezione del giorno 25 ottobre 2011 Principio delle scelte multiple.

(1)

Matematica Discreta

Lezione del giorno 25 ottobre 2011 Principio delle scelte multiple.

Il “principio delle scelte multiple” serve per contare gli elementi di un insieme finito, almeno in alcuni casi particolari.

Partiamo da un esempio.

Sia A l’insieme dei numeri naturali di 2 cifre (decine e unità) con cifre scelte fra i valori 1,2,3,4, e tali che la cifra delle decine sia minore di quella delle unità, e supponiamo di volere contare il numero di elementi di A.

Notiamo che ogni elemento di A dipende dai valori di 2 variabili: la cifra x

1

delle decine e la cifra x

2

delle unità: quindi contare gli elementi di A equivale a contare le coppie di valori delle 2 variabili x

1

,x

2

.

Possiamo allora utilizzare il seguente metodo di calcolo: fissiamo un primo valore della variabile x

1

, e in corrispondenza contiamo quanti sono i valori della variabile x

2

; poi fissiamo un secondo valore della variabile x

1

, e in corrispondenza contiamo quanti sono i valori della variabile x

2

; continuiamo a procedere in questo modo (fissando ogni volta un valore della variabile x

1

e in corrispondenza contando quanti sono i valori della variabile x

2

) fino ad esaurire tutti i possibili valori della variabile x

1

. Sommando tutti i numeri ottenuti otterremo il numero degli elementi di A.

In dettaglio:

Fissato il valore x

1

=1 (quindi la cifra delle decine è =1) otteniamo in corrispondenza 3 valori di x

2

(valori della cifra delle unità che sono 2,3,4), analogamente fissato il valore x

1

=2 otteniamo in corrispondenza 2 valori di x

2

(che sono 3,4), fissato il valore x

1

=3 otteniamo in corrispondenza 1 valore di x

2

(che è 4), fissato il valore x

1

=4 otteniamo in corrispondenza 0 valori di x

2

. In totale il numero di coppie di valori x

1

,x

2

(e quindi il numero di elementi di A) è la somma 3+2+1+0=6.

Ora facciamo un altro esempio, con una situazione particolare.

Sia A l’insieme dei numeri naturali di 2 cifre (decine e unità) con cifre scelte fra i valori 1,2,3,4,5,6 e tali che la cifra delle decine sia diversa da quella delle unità. Come nell’esempio precedente, possiamo notare che ogni elemento dipende dai valori di 2 variabili: la cifra x

1

delle decine e la cifra x

2

delle unità.

La variabile x

1

può assumere 6 valori distinti 1,2,3,4,5,6. Fissato un valore di x

1

, il numero dei valori corrispondenti di x

2

è costantemente uguale a 5 (sono tutti i valori 1,2,3,4,5,6 tranne quello scelto per x). Utilizzando il metodo precedente, si ottiene che il numero di elementi di A è la somma 5+5+5+5+5+5=65=30. Dunque rispetto all’esempio precedente il calcolo è stato più immediato:

per ottenere il numero di elementi di A abbiamo calcolato il prodotto del numero dei valori possibili di x

1

per il numero dei valori possibili di x

2

. (questo però solo perché, fissato un valore di x

1

, il numero dei valori corrispondenti di x

2

rimaneva costante, anche modificando il valore di x

1

).

Da questo esempio possiamo dedurre il cosiddetto principio delle scelte multiple per 2 variabili:

Se A è un insieme finito, e se:

- ogni elemento di A dipende dal valore di 2 variabili x

1

,x

2

- il numero di valori possibili di x

1

è = h

1

- fissato un valore di x

1

, il numero di valori possibili di x

2

è costantemente = h

2

allora il numero di elementi di A è uguale al prodotto h

1

h

2

.

(2)

Con ragionamenti simili ai precedenti si ottiene il principio delle scelte multiple per un numero qualunque di variabili:

Se A è un insieme finito, e se:

- ogni elemento dell’insieme finito A dipenda dai valori di n variabili x

1

,x

2

,….,x

n

- il numero di possibili valori di x

1

é = h

1

- fissato un valore di x

1

, il numero di valori possibili di x

2

è costantemente = h

2

- fissato un valore di x

1

e di x

2

, il numero di valori possibili di x

3

é costantemente = h

3

……

- fissato un valore di x

1

,x

2

,…,x

n-1

, il numero dei valori possibili di x

n

é costantemente = h

n

allora il numero degli elementi di A è uguale al prodotto h

1

h

2

……h

n

. Vediamo alcune applicazioni del principio delle scelte multiple.

Numero delle funzioni fra insiemi finiti

Siano A,B due insiemi finiti rispettivamente con A=n, B=m, e contiamo il numero di tutte le possibili funzioni f: A  B.

Se {a

1

, a

2

, ….., a

n

} sono gli elementi di A, ognuna di tali funzioni dipende dalle n variabili seguenti:

x

1

=valore del corrispondente in B dell’elemento a

1

; x

2

=valore del corrispondente in B dell’elemento a

2

;

…..

x

n

=valore del corrispondente in B dell’elemento a

n

.

La variabile x

1

ha m valori possibili (gli m elementi di B); fissato un valore di x

1

, la variabile x

2

ha m valori possibili (di nuovo gli m elementi di B); fissato un valore di x

1

e un valore di x

2

, la variabile x

3

ha m valori possibili (di nuovo gli m elementi di B); etc ..…. ; infine fissato un valore di x

1

, uno di x

2

,…, uno di x

n-1

, la variabile x

n

ha m valori possibili (sempre gli m elementi di B). Per il principio delle scelte multiple, il numero delle possibili funzioni f: A  B è il prodotto mm…..m (con n fattori), quindi è la potenza m

ⁿ

.

La formula che dà il numero di tutte le funzioni f: A  B è allora B

^A

.

Esempio: Se A={a,b}, B={1,2,3}, il numero delle possibili funzioni f: A  B è 3

²

=9, mentre il numero delle possibili funzioni f: B  A è 2

³

=8 .

Numero delle funzioni iniettive fra insiemi finiti

Siano A,B due insiemi finiti rispettivamente con A=n, B=m, e contiamo il numero di tutte le possibili funzioni iniettive f: A  B.

Sappiamo già che nel caso n>m tale numero è 0 perché (per un Teorema dimostrato in precedenza) non esiste in questo caso nessuna funzione iniettiva da A in B.

Quindi supponiamo nm.

Se {a

1

, a

2

, ….., a

n

} sono gli elementi di A, ognuna di tali funzioni iniettive dipende dalle n variabili seguenti:

x

1

=valore del corrispondente in B dell’elemento a

1

; x

2

=valore del corrispondente in B dell’elemento a

2

;

…..

x

n

=valore del corrispondente (in B) dell’elemento a

n

.

La variabile x

1

ha m valori possibili (gli m elementi di B); fissato un valore di x

1

, la variabile x

2

ha

m-1 valori possibili (gli m elementi di B escluso quello scelto come corrispondente di a

1

); fissato un

(3)

valore di x

1

e uno di x

2

, la variabile x

3

ha m-2 valori possibili (gli m elementi di B meno quelli scelti come corrispondenti di a

1

,a

2

); etc...…. ; fissato un valore di x

1

, uno di x

2

,…, uno di x

n-1

, la variabile x

n

ha m-(n-1)=m-n+1 valori possibili (gli m elementi di B meno quelli scelti come corrispondenti di a

1

,a

2

,….,a

n-1

).

Per il principio delle scelte multiple, il numero delle possibili funzioni iniettive f: A  B è il prodotto m(m-1)(m-2)….. (m-n+1), quindi è il prodotto in ordine decrescente dei numeri naturali da m ad m-n+1 (supponendo sempre nm) .

Esempio: Se A={a,b,c,d}, B={1,2,3,4,5,6}, A=4, B=6 il numero delle possibili funzioni iniettive f: A  B è 6543=360.

Numero delle funzioni surgettive fra insiemi finiti

Il problema di contare il numero delle funzioni surgettive fra insiemi finiti sarà affrontato in seguito, nell’ambito della teoria dei numeri di Stirling.

Numero delle funzioni biunivoche fra insiemi finiti

Siano A,B due insiemi finiti rispettivamente con A=n, B=m, e contiamo il numero di tutte le possibili funzioni biunivoche f: A  B.

Sappiamo già che nel caso nm tale numero è 0 perché (per un Teorema dimostrato in precedenza) non esiste in questo caso nessuna funzione biunivoca da A in B.

Quindi supponiamo n=m.

Per un teorema già dimostrato, sappiamo che, sotto l’ipotesiA=B, una funzione iniettiva è sempre anche surgettiva, quindi biunivoca: basta allora contare solo le funzioni iniettive da A a B.

Applicando la formula precedente (con n=m) si ottiene che il numero delle possibili funzioni biunivoche f: A  B è il prodotto n(n-1)….21

Tale numero (ottenuto moltiplicando tutti i numeri naturali consecutivi da 1 ad n) è detto fattoriale di n ed è indicato con il simbolo n!. Quindi:

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

rappresenta il numero delle funzioni biunivoche fra 2 insiemi finiti di eguale cardinalità n.

Esempio: Se A={1,2,3,4,5}, B={6,7,8,9,10}, il numero delle funzioni biunivoche f: A  B è 5!

=12345=120.

Calcolo combinatorio

Il calcolo combinatorio è quella parte della teoria degli insiemi che studia i diversi modi di

“combinare” gli elementi di un insieme finito.

Disposizioni semplici e con ripetizione

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 disposizione di classe m degli n elementi a

1

,a

2

,…,a

n

(o disposizione degli n elementi a

1

,a

2

,…,a

n

presi ad m ad m) un qualunque modo di scegliere ordinatamente m fra gli n elementi a

1

,a

2

,…,a

n

(quindi 2 disposizioni si distinguono fra loro non solo per gli m elementi scelti ma anche per il loro ordine).

Una disposizione è detta semplice se gli m elementi scelti sono tutti distinti (e in questo caso

necessariamente deve essere nm) oppure con ripetizione se è possibile (ma non obbligatorio)

ripetere qualche elemento più volte (e in questo caso n,m possono essere arbitrari) .

(4)

Indicheremo con il simbolo D

n,m

l’insieme di tutte le possibili disposizioni semplici di classe m degli n elementi a

1

,a

2

,…,a

n

, e con il simbolo D

^rn,m

l’insieme di tutte le possibili disposizioni con ripetizione di classe m degli n elementi a

1

,a

2

,…,a

n

(nel simbolo, l’insieme A degli elementi non è indicato esplicitamente: d’altronde per le considerazioni che faremo, la natura degli elementi a

1

,a

2

,

…,a

n

non avrà influenza).

Ovviamente ogni disposizione semplice è una particolare disposizione con ripetizione, quindi, come insiemi, si ha la seguente inclusione D

n,m

 D

^rn,m

.

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

D

3,2

= {ab, ba, ac, ca, bc, cb} ; D

^r3,2

= { ab, ba, ac, ca, bc, cb, aa, bb, cc}

Numero delle disposizioni.

Contiamo le disposizioni con ripetizione di classe m di n elementi a

1

,a

2

,…,a

n

.

Ognuna di tali disposizioni dipende dai valori delle seguenti m variabili x

1

, x

2

, ……, x

m

: x

1

=valore dell’elemento nella prima posizione della disposizione;

x

2

= valore dell’elemento nella seconda posizione della disposizione ;

…..

x

m

= valore dell’elemento nell’ ultima posizione della disposizione (la posizione numero m) .

La variabile x

1

ha n valori possibili (gli n elementi a

1

,a

2

,…,a

n

); fissato un valore di x

1

, la variabile x

2

ha n valori possibili (sempre gli n elementi a

1

,a

2

,…,a

n

); ..…. ; fissato un valore di x

1

, uno di x

2

,…, uno di x

m-1

, la variabile x

m

ha n valori possibili (sempre gli n elementi a

1

,a

2

,…,a

n

). Per il principio delle scelte multiple, il numero delle possibili disposizioni con ripetizione di D

^rn,m

è il prodotto nn…..n (con m fattori), quindi è la potenza n

^m

:

D

^rn,m

 = n

^m

Contiamo ora le disposizioni semplici di classe m di n elementi a

1

,a

2

,…,a

n

.

Ovviamente nel caso n<m non esiste nessuna di tali disposizioni semplici (essendo gli elementi dati in numero minore del numero m di quelli da scegliere, si è obbligati a delle ripetizioni):

D

^rn,m

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

Ogni disposizione semplice di classe m degli n elementi a

1

,a

2

,…,a

n

dipende dai valori di m variabili x

1

, x

2

, ……, x

m

, il cui significato è lo stesso di quello considerato nel caso delle disposizioni semplici.

La variabile x

1

ha n valori possibili (gli n elementi a

1

,a

2

,…,a

n

); fissato un valore di x

1

, la variabile x

2

ha (n-1) valori possibili (gli n elementi a

1

,a

2

,…,a

n

meno quello scelto come valore di x

1

); ..…. ; fissato un valore di x

1

, uno di x

2

,…, uno di x

m-1

, la variabile x

m

ha n-(m-1)=n-m+1 valori possibili (gli n elementi a

1

,a

2

,…,a

n

meno gli m-1 elementi scelti come valore di x

1

, x

2

,…, x

m-1

).

Per il principio delle scelte multiple, il numero delle possibili disposizioni semplici di D

n,m

è il prodotto n(n-1)(n-2)….. (n-m+1) (sempre nell’ipotesi che sia nm):

D

n,m