Matematica Discreta I - Matematica e Informatica

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 1,x2,…..,xn 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 {a1, a2, ….., an} sono gli elementi di A, ognuna di tali funzioni dipende dalle n variabili seguenti: x1=valore del corrispondente in B dell’elemento a1 ; x2=valore del corrispondente in B dell’elemento a2 ; ….. xn=valore del corrispondente in B dell’elemento an . La variabile x1 ha m valori possibili (gli m elementi di B); fissato un valore di x 1, la variabile x2 ha m valori possibili (di nuovo gli m elementi di B); ..…. ; fissato un valore di x1, uno di x2,…, uno di xn-1, la variabile xn 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 mn. 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 è 32=9, mentre il numero delle possibili funzioni f: B  A è 23=8 .