Matematica Discreta I Lezione del giorno 24 ottobre 2007 Principio delle scelte multiple.

Matematica Discreta I

Lezione del giorno 24 ottobre 2007 Principio delle scelte multiple.

Supponiamo di volere contare il numero di elementi di un insieme finito C e di sapere che ogni elemento di A dipende dai valori di 2 variabili x,y; supponiamo anche che i valori possibili della x siano in numero di n, e che, fissato un valore della x, i valori possibili della y siano in numero di m (con m costante, che non dipende dal valore fissato per la x). Se x=x

,x

…..,x

sono gli n valori possibili della x, e per ognuno di tali valori della x, si ottengono in corrispondenza m valori della y dunque si conclude che gli elementi dell’insieme A (che sono tanti quante le coppie dei valori di x e y) sono in numero di m+m+...+m (con n addendi) e quindi in totale in numero di nm.

Il principio delle scelte multiple si può facilmente, con ragionamenti analoghi a quello precedente, estendere al caso di elementi che dipendono da più di 2 variabili.

Per esempio, se ogni elemento dell’insieme finito A dipende dai valori di 3 variabili x,y,z e se:

- i valori possibili della variabile x sono in numero di n

- fissato un valore di x, i valori della variabile y sono in numero di m

- fissato un valore di x e un valore di y, i valori della variabile z sono in numero di p allora si dimostra facilmente che gli elementi di A sono in numero di nmp.

Esempio:

Contiamo il numero degli elementi dell’insieme A contenente tutti i numeri naturali di 2 cifre (in base 10) con le cifre tutte dispari. Ogni elemento di A dipende da 2 variabili: x=valore della prima cifra, y=valore della seconda cifra. I valori possibili di x sono le cifre 1,3,5,7,9 (in numero di n=5);

fissato un valore di x, i valori possibili di y sono in numero di m=5 (gli stessi valori possibili di x).

Per il principio delle scelte multiple gli elementi di A sono in numero di 55=25.

Contiamo poi il numero degli elementi dell’insieme A contenente tutti i numeri naturali di 2 cifre (in base 10) con le cifre tutte dispari e diverse fra loro. Ogni elemento di A dipende da 2 variabili:

x=valore della prima cifra, y=valore della seconda cifra. I valori possibili di x sono le cifre 1,3,5,7,9 (in numero di n=5); fissato un valore di x, i valori possibili di y sono in numero di m=4 (i 5 valori possibili di x escluso il valore fissato per la x). Per il principio delle scelte multiple gli elementi di A sono in numero di 54=20.

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

, a

, ….., a

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

x

=valore del corrispondente in B dell’elemento a

; x

=valore del corrispondente in B dell’elemento a

;

…..

x

=valore del corrispondente in B dell’elemento a

.

La variabile x

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

, la variabile x

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

, uno di x

,…, uno di x

, la variabile x

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

.

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 .