Principi d'inclusió-exclusió

En combinatòria, el principi d'inclusió-exclusió (conegut també com a principi del garbell) permet calcular el cardinal de l'unió de varis conjunts, per mig dels cardinals de cada u d'ells i totes els seus possibles interseccions.

Si A₁, ..., A_n són conjunts finitos llavors:

$\begin{array}{cc}\left|\bigcup _{i=1}^n{A}_i\right|& =\sum _{i=1}^n\left|A_i\right|-\sum _{i,j:1\le i<j\le n}|A_i\cap A_j|\\ & +\sum _{i,j,k:1\le i<j<k\le n}|A_i\cap A_j\cap A_k|-\cdots +{(-1)}^{n+1}|A_1\cap \cdots \cap A_n|\end{array}$

a on |A| denota el cardinal de A.

Una escritura més rigorosa pero menys llegible és:

$\left|\bigcup _{i=1}^n{A}_i\right|=\sum _{k=1}^n(-1{)}^{k+1}\begin{array}{c}\\ \\ |\cap A_i|\\ {}_{i\in I\subseteq [1;n]}\\ {}_{\left|I\right|=k}\end{array}$

Inclusió-exclusió per a tres conjunts.

Prenent n=2 tenim un cas de doble conteo, podem trobar el tamany de l'unió de dos conjunts A i B sumant |A| i |B| i restant el tamany de la seua intersecció. El nom prové de l'idea en la que el principi es basa: una molt generosa inclusió seguida d'una compensadora exclusió. Si n>2 l'exclusió de les parelles d'interseccions és (tal volta) massa rigorosa i la fòrmula correcta és com es mostra, en signes alternats.

Esta fòrmula s'atribuïx a Abraham de Moivre encara que a voltes li l'associa en Joseph Sylvester o Henri Poincaré.

El gràfic de la dreta ilustra el cas de tres conjunts A, B i C. Pero no es pot utilisar en certes voltes.

El principi d'inclusió-exclusió en provabilitat

En provabilitat, per a successos A₁, ..., A_n en un espai provabilístic $(\Omega ,ℱ,\mathbb{P})$, el principi d'inclusió-exclusió per a n = 2 pren la forma:

$\mathbb{P}(A_1\cup A_2)=\mathbb{P}(A_1)+\mathbb{P}(A_2)-\mathbb{P}(A_1\cap A_2),$

per a n = 3

$\begin{array}{cc}\mathbb{P}(A_1\cup A_2\cup A_3)& =\mathbb{P}(A_1)+\mathbb{P}(A_2)+\mathbb{P}(A_3)\\ & -\mathbb{P}(A_1\cap A_2)-\mathbb{P}(A_1\cap A_3)-\mathbb{P}(A_2\cap A_3)\\ & +\mathbb{P}(A_1\cap A_2\cap A_3)\end{array}$

I en general

$\begin{array}{cc}\mathbb{P}\left(\bigcup _{i=1}^n{A}_i\right)& =\sum _{i=1}^n\mathbb{P}(A_i)-\sum _{i,j:i<j}\mathbb{P}(A_i\cap A_j)\\ & +\sum _{i,j,k:i<j<k}\mathbb{P}(A_i\cap A_j\cap A_k)-\cdots +(-1{)}^{n-1}\mathbb{P}(\bigcap _{i=1}^n{A}_i),\end{array}$

Que pot escriure's més concisamente com:

$\mathbb{P}\left(\bigcup _{i=1}^n{A}_i\right)=\sum _{k=1}^n(-1{)}^{k-1}\sum _{\genfrac{}{}{0ex}{}{I\subset \{1,\dots ,n\}}{|I|=k}}\mathbb{P}(A_I),$

A on l'última suma recorre els subconjunts I d'índexs 1, ..., n que contenen exactament k elements i

$A_I:=\bigcap _{i\in I}{A}_i$

Denota l'intersecció de tots els A_i en índexs en I.

El principi també es verifica per a un espai general de mida (S,Σ,μ) i subconjunts mesurables A₁, ..., A_n de mida finita sense més que reemplaçar $\mathbb{P}$ per μ.

Cas especial

En la versió provabilística del principi d'inclusió-exclusió, si la provabilitat de l'intersecció A_I solament depén del cardinal de I, és dir, que per a cada k de {1, ..., n} hi ha un a_k tal que

$a_k=\mathbb{P}(A_I)\text{para todo}I\subset \{1,\dots ,n\}\text{tal que}|I|=k,$

Llavors la fòrmula anterior se simplifica:

$\mathbb{P}\left(\bigcup _{i=1}^n{A}_i\right)=\sum _{k=1}^n(-1{)}^{k-1}(\genfrac{}{}{0ex}{}{n}{k})a_k$

De manera similar, si els conjunts finitos A₁, ..., A_n formen una família en interseccions regulars, és dir, tals que per a cada k de {1, ..., n} l'intersecció

$A_I:=\bigcap _{i\in I}{A}_i$

té el mateix cardinal, llavors podem definir $a_k=|A_I|$ per a $|I|=k$ i

$\left|\bigcup _{i=1}^n{A}_i\right|=\sum _{k=1}^n(-1{)}^{k-1}(\genfrac{}{}{0ex}{}{n}{k})a_k.$

Una anàloga simplificació pot fer-se en el cas d'un espai general de mida (S,Σ,μ) i subconjunts mesurables A₁, ..., A_n de mida finita.

Referències

• Matoušek, Jiří; Nešetřil, {{{nom2}}} (2008). Invitació a la matemàtica discreta, Reverte. ISBN 9788429151800.