Inmatematica ed in particolare nellateoria degli insiemi , ilprincipio di inclusione-esclusione è un'identità che mette in relazione lacardinalità di uninsieme , espresso comeunione di insiemi finiti, con le cardinalità diintersezioni tra questi insiemi.
Denotiamo con| A | {\displaystyle \left|A\right|} A {\displaystyle A} A 1 , A 2 , ⋯ , A n {\displaystyle A_{1},A_{2},\cdots ,A_{n}}
| ⋃ i = 1 n A i | = ∑ i = 1 n | A i | − ∑ 1 ≤ i < j ≤ n | A i ∩ A j | + ∑ 1 ≤ i < j < k ≤ n | A i ∩ A j ∩ A k | − ⋯ ( − 1 ) n − 1 | A 1 ∩ ⋯ ∩ A n | = {\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|=} = ∑ i = 1 n ( − 1 ) i + 1 ∑ 1 ≤ j 1 < . . . < j i ≤ n | ⋂ k = 1 i A j k | {\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 undiagramma di Eulero-Venn del caso per tre insiemi Nel cason = 2 {\displaystyle n=2}
| A ∪ B | = | A | + | B | − | A ∩ B | {\displaystyle |A\cup B|=|A|+|B|-|A\cap B|} Nel cason = 3 {\displaystyle n=3}
| A ∪ B ∪ C | = | A | + | B | + | C | − | A ∩ B | − | A ∩ C | − | B ∩ C | + | A ∩ B ∩ C | {\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:
| A ∪ B ∪ C | = | ( A ∪ B ) ∪ C | = | A ∪ B | + | C | − | ( A ∪ B ) ∩ C | {\displaystyle |A\cup B\cup C|=|(A\cup B)\cup C|=|A\cup B|+|C|-|(A\cup B)\cap C|}
= | A | + | B | − | A ∩ B | + | C | − | ( A ∩ C ) ∪ ( B ∩ C ) | {\displaystyle \,=\,|A|+|B|-|A\cap B|+|C|-|(A\cap C)\cup (B\cap C)|} = | A | + | B | + | C | − | A ∩ B | − ( | A ∩ C | + | B ∩ C | − | ( A ∩ C ) ∩ ( B ∩ C ) | ) {\displaystyle =|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 ∩ B | − | A ∩ C | − | B ∩ C | + | A ∩ B ∩ C | {\displaystyle =|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|} Si dovrà dimostrare che ogni elemento dell'insieme⋃ i = 1 n A i {\displaystyle \bigcup _{i=1}^{n}A_{i}} x ∈ A 1 ∩ A 2 ∩ ⋯ ∩ A k {\displaystyle x\in A_{1}\cap A_{2}\cap \cdots \cap A_{k}} x ∉ A k + 1 ∩ ⋯ ∩ A n {\displaystyle x\notin A_{k+1}\cap \cdots \cap A_{n}} x {\displaystyle x} k {\displaystyle k}
Il termine∑ i = 1 n | A i | {\displaystyle \sum _{i=1}^{n}\left|A_{i}\right|} x {\displaystyle x} ( k 1 ) {\displaystyle {\binom {k}{1}}} sommatoria , cioè∑ 1 ≤ i < j ≤ n | A i ∩ A j | {\displaystyle \sum _{1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right|} x {\displaystyle x} ( k 2 ) {\displaystyle {\binom {k}{2}}}
Dunque l'elementox {\displaystyle x}
∑ i = 1 k ( − 1 ) i − 1 ( k i ) {\displaystyle \sum _{i=1}^{k}(-1)^{i-1}{\binom {k}{i}}}
Osserviamo che l'indicei {\displaystyle i} k {\displaystyle k} i = k + 1 {\displaystyle i=k+1} k + 1 {\displaystyle k+1} A i {\displaystyle A_{i}} x {\displaystyle x}
Si può ora dimostrare facilmente, considerando lo sviluppo delBinomio di Newton , che la sommatoria in questione è uguale a1 {\displaystyle 1}
1 − ∑ i = 1 k ( − 1 ) i − 1 ( k i ) = ∑ i = 0 k ( − 1 ) i ( k i ) = ( 1 − 1 ) k = 0 ◻ {\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 }
Abbiamo che
| ⋃ i = 1 n A i | = ∑ k = 1 n ( − 1 ) k + 1 ∑ 1 ≤ i 1 < ⋯ < i k ≤ n | A i 1 ∩ A i 2 ∩ ⋯ ∩ A i k | {\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 pern = 2 {\displaystyle n=2} n = 1 {\displaystyle n=1} | A 1 | = | A 1 | {\displaystyle \left|A_{1}\right|=\left|A_{1}\right|}
| A 1 ∪ A 2 | = | A 1 | + | A 2 | − | A 1 ∩ A 2 | {\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 pern {\displaystyle n} n + 1 {\displaystyle n+1}
⋃ i = 1 n + 1 A i = ( ⋃ i = 1 n A i ) ∪ A n + 1 {\displaystyle \bigcup _{i=1}^{n+1}A_{i}=\left(\bigcup _{i=1}^{n}A_{i}\right)\cup A_{n+1}}
Poiché l'ipotesi è vera pern = 2 {\displaystyle n=2}
| ⋃ i = 1 n + 1 A i | = | ⋃ i = 1 n A i | + | A n + 1 | − | ( ⋃ i = 1 n A i ) ∩ A n + 1 | {\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
∑ k = 1 n ( − 1 ) k + 1 ∑ 1 ≤ i 1 < ⋯ < i k ≤ n | A i 1 ∩ ⋯ ∩ A i k | + | A n + 1 | − ∑ k = 1 n ( − 1 ) k + 1 ∑ 1 ≤ i 1 < ⋯ < i k ≤ n | A i 1 ∩ ⋯ ∩ A i k ∩ A n + 1 | = {\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|=}
= ∑ k = 1 n + 1 ( − 1 ) k + 1 ∑ 1 ≤ i 1 < ⋯ < i k ≤ n + 1 | A i 1 ∩ ⋯ ∩ A i k | {\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 .
Il principio è stato utilizzato daNicolaus II Bernoulli (1695-1726); la formula viene attribuita adAbraham de Moivre (1667-1754); per il suo utilizzo e per la comprensione della sua portata vengono ricordatiJoseph Sylvester (1814-1897) edHenri Poincaré (1854-1912).
Inclusione-esclusione, principio di Enciclopedia della Matematica ,Istituto dell'Enciclopedia Italiana , 2013.(EN principle of inclusion and exclusion Enciclopedia Britannica (EN Inclusion-Exclusion Principle MathWorld (EN Inclusion-and-exclusion principle Encyclopaedia of Mathematics 
Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica