Resolução:
Para resolvermos esta questão temos que usar o conceito de inclusão e exclusão de conjuntos. Basicamente, este conceito diz o seguinte:
“Dados dois conjuntos A e B, para sabermos o número de elementos de A união B, temos que fazer:
n(A U B) = n(A) + n(B) – n(A ^ B)”
onde n(A) é o número de elementos de A,
n(A U B) é o número de elementos de A uniáo com B,
n(A ^ B) é o número de elementos de A intersecção B.
Se o número de conjuntos for 3, teremos:
n(A U B U C) = n(A) + n(B) + n(C) – n(A ^ B) – n(A ^ C) – n(B ^ C) + n(A ^ B ^ C)
E se forem “n” conjuntos, da mesma forma, pegamos a soma de todos os conjuntos, tiramos a intersecção dos conjuntos 2 a 2, somamos a intersecção dos conjuntos 3 a 3, tiramos a intersecção dos conjuntos 4 a 4, somamos a intersecção dos conjuntos 5 a 5, e assim sucessivamente, sempre somando uma intersecção e subtraindo a seguinte, até a intersecção de todos os conjuntos.
No caso do problema proposto, temos que encontrar o número de maneiras de ordenar as letras a, a, b, b, b, c, c, d, d de modo que duas letras iguais nunca fiquem juntas.
Para fazermos isso, temos que calcular o total de permutações dessas 9 letras e tirar as permutações onde aparecem letras iguais lado a lado. Aí vamos ter que usar o princípio da inclusão e exclusão. Calcularemos o total de permutações onde aparece uma das letras sempre junto com seu par ou trio (no caso do b), depois o número de permutações onde aparecem 2 das letras sempre juntas com seus pares, depois 3 letras sempre juntas e depois todas as letras sempre juntas. E faremos:
Resposta = n(total) – n(aa) – n(bb) – n(cc) – n(dd) + n(aabb) + n(aacc) + n(aadd) + n(bbcc) + n(bbdd) + n(ccdd) – n(aabbcc) – n(aabbdd) – n(aaccdd) – n(bbccdd) + n(aabbccdd)
Repare que eu não escrevi nunca os três b´s juntos, porque bastam dois juntos para não entrar no conjunto que queremos. Só que quando calcularmos, por exemplo, o número de permutações que têm dois b juntos, estaremos contando 2 vezes as permutações que têm 3 b juntos, porque contamos quando os dois b estão antes do b sozinho e quando os dois b estão depois do b sozinho. E na verdade estas duas permutações têm os 3 b juntos. Então, sempre que calcularmos as permutações que contém pelo menos dois b juntos, calcularemos quantas tem 2 b juntos e tiraremos uma vez as permutações que têm os 3 b juntos. Este é o detalhe do problema. Vamos às contas:
Total de permutações: 9 letras, sendo 2a, 3b, 2c e 2d
n(total) = 9!/(2!.3!.2!.2!) = 7560
Permutações onde uma das letras aparece lado a lado com outra letra igual (quando uma letra está junto com outra, consideramos como se fosse uma letra só mudando de lugar):
n(aa) = 8!/(3!.2!.2!) = 1680
n(bb) – n(bbb) = 8!/(2!.2!.2!) – 7!/(2!.2!.2!) = 4410
n(cc) = 8!/(3!.2!.2!) = 1680
n(dd) = 8!/(3!.2!.2!) = 1680
Permutações onde duas das letras estão juntas com o par:
n(aabb) – n(aabbb) = 7!/(2!.2!) – 6!/(2!.2!) = 1080
n(aacc) = 7!/(3!.2!) = 420
n(aadd) = 7!/(3!.2!) = 420
n(bbcc) – n(bbbcc) = 7!/(2!.2!) – 6!/(2!.2!) = 1080
n(bbdd) – n(bbbdd) = 7!/(2!.2!) – 6!/(2!.2!) = 1080
n(ccdd) = 7!/(3!.2!) = 420
Permutações onde três das letras estão juntas com o par:
n(aabbcc) – n(aabbbcc) = 6!/2! – 5!/2! = 300
n(aabbdd) – n(aabbbdd) = 6!/2! – 5!/2! = 300
n(aaccdd) = 6!/3! = 120
n(bbccdd) – n(bbbccdd) = 6!/2! – 5!/2! = 300
Permutações onde todas as letras estão juntas com o par:
n(aabbccdd) – n(aabbbccdd) = 5! – 4! = 96
E fazendo as contas:
Resposta = 7560 – 1680 – 4410 – 1680 – 1680 + 1080 + 420 + 420 + 1080 + 1080 + 420 – 300 – 300 – 120 – 300 + 96
Resposta = 1686