O leitor neste texto verá uma continuação da ideia de permutação agora para quando houver objetos iguais entre os que ele vai permutar, chamamos isso de permutação com repetição. Este texto pode ser visto em particular como uma continuação natural do texto sobre permutação aqui do blog, como também mais um texto na série sobre análise combinatória.
Pequena revisão
Antes de irmos aos casos com repetição vamos relembrar rapidamente o que é uma permutação.
Uma permutação é como chamamos problemas que são equivalentes a contar a quantidade de maneiras distintas de enfileirar n objetos distintos.
Dessa forma transformamos vários problemas como se fosse apenas um problema que pode ser facilmente resolvido. Podemos enfileirar n objetos distintos de n! maneiras.
Caso o leitor não esteja familiarizado com a ideia de fatorial confira o seguinte texto:
Fatorial (!) : Aprenda tudo sobre.
Para o leitor saber mais sobre permutações simples confira o seguinte texto:
Permutação: Análise Combinatória
Permutação com repetição
Vamos pensar nos casos com repetição inicialmente através do seguinte problema sobre anagramas. Caso o leitor não saiba, um anagrama é uma sequência de letras. Por exemplo, um anagrama da palavra SOLA é OLAS.
Exemplo 1. Quantos anagramas possui a palavra LAMAS?
A palavra LAMAS possui letras “A” repetidas, mas inicialmente vamos pensar como se as letras “A” fossem diferentes. Assim esse problema pode ser visto como uma permutação simples e como a palavra possui 5 letras então possui 5! maneiras de fazer isso.
Entretanto, quaisquer dois anagramas que apenas mudem as posições dos “A” são na verdade o mesmo anagrama, logo contamos os casos duas vezes. Isto significa que a resposta verdadeira é 5!/2 = 120/2 = 60.
Exemplo 2. Quantos anagramas possui a palavra CARAVANA?
Vamos ter um pensamento análogo ao anterior para resolver esse exemplo.
A palavra CARAVANA possui 8 letras das quais 4 são letras “A”, vamos considerar inicialmente como se as 4 letras “A” forem distintas, e assim é possível ter 8! anagramas.
Perceba que qualquer mudança de posições apenas das letras “A” não alteram o anagrama, e podemos permutá-las de 4! maneiras, isto significa que cada caso está sendo contado 4! vezes.
Portanto o número real de anagramas é 8!/4!.
Exemplo 3. Quantos anagramas possui a palavra BANANA?
Primeiro, a palavra BANANA possui 6 letras das quais duas se repetem, o A é repetido 3 vezes e o N duas vezes.
Analogamente aos casos anteriores, inicialmente possuímos 6! maneiras de formar anagramas, mas cada permutação de “A” não altera um anagrama, e, ao mesmo tempo, cada permutação de N também não altera um anagrama.
Como podemos permutar os “A” de 3! e os N de 2! então pelo princípio multiplicativo estamos contando cada caso 3!2! vezes. Portanto o número real de anagramas é: 6!/(3!2!).
Caso geral de permutação com repetição
As ideias presentes no exemplo nos ajudarão a resolver todos os casos de permutações com repetições.
Sejam n objetos dos quais k₁ deles são iguais entre si, e outros k₂ deles também são iguais entre si, e assim por diante até os kₓ deles são iguais entre si. Podemos ordenar esses objetos de uma fileira de n!(k₁!k₂!…kₓ!)
Problema.
Agora é sua vez, resolva o seguinte problema aplicando a ideia que acaba de ser ensinada:
Problema. Quantas diagonais têm um polígono convexo de n lados?
Resposta. n(n-3)/2
