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:
donde |A| denota el cardinal de A.
Una escritura más rigurosa pero menos legible es:
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.
En probabilidad, para sucesos A1, ..., An en un espacio probabilístico , el principio de inclusión-exclusión para n = 2 toma la forma:
para n = 3
Y en general
Que puede escribirse más concisamente como:
Donde la última suma recorre los subconjuntos I de índices 1, ..., n que contienen exactamente k elementos y
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 por μ.
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
Entonces la fórmula anterior se simplifica:
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
Tiene el mismo cardinal, sea ak = |AI|, independientemente del k-elemento subconjunto I de {1, ..., n}, entonces
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.
Para demostrar el principio de inclusión-exclusión tendremos, en primer lugar, que verificar la identidad
Para funciones indicadoras. Denotemos con A la unión de los conjuntos A1, ..., An. Entonces
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 μ.
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 representamos el complementario de Ak respecto a un conjunto universal A tal que para todo k. Entonces
Cambiando así el problema de calcular una intersección por el de calcular una suma.