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

Rappresentazione con un diagramma di Eulero-Venn del caso per tre insiemi

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|}$

Dimostrazioni

Dimostrazione I

Si dovrà dimostrare che ogni elemento dell'insieme ${\displaystyle \bigcup _{i=1}^{n}A_{i}}$ viene contato una e una sola volta. Sia ${\displaystyle x\in A_{1}\cap A_{2}\cap \cdots \cap A_{k}}$ e ${\displaystyle x\notin A_{k+1}\cap \cdots \cap A_{n}}$, riordinando cioè gli insiemi e supponendo che ${\displaystyle x}$ appartenga ai primi ${\displaystyle k}$.

Il termine ${\displaystyle \sum _{i=1}^{n}\left|A_{i}\right|}$ conta ${\displaystyle x}$ esattamente ${\displaystyle {\binom {k}{1}}}$ volte, mentre il secondo termine dello sviluppo della sommatoria, cioè ${\displaystyle \sum _{1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right|}$ conta ${\displaystyle x}$ esattamente ${\displaystyle {\binom {k}{2}}}$ volte, ecc.

Dunque l'elemento ${\displaystyle x}$ nel principio di inclusione-esclusione è contato esattamente

${\displaystyle \sum _{i=1}^{k}(-1)^{i-1}{\binom {k}{i}}}$ volte

Osserviamo che l'indice ${\displaystyle i}$ varia fino a ${\displaystyle k}$ perché considerando ${\displaystyle i=k+1}$, l'intersezione di ${\displaystyle k+1}$ con gli altri ${\displaystyle A_{i}}$ non conterrà ${\displaystyle x}$.

Si può ora dimostrare facilmente, considerando lo sviluppo del Binomio di Newton, che la sommatoria in questione è uguale a ${\displaystyle 1}$:

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

${\displaystyle \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 ${\displaystyle n=2}$, dato che per ${\displaystyle n=1}$ è banalmente ${\displaystyle \left|A_{1}\right|=\left|A_{1}\right|}$, e il caso tornerà poi utile nel proseguimento della dimostrazione:

${\displaystyle \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 ${\displaystyle n}$ insiemi, e dimostriamo che allora è vero anche per ${\displaystyle n+1}$ insiemi. Vale che

${\displaystyle \bigcup _{i=1}^{n+1}A_{i}=\left(\bigcup _{i=1}^{n}A_{i}\right)\cup A_{n+1}}$

Poiché l'ipotesi è vera per ${\displaystyle n=2}$ vale

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

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

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

Voci correlate

• Formula di inversione di Moebius-Rota
• Disuguaglianze di Boole e di Bonferroni
• Teorema della probabilità totale
• Reticolo booleano

Collegamenti esterni

• (EN) principle of inclusion and exclusion, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Principio di inclusione-esclusione, su MathWorld, Wolfram Research.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica