Análise Combinatória

Insano! 

1)  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. 

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