Princípio da inclusão-exclusão

O Princípio da Inclusão-Exclusão (PIE) é uma generalização de um dos princípios básicos de contagem, o princípio aditivo. Este princípio está interessado na obtenção de uma fórmula para contar o número de elementos que pertencem a união de vários conjuntos não necessariamente excludentes ou disjuntos.

O princípio funciona basicamente somando-se e subtraindo-se correções à uma estimativa até que se chegue no valor desejado.

Na sua forma mais simples calcula a cardinalidade da união de dois conjuntos A e B, no qual a intersecção entre A e B dá-se um conjunto vazio.

Para dois conjuntos

Ao somar as cardinalidades de $A$ e $B$ temos um número maior que a cardinalidade da união, já que estamos somando a intersecção duas vezes, sendo assim necessário subtrai-la para termos o resultado correto.

$\mathrm{\#}(A\cup B)=\mathrm{\#}(A)+\mathrm{\#}(B)-\mathrm{\#}(A\cap B)$

Para três conjuntos

Quando temos três conjuntos a cardinalidade da união deles não é expressa pela soma das cardinalidades dos três, já que isso incluiria suas intersecções duplas duas vezes, entretanto, subtrair a cardinalidades das intersecções duplas não é o bastante pois isso a intersecção dos três conjuntos, sendo então necessário somá-lo ao final.

$\mathrm{\#}(A\cup B\cup C)=\mathrm{\#}(A)+\mathrm{\#}(B)+\mathrm{\#}(C)-\mathrm{\#}(A\cap B)-\mathrm{\#}(B\cap C)-\mathrm{\#}(C\cap A)+\mathrm{\#}(A\cap B\cap C)$

Para múltiplos conjuntos

Esse resultado por ser generalizado para a união de n conjuntos:

$\mathrm{\#}\left(\bigcup _{i=1}^n{A}_j\right)=\sum _{k=1}^n(-1{)}^{k+1}\left(\sum _{1⩽i_1<\cdots <i_k⩽n}\mathrm{\#}(A_{i_1}\cap \cdots \cap A_{i_k})\right)$