Principio di inclusione-esclusione

Questa voce o sezione sull'argomento matematica non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento.

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 ${\displaystyle \left|A\right|}$ la cardinalità di un insieme ${\displaystyle A}$ e consideriamo una famiglia finita di insiemi finiti: ${\displaystyle A_{1},A_{2},\cdots ,A_{n}}$. Per la cardinalità dell'unione di tale famiglia si ha

${\displaystyle \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|=}$

${\displaystyle =\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 ${\displaystyle n=2}$ la formula si riduce a quella, molto intuitiva e ricavabile dalle definizioni, esprimibile come

${\displaystyle |A\cup B|=|A|+|B|-|A\cap B|}$

Nel caso ${\displaystyle n=3}$ il principio si esprime con l'uguaglianza

${\displaystyle |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:

${\displaystyle |A\cup B\cup C|=|(A\cup B)\cup C|=|A\cup B|+|C|-|(A\cup B)\cap C|}$

${\displaystyle \,=\,|A|+|B|-|A\cap B|+|C|-|(A\cap C)\cup (B\cap C)|}$

${\displaystyle =|A|+|B|+|C|-|A\cap B|-\left(|A\cap C|+|B\cap C|-|(A\cap C)\cap (B\cap C)|\right)}$

${\displaystyle =|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|}$