Principio de inclusión-exclusión

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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:


\begin{align}
\biggl|\bigcup_{i=1}^n A_i\biggr| & {} =\sum_{i=1}^n\left|A_i\right|
-\sum_{i,j\,:\,1 \le i < j \le n}\left|A_i\cap A_j\right| \\
& {}\qquad +\sum_{i,j,k\,:\,1 \le i < j < k \le 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{align}

donde |A| denota el cardinal de A.

Una escritura más rigurosa pero menos legible es:

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

El principio de inclusión-exclusión en probabilidad[editar]

En probabilidad, para sucesos A1, ..., An en un espacio probabilístico \scriptstyle(\Omega,\mathcal{F},\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{align}\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{align}

Y en general

\begin{align}
\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{align}

Que puede escribirse más concisamente como:

\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:=\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 \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=\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:

\mathbb{P}\biggl(\bigcup_{i=1}^n A_i\biggr)  =\sum_{k=1}^n (-1)^{k-1}\binom nk 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:=\bigcap_{i\in I} A_i

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

\biggl|\bigcup_{i=1}^n A_i\biggr|  =\sum_{k=1}^n (-1)^{k-1}\binom nk 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_{\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})\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 \scriptstyle\overline{A}_k representamos el complementario de Ak respecto a un conjunto universal A tal que \scriptstyle A_k\, \subseteq\, A para todo k. Entonces

 
\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 un suma.

Referencias[editar]

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

Enlaces externos[editar]