Matematica Discreta Lezione del giorno 14 gennaio 2011 Numero delle funzioni surgettive fra insiemi finiti

Matematica Discreta

Lezione del giorno 14 gennaio 2011

Numero delle funzioni surgettive fra insiemi finiti

Siano A,B insiemi finiti con A=n, B=m, e contiamo il numero delle possibili funzioni surgettive f : A  B.

Sappiamo che se n<m tale numero è 0. Supponiamo dunque nm .

Data una funzione surgettiva f : A  B, da essa si può ricavare una partizione di A in m sottoinsiemi, ponendo in ciascuno degli m sottoinsiemi quegli elementi di A che hanno lo stesso corrispondente in B.

Per esempio se n=6, m=3, A={1,2,3,4,5,6}, B={1,2,3} e se f : A  B è definita ponendo:

f(1)=1, f(2)=1, f(3)=2, f(4)=3, f(5)=3, f(6)=3

si ricava una partizione di A in 3 sottoinsiemi {{1,2}, {3}, {4,5,6,7}}; schematizzando:

{1,2}1, {3}2, {4,5,6}3.

Ma se fissiamo una partizione di A in m sottoinsiemi, e costruiamo la corrispondente funzione surgettiva f : A  B (associando agli elementi di uno stesso sottoinsieme di A lo stesso elemento di B) non otteniamo una sola possibile funzione surgettiva, ma diverse funzioni surgettive.

Per esempio, se A,B sono come sopra, la partizione precedente {{1,2}, {3}, {4,5,6}} non determina solo la funzione f definita nell’esempio, ma anche la funzione g: A  B definita ponendo:

g(1)=2, g(2)=2, g(3)=3, g(4)=1, g(5)=1, g(6)=1 con schema:

{1,2}2, {3}3, {4,5,6}1.

Oltre f,g è evidente che possiamo costruire altre funzioni surgettive, in cui si cambia “l’ordine” in cui sono disposti gli elementi di B per definire le immagini degli elementi di A.

In generale quindi, per ottenere una funzione surgettiva f : A  B si deve fissare una partizione di A in m sottoinsiemi (tale scelta si può effettuare in S(n,m) modi diversi, dove S(n,m) è il numero di Stirling) e, fissata tale partizione, scegliere una permutazione degli elementi di B per definire le immagini degli elementi di A (con la regola che elementi dello stesso sottoinsieme della partizione hanno la stessa immagine in B). Poiché questa seconda scelta (fissata la prima scelta) si può effettuare in m! modi diversi, per il principio delle scelte multiple il numero delle funzioni surgettive da un insieme di cardinalità n in un insieme di cardinalità m (con nm) è il prodotto m!

S(n,m).

Esempio: il numero delle funzioni surgettive da un insieme di cardinalità 4 in un insieme di cardinalità 3 è il prodotto 3!S(4,3)=66=36 (su un totale di 3

=81 funzioni da un insieme di cardinalità 4 in un insieme di cardinalità 3). Notare che il valore S(4,3)=6 è ricavato dalla riga numero 4 del triangolo di Stirling.

Principio dei cassetti.

Si basa sul seguente risultato di insiemistica: se A,B sono insiemi finiti, con A=n, B=m, e se n>m , comunque data una funzione f: A → B, esistono sempre almeno 2 elementi diversi in A che hanno in B lo stesso corrispondente mediante f (tale risultato è ovvio perché sappiamo che, se n>m, la funzione f certamente non è iniettiva).

Se pensiamo ad A come un insieme di n “oggetti”, a B come un insieme di m “cassetti”, e alla

funzione f come un modo di inserire ogni oggetto in un cassetto, il principio afferma semplicemente

che se il numero di oggetti è maggiore di quello dei cassetti, certamente esistono almeno 2 oggetti diversi che saranno inseriti nello stesso cassetto.

Vediamo un paio di applicazioni del principio dei cassetti:

1) Il problema delle “strette di mano”.

Supponiamo che A sia un insieme di n persone che si riuniscono, e che ognuna stringa la mano ad alcune altre (al limite anche a nessuna o a tutte le altre). Si può allora concludere con certezza che esistono sempre almeno 2 persone diverse che hanno stretto la mano allo stesso numero di persone.

Infatti se B è l’insieme dei numeri interi da 0 ad (n.-1), possiamo definire una funzione f: A → B, associando ad ogni persona il numero di strette di mano. Ovviamente però non può avvenire contemporaneamente che i valori 0 e (n-1) siano corrispondenti di elementi di A (se esiste una persona che ha stretto le mani a tutte le altre, non ne esiste una che non ha stretto le mani a nessuno). Quindi possiamo restringere il codominio B, sostituendolo con un insieme C ottenuto togliendo da B quel numero (0 oppure (n-1)) che non è corrispondente di nessun elemento di A.

Otteniamo così una funzione f: A → C, dove A=n, C=n-1<n: applicando il principio dei

cassetti si ha la tesi.