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 A₁, ..., A_n son conjuntos finitos entonces:

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

donde |A| denota el cardinal de A.

Una escritura más rigurosa pero menos legible es:

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

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

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

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

Y 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 puede escribirse más concisamente como:

$\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),$

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

$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 $\mathbb{P}$ por μ.

Caso especial

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

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

Entonces 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 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

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

tiene el mismo cardinal, entonces podemos definir $a_k=|A_I|$ para $|I|=k$ y

$\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ón puede hacerse en el caso de un espacio general de medida (S,Σ,μ) y subconjuntos medibles A₁, ..., A_n de medida finita.

Demostración

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

$1_{\underset{i=1}{\overset{n}{\cup }}{A}_i}=\sum _{k=1}^n(-1{)}^{k-1}\sum _{\genfrac{}{}{0ex}{}{I\subset \{1,\dots ,n\}}{|I|=k}}{1}_{A_I}(*)$

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

$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 μ.

Aplicaciones

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

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 ${\bar{A}}_k$ representamos el complementario de A_k respecto a un conjunto universal A tal que $A_k\subseteq A$ para todo k. Entonces

$\bigcap _{i=1}^n{A}_i=\overline{\bigcup _{i=1}^n{\stackrel{‾}{A}}_i}$

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

Referencias

• Plantilla:Cita libro