Principio di inclusione-esclusione

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

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.

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).

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

• Inclusione-esclusione, principio di, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.  
• (EN) principle of inclusion and exclusion, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.  
• (EN) Eric W. Weisstein, Inclusion-Exclusion Principle, su MathWorld, Wolfram Research.  
• (EN) Inclusion-and-exclusion principle, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.  

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