# Principio di inclusione-esclusione

In matematica ed in particolare nella teoria degli insiemi, il principio di inclusione-esclusione è un'identità che mette in relazione la cardinalità di un insieme, espresso come unione di insiemi finiti, con le cardinalità di intersezioni tra questi insiemi.
Denotiamo con $\left|A\right|$ la cardinalità di un insieme $A$ e consideriamo una famiglia finita di insiemi finiti: $A_{1},A_{2},\cdots ,A_{n}$. Per la cardinalità dell'unione di tale famiglia si ha
    $\left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{i=1}^{n}\left|A_{i}\right|-\sum _{1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right|+\sum _{1\leq i<j<k\leq n}\left|A_{i}\cap A_{j}\cap A_{k}\right|-\ \cdots \ (-1)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|=$
$=\sum _{i=1}^{n}\left(-1\right)^{i+1}\sum _{1\leq j_{1}<...<j_{i}\leq n}\left|\bigcap _{k=1}^{i}A_{j_{k}}\right|$
Nel caso $n=2$ la formula si riduce a quella, molto intuitiva e ricavabile dalle definizioni, esprimibile come
    $|A\cup B|=|A|+|B|-|A\cap B|$
Nel caso $n=3$ il principio si esprime con l'uguaglianza
    $|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$
Questa si dimostra servendosi più volte della precedente e della distributività della intersezione rispetto alla unione:
$|A\cup B\cup C|=|(A\cup B)\cup C|=|A\cup B|+|C|-|(A\cup B)\cap C|$
    $\,=\,|A|+|B|-|A\cap B|+|C|-|(A\cap C)\cup (B\cap C)|$
    $=|A|+|B|+|C|-|A\cap B|-\left(|A\cap C|+|B\cap C|-|(A\cap C)\cap (B\cap C)|\right)$
    $=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$

## Dimostrazioni
### Dimostrazione I

Si dovrà dimostrare che ogni elemento dell'insieme $\bigcup _{i=1}^{n}A_{i}$ viene contato una e una sola volta. Sia $x\in A_{1}\cap A_{2}\cap \cdots \cap A_{k}$ e $x\notin A_{k+1}\cap \cdots \cap A_{n}$, riordinando cioè gli insiemi e supponendo che $x$ appartenga ai primi $k$.
Il termine $\sum _{i=1}^{n}\left|A_{i}\right|$ conta $x$ esattamente ${\binom {k}{1}}$ volte, mentre il secondo termine dello sviluppo della sommatoria, cioè $\sum _{1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right|$ conta $x$ esattamente ${\binom {k}{2}}$ volte, ecc.
Dunque l'elemento $x$ nel principio di inclusione-esclusione è contato esattamente
$\sum _{i=1}^{k}(-1)^{i-1}{\binom {k}{i}}$ volte
Osserviamo che l'indice $i$ varia fino a $k$ perché considerando $i=k+1$, l'intersezione di $k+1$ con gli altri $A_{i}$ non conterrà $x$.
Si può ora dimostrare facilmente, considerando lo sviluppo del Binomio di Newton, che la sommatoria in questione è uguale a $1$:
$1-\sum _{i=1}^{k}(-1)^{i-1}{\binom {k}{i}}=\sum _{i=0}^{k}(-1)^{i}{\binom {k}{i}}=(1-1)^{k}=0\qquad \Box$

### Dimostrazione II (induzione su n)

Abbiamo che
$\left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{k=1}^{n}(-1)^{k+1}\sum _{1\leq i_{1}<\cdots <i_{k}\leq n}\left|A_{i_{1}}\cap A_{i_{2}}\cap \cdots \cap A_{i_{k}}\right|$
Verifichiamola per $n=2$, dato che per $n=1$ è banalmente $\left|A_{1}\right|=\left|A_{1}\right|$, e il caso tornerà poi utile nel proseguimento della dimostrazione:
$\left|A_{1}\cup A_{2}\right|=\left|A_{1}\right|+\left|A_{2}\right|-\left|A_{1}\cap A_{2}\right|$
Ipotizziamo ora vero il principio per $n$ insiemi, e dimostriamo che allora è vero anche per $n+1$ insiemi. Vale che
$\bigcup _{i=1}^{n+1}A_{i}=\left(\bigcup _{i=1}^{n}A_{i}\right)\cup A_{n+1}$
Poiché l'ipotesi è vera per $n=2$ vale
$\left|\bigcup _{i=1}^{n+1}A_{i}\right|=\left|\bigcup _{i=1}^{n}A_{i}\right|+\left|A_{n+1}\right|-\left|\left(\bigcup _{i=1}^{n}A_{i}\right)\cap A_{n+1}\right|$
Ovvero
$\sum _{k=1}^{n}(-1)^{k+1}\sum _{1\leq i_{1}<\cdots <i_{k}\leq n}\left|A_{i_{1}}\cap \cdots \cap A_{i_{k}}\right|+\left|A_{n+1}\right|-\sum _{k=1}^{n}(-1)^{k+1}\sum _{1\leq i_{1}<\cdots <i_{k}\leq n}\left|A_{i_{1}}\cap \cdots \cap A_{i_{k}}\cap A_{n+1}\right|=$
$=\sum _{k=1}^{n+1}(-1)^{k+1}\sum _{1\leq i_{1}<\cdots <i_{k}\leq n+1}\left|A_{i_{1}}\cap \cdots \cap A_{i_{k}}\right|$
Tale proposizione è vera in quanto i due termini dell'uguaglianza hanno gli stessi addendi con lo stesso segno. Come volevasi dimostrare.

## Storia

Il principio è stato utilizzato da Nicolaus II Bernoulli (1695-1726); la formula viene attribuita ad Abraham de Moivre (1667-1754); per il suo utilizzo e per la comprensione della sua portata vengono ricordati Joseph Sylvester (1814-1897) ed Henri Poincaré (1854-1912).