Principio de inclusión-exclusión

Principio de inclusión-exclusión

Principio de inclusión-exclusión

En Matemáticas combinatorias, el principio de inclusión-exclusión (conocido también como principio de la criba) establece que 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. 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é.

Inclusión-exclusión para tres conjuntos

Para el caso de tres conjuntos A, B, C el principio se ilustra en el gráfico de la derecha

Contenido

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

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

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

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

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 si 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 [[1]]. 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 \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.

Obtenido de "Principio de inclusi%C3%B3n-exclusi%C3%B3n"

Wikimedia foundation. 2010.

Игры ⚽ Поможем написать курсовую

Mira otros diccionarios:

  • Inclusión (pedagogía) — La inclusión es un concepto teórico de la pedagogía que hace referencia al modo en que la escuela debe dar respuesta a la diversidad. Es un término que surge en los años 90 y pretende sustituir al de integración, hasta ese momento el dominante en …   Wikipedia Español

  • Criba de Brun — En matemáticas, el método de cribado de Brun, el teorema de Brun o criba de Brun es un resultado en la teoría de números más específicamente en teoría de cribas dado por Viggo Brun en 1919. Tiene importancia histórica en la introducción de los… …   Wikipedia Español

  • Unión de conjuntos — La unión de los conjuntos A y B es otro conjunto A ∪ B que contiene todos los elementos de A y de B. En la teoría de conjuntos, la unión de dos (o más) conjuntos es una operación que resulta en otro conjunto cuyos elementos son los elementos de… …   Wikipedia Español

  • Desigualdad de Boole — Saltar a navegación, búsqueda En teoría de la probabilidad, la desigualdad de Boole estipula que para toda familia finita o numerable de sucesos, la probabilidad de que al menos uno de esos sucesos ocurra es menor o igual a la suma de las… …   Wikipedia Español

  • Subfactorial — n !n 0 1 1 0 2 1 3 2 4 9 5 44 6 265 7 …   Wikipedia Español

  • Función indicatriz — Gráfico de una función indicatríz que muestra a un subconjunto de los puntos de un cuadrado (en rojo), donde los puntos tienen coordenada z=1 (color ocre), mientras que los puntos del cuadrado …   Wikipedia Español

  • Café (todos) — Wikipedia:Café (todos) Saltar a navegación, búsqueda Atajos WP:C …   Wikipedia Español

  • Manuel Castells — en 2009. Manuel Castells Oliván (Hellín, Albacete, España, 1942) es un sociólogo y profesor universitario, catedrático de Sociología y de Urbanismo en la Universidad de California en Berkeley, así como director del Internet Interdisciplinary… …   Wikipedia Español

  • Genética Forense — Este artículo o sección sobre ciencia necesita ser wikificado con un formato acorde a las convenciones de estilo. Por favor, edítalo para que las cumpla. Mientras tanto, no elimines este aviso puesto el 24 de mayo de 2010. También puedes ayudar… …   Wikipedia Español

  • Gobernanza financiera — Se entiende por gobernanza financiera el conjunto de procesos, reglas, normas, valores e instituciones a través de los cuales los diferentes actores (organismos públicos locales, estatales e internacionales , así como empresas, movimientos… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”