Matematica Discreta Lezione del giorno 15 dicembre 2010 Numero delle funzioni iniettive fra insiemi finiti

(1)

Matematica Discreta

Lezione del giorno 15 dicembre 2010

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 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.

(2)

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 branca della teoria degli insiemi che studia (e tenta di contare) i diversi modi di “combinare” gli elementi di un insieme dato e cerca

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) .

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