Sul numero di funzioni iniettive e suriettive tra due insiemi finiti

Dati due insiemi finiti $X$ e $Y$, ci poniamo quattro domande:

  1. Quante sono le funzioni $X \to Y$?
  2. Quante sono le funzioni iniettive $X \to Y$?
  3. Quante sono le funzioni suriettive $X \to Y$?
  4. 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.

Questa voce è stata pubblicata in statistica. Contrassegna il permalink.

2 risposte a Sul numero di funzioni iniettive e suriettive tra due insiemi finiti

  1. Marco scrive:

    Le formule vengono mostrate come codice LaTeX sia in Firefox sia in Chrome. Il problema riguarda anche vecchi articoli che prima si visualizzavano correttamente. Potete verificare il caricamento dello script di rendering delle formule, ad esempio MathJax o KaTeX?

Commenta

Questo sito utilizza Akismet per ridurre lo spam. Scopri come vengono elaborati i dati derivati dai commenti.