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.

$\#(A\cup B)=\#(A)+\#(B)-\#(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.

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

Para múltiplos conjuntos

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

$\#\left(\bigcup _{i=1}^{n}A_{j}\right)=\sum _{k=1}^{n}(-1)^{k+1}\left(\sum _{1\leqslant i_{1}<\cdots <i_{k}\leqslant n}\#\left(A_{i_{1}}\cap \cdots \cap A_{i_{k}}\right)\right)$