Inclusione-Esclusione

# Inclusione-Esclusione ###### tags: `md` #### Principio di Inclusione-Esclusione ###### Teorema Principio di Inclusione-Esclusione Consideriamo un intero $n ≥ 1$ e siano $A_1,A_2,\ldots,A_n$ insiemi ﬁniti. Dato un sottoinsieme $I = {i_1,i_2,\ldots,i_r}$ di $N_n$ poniamo $$ A_I =\bigcap_{i\in I}A_i = A_{i1}\cap A_{i2} \cap\cdots\cap A_{ir} $$ Allora $$ |\bigcup_{i=1}^n A_i| = \sum_{\emptyset \neq I\sube N_n} (−1)^{|I|−1}|A_I| $$ (si noti che l’indice I nella formula varia fra tutti i sottoinsiemi di Nn escluso l’insieme vuoto) ###### Dimostrazione La nostra strategia sarà quella di dimostrare che il membro di sinistra e quello di destra forniscono lo stesso numero, ossia la cardinalità di $\bigcup^n_{i=1}A_i$. Mostreremo cioè che ogni elemento $x\in \bigcup^n_{i=1}A_i$ è contato esattamente una volta nel membro di sinistra e in quello di destra della formula. Visto che questo è ovvio per il membro di sinistra, studiamo il membro di destra. Preso dunque un $x\in \bigcup^n_{i=1}A_i$, questo apparterrà ad alcuni degli $A_i$, diciamo che appartenga esattamente a $r$ di essi: $A_{i1},A_{i2},\cdots,A_{ir}$. Allora $x$ nel membro di destra viene contato esattamente con questo coefficiente: $$ r−{r\choose 2}+{r\choose 3}−{r\choose 4}+\cdots+ (−1)^{r−1}{r\choose r} $$ Infatti nel membro di destra vengono conteggiati col segno "+" gli elementi di tutti gli $r$ insiemi $A_{i1},A_{i2},\cdots,A_{ir}$, col segno "−" gli elementi di tutte le loro $r\choose 2$ intersezioni a due a due, col segno più gli elementi di tutte le loro ${r\choose 3}$ intersezioni a $3$ a $3$ e così via... Ma per il Teorema del binomio di Newton noi sappiamo che $$ 0 = (1−1)^r={r\choose 0}−{r\choose 1}+{r\choose 2}−{r\choose 3}+\cdots+ (−1)^r{r\choose r} $$ da cui, visto che ${r\choose 0}= 1$ e ${r\choose 1}=r$, $$ 1 =r−{r\choose 2}+{r\choose 3}−{r\choose 4}+ \cdots + (−1)^{r−1}{r\choose r} $$ Questo permette di concludere che (indipendentemente da quale sia $r$) il coefficiente con cui viene contato $x$ nel membro di destra è $1$, come volevamo. ###### Teorema Dati due insiemi ﬁniti $A$ e $B$, la loro unione $A \cup B$ vale $|A\cup B| = |A|+|B|−|A\cap B| $ ###### Teorema Dati due insiemi ﬁniti $A$, $B$, e $C$ la loro unione $A \cup B \cup C$ vale $|A \cup B \cup C| = |A|+|B|+|C|−|A \cap B|−|A \cap C|−|B \cap C|+|A \cap B \cap C|$ #### Applicazioni Dati due insiemi ﬁniti non vuoti $X$ e $Y$ , chiamiamo $Surj (X \to Y)$ l'insieme di tutte le funzioni surgettive che hanno $X$ come dominio e $Y$ come codominio: $Surj (X \to Y) = \{f | f : X \to Y \text{ è una funzione surgettiva}\}$ Tramite il principio di Inclusione-Esclusione possiamo determinare la cardinalità di $Surj(X \to Y)$ ###### Teorema Siano $X$ e $Y$ ﬁniti non vuoti con $|X| = n \ge 1$ e $|Y| = m \ge 1$. Vale: $$ |Surj(X \to Y)| = \sum_{j=0}^m{m \choose j}(−1)^j(m−j)^n $$ ###### Osservazione Come potete veriﬁcare, quando $|Y| = 1$ o $|Y| = 2$, la formula precedente conferma i risultati $1$ e $2^n −2$ che abbiamo ottenuto sopra. In particolare se $n < m$ come sappiamo $|Surj (X \to Y )| = 0$ dunque la formula sopra ci dice: $$ 0 = \sum_{j=0}^m {m \choose j}(−1)^j(m−j)^n $$ ###### Dimostrazione Sia $X=\{x_1,x_2,\cdots, x_n\}$ e $Y=\{y_1,y_2,\cdots, y_m\}$. Per ogni $i=1,2,\ldots,m$ chiamiamo $A_i$ l'insieme delle funzioni da $X$ a $Y$ la cui immagine non contiene $y_i$: $$ A_i=\{g|g:X\to Y \and y_i\notin Imm(g)\} $$ Allora l'insieme delle funzioni non surgettive coincide con $\bigcup^m_{i=1}A_i$; se riusciamo a calcolare la cardinalità di questo insieme possiamo facilmente ricavare quella di $Surj(X\to Y)$ "per complementare", visto che conosciamo anche la cardinalità (uguale a $m^n$) dell'insieme $F(X\to Y)$ di tutte le funzioni da $X$ a $Y$. Infatti $$ Surj(X\to Y) =F(X\to Y)−\bigcup^m_{i=1}A_i $$ e dunque $$ |Surj(X\to Y)|=m^n−|\bigcup^m_{i=1}A_i| $$ Ora, per calcolare $|\bigcup^m_{i=1}A_i|$ possiamo usare il principio di Inclusione-Esclusione. Per prima cosa osserviamo che, se $I=\{i_1,i_2,\ldots, i_j\}\subseteq\{1,2,\ldots, m\}$ allora $$ |A_I|=|A_{i1}\cap A_{i2}\cap\cdots\cap A_{ij}|= (m−j)^n $$ Infatti $A_{i1}\cap A_{i2}\cap \cdots \cap A_{ij}$ è l'insieme delle funzioni da $X$ a $Y$ che non contengono nella loro immagine né $y_{i1}$ né $y_{i2}$ ... né $y_{ij}$ e tale insieme è in corrispondenza biunivoca con l'insieme $F(X\to(Y−\{y_{i1},\ldots, y_{ij}\}))$. Per il principio di Inclusione-Esclusione: $$ |\bigcup^m_{i=1}A_i|=\sum_{ \emptyset \neq I\subseteq \mathbb{N}_m} (−1)^{|I|−1}|A_I|=\sum^m_{j=1} \sum_{I\subseteq \mathbb {N}_m\atop |I|=j}(−1)^{j−1}(m−j)^n $$ dove l'ultima espressione è stata ottenuta spezzando la sommatoria: abbiamo raggruppato tutti gli $I\subseteq\mathbb{N}_m$ che hanno la stessa cardinalità $j$ e poi sommato su $j= 1,2,\ldots,m$. Ora, gli $I\subseteq \mathbb{N}_m$ che hanno cardinalità $j$ sono ${m\choose j}$, dunque possiamo scrivere: $$ =\sum^m_{j=1}{m\choose j}(−1)^{j−1}(m−j)^n $$ In conclusione $$ |Surj(X\to Y)|=m^n−\sum^m_{j=1}{m\choose j}(−1)^{j−1}(m−j)^n $$ Questa formula può essere espressa in maniera più compatta. Infatti: $$ m^n−\sum^m_{j=1}{m\choose j}(−1)^{j−1}(m−j)^n=m^n+\sum^m_{j=1}{m\choose j}(−1)^j(m−j)^n $$ e, visto che ${m\choose 0}= 1$, possiamo modificare la sommatoria in modo che includa anche il primo addendo $m^n$: $$ |Surj(X\to Y)|=\sum^m_{j=0}{m\choose j}(−1)^j(m−j)^n $$ `omessi gruppi simmetrici pagina 97` `omesse permutazioni senza gruppi fissi pagina 100`