Principio de inclusión-exclusión

En combinatoria, el principio de inclusión-exclusión (conocido también como principio de la criba) permite calcular el cardinal de la unión de varios conjuntos, mediante los cardinales de cada uno de ellos y todas sus posibles intersecciones.

Si A1, ..., An son conjuntos finitos entonces:

| ⋃ i = 1 n A i | = ∑ i = 1 n | A i | − ∑ i , j : 1 ≤ i < j ≤ n | A i ∩ A j | + ∑ i , j , k : 1 ≤ i < j < k ≤ n | A i ∩ A j ∩ A k | − ⋯ + ( − 1 ) n + 1 | A 1 ∩ ⋯ ∩ A n | {\displaystyle {\begin{aligned}{\biggl |}\bigcup _{i=1}^{n}A_{i}{\biggr |}&{}=\sum _{i=1}^{n}\left|A_{i}\right|-\sum _{i,j\,:\,1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right|\\\&{}\qquad +\sum _{i,j,k\,:\,1\leq i<j<k\leq n}\left|A_{i}\cap A_{j}\cap A_{k}\right|-\ \cdots \ +\left(-1\right)^{n+1}\left|A_{1}\cap \cdots \cap A_{n}\right|\end{aligned}}}

donde |A| denota el cardinal de A.

Una escritura más rigurosa pero menos legible es:

| ⋃ i = 1 n A i | = ∑ k = 1 n ( − 1 ) k + 1 | ∩ A i | i ∈ I ⊆ [ 1 ; n ] | I | = k {\displaystyle {\biggl |}\bigcup _{i=1}^{n}A_{i}{\biggr |}=\sum _{k=1}^{n}(-1)^{k+1}{\begin{matrix}{}\\\\{}\\\\\left|\cap A_{i}\right|\\\\{}_{i\in I\subseteq [1;n]}\\\\{}_{\left|I\right|=k}\end{matrix}}}
Inclusión-exclusión para tres conjuntos.

Tomando n=2 tenemos un caso de doble conteo, podemos hallar el tamaño de la unión de dos conjuntos A y B sumando |A| y |B| y restando el tamaño de su intersección. El nombre proviene de la idea en la que el principio se basa: una muy generosa inclusión seguida de una compensadora exclusión. Si n>2 la exclusión de las parejas de intersecciones es (tal vez) demasiado rigurosa y la fórmula correcta es como se muestra, con signos alternados.

Esta fórmula se atribuye a Abraham de Moivre aunque a veces se la asocia con Joseph Sylvester o Henri Poincaré.

El gráfico de la derecha ilustra el caso de tres conjuntos A, B y C. Pero no se puede utilizar en ciertas veces.

## El principio de inclusión-exclusión en probabilidad

[editar]

En probabilidad, para sucesos A1, ..., An en un espacio probabilístico ( Ω , F , P ) {\displaystyle \scriptstyle (\Omega ,{\mathcal {F}},\mathbb {P} )} , el principio de inclusión-exclusión para n = 2 toma la forma:

P ( A 1 ∪ A 2 ) = P ( A 1 ) + P ( A 2 ) − P ( A 1 ∩ A 2 ) , {\displaystyle \mathbb {P} (A_{1}\cup A_{2})=\mathbb {P} (A_{1})+\mathbb {P} (A_{2})-\mathbb {P} (A_{1}\cap A_{2}),}

para n = 3

P ( A 1 ∪ A 2 ∪ A 3 ) = P ( A 1 ) + P ( A 2 ) + P ( A 3 ) − P ( A 1 ∩ A 2 ) − P ( A 1 ∩ A 3 ) − P ( A 2 ∩ A 3 ) + P ( A 1 ∩ A 2 ∩ A 3 ) {\displaystyle {\begin{aligned}\mathbb {P} (A_{1}\cup A_{2}\cup A_{3})&=\mathbb {P} (A_{1})+\mathbb {P} (A_{2})+\mathbb {P} (A_{3})\\\&\qquad -\mathbb {P} (A_{1}\cap A_{2})-\mathbb {P} (A_{1}\cap A_{3})-\mathbb {P} (A_{2}\cap A_{3})\\\&\qquad +\mathbb {P} (A_{1}\cap A_{2}\cap A_{3})\end{aligned}}}

Y en general

P ( ⋃ i = 1 n A i ) = ∑ i = 1 n P ( A i ) − ∑ i , j : i < j P ( A i ∩ A j ) + ∑ i , j , k : i < j < k P ( A i ∩ A j ∩ A k ) − ⋯ + ( − 1 ) n − 1 P ( ⋂ i = 1 n A i ) , {\displaystyle {\begin{aligned}\mathbb {P} {\biggl (}\bigcup _{i=1}^{n}A_{i}{\biggr )}&{}=\sum _{i=1}^{n}\mathbb {P} (A_{i})-\sum _{i,j\,:\,i<j}\mathbb {P} (A_{i}\cap A_{j})\\\&\qquad +\sum _{i,j,k\,:\,i<j<k}\mathbb {P} (A_{i}\cap A_{j}\cap A_{k})-\ \cdots \ +(-1)^{n-1}\,\mathbb {P} {\biggl (}\bigcap _{i=1}^{n}A_{i}{\biggr )},\end{aligned}}}

Que puede escribirse más concisamente como:

P ( ⋃ i = 1 n A i ) = ∑ k = 1 n ( − 1 ) k − 1 ∑ I ⊂ { 1 , … , n } | I | = k P ( A I ) , {\displaystyle \mathbb {P} {\biggl (}\bigcup _{i=1}^{n}A_{i}{\biggr )}=\sum _{k=1}^{n}(-1)^{k-1}\sum _{\scriptstyle I\subset \\{1,\ldots ,n\\} \atop \scriptstyle |I|=k}\mathbb {P} (A_{I}),}

Donde la última suma recorre los subconjuntos I de índices 1, ..., n que contienen exactamente k elementos y

A I := ⋂ i ∈ I A i {\displaystyle A_{I}:=\bigcap _{i\in I}A_{i}}

Denota la intersección de todos los Ai con índices en I.

El principio también se verifica para un espacio general de medida (S,Σ,μ) y subconjuntos medibles A1, ..., An de medida finita sin más que reemplazar  P {\displaystyle \mathbb {P} } por μ.

## Caso especial

[editar]

En la versión probabilística del principio de inclusión-exclusión, si la probabilidad de la intersección AI solo depende del cardinal de I, es decir, que para cada k de {1, ..., n} hay un ak tal que

a k = P ( A I ) para todo I ⊂ { 1 , … , n } tal que | I | = k , {\displaystyle a_{k}=\mathbb {P} (A_{I})\quad {\text{para todo}}\quad I\subset \\{1,\ldots ,n\\}\quad {\text{tal que}}\quad |I|=k,}

Entonces la fórmula anterior se simplifica:

P ( ⋃ i = 1 n A i ) = ∑ k = 1 n ( − 1 ) k − 1 ( n k ) a k {\displaystyle \mathbb {P} {\biggl (}\bigcup _{i=1}^{n}A_{i}{\biggr )}=\sum _{k=1}^{n}(-1)^{k-1}{\binom {n}{k}}a_{k}}

De manera similar, si los conjuntos finitos A1, ..., An forman una familia con intersecciones regulares, es decir, tales que para cada k de {1, ..., n} la intersección

A I := ⋂ i ∈ I A i {\displaystyle A_{I}:=\bigcap _{i\in I}A_{i}}

tiene el mismo cardinal, entonces podemos definir  a k = | A I | {\displaystyle a_{k}=|A_{I}|} para  | I | = k {\displaystyle |I|=k} y

| ⋃ i = 1 n A i | = ∑ k = 1 n ( − 1 ) k − 1 ( n k ) a k . {\displaystyle {\biggl |}\bigcup _{i=1}^{n}A_{i}{\biggr |}=\sum _{k=1}^{n}(-1)^{k-1}{\binom {n}{k}}a_{k}\,.}

Una análoga simplificación puede hacerse en el caso de un espacio general de medida (S,Σ,μ) y subconjuntos medibles A1, ..., An de medida finita.

## Demostración

[editar]

Para demostrar el principio de inclusión-exclusión tendremos, en primer lugar, que verificar la identidad

1 ∪ i = 1 n A i = ∑ k = 1 n ( − 1 ) k − 1 ∑ I ⊂ { 1 , … , n } | I | = k 1 A I ( ∗ ) {\displaystyle 1_{\cup _{i=1}^{n}A_{i}}=\sum _{k=1}^{n}(-1)^{k-1}\sum _{\scriptstyle I\subset \\{1,\ldots ,n\\} \atop \scriptstyle |I|=k}1_{A_{I}}\qquad (*)}

Para funciones indicadoras. Denotemos con A la unión de los conjuntos A1, ..., An. Entonces

0 = ( 1 A − 1 A 1 ) ( 1 A − 1 A 2 ) ⋯ ( 1 A − 1 A n ) , {\displaystyle 0=(1_{A}-1_{A_{1}})(1_{A}-1_{A_{2}})\cdots (1_{A}-1_{A_{n}})\,,}

Ya que ambos miembros se anulan si x no pertenece a A y si x pertenece a alguno de ellos, digamos que Am, entonces el correspondiente mfactor se anularía. Expandiendo el producto de la derecha se obtiene la igualdad pedida.

Uso de (*): Para demostrar el principio de inclusión-exclusión con los cardinales de los conjuntos, sumar la ecuación (*) sobre todo x de la unión de A1, ..., An. Para derivar la versión usada en probabilidad tomarla en (*). En general, integrar la ecuación (*) respecto a μ.

## Aplicaciones

[editar]

Una conocida aplicación del principio de inclusión-exclusión es el problema de contar el número de desarreglos de un conjunto finito. Un desarreglo de un conjunto A es una biyección de A en sí mismo sin puntos fijos. Usando el principio de inclusión-exclusión puede demostrarse que si el cardinal de A es n, entonces el número de desarreglos es [n! / e] donde [x] designa el entero más cercano a x. Puede encontrarse una detallada demostración aquí (en inglés). Esto se conoce también como el subfactorial de n, se escribe !n. Se sigue que si asignamos la misma probabilidad a todas las biyecciones entonces la probabilidad de que una biyección aleatoria sea un desarreglo tiende rápidamente a 1/e a medida que n crece.

## Conteo de intersecciones

[editar]

El principio de inclusión-exclusión puede utilizarse también, combinado con las leyes de Morgan, para contar la intersección de conjuntos. Con  A ¯ k {\displaystyle \scriptstyle {\overline {A}}_{k}} representamos el complementario de Ak respecto a un conjunto universal A tal que  A k ⊆ A {\displaystyle \scriptstyle A_{k}\,\subseteq \,A} para todo k. Entonces

⋂ i = 1 n A i = ⋃ i = 1 n A ¯ i ¯ {\displaystyle \bigcap _{i=1}^{n}A_{i}={\overline {\bigcup _{i=1}^{n}{\overline {A}}_{i}}}}

Cambiando así el problema de calcular una intersección por el de calcular una suma.

## Referencias

[editar]

* Matoušek, Jiří; Nešetřil, Jaroslav (2008). Invitación a la matemática discreta. Reverte. ISBN 9788429151800.

## Enlaces externos

[editar]

* Esta obra contiene una traducción derivada de «Inclusion-exclusion principle» de Wikipedia en inglés, publicada por sus editores bajo la Licencia de documentación libre de GNU y la Licencia Creative Commons Atribución-CompartirIgual 4.0 Internacional.

Control de autoridades|

* Proyectos Wikimedia
* Datos: Q849335
* Diccionarios y enciclopedias
* Britannica: url

|

* Datos: Q849335