Disposizioni e Permutazioni.

Abbiamo:

* A = {1, 2, 3, 4} (4 elementi)

* B = {1, 2, 3} (3 elementi)

Per avere una funzione suriettiva, dobbiamo assicurarci che ogni elemento di B (1, 2 e 3) sia l'immagine di almeno un elemento di A.

Un approccio più efficiente: il principio di inclusione-esclusione

Invece di contare le funzioni suriettive, contiamo quelle che non sono suriettive. Queste sono le funzioni che "saltano" almeno un elemento di B.

* Funzioni che saltano un elemento di B:

   * Scegliamo uno degli elementi di B da saltare (3 possibilità).

   * Le rimanenti funzioni sono tutte le possibili funzioni da A a B-{elemento saltato}. Questo è un insieme con 3 elementi. Quindi abbiamo 3^4 possibilità.

   * In totale abbiamo 3 * 3^4 funzioni che saltano un elemento.

Il numero di funzioni suriettive è dato da:

* Totale funzioni da A a B - Funzioni che saltano almeno un elemento + Funzioni che saltano tutti gli elementi

* 3^4 - (3 * 3^4 - 3 * 2^4 + 1)

Calcoliamo:

* 3^4 = 81

* 3 * 3^4 = 243

* 3 * 2^4 = 48

* Quindi, il numero di funzioni suriettive è: 81 - (243 - 48 + 1) = 36

Conclusione

Ci sono 36 funzioni suriettive possibili dall'insieme A all'insieme B.

Suriettiva => 1 2 3 devono comparire almeno una volta come immagini

Scelgo 3 elementi da 4 => 4 modi

A questi tre elementi abbino 123 in ordine qualunque : 3! = 6 modi

4 x 6 = 24

L'ultimo elemento rimasto va abbinato a uno tra 1 2 3 : tre modi

e 24 x 3 = 72

A questo punto ogni funzione é stata contata due volte

INFATTI

1 2 3 4

3 2 1 1

ottenuta facendo l'abbinamento su 124 e poi ripetendo 1 su 3

equivale a quella che si ottiene facendolo su 123 e poi ripetendolo su 4

Dunque 72 : 2 = 36