Principio di inclusione esclusione

[rmba]

Un saluto a tutti.
Sto cercando di capire come funziona il principio di inclusione esclusione, ma con risultati quasi nulli.

Prendo come riferimento questa dispensa: http://uz.sns.it/~fvenez/inc-esc.pdf

Prima di tutto non capisco come funziona la sommatoria S(k)..

Secondo, mi servirebbe qualche esempio per rendermi conto di come, preso un elemento appartenente ad un certo numero di sottoinsiemi, questo sia contato contato una sola volta nella sommatoria S(k).

Mi potete aiutare?

Grazie.

[killing_buddha]

Un metodo estremamente elegante di ottenere il principio di inclusione-esclusione e' descritto all'inizio del capitolo "Sieve methods" del libro "Enumerative Combinatorics" di R. Stanley, qui a pagina 223 e segg.

[axpgn]

Mah, non saprei se possa esserti utile ma come esempio prova a determinare quanti sono, tra i numeri naturali da uno a cento (compresi), quanti sono quelli divisibili per $2$ o per $3$ o per $5$ (OR inclusivo).
Poni $U={1,2,...,100}$, $A, B, C$ gli insiemi contenenti, rispettivamente, i numeri divisibili per $2$, per $3$ e per $5$ e sia $P$ l'unione dei tre insiemi $A, B, C$.
Qual'è la cardinalità di $P$?
Ora si trova facilmente che $|A|=100/2=50$, $|B|=\lfloor 100/3 \rfloor=33$, $|C|=100/5=20$ ma la cardinalità di $P$ non è la somma delle tre cardinalità: numeri come $10$ o $24$ o $35$ sono contati due volte.
Più precisamente i numeri divisibili per $2*3=6$ stanno sia in $A$ che in $B$, quelli divisibili per $2*5=10$ stanno sia in $A$ che in $C$ e quelli divisibili per $3*5=15$ stanno sia in $B$ che in $C$, dunque alla somma di $|A|+|B|+|C|$ dobbiamo togliere $|A nn B|$ e $|A nn C|$ e $|B nn C|$.
Finita? No, perché numeri come $2*3*5=30$ stanno in tutti e tre gli insiemi e quindi li abbiamo contati tre volte con la prima somma e poi tolti tre volte togliendo le tre intersezioni col risultato di non contarlo per niente , quindi vanno ri-aggiunti i numeri divisibili per $30$ cioè quelli che stanno in $|A nn B nn C|$.
Riassumendo: $|P|=|A|+|B|+|C|-|A nn B|-|A nn C|-|B nn C|+|A nn B nn C|$

[rmba]

Nessuno potrebbe scrivermi lo sviluppo della sommatoria

[img]https://wikimedia.org/api/rest_v1/media/math/render/svg/6b2e56dfde39eef90d157bf8a6b0f505942ec859[/img]

perchè non riesco proprio a capire come variano gli indici nella seconda.

Grazie.

[rmba]

Nessuno può darmi una mano?

Grazie.