Principio di inclusione-esclusione

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 la cardinalità di un insieme e consideriamo una famiglia finita di insiemi finiti: . Per la cardinalità dell'unione di tale famiglia si ha

Rappresentazione con un diagramma di Eulero-Venn del caso per tre insiemi

Nel caso la formula si riduce a quella, molto intuitiva e ricavabile dalle definizioni, esprimibile come

Nel caso il principio si esprime con l'uguaglianza

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

DimostrazioniModifica

Dimostrazione IModifica

Si dovrà dimostrare che ogni elemento dell'insieme   viene contato una e una sola volta. Sia   e  , riordinando cioè gli insiemi e supponendo che   appartenga ai primi  .

Il termine   conta   esattamente   volte, mentre il secondo termine dello sviluppo della sommatoria, cioè   conta   esattamente   volte, ecc.

Dunque l'elemento   nel principio di inclusione-esclusione è contato esattamente

  volte

Osserviamo che l'indice   varia fino a   perché considerando  , l'intersezione di   con gli altri   non conterrà  .

Si può ora dimostrare facilmente, considerando lo sviluppo del Binomio di Newton, che la sommatoria in questione è uguale a  :

 

Dimostrazione II (induzione su n)Modifica

Abbiamo che

 

Verifichiamola per  , dato che per   è banalmente  , e il caso tornerà poi utile nel proseguimento della dimostrazione:

 

Ipotizziamo ora vero il principio per   insiemi, e dimostriamo che allora è vero anche per   insiemi. Vale che

 

Poiché l'ipotesi è vera per   vale

 

Ovvero

 

 

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

StoriaModifica

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).

Voci correlateModifica

Collegamenti esterniModifica

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