Forum Scienze Matematiche

Forum di matematica, fisica, informatica per studenti e appassionati

Passa al contenuto

Il principio di inclusione-esclusione

Domande di teoria, mini-dispense degli utenti, richieste di riferimenti ad articoli, ...

Moderatore: Moderatori

Rispondi al messaggio
( Voti: 0, Media: 0 )

Il principio di inclusione-esclusione

Messaggiodi fry il mer 26 ago 2009, 10:50

Disuguaglianze di Bonferroni. Siano $n, r \in \mathbb{N} := \{1, 2, \ldots\}$ e $A_1, A_2, \ldots, A_n$ alcuni insiemi finiti (fixed), allora

    $\displaystyle \sum_{k=1}^{2r} (-1)^{k+1} \, S(n, k) \leq \, \left| \bigcup_{k=1}^n A_k \right| \leq \sum_{k=1}^{2r - 1} (-1)^{k+1} \, S(n, k)$
dove per ogni $k \in \mathbb{N}$ si ha
    $\displaystyle S(n, k) := \sum_{i_1, i_2, \ldots, i_k}' \left| \bigcap_{j=1}^k A_{i_j} \right|$
e la sommatoria primata intende che $i_1, i_2, \ldots, i_k \in \mathbb{N}$ con $i_1 < i_2 < \ldots < i_k \leq n$.

Clicca qui per rivelare la dimostrazione nascosta.
Prova. Per ogni $\displaystyle a \in \bigcup_{k=1}^n A_k$ esiste un intero $m \in \mathbb{N}$ tale da essere il più grande intero per cui esistono $i_1, i_2, \ldots, i_m \in \overline{1,n}$ distinti a due a due per cui $a \in A_{i_1}, A_{i_2}, \ldots, A_{i_m}$. Dunque per ogni $k \in \mathbb{N}$ il contributo di $a$ alla somma $S(n, k)$ è uguale a $\binom{m}{k}$ e segue che per ogni $r&#39; \in \mathbb{N}$ il contributo di $a$ alla somma
    $\displaystyle \sum_{k=1}^{r&#39;} (-1)^{k+1} \, S(n, k)$
è uguale a

    $\displaystyle \sum_{k=1}^{r&#39;} (-1)^{k+1} \, \binom{m}{k} = \sum_{k=1}^{r&#39;} (-1)^{k+1} \, \left[\binom{m-1}{k-1} + \binom{m-1}{k}\right] = 1 + (-1)^{r&#39;+1} \binom{m-1}{r&#39;}$
cioè $\geq 1$ quando $2 \nmid r&#39;$ e $\leq 1$ quando $2 \mid n$, da cui la tesi.

Principio di inclusione-esclusione. Sia $n \in \mathbb{N}$ e siano $A_1, A_2, \ldots, A_n$ alcuni insiemi finiti (fixed), allora con la notazione precedente

    $\displaystyle \left| \bigcup_{k=1}^n A_k \right| = \sum_{k=1}^n (-1)^{k+1} \, S(n, k)$
Clicca qui per rivelare la dimostrazione nascosta.
Prova. E' sufficiente considerare che $S(n,k) = 0$ per ogni $k > n$, quindi se $2r - 1 \geq n$ le due somme delle disuguaglianze di Bonferroni sono uguali.
"Hey. They laughed at Louis Armstrong when he said he was gonna go to the moon. Now he's up there, laughing at them."
Avatar utente
fry
 
Messaggi: 508
Iscritto il: ven 20 giu 2008, 20:06
Gruppo: Moderatori
Top
  • 0

Messaggiodi Ani-sama il lun 31 ago 2009, 17:44

Immagino che si tratti di insiemi finiti. :P Per inciso, resta tutto vero (e dimostrazioni pressoché identiche) se al posto delle cardinalità si mettono misure qualsiasi, purché venga fatta l'ipotesi che gli insiemi in gioco siano misurabili e con misura finita.
Avatar utente
Ani-sama
 
Messaggi: 378
Iscritto il: mar 24 giu 2008, 18:03
Località: Pavia
Gruppo: Utenti registrati
Top
Rispondi al messaggio

Torna a Teoria

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Traduzione Italiana phpBB.it