Matematica Discreta Lezione del giorno 8 novembre 2011 Numero delle funzioni surgettive fra insiemi finiti

(1)

Matematica Discreta

Lezione del giorno 8 novembre 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 A

1

={1,2}, A

2

={3}, A

3

={4,5,6}; schematizzando:

A

1

={1,2}1 A

2

={3}2 A

3

={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 A

1

={1,2}, A

2

={3}, A

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:

A

1

={1,2}2 A

2

={3}3 A

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 (ciò corrisponde a considerare dunque tutte le permutazioni degli elementi di B).

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.

(2)

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.

2) Il problema del “bersaglio”.

Si supponga di colpire con 101 colpi (tutti a segno) un bersaglio quadrato con il lato di lunghezza 70 cm. Allora certamente esistono almeno 2 colpi sul bersaglio che distano meno di 10 cm.

Infatti basta suddividere il bersaglio in 100 quadrati, ognuno con il lato di lunghezza 7 cm., considerare l’insieme A dei 101 colpi e l’insieme B dei 100 quadrati, e definire poi la funzione f: A→ B che associa ad ogni colpo di A il quadrato in cui esso cade. Per il principio dei cassetti (essendo la cardinalità 101 di A maggiore della cardinalità 100 di B) esistono almeno 2 colpi che cadono nello stesso quadrato, e geometricamente la loro distanza non è superiore alla lunghezza della diagonale che è uguale a

7 2

cioè circa 9,9 cm.

Principio della somma

Siano A,B insiemi finiti con A=n, B=m.

Se A,B non hanno elementi comuni, cioè se A∩B=, è ovvio che la cardinalità dell’unione AB coincide con la somma delle singole cardinalità dei 2 insiemi, perché l’elenco degli elementi distinti di AB si ottiene semplicemente elencando consecutivamente gli elementi di A e di B:

AB = n + m = A +B (è il cosiddetto principio della somma per 2 insiemi).

E’ ovvio che tale principio si generalizza ad un numero qualunque di insiemi: se A

1

,A

2

,…,A

n

sono n insiemi finiti, e se a 2 a 2 hanno intersezione vuota, si ha allora:

A

1

A

2

…A

n

= A

1

+A

2

+….+A

n

 (principio della somma per n insiemi).

(3)

Principio di inclusione-esclusione

Siano A,B insiemi finiti con A=n, B=m.

Se A,B hanno qualche elemento in comune, cioè se A∩B, il principio della somma non è più valido, perché la somma delle singole cardinalità di A e B non coincide con la cardinalità dell’unione AB, in quanto nella somma delle cardinalità gli elementi comuni sarebbero erroneamente contati 2 volte.

Si deve quindi modificare la formula nel modo seguente:

AB = A +B- A∩B (è il cosiddetto principio di inclusione-esclusione per 2 insiemi) E’ ovvio che il principio della somma diventa un caso particolare del principio di inclusione- esclusione nel caso che sia A∩B= (perché in tale caso la cardinalità di A∩B è 0).

Tale principio di inclusione-esclusione si può estendere facilmente a più di 2 insiemi. Se per esempio sono dati 3 insiemi finiti A,B,C, per calcolare la cardinalità della loro unione, usando le proprietà insiemistiche dell’unione e dell’intersezione (in particolare la proprietà distributiva) e usando più volte il principio di inclusione-esclusione valido per 2 insiemi, si ha:

ABC=(AB)C=AB+C-(A∩B)C=AB+C-(A∩C)(B∩C)=

= A+B- A∩B+C- {A∩C+B∩C-(A∩C)∩(B∩C)}=

(notando che (A∩C)∩(B∩C)=A∩B∩C)

=A+B+C-[A∩B+A∩C+B∩C]+A∩B∩C

e si ottiene quindi la formula del principio di inclusione-esclusione nel caso di 3 insiemi finiti:

ABC = A+B+C-[A∩B+A∩C+B∩C]+A∩B∩C.

Esiste una formula generale per il caso di n insiemi (che si dimostra con il principio di induzione, ma della quale omettiamo la dimostrazione): se sono dati n insiemi finiti A

1

,A

2

,…,A

n

, la cardinalità della loro unione si calcola con la formula

A

1

A

2

…A

n

=α

1

- α

2

+ α

3

- α

4

+……. ± α

n

dove α

1

è la somma delle cardinalità dei singoli insiemi; α

2

è la somma delle cardinalità di tutte le

possibili intersezioni a 2 a 2 degli insiemi; α

3

è la somma delle cardinalità di tutte le possibili

intersezioni a 3 a 3 degli insiemi; etc…….. …….; α

n