Principio de inclusión-exclusión

Si A1, ..., An son conjuntos finitos entonces: donde |A| denota el cardinal de A.

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

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

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.

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.