Principio de inclusión-exclusión

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

${\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

${\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

${\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:

${\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

${\displaystyle A_{I}:=\bigcap _{i\in I}A_{i}}$

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

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

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

${\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:

${\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 A₁, ..., A_n forman una familia con intersecciones regulares, es decir, tales que para cada k de {1, ..., n} la intersección

${\displaystyle A_{I}:=\bigcap _{i\in I}A_{i}}$

Tiene el mismo cardinal, sea a_k = |A_I|, independientemente del k-elemento subconjunto I de {1, ..., n}, entonces

${\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 A₁, ..., A_n de medida finita.

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

${\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 A₁, ..., A_n. Entonces

${\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 A_m, 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 A₁, ..., A_n. Para derivar la versión usada en probabilidad tomarla en (*). En general, integrar la ecuación (*) respecto a μ.

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.

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 ${\displaystyle \scriptstyle {\overline {A}}_{k}}$ representamos el complementario de A_k respecto a un conjunto universal A tal que ${\displaystyle \scriptstyle A_{k}\,\subseteq \,A}$ para todo k. Entonces

${\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.

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

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