Dati due insiemi finiti $X$ e $Y$, ci poniamo quattro domande:
- Quante sono le funzioni $X \to Y$?
- Quante sono le funzioni iniettive $X \to Y$?
- Quante sono le funzioni suriettive $X \to Y$?
- Quante sono le funzioni biettive $X \to Y$?
Chiamando con $\abs{X}$ il numero di elementi di $X$ (i.e. la sua cardinalità) e similmente per $Y$, possiamo subito risolvere la prima domanda. Infatti una funzione $X \to Y$ assegna ad ogni elemento di $X$ un elemento di $Y$; in particolare, ogni elemento di $X$ deve avere assegnato un valore. Perciò per ogni elemento di $X$ abbiamo $\abs{Y}$ possibilità arbitrarie. Quindi la risposta alla 1. è che in totale abbiamo $\abs{Y} \cdot \abs{Y} \cdots \abs{Y} = \abs{Y}^{\abs{X}}$ funzioni generiche $X \to Y$.
Per quanto riguarda la seconda domanda, una funzione $f:X \to Y$ è biettiva se $f(x_1)=f(x_2)$ implica $x_1=x_2$. Ovvero non possiamo assegnare lo stesso elemento di $Y$ a due diversi elementi di $X$. Ragioniamo quindi come prima. Per il primo elemento di $X$ abbiamo $\abs{Y}$ possibilità, mentre per il secondo elemento di $X$ soltanto $\abs{Y}-1$ possibilità, in quanto non possiamo assegnargli l’elemento di $Y$ assegnato al primo elemento elemento di $X$. Continuando, per il $k$-esimo elemento di $X$ abbiamo $\abs{Y}-k+1$ possibilità. Perciò in totale il numero di funzioni iniettive è dato da
$$\abs{Y} \cdot (\abs{Y}-1) \cdot (\abs{Y}-2) \cdots (\abs{Y}-\abs{X}+1) = \frac{\abs{Y} ! }{(\abs{Y}-\abs{X})!}$$
Notiamo in particolare che ciò ha senso solo se $\abs{Y} \geq \abs{X}$; altrimenti per forza due elementi di $X$ dovranno avere lo stesso valore di $Y$ e quindi non abbiamo funzioni iniettive.
Il caso delle funzioni biettive in realtà segue facilmente da questo. Infatti se la funzione è biettiva, dobbiamo avere necessariamente $\abs{X}=\abs{Y}$; se ciò non si verifica, il numero di funzioni biettive è nullo. Al contrario, se i due insiemi hanno lo stesso numero di elementi, una funzione biettiva è semplicemente una permutazione degli elementi, e sappiamo che ne abbiamo esattamente $\abs{X}!$. In alternativa, se i due insiemi hanno lo stesso numero di elementi, una funzione iniettiva è automaticamente biettiva e quindi la formula segue dal caso precedente ponendo $\abs{X}=\abs{Y}$.
La cosa più difficile è il caso 3. in cui dobbiamo contare le funzioni suriettive. A tal scopo seguiamo il suggerimento trovato qui e applichiamo il principio di inclusione-esclusione. Innanzitutto il numero di funzioni suriettive sarà dato dal numero totale di funzioni meno quello delle funzioni non suriettive. Se una funzione non è suriettiva, è perché la sua immagine non contiene almeno un elemento $y \in Y$. Chiamiamo $\Omega_y$ il sottoinsieme delle funzioni $X \to Y$ che “mancano” $y \in Y$. L’insieme delle funzioni non suriettive sarà quindi l’unione di questi sottoinsiemi,
$$ \bigcup_{y \in Y} \Omega_y$$
Tuttavia questi sottoinsiemi non sono disgiunti: infatti una funzione può mancare due elementi di $Y$ (e quindi trovarsi in due sottoinsiemi) oppure in tre, ecc. Perciò per contare il numero di elementi di questo insieme utilizziamo il principio di inclusione-esclusione, secondo cui
$$\abs{\bigcup_{y =1}^{\abs{Y}} \Omega_y } = \sum_{y =1}^{\abs{Y}} (-1)^{y+1} \sum_{1\leq j_1 < j_2 < \cdots < j_y \leq \abs{Y}} \abs{\bigcap_{k=1}^{y} \Omega_{j_y} }$$
dove per semplicità abbiamo enumerato gli elementi di $Y$ da $1$ a $\abs{Y}$. Ora possiamo calcolare i vari pezzi. Innanzitutto $\bigcap_{k=1}^{y} \Omega_{j_y}$ è l’insieme delle funzioni $X \to Y$ la cui immagine non contiene nessuno tra $j_1, j_2, \ldots, j_y$ (che sono tutti diversi). Queste sono esattamente le funzioni generiche da $X$ all’insieme $Y-\cup_{k=1}^{y}\{j_k\}$ (ovvero $Y$ a cui abbiamo tolto $j_1, j_2, \ldots, j_y$). Poiché i $j$ sono tutti diversi, $\abs{Y-\cup_{k=1}^{y}\{j_k\}}=\abs{Y}-y$ e poiché le funzioni sono generiche possiamo utilizzare il risultato del primo punto ottenendo
$$\abs{\bigcap_{k=1}^{y} \Omega_{j_y}} = (\abs{Y}-y)^\abs{X}$$
Poiché questo numero non dipende dai $j$ ma solo da $y$, possiamo quindi portarlo fuori dalla somma. Rimane quindi da calcolare la somma sui $j$, che per questo motivo si riduce al calcolare, dato $y$, quante sono le possibili scelte dei $j$ tali che $1\leq j_1 < j_2 < \cdots < j_y \leq \abs{Y}$. Ma questo è equivalente a scegliere $y$ elementi di $Y$ diversi, che sono ${\abs{Y} \choose y}$. Quindi sostituendo abbiamo
$$\abs{\bigcup_{y =1}^{\abs{Y}} \Omega_y } = \sum_{y =1}^{\abs{Y}} (-1)^{y+1} {\abs{Y} \choose y} (\abs{Y}-y)^\abs{X}$$
L’espressione diventa più semplice sostituendo $y \to \abs{Y}-y$, ovvero
$$\abs{\bigcup_{y =1}^{\abs{Y}} \Omega_y } = \sum_{y=0}^{\abs{Y}-1} (-1)^{\abs{Y}+1-y} {\abs{Y} \choose y} y^\abs{X}$$
Per ottenere il numero di funzioni suriettive dobbiamo quindi sottrarre questo numero dal numero di funzioni totali, ottenendo
$$\abs{Y}^\abs{X} -\abs{\bigcup_{y =1}^{\abs{Y}} \Omega_y } = \abs{Y}^\abs{X}+\sum_{y=0}^{\abs{Y}-1} (-1)^{\abs{Y}-y} {\abs{Y} \choose y} y^\abs{X} = \sum_{y=0}^{\abs{Y}} (-1)^{\abs{Y}-y} {\abs{Y} \choose y} y^\abs{X}$$
dove abbiamo potuto riassorbire l’elemento esterno nella somma estendendola fino ad $y=\abs{Y}$. Perciò il numero di funzioni suriettive $X \to Y$ è dato da
$$\sum_{y=0}^{\abs{Y}} (-1)^{\abs{Y}-y} {\abs{Y} \choose y} y^\abs{X}$$
Anche qui abbiamo una limitazione più ovvia: ovvero le funzioni suriettive esistono solo se $\abs{X} \geq \abs{Y}$, altrimenti esisterà sempre un elemento di $Y$ che non ha controimmagine.