Principio di inclusione-esclusione

Questa voce o sezione sull'argomento matematica non cita le fonti necessarie o quelle presenti sono insufficienti.

In matematica ed in particolare nella teoria degli insiemi, il principio di inclusione-esclusione è un'identità che mette in relazione la cardinalità di un insieme, espresso come unione di insiemi finiti, con le cardinalità di intersezioni tra questi insiemi.

Denotiamo con ${\displaystyle \left|A\right|}$ la cardinalità di un insieme ${\displaystyle A}$ e consideriamo una famiglia finita di insiemi finiti: ${\displaystyle A_{1},A_{2},\cdots ,A_{n}}$. Per la cardinalità dell'unione di tale famiglia si ha

${\displaystyle \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|=}$

${\displaystyle =\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|}$

Nel caso ${\displaystyle n=2}$ la formula si riduce a quella, molto intuitiva e ricavabile dalle definizioni, esprimibile come

${\displaystyle |A\cup B|=|A|+|B|-|A\cap B|}$

Nel caso ${\displaystyle n=3}$ il principio si esprime con l'uguaglianza

${\displaystyle |A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|}$

Questa si dimostra servendosi più volte della precedente e della distributività della intersezione rispetto alla unione:

${\displaystyle |A\cup B\cup C|=|(A\cup B)\cup C|=|A\cup B|+|C|-|(A\cup B)\cap C|}$

${\displaystyle \,=\,|A|+|B|-|A\cap B|+|C|-|(A\cap C)\cup (B\cap C)|}$

${\displaystyle =|A|+|B|+|C|-|A\cap B|-\left(|A\cap C|+|B\cap C|-|(A\cap C)\cap (B\cap C)|\right)}$

${\displaystyle =|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|}$

Si dovrà dimostrare che ogni elemento dell'insieme ${\displaystyle \bigcup _{i=1}^{n}A_{i}}$ viene contato una e una sola volta. Sia ${\displaystyle x\in A_{1}\cap A_{2}\cap \cdots \cap A_{k}}$ e ${\displaystyle x\notin A_{k+1}\cap \cdots \cap A_{n}}$, riordinando cioè gli insiemi e supponendo che ${\displaystyle x}$ appartenga ai primi ${\displaystyle k}$.

Il termine ${\displaystyle \sum _{i=1}^{n}\left|A_{i}\right|}$ conta ${\displaystyle x}$ esattamente ${\displaystyle {\binom {k}{1}}}$ volte, mentre il secondo termine dello sviluppo della sommatoria, cioè ${\displaystyle \sum _{1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right|}$ conta ${\displaystyle x}$ esattamente ${\displaystyle {\binom {k}{2}}}$ volte, ecc.

Dunque l'elemento ${\displaystyle x}$ nel principio di inclusione-esclusione è contato esattamente

${\displaystyle \sum _{i=1}^{k}(-1)^{i-1}{\binom {k}{i}}}$ volte

Osserviamo che l'indice ${\displaystyle i}$ varia fino a ${\displaystyle k}$ perché considerando ${\displaystyle i=k+1}$, l'intersezione di ${\displaystyle k+1}$ con gli altri ${\displaystyle A_{i}}$ non conterrà ${\displaystyle x}$.

Si può ora dimostrare facilmente, considerando lo sviluppo del Binomio di Newton, che la sommatoria in questione è uguale a ${\displaystyle 1}$:

${\displaystyle 1-\sum _{i=1}^{k}(-1)^{i-1}{\binom {k}{i}}=\sum _{i=0}^{k}(-1)^{i}{\binom {k}{i}}=(1-1)^{k}=0\qquad \Box }$

Abbiamo che

${\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{k=1}^{n}(-1)^{k+1}\sum _{1\leq i_{1}<\cdots <i_{k}\leq n}\left|A_{i_{1}}\cap A_{i_{2}}\cap \cdots \cap A_{i_{k}}\right|}$

Verifichiamola per ${\displaystyle n=2}$, dato che per ${\displaystyle n=1}$ è banalmente ${\displaystyle \left|A_{1}\right|=\left|A_{1}\right|}$, e il caso tornerà poi utile nel proseguimento della dimostrazione:

${\displaystyle \left|A_{1}\cup A_{2}\right|=\left|A_{1}\right|+\left|A_{2}\right|-\left|A_{1}\cap A_{2}\right|}$

Ipotizziamo ora vero il principio per ${\displaystyle n}$ insiemi, e dimostriamo che allora è vero anche per ${\displaystyle n+1}$ insiemi. Vale che

${\displaystyle \bigcup _{i=1}^{n+1}A_{i}=\left(\bigcup _{i=1}^{n}A_{i}\right)\cup A_{n+1}}$

Poiché l'ipotesi è vera per ${\displaystyle n=2}$ vale

${\displaystyle \left|\bigcup _{i=1}^{n+1}A_{i}\right|=\left|\bigcup _{i=1}^{n}A_{i}\right|+\left|A_{n+1}\right|-\left|\left(\bigcup _{i=1}^{n}A_{i}\right)\cap A_{n+1}\right|}$

Ovvero

${\displaystyle \sum _{k=1}^{n}(-1)^{k+1}\sum _{1\leq i_{1}<\cdots <i_{k}\leq n}\left|A_{i_{1}}\cap \cdots \cap A_{i_{k}}\right|+\left|A_{n+1}\right|-\sum _{k=1}^{n}(-1)^{k+1}\sum _{1\leq i_{1}<\cdots <i_{k}\leq n}\left|A_{i_{1}}\cap \cdots \cap A_{i_{k}}\cap A_{n+1}\right|=}$

${\displaystyle =\sum _{k=1}^{n+1}(-1)^{k+1}\sum _{1\leq i_{1}<\cdots <i_{k}\leq n+1}\left|A_{i_{1}}\cap \cdots \cap A_{i_{k}}\right|}$

Tale proposizione è vera in quanto i due termini dell'uguaglianza hanno gli stessi addendi con lo stesso segno. Come volevasi dimostrare.

Il principio è stato utilizzato da Nicolaus II Bernoulli (1695-1726); la formula viene attribuita ad Abraham de Moivre (1667-1754); per il suo utilizzo e per la comprensione della sua portata vengono ricordati Joseph Sylvester (1814-1897) ed Henri Poincaré (1854-1912).

• Formula di inversione di Moebius-Rota
• Disuguaglianze di Boole e di Bonferroni
• Teorema della probabilità totale
• Reticolo booleano

• (EN) principle of inclusion and exclusion, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Principio di inclusione-esclusione, su MathWorld, Wolfram Research.

V · D · M Algebra
Numeri	Naturali · Interi · Razionali · Irrazionali · Algebrici · Trascendenti · Reali · Complessi · Numero ipercomplesso · Numero p-adico · Duali · Complessi iperbolici
Principi fondamentali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza · Relazione d'ordine · Associatività della potenza
Algebra elementare	Equazione · Disequazione · Polinomio · Triangolo di Tartaglia · Teorema binomiale · Teorema del resto · Lemma di Gauss · Teorema delle radici razionali · Regola di Ruffini · Criterio di Eisenstein · Criterio di Cartesio · Disequazione con il valore assoluto · Segno · Metodo di Gauss-Seidel · Polinomio simmetrico · Funzione simmetrica
Elementi di Calcolo combinatorio	Fattoriale · Permutazione · Disposizione · Combinazione · Dismutazione · Principio di inclusione-esclusione
Concetti fondamentali di Teoria dei numeri	Primi Numero primo · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Crivello di Atkin · Test di primalità · Teorema fondamentale dell'aritmetica Divisori Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Criteri di divisibilità · Divisore Aritmetica modulare Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Funzione φ di Eulero · Teorema di Wilson · Reciprocità quadratica
Teoria dei gruppi	Gruppi Gruppo (finito · ciclico · abeliano) · Gruppo primario · Gruppo quoziente · Gruppo nilpotente · Gruppo risolubile · Gruppo simmetrico · Gruppo diedrale · Gruppo semplice · Gruppo sporadico · Gruppo mostro · Gruppo di Klein · Gruppo dei quaternioni · Gruppo generale lineare · Gruppo ortogonale · Gruppo unitario · Gruppo unitario speciale · Gruppo residualmente finito · Gruppo spaziale · Gruppo profinito · Out(Fn) · Parola · Prodotto diretto · Prodotto semidiretto · Prodotto intrecciato Teoremi Alternativa di Tits · Teorema di isomorfismo · Teorema di Lagrange · Teorema di Cauchy · Teoremi di Sylow · Teorema di Cayley · Teorema di struttura dei gruppi abeliani finiti · Lemma della farfalla · Lemma del ping-pong · Classificazione dei gruppi semplici finiti Sottoinsiemi Sottogruppo · Sottogruppo normale · Sottogruppo caratteristico · Sottogruppo di Frattini · Sottogruppo di torsione · Classe laterale · Classe di coniugio · Serie di composizione Omomorfismo · Isomorfismo · Automorfismo interno · Automorfismo esterno · Permutazione · Presentazione di un gruppo · Azione di gruppo
Teoria degli anelli	Anello (artiniano · noetheriano · locale) · Caratteristica · Ideale (primo · massimale) · Dominio (a fattorizzazione unica · a ideali principali · euclideo) · Matrice · Anello semplice · Anello degli endomorfismi · Teorema di Artin-Wedderburn · Modulo · Dominio di Dedekind · Estensione di anelli · Teorema della base di Hilbert · Anello di Gorenstein · Base di Gröbner · Prodotto tensoriale · Primo associato
Teoria dei campi	Campo · Polinomio irriducibile · Polinomio ciclotomico · Teorema fondamentale dell'algebra · Campo finito · Automorfismo · Endomorfismo di Frobenius Estensioni Campo di spezzamento · Estensione di campi · Estensione algebrica · Estensione separabile · Chiusura algebrica · Campo di numeri · Estensione normale · Estensione di Galois · Estensione abeliana · Estensione ciclotomica · Teoria di Kummer Teoria di Galois Gruppo di Galois · Teoria di Galois · Teorema fondamentale della teoria di Galois · Teorema di Abel-Ruffini · Costruzioni con riga e compasso
Altre strutture algebriche	Magma · Semigruppo · Corpo · Spazio vettoriale · Algebra su campo · Algebra di Lie · Algebra differenziale · Algebra di Clifford · Gruppo topologico · Gruppo ordinato · Quasi-anello · Algebra di Boole
argomenti	Teoria delle categorie · Algebra lineare · Algebra commutativa · Algebra omologica · Algebra astratta · Algebra computazionale · Algebra differenziale · Algebra universale

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica