Principio di inclusione-esclusione

Da Wikipedia, l'enciclopedia libera.

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|

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

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[modifica | modifica wikitesto]

Dimostrazione I[modifica | modifica wikitesto]

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)[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]


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