O Princípio da Inclusão/Exclusão é a generalização do Princípio Aditivo, para os casos onde 2 ou mais conjuntos tem interseção não-vazia. Abaixo apresentaremos os casos particulares para 2 e 3 conjuntos, e em seguida a formulação geral para N conjuntos.
Sejam A e B dois conjuntos com interseção A∩B não-vazia. Quantos são os elementos do conjunto união A∪B? A princípio a expressão |A∪B| = |A| + |B| pode parecer correta, mas há um problema: quando somamos todos os elementos do conjunto A, somamos também os elementos da interseção A∩B; ao somarmos os elementos de B, os elementos da interseção são novamente somados, de modo que a expressão proposta conta elementos duplicados.
Esta duplicação pode ser removida descontado uma vez cada elemento dobrado. Assim
| A ou B | = | A | + | B | - | A e B |
A expressão acima é o Princípio da Inclusão/Exclusão para dois conjuntos.
Para o caso de 3 conjuntos, devemos atentar as possíveis interseções entre os conjuntos e os efeitos colaterais da soma e subtração de cada uma. Na soma
| A ou B ou C | = | A | + | B | + | C |
as interseções A∩B, A∩C e B∩C são contadas duas vezes, e a interseção A∩B∩C três vezes!. Ao remover as duplicatas, ficamos com
| A ou B ou C | = | A | + | B | + | C | - | A e B | - | A e C | - | B e C |
As duplicatas foram removidas, mas a interseção A∩B∩C foi removida completamente (três vezes), de modo que não está mais sendo contada. A última correção necessária, portanto, é incluir a interseção ausente:
| A ou B ou C | = | A | + | B | + | C | - | A e B | - | A e C | - | B e C |
+ | A e B e C |
Este é o Princípio da Inclusão/Exclusão para três conjuntos.
Seja S{i} o somatório com i variando de 1 a N. Para N conjuntos A1, A2, ..., AN, temos que
| A1 e A2 e ... e AN | = S{i} | Ai | - S{i<j}| Ai e Aj | + S{i<j<k}| Ai e Aj e Ak |
+ ... + (-1)^N | A1 e A2 e ... e AN |
Veja que o número de elementos dos próprios, e de suas interseções em quantidade par, são somados ao total; já as interseções em quantidade ímpar são removidas.
A seguir apresentaremos duas aplicações do Princípio da Inclusão/Exclusão.
Uma permutação de N elementos é dita caótica se nenhum dos N elementos ocupa, na permutação, a mesma posição que ocupava na posicionamento original (isto é, o elemento i não ocupa a i-ésima posição).
Podemos contar o total de permutações caóticas D(N) (D de derangement, em inglês) da seguinte forma: seja Ak o conjunto das permutações nas quais o elemento k ocupa a k-ésima posição. Assim
D(N) = P(N) - S{i} | Ai | + S{i<j}| Ai e Aj | - S{i<j<k}| Ai e Aj e Ak |
+ ... + (-1)^N | A1 e A2 e ... e AN |
onde P(N) é o total de permutações de N elementos. Observe que |Ai| = (N - 1)! (pois o elemento i está fixo), |Ai e Aj| = (N - 2)! (dois elementos fixos), e assim por diante. Logo
D(N) = N! - binom(n, 1)(N - 1)! + binom(n, 2)(N - 2)! - ... + (-1)^N binom(N,N)
o que nos dá
D(N) = N!(1 - 1/1! + 1/2! - 1/3! + ... + (-1)^N/N!)
Na prática, para computar D(N) é melhor utilizar a seguinte recorrência. Para N = 1, não há permutações caóticas entre as 1! possíveis. Para o caso N = 2, há uma permutação caótica entre as 2 possíveis. Assim os casos base são
D(1) = 0
D(2) = 1
Para computar D(N) devemos decidir o que fazer com o primeiro elemento. Temos duas situações possíveis
- Trocar 1 com j, de forma que cada um ocupe a posição do outro;
- Passar um elemento j para a posição 1, mas não escrever 1 na posição do j.
Tanto no primeiro quanto no segundo cenário temos (N - 1) valores possíveis para j. No primeiro caso, após a troca de ambos, restam N - 2 elementos a serem posicionados, o que pode ser feito de D(N - 2) maneiras; no segundo caso, como 1 não pode ocupar a posição j, ficamos na mesma situação de posicionar N - 1 elementos, pois o 1 faz o papel do j, o que pode ser feito de D(N - 1) maneiras. Assim
D(N) = (N - 1)(D(N - 1) + D(N - 2))
Os primeiros valores para esta sequência são 1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932, ...
Uma notação alternativa para D(N) é !n, que faz referência as permutações (que seriam n!).
Sejam A e B dois conjuntos com n e m elementos, respectivamente. Quantas são as funções f: A -> B?
Esta é uma pergunta relativamente fácil de responder: seja F = {funções f: A -> B}. Cada um dos elementos de A devem estar associados a um único elemento de B. Assim temos, para cada um dos n elementos, m escolhas possíveis. Pelo Princípio Multiplicativo temos que
| F | = m^n
A pergunta se torna mais interessante, porém, se adicionarmos algumas restrições. A primeira variante seria: quantas são as funções bijetoras de A em B?
Para que existam funções bijetoras de A em B, é necessário que n = m. Neste caso, seja J = {f: A -> B | f é bijetora}. Agora, cada um elemento de A tem que estar associado a um único elemento de B, e cada elemento de B deve estar associado a um único elemento de A, e todos os elementos de B devem estar associados a algum elemento de A. Assim, o primeiro elemento de A tem n escolhas, o segundo tem (n - 1), o terceiro (n - 2), e assim por diante. Portanto,
| J | = n x (n - 1) x (n - 2) x ... x 2 x 1 = P(n) = n!
A segunda variante da pergunta é: quantas são as funções injetoras de A em B?
Para que existam funções injetoras de A em B, é necessário que n <= m. Neste caso, seja I = {f: A -> B | f é injetora}. Agora, cada um elemento de A tem que estar associado a um único elemento de B, e cada elemento de B deve estar associado a um único elemento de A. Assim, o primeiro elemento de A tem m escolhas, o segundo tem (m - 1), o terceiro (m - 2), e assim por diante. Portanto,
| I | = m x (m - 1) x (m - 2) x ... x (m - n + 1) = A(m, n) = m!/(m - n)!
Por fim, a mais interessante variação da pergunta: quantas são as funções sobrejetoras de A em B?
Precisamos, neste cenários, que n >= m. Seja S = {f: A-> B | f é sobrejetora} e defina Ck = {f: A -> B | f(ai) != bk, para todos elementos ai de A}. Veja que uma função deixa de ser sobrejetora se pertencer a ao menos um dos conjuntos Ck. Pelo Princípio da Inclusão/Exclusão temos que
| S | = | F | - S{i} | Ci | + S{i<j}| Ci e Cj | - S{i<j<k}| Ci e Cj e Ck |
+ ... + (-1)^N | C1 e C2 e ... e CN |
Observe que |Ci| = (m - 1)^n, |Ci e Cj| = (m - 2)^n, e assim por diante, de modo que
| S | = m^n - binom(m, 1) (m - 1)^n + binom(m, 1) (m - 2)^n
+ ... + (-1)^m (binom(m, m) (m - m)^n
o que nos dá
| S | = S{i} (-1)^i binom(m, i) (m - i)^n,
para i variando de 0 a m.
Este valor coincide com o número de maneiras de se distribuir n bolas distintas em m caixas distintas, sem que nenhuma caixa fique vazia.
Deste mesmo resultado pode-se deduzir este outro importante resultado: há T = | S | / m! maneiras de se distribuir n bolas distintas em m caixas iguais, sem que nenhuma caixa fique vazia.
SANTOS, José Plínio O., MELLO, Margarida P., MURARI, Idani T. Introdução à Análise Combinatória, Editora Ciência Moderna, 2007.