Inclusione/esclusione in forma debole
Inviato: 04 lug 2006, 09:20
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.
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.