Inclusione/esclusione in forma debole

[Marco]

Molti dei frequentatori del sito conoscono il Principio di Inclusione/Esclusione: se vogliamo ottenere gli elementi di un'unione finita di insiemi finiti, bisogna sommare i singoli insiemi, sottrarre le intersezioni a due a due, riaggiungere le intersezioni a 3 a 3, e così via, a segni alterni.

Da questo seguono diverse cosette utili, ad esempio una formula della cardinalità di un'unione. Fisso la notazione per chiarezza.

Siano $ n $ un numero naturale positivo e $ A_1, \dots, A_n $ insiemi finiti.

$ U $ la cardinalità dell'unione degli $ A_i $:
$ $ U = \mathrm{card} \bigcup_{1 \leqslant i \leqslant n} A_i $.

Sia $ I_1 $ la somma delle cardinalità degli $ A_i $:
$ $ I_1 = \sum_{1 \leqslant i \leqslant n} \mathrm{card} A_i $

Sia $ I_2 $ la somma delle cardinalità delle intersezioni a due a due:
$ $ I_2 = \sum_{1 \leqslant i<j \leqslant n} \mathrm{card} \left( A_i \cap A_j \right) $

Sia $ I_3 $ la somma delle cardinalità delle intersezioni a tre a tre:
$ $ I_3 = \sum_{1 \leqslant i<j<k \leqslant n} \mathrm{card} \left( A_i \cap A_j \cap A_k \right) $

In generale:
$ $ I_k = \sum_{1 \leqslant i_1<i_2<\cdots<i_k \leqslant n} \mathrm{card} \left( A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_k} \right) $.

E così via fino a $ I_n $ che è la cardinalità dell'intersezione di tutti gli $ A_i $ (che è l'unica intersezione a $ n $ a $ n $ possibile):
$ $ I_n = \sum_{1 \leqslant i_1<i_2<\cdots<i_n \leqslant n} \mathrm{card} \left( A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_n} \right) = \mathrm{card} \bigcap_{1 \leqslant i \leqslant n} A_i $.

Definisco ora con $ S_k $ le somme parziali a segni alterni dei primi $ k $ $ I_j $:
$ $ S_1 = I_1 $,
$ $ S_2 = I_1 - I_2 $,
$ $ S_3 = I_1 - I_2 + I_3 $,
...
$ $ S_k = \sum_{1 \leqslant j \leqslant k} (-1)^{j-1} I_j $.

Finalmente possiamo dare la formula di Inclusione/Esclusione:

$ U = I_1 - I_2 + I_3 - \cdots \pm I_n [ = S_n] $.

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

Domanda preliminare: la sapete dimostrare?

Ma veniamo al punto, dopo tutta questa lunga introduzione: capita ogni tanto di dover dare una stima (una maggiorazione o una minorazione) di un numero calcolato tramite il PIE. Questo di solito è fastidioso, perché la somma è a segni alterni, quindi non si può maggiorare o minorare in modo ovvio (e normalmente tenere solo i pezzi positivi o negativi "butta via" troppo per poter avere stime sharp).

La cosa che forse non tutti sanno, è che se fermiamo la somma ai primi $ k $ termini otteniamo una stima di $ U $ che è dall'alto o dal basso alternativamente con la parità di $ k $, a seconda se l'ultimo addendo considerato è positivo o negativo. La stima migliora sempre più, man mano che aggiungiamo termini, fino a stringersi attorno al valore esatto di $ U $.

Per la precisione vale la seguente:

$ $ S_2 \leqslant S_4 \leqslant \cdots \leqslant S_{2k} \leqslant \cdots \leqslant U [= S_n] \leqslant \cdots \leqslant S_{2k+1} \leqslant \cdots \leqslant S_3 \leqslant S_1 $.

EDIT: No. Così è falso, così come è falsa la frase in rosso. Quel che si può dire (e che è la stima che talvolta serve) è che:

$ $ S_2, S_4, \cdots, S_{2k} \leqslant U [= S_n] \leqslant \cdots, S_{2k+1}, \cdots, S_3, S_1 $.

Vi chiedo di dimostrarla.

M.

[edriv]

Comincio dalla dimostrazione del PIE:

Siano $ A_1,\ldots,A_n $ gli insiemi che consideriamo.
Sia $ x $ un qualsiasi elemento di un qualsiasi insieme.
Siano $ i_1, \ldots,i_k $ gli indici di tutti e soli gli insiemi che contengono x.

Quante volte viene contato x?
In $ I_1 $ viene tante volte quanti sono gli insiemi che contengono x, quindi k.
In $ I_2 $ viene contato tante volte quante sono le coppie di insiemi che contengono x, quindi $ \binom k2 $.
...
In $ I_j $ viene contato tante volte quante sono le j-uple di insiemi che contengono x, quindi $ \binom kj $.
Se j > k, non viene mai contato perche' e' sempre considerata l'intersezione con un insieme che non lo contiene.

Se usiamo la formula del principio di inclusione-esclusione, otteniamo che x viene contato $ \binom k1 - \binom k2 + \ldots \pm \binom kk = \binom k0-\sum_{j=0}^k (-1)^j \binom kj = 1-0=1 $ volte, per la nota formula sulle somme di binomiali.
-------------

Sulla seconda dimostrazione ho qualche problema.
Prendiamo per esempio da dimostrare che $ S_1 \ge S_3 $, ovvero $ I_1 \ge I_1-I_2+I_3 $, vera se e soltanto se:
$ I_2 \ge I_3 $.

Consideriamo la famiglia di insiemi $ A_1,A_2,A_3,A_4,A_5,A_6 $, tutti uguale, che contengono lo stesso elemento.

Evidentemente $ I_2 = \binom 62 \cdot 1, I_3 = \binom 63 \cdot 1 $, ma allora $ I_3 = 20 > 15 = I_2 $.............

edit: aggiunto il "meno uno alla j"

[Marco]

Oh, uhm.... non fa una grinza... chissà che mi ero fumato!?! Effettivamente ho chiesto davvero un po' troppo....

Correggo nel messaggio iniziale.

P.S.: Nella dimo di I/E manca "un meno uno alla j"...