Matematica Discreta
Lezione del giorno 6 novembre 2009
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 {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 x1, la variabile x2 ha m valori possibili (di nuovo gli m elementi di B); fissato un valore di x1 e un valore di x2, la variabile x3 ha m valori possibili (di nuovo gli m elementi di B); etc ..…. ; infine 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 mm…..m (con n fattori), quindi è la potenza mn.
La formula che dà il numero di tutte le funzioni f: A B è allora BA .
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 .
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 non esiste nessuna di tali funzioni iniettive.
Quindi supponiamo nm.
Se {a1,a2, ….., an} sono gli elementi di A, ognuna di tali funzioni iniettive 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 x1, la variabile x2 ha m-1 valori possibili (gli m elementi di B escluso quello scelto come corrispondente di a1); fissato un valore di x1 e uno di x2, la variabile x3 ha m-2 valori possibili (gli m elementi di B meno quelli scelti come corrispondenti di a1,a2); etc...…. ; fissato un valore di x1, uno di x2,…, uno di xn-1, la variabile xn ha m-(n-1)=m-n+1 valori possibili (gli m elementi di B meno quelli scelti come corrispondenti di a1,a2,….,an-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 nm) .
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 è 6543=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 nm non esiste nessuna di tali funzioni.
Quindi supponiamo n=m.
Per un teorema già dimostrato, sappiamo che, sotto l’ipotesiA=B, una funzione iniettiva è sempre anche surgettiva, quindi biunivoca: basta allora contare 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)(n-2)…..1=n!, ossia n fattoriale.
Esempio: Se A={a,b,c,d,e}, B={1,2,3,4,5}, il numero delle possibili funzioni biunivoche f: A B è 5!=12345=120.
Aritmetica dei numeri naturali.
Dell’insieme dei numeri naturali N supporremo note le seguenti nozioni e proprietà (che fisseremo come “assiomi” alla base della teoria):
1) La definizione delle operazioni di somma a+b e prodotto ab fra 2 generici numeri naturali a,b (entrambe con risultato uguale ad un numero naturale) , con le relative proprietà:
a) Proprietà associativa: comunque presi a,b,cN si ha (a+b)+c=a+(b+c), (ab)c=a(bc) b) Proprietà commutativa: comunque presi a,bN si ha a+b=b+a, ab=ba
c) Proprietà distributiva della somma rispetto al prodotto: comunque presi a,b,cN si ha a(b+c)=ab+ac
2) La definizione di ordinamento dei numeri naturali cioè il significato del simbolo a<b per 2 generici numeri naturali a,b, con le relative proprietà:
a) comunque presi a,b,cN se a<b si ha (ac)<(bc) e (a+c)<(b+c)
b) comunque presi a,b,c,dN se a<b e se c<d si ha (a+c)<(b+d) e (ac)<(bc)
Scriveremo ab per indicare che a<b oppure a=b: anche per le diseguaglianze della forma ab sono valide proprietà analoghe a quelle elencate sopra.
A queste proprietà aggiungeremo il cosiddetto Assioma del minimo (o Assioma del buon ordinamento dei naturali):
3) In ogni sottoinsieme non vuoto S di N esiste sempre un elemento minimo, cioè esiste un sS tale che sia abbia sx per ogni xS.
Tale assioma ha un intuitivo significato geometrico: rappresentando i numeri naturali come punti di una retta (a distanza unitaria ognuno dal successivo, cominciando dal valore 1 e proseguendo verso destra), comunque preso un insieme S non vuoto di alcuni di tali punti, esiste sempre un punto di S che è più a sinistra di tutti gli altri punti di S.
Supponiamo di avere un predicato P(n) nella variabile n, con la variabile che assume valori nell’insieme N dei numeri naturali. Se volessimo dimostrare che P(n) è vero per ogni valore della variabile n, non potremmo procedere con una verifica per tutti i valori di n, che sono infiniti.
Per esempio dato il predicato P(n)=”(n+1)2>n+2” possiamo notare che per n=1 è vero (perché 4>3), per n=2 è vero (perché 9>4), per n=3 è vero (perché 16>5), ma come possiamo essere certi che P(n) sia vero per ogni valore di n nell’insieme dei numeri naturali ?
Una soluzione a questo problema è fornita, come vedremo in seguito, dal Principio di induzione.
