Principio di inclusione ed esclusione

Da Wikipedia, l'enciclopedia libera.

Il termine principio di inclusione ed esclusione viene usato per denotare una formula che permette di esprimere la cardinalità di un insieme individuato come unione di insiemi finiti mediante le cardinalità di intersezioni di questi insiemi, cardinalità inferiori e quindi tendenzialmente più facili da determinare.

Denotiamo con |A| la cardinalità di un insieme A e consideriamo una famiglia finita di insiemi finiti : $A 1, A 2,..., 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\cdots\ (-1)^{n-1} \left|A_1\cap\cdots\cap A_n\right| =$

$=\sum_{i=1}^n\left ( \left(-1\right)^{i+1}\sum_{0\leq j_1 <...< j_i \leq n} \left | \bigcap_{k=1}^{i} A_{j_k} \right| \right )$

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

Anch'essa è interpretabile senza difficoltà mediante un diagramma di Eulero - Venn.

Nel caso generale si dimostra per induzione su n: si assume vera per una famiglia di n insiemi e si manipola l'espressione per la famiglia estesa con $A n + 1$ servendosi delle formule relativa a famiglie con al più n insiemi.

Il principio è stato utilizzato da Nicolaus Bernoulli (II) (1695-1626); 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).

Vedi anche

Estratto da "http://it.wikipedia.org../../../p/r/i/Principio_di_inclusione_ed_esclusione.html"

Categorie: Combinatoria | Teoria degli insiemi