Principio inclusione-esclusione

[alessioben]

Ciao a tutti,
ho un problema di insiemistica nel capire la formula generale del prinicipio inclusione-esclusione.

Con n=1 , 2 o 3 il prof ha fatto l'esempio esplicito e l'ho capito.
Quando ha scritto la seguente formula generale ha detto di applicarla al caso 3 per capire i passaggi. Il problema è che ho cercato di applicarla ma non sono riuscito ad arrivare a quella corretta... Non parliamo della dimostrazione perché quella l'ha addirittura lasciata a metà.

$ | B| =sum((-1)^(| I| +1)| nn _(iin I) A_i| ) $
$ Isube {1,...,n} $

Grazie per i chiarimenti.

[Quinzio]

Vediamo il caso $n = 3$.
$ Isube {1,...,n} $ diventa $I sube {1,2,3}$.
Questa espressione dice che $I$ e' un sottinsieme di ${1,2,3}$, quindi dobbiamo prendere tutti i casi possibili.
$I = {1} $
$I = {2} $
$I = {3}$
$I = {1,2} $
$I = {2,3} $
$I = {1,3} $
$I = {1,2,3} $
E' meglio distinguerli con un pedice cosi' dopo diventa piu' chiaro.
$I_1 = {1} $
$I_2 = {2} $
$I_3 = {3}$
$I_4 = {1,2} $
$I_5 = {2,3} $
$I_6 = {1,3} $
$I_7 = {1,2,3} $

Adesso la formula diventa:
$ | B| =sum_{k=1}^6 ((-1)^(| I_k| +1)| nn _(iin I_k) A_i| ) $

Quindi la sommatoria e' una somma di 6 termini, e adesso vediamo il primo, con $k=1$, per cui $I_1 = {1}$ e la cardinalita' e' $|I_1| = 1$ perche' contiene solo un numero.

$ (-1)^(| I_1| +1)| nn _(iin I_1) A_i| $

$ =(-1)^(1 +1)| nn _(iin I_1) A_i| $

$ = 1 | nn _(iin I_1) A_i| $

$ = | nn _(iin I_1) A_i| $

Adesso dobbiamo fare la disgiunzione di tutti gli $A_i$ dove $i$ e' un indice che "scansiona" tutti gli elementi di $I$.
In questo caso $I$ ha solo un elemento quindi l'espressione diventa
$|A_1|$.
Dobbiamo prendere la cardinalita' di $A_1$, qualunque essa sia.

---------------------------------------------------------

Poi ne vediamo un altro, con $k=4$, per cui $I_4 = {1,2}$ e la cardinalita' e' $|I_4| = 2$ perche' contiene due numeri.

$ (-1)^(| I_4| +1)| nn _(iin I_4) A_i| $

$ =(-1)^(2 +1)| nn _(iin I_4) A_i| $

$ = -1 | nn _(iin I_4) A_i| $

$ =- | nn _(iin I_4) A_i| $

Adesso dobbiamo fare la disgiunzione di tutti gli $A_i$ dove $i$ e' un indice che "scansiona" tutti gli elementi di $I$.
In questo caso $I$ ha due elementi ${1,2}$ quindi l'espressione diventa
$|A_1 nn A_2|$.
Fare la disgiunzione $nn$ significa prendere solo gli elementi in comune.
Poi si deve prendere la cardinalita' di questi elementi in comune, ovvero contare quanti sono.

Adesso dovrebbe essere tutto piu' chiaro.

[Quinzio]

Una versione della stessa formula piu' corretta, secondo me, e' quella riportata da Wikipedia.
Sembra cervellotica, ma contiene tutto il necessario.

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

La dimostrazione poi e' qui, se il prof l'ha lasciata a meta', pazienza.

https://it.wikipedia.org/wiki/Principio ... esclusione