Matematica Discreta I
Lezione del giorno 24 ottobre 2007
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 {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
1ha m valori possibili (gli m elementi di B); fissato un valore di x
1, la variabile x
2ha m-1 valori possibili (gli m elementi di B escluso quello scelto come corrispondente di a
1); fissato un valore di x
1e uno di x
2, la variabile x
3ha 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
nha 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 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.
(Per contare il numero delle funzioni surgettive fra insiemi finiti si rinvia alla teoria dei numeri di Stirling, che sarà esposta in seguito).
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 tale ipotesi, 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, ossia il prodotto di tutti i numeri naturali consecutivi da 1 ad n, detto fattoriale di n e indicato con il simbolo n! .
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.
Permutazioni
Sia A={a
1, a
2,…..,a
n} un insieme finito con n elementi e sia f: A A una funzione biunivoca.
Possiamo rappresentare la funzione f costruendo 2 righe: nella prima vi sono gli elementi di A (in un certo ordine fissato) e nella seconda, sotto ogni elemento di A, vi è il suo corrispondente secondo la funzione f:
f =
) f(a . . ) f(a ) f(a
a . . a a
n 2
1
n 2
1
Nella seconda riga vi sono gli elementi a
1, a
2, ….., a
ndisposti in un qualunque ordine: chiameremo permutazione degli elementi a
1, a
2, ….., a
nun qualunque modo di disporre ordinatamente gli elementi a
1, a
2, ….., a
n.
Ne segue che le permutazioni possibili di a
1, a
2, ….., a
nsono tante quante le possibili funzioni biunivoche f: A A, quindi sono in numero di n! .
Alla funzione identica i
A: A A corrisponde la cosiddetta permutazione identica, nella quale gli elementi a
1, a
2, ….., a
nsono disposti nel loro ordine iniziale.
Esempio:
Se A = {a , b , c}, si ottengono 3!=6 funzioni biunivoche f: A A:
c b a
c b
a ,
b c a
c b
a ,
a b c
c b
a ,
c a b
c b
a ,
a c b
c b
a ,
b a c
c b a
e in corrispondenza 6 permutazioni degli elementi a,b,c:
abc, acb, cba, bac, bca, cab
Poiché la natura degli elementi dell’insieme A é ininfluente, ci limiteremo al caso in cui A contenga i primi n numeri naturali consecutivi: A = { 1,2,…..,n }.
Data una permutazione dei numeri naturali 1, 2, ….., n, e fissati due numeri distinti i,j compresi fra 1 ed n, diremo che la permutazione ha una inversione in i,j se nella permutazione i numeri compaiono in ordine opposto a quello naturale (ossia se il maggiore dei 2 compare a sinistra del minore).
Per esempio la seguente permutazione dei numeri 1,2,3,4,5:
21453
presenta una inversione in 2,1, una inversione in 4,3, una inversione in 5,3.
Una permutazione dei numeri naturali 1, 2, ….., n è detta pari o dispari a secondo se il numero totale di inversioni che presenta è pari o dispari (la permutazione “identica” 1 2 … n, che presenta 0 inversioni, si considera convenzionalmente pari).
La permutazione dell’esempio precedente è dispari, perché ha 3 inversioni.
Determinante di una matrice quadrata
Consideriamo una matrice con n righe ed m colonne (brevemente la chiameremo matrice nxm):
essa è una tabella di nxm caselle disposte in n righe ed m colonne; nelle caselle supporremo che vi siano valori numerici (per esempio numeri reali). Si dice che la matrice è quadrata se n=m (cioè se ha lo stesso numero di righe e di colonne).
In una matrice generica nxm indicheremo con il simbolo a
ijl’elemento della matrice nella casella
all’incrocio tra la riga i e la colonna j. Con tale convenzione, una matrice nxm sarà rappresentata da:
M =
nn n2
n1
3n 32
31
2n 22
21
1n 12
11
a . . . a a
. . . . . .
. . . . . .
a a
a
a a
a
a a
a
Sia data una generica matrice quadrata nxn, rappresentata come sopra.
Consideriamo nella matrice nxn un prodotto di n fattori, dove i fattori sono scelti fra gli elementi della matrice data secondo le seguenti regole:
- il primo fattore è scelto fra gli elementi della prima riga, il secondo fra gli elementi della seconda riga, etc…., l’ultimo fattore fra gli elementi della riga numero n
- i fattori sono scelti tutti in colonne diverse
Uno di tali prodotti si può indicare formalmente con:
a
1?a
2?a
3?…..a
n?dove i secondi indici ‘?’ indicano gli indici delle colonne in cui si sceglieranno gli elementi. Poiché le colonne devono essere diverse tra loro, i punti interrogativi ‘?’ saranno tutti i numeri naturali da 1 ad n in un certo ordine. Quindi il prodotto costruito con tale criterio avrà la forma:
a1j1a
1j2a
1j3...a
1jn
dove gli indici di colonna j
1, j
2, j
3, …., j
nformano una permutazione dei numeri naturali 1,2,…,n.
In totale, facendo variare la permutazione degli indici di colonna, si ottengono n! possibili prodotti costruiti con il criterio precedente.
Esempio: In una matrice 3x3:
33 32 31
23 22 21
13 12 11
a a a
a a a
a a a
si ottengono 3!=6 prodotti possibili, ed esattamente i seguenti:
33 22 11
a a
a , a
13a
21a
32 , a12a
23a
31 , a11a
23a
32 , a13a
22a
31 a
12a
21a
33
a
23a
32 , a13a
22a
31 a
12a
21a
33
corrispondenti rispettivamente alle 6 permutazioni di indici di colonna 123, 312, 231, 132, 321, 213.
Definiremo determinante della matrice quadrata nxn quel numero ottenuto sommando gli n!
prodotti di n fattori (costruiti come sopra), e dove ogni prodotto é preso con il suo segno se la permutazione degli indici di colonna corrispondente è pari, e con il segno opposto se la permutazione corrispondente è dispari.
Se M è una matrice nxn, det(M) indicherà il suo determinante.
Esempio: In una generica matrice matrice 2x2:
M =
22 21
12 11
a a
a a
i possibili prodotti di 2 fattori da considerare sono i numero di 2!=2 e sono i seguenti:
a
11a
22(permutazione degli indici di colonna: 12; 0 inversioni, pari) a
12a
21(permutazione degli indici di colonna: 21; 1 inversione, dispari) dunque il determinante è:
det(M)=a
11a
22– a
12a
21.
Questo porta alla seguente regola pratica per il calcolo del determinante di una matrice 2x2:
basta calcolare la differenza dei prodotti “in croce”, cioè dei prodotti degli elementi che si trovano lungo le diagonali (differenza fra il prodotto degli elementi della diagonale “principale” \ e il prodotto di quelli della diagonale “secondaria” /)
Esempio: In una generica matrice 3x3:
M=
33 32 31
23 22 21
13 12 11
a a a
a a a
a a a
i possibili prodotti di 3 fattori da considerare sono i numero di 3!=6 e sono i seguenti (come già visto in precedenza):
33 22 11
a a
a (permutazione degli indici di colonna: 123; 0 inversioni, pari)
32 21 13
a a
a (permutazione degli indici di colonna: 312; 2 inversioni, pari)
31 23 12
a a
a (permutazione degli indici di colonna: 231; 2 inversioni, pari)
32 23 11
a a
a (permutazione degli indici di colonna: 132; 1 inversione, dispari)
31 22 13
a a
a (permutazione degli indici di colonna: 321; 3 inversioni, pari)
33 21 12
