As permutações

Conceito de permutação:
Em análise combinatória, permutação é o ato de ''trocar'', ''reorganizar'', ''mudar'', reagrupar'' diversos elementos pertencentes à um conjunto.
Com as permutações, é possível descobrirmos de quantas maneiras determinados elementos de um conjunto possam ser reagrupados.
Por exemplo, temos três animais (todos eles pertencem ao mesmo grupo), esses animais são: um cachorro, um gato e um rato. Inicialmente, eles estão enfileirados da seguinte maneira:

Ou seja, temos o cachorro na primeira fileira, o gato na segunda e o rato na terceira. Mas, se eu quiser, eu posso reagrupá-los assim:

Agora eu tenho na primeira fileira o gato, na segunda o rato e na terceira o cachorro. Mas eu posso reagrupar esses três animais de diversas formas:

Eu posso reagrupar os três animais, tendo o cachorro na primeira fileira:

Cachorro, Gato, Rato ou

Cachorro, Rato, Gato

Ou tendo o gato na primeira fileira:

Gato, Cachorro, Rato ou

Gato, Rato, Cachorro

E por fim, tendo o rato na primeira fileira:

Rato, Cachorro, Gato ou

Rato, Gato, Cachorro

Essas são todas as possíveis maneiras de reagrupar esses três animais numa fila.

Note que ao todo, eu posso obter 6 tipos de arrumações diferentes, ou 6 permutações:

Porém, existe um modo mais fácil para obtermos esse resultado, sem necessariamente ter que reagrupar todos os elementos do conjunto:

Pense comigo, se temos três animais para serem organizado em três posições na fila, então podemos ter algo como isto:

Temos então inicialmente três opções de posições disponíveis, para três elementos.

Se qualquer um dos três animais, o cachorro por exemplo, assumir a primeira posição, os outros dois animais (O gato e o rato) vão ter apenas mais duas posições para serem colocados, pois na primeira posição já está o cachorro:

Então agora teremos duas opções para dois elementos. O gato pode tanto ficar na posição 2 quanto na posição 3, assim como o rato.

Mas e se o gato assumir a posição 2 o que acontece? Daí teremos apenas uma posição para o rato assumir, pois as duas anteriores já estão ocupadas:

Por fim, o que ocorreu? Primeiro tinham-se três opções disponíveis de posições numa fila, depois que um elemento tomou uma das posições, restaram apenas 2 opções, e logo em seguida que outro elemento tomou outra posição, só restou uma opção para o terceiro elemento.

Observando o desenrolar da estória, percebemos que tínhamos 3.2.1 maneiras desses animais se arrumarem nessa fila, pois primeiro tinham-se 3 opções, depois 2 e por fim 1.

3.2.1 = 6 

Onde novamente chegamos ao resultado de 6 maneiras desses três animais ficarem enfileirados. 

3.2.1 = 6 Isso não te faz lembrar de algo? Algo como a aula passada, sobre fatoriais?

O fatorial de 3 pode ser escrito da seguinte forma: 3! = 3.2.1 e isso não dará 6? Pois então! Podemos então dizer de um modo geral que, a permutação de um grupo de elementos se dá por: P=n! onde ''n'' fatorial é a quantidade de elementos que temos para permutarmos. Nesse caso aqui temos três animais, então podemos dizer que: P = 3!

Na aula passada você já havia visto um exemplo de permutação, onde pediu-se para que calculássemos os possíveis anagramas da palavra "Pensar'', lembra?

Se permutar significa reagrupar, então podemos dizer que um anagrama é uma permutação de letras, onde pode-se reagrupa-las de diversas maneiras até que se forme outras palavras, com sentido ou não.

O mesmo ocorre com números! Por exemplo, de quantas maneiras podemos reorganizar os números com os seguintes algarismos: 1,2,3,4,5?

Podemos pegar esses algarismos e formar algo como:

54321 ou 45231

Enfim, esses são apenas dois exemplos, é óbvio que existam muito mais! 

Para sabermos realmente de quantas maneiras esses números podem ser reorganizados, basta utilizar as permutações, onde P = n!

No caso aqui 'n' é cinco, pois temos cinco elementos distintos, ou seja, cinco números a serem reagrupados, logo:

P = 5!

5! = 5.4.3.2.1 = 120

P= 120

Então, temos 120 formas de reagrupar esses números, com esses cinco algarismos.

Permutação simples:
As permutações simples são aquelas permutações em que apenas devemos obter o número de reagrupamentos num determinado grupo de elementos, assim como visto nos exemplos acima.
Mas não se engane... Em permutação pode-se exigir outros fatores, onde esses fatores devem suprir a condição imposta pelo problema, por isso preste bastante atenção nos enunciados de análise combinatória! Na verdade, nessa área cada caso varia, então é de suma importância o entendimento do que o problema pede.
Exemplos?

Temos seis pessoas organizadas numa fila. Sabendo disso responda:

A) De quantas formas essas pessoas podem se reorganizar na fila?
B) Dessas seis pessoas, uma chama-se Bruna e a outra chama-se Jorge, de quantas maneiras podemos organizar essa fila, fazendo com que Jorge e Bruna fiquem juntos?
C) E de quantas formas Jorge e Bruna ficarão separados na fila?

Então vamos partir do princípio onde queremos saber de quantas formas TODAS as seis pessoas podem ser organizadas na fila:
Então se temos 6 elementos (pessoas) teremos P = 6!, onde 6! equivale à 720.
Logo, essas seis pessoas poderão ser reagrupadas de 720 maneiras, nessa fila.

Mas agora o problema pede para que calculemos as vezes em que Jorge e Bruna (duas pessoas dentre as seis) apareçam juntas na fila.
Então vamos ''visualizar'' essa situação, vamos ver todas as possibilidades dessas duas pessoas ficarem uma ao lado da outra na fila de seis pessoas:

Aqui está a fila com seis pessoas, onde vamos representar Jorge pela cor azul e Bruna pela cor rosa.

No primeiro caso Jorge e Bruna podem ficar juntos ocupando as duas primeiras posições.

No segundo caso, Jorge e Bruna ficarão juntos na segunda e terceira posições.

No terceiro caso, Jorge e Bruna podem ficar juntos se ocuparem a terceira e quarta posições, respectivamente.

Agora o Jorge e a Bruna poderão ficar juntos se ocuparem a quarta e quinta posições.

Por fim, eles podem ficar juntos na quinta e sexta posições.

Então temos ao todo 5 formas de Jorge e Bruna ficarem juntos nessa fila.

Mas você concorda comigo que eles ficaram juntos nessa fila, apenas com o Jorge na frente? Eles também podem ficar juntos quando Bruna está na frente:

Ou seja, mais 5 formas, logo, somando todas as formas de Jorge e Bruna ficarem junto na fila, teremos: 5+5 = 10

Mas não se esqueça que ainda temos outras quatro pessoas dessas seis, então, enquanto Jorge e Bruna ficam sempre lado à lado, as outras quatro pessoas trocam de lugares sempre, ou seja, vamos permutar as outras pessoas: P= 4! = 24

Agora vamos unir tudo e descobrir de quantas formas podemos reorganizar essa fila com seis pessoas, sendo que duas delas fiquem sempre lado à lado:

24. 10 = 240

Ou seja, Bruna e Jorge podem ficar juntos nessa fila de 240 formas.

O terceiro problema nos pede para que calculemos de quantas maneiras Bruna e Jorge ficarão separados na fila.

Mas agora não tem problema! Se eles ficarão juntos de 240 formas na fila, separados eles ficarão a quantidade total de permutação de todos da fila, menos a quantidade de vezes em que aparecem juntos, ou seja:

720 - 240 = 480.

Conclusão: Bruna e Jorge ficarão separados de 480 formas nessa fila.

Outros exemplos?

Tome como foco a palavra "ANÉIS" e responda:

A) Quantos anagramas podemos formar com a palavra "ANÉIS''?

B) Quantos desses anagramas começam com vogais?

C) E quantos terminam com consoantes?

D) Quantos anagramas podemos formar, sendo que ''A'' e ''N'' devem ficar seperados?

Para resolver o item A), basta permutarmos as cinco letras da palavra ''anéis'':

P5 = 5! = 120.

Então, podemos formar 120 anagramas com essa palavra.

Preste agora atenção no item B). Eles nos pede para que calculemos quantos são os anagramas em que se iniciem com vogais.

Vamos visualizar melhor isso:

Aí esta nossa fileira que poderá reagrupar essa palavra com cinco letras.

Tendo em mente que a primeira posição será ocupada por alguma vogal (independente de qual delas será), sabemos então que essa posição vai estar ocupada:

Então o que nos resta é permutarmos as letras nas outras quatro opções restantes: P4 = 4! = 24

Pois bem, se temos três vogais "A", ''É'' e ''I'', basta multiplicar a quantidade de vogais, pela permutação dos lugares disponíveis: 24*3 = 72

Conclusão: Desses 120 anagramas, 72 se iniciarão em vogais.

O item C) nos pede para que calculemos os anagramas que possam terminar em consoantes. Sabendo que a última posição irá ser ocupada por alguma consoante, teremos novamente quatro posições a serem permutadas:

Agora temos duas consoantes na palavra "ANÉIS'': ''N'' e ''S'', então seguindo o raciocínio do exercício anterior, vamos multiplicar as permutações dos lugares restantes (24) pelo número de consoantes (2):

24*2 = 48

Então, desses 120 anagramas, 48 deles irão terminar com uma consoante.

Para o item D), podemos seguir a mesma lógica da resolução do problema da Bruna e do Jorge, se queremos saber quantos anagramas podemos formar, sendo que ''A'' e ''N'' fiquem sempre separados.

Primeiramente, vamos analisar em quantas posições teremos a sequência ''AN'':

Pois bem, a ordem "AN'' pode estar em quatro posições dessa fila.

Levando em conta a ordem "NA", onde esses dois elementos também ficariam juntos, teremos obviamente mais quatro possibilidades dessas letras aparecem juntas na fila. Ou seja, somando tudo teremos 4+4= 8

Temos também mais três letras distintas a serem permutadas entre si, ou seja: P3 = 3! = 6

Agora, basta multiplicar a quantidade de vezes que ''A''  e ''N'' ficariam lado à lado, pela permutação das outras letras restantes: 8*6 = 48

Ou seja, desses 120 anagramas, em 48 deles, as letras ''A'' e ''N'' ficarão juntas.

Mas queremos saber na verdade, em quantos anagramas essas letras ficarão separadas! Para isso, basta subtrair o total de permutações com todas as letras, com o total de vezes que essas letras ficariam juntas:

120 - 48 = 72

Por fim, desses 120 anagramas, 72 contém as letras "A" e "N" separadas.

Permutação Circular:

Outro tipo de permutação muito conhecido são as permutações circulares, onde um determinado grupo de elementos estão formando uma circunferência.

Se por exemplo, temos quatro crianças: Jairo (J), Marcos (M), Ana (A) e Lara (L), em fila elas poderíamos permutar de 24 formas, pois P = 4! = 24.

Mas, se essas crianças estivessem brincando de ciranda e formassem uma roda, elas estariam dispostas da seguinte maneira:

Perceba que para JMAL, Lara sempre vai estar ao lado de Ana e Jairo, assim como Jairo estará sempre ao lado de Marcos e Lara, e assim por diante... (A não ser que troquem de lugar, o que não é o caso)

Disto isso, podemos notar que sempre formaremos quatro rodas iguais, para quatro elementos:

A roda: JMAL é igual às rodas: JLAM e  JMLA

E isso acontece porque os elementos estão formando uma circunferência, onde numa circunferência não temos uma ordem inicial nem uma ordem final.

Para calcularmos esses reagrupamentos possíveis dessas crianças nessa roda, basta dividir o fatorial de pessoas envolvidas na roda, pela quantidade de rodas possíveis a serem formadas:

Desenvolvendo, teremos:

Então, essas crianças poderiam ser reagrupar de seis maneiras diferentes nessa roda.

Há também uma expressão geral para permutações circulares que diz:

Ou seja, se temos uma roda de n elementos, as permutações circulares possíveis será de (n-1)!, ou seja o fatorial do seu antecessor.

Quer ver?

No exemplo ainda dessas crianças, se temos 4 elementos numa roda, então:

Se essa operação nos resultará em seis, isso quer dizer que é o fatorial do nosso antecessor.

O antecessor de 4 é 3, e o fatorial de 3 é justamente 6-> 3! = 3.2.1

Sabendo disso, fica muito mais fácil calcularmos permutações circulares.

Permutações com repetições:
Em problemas de permutação simples, normalmente pergunta-se de quantas maneiras tais elementos de um grupo podem ser reagrupados, apenas isso. Os problemas de permutações simples não exigem que você obtenha o número de permutações distintas do grupo X, e sim apenas que você obtenha o total de permutações desse grupo, incluindo as possíveis repetições.
Já num problema de permutação com repetições, os problemas, na maioria das vezes, exigem que você informe as permutações distintas daquele grupo de elementos, ou seja, as permutações possíveis, só que eliminando as possibilidades de repetições.

Como assim? Veja a diferença entre um problema de permutação simples, e outro problema sobre permutações distintas:

Permutação simples: 

Numa biblioteca, há cinco livros de matemática, todos contendo conteúdos diferenciados. De quantas maneiras esses livros poderão ser organizados na prateleira?

Aqui a questão é simples, basta permutarmos todos esses livros, que por sua vez possuem todos conteúdos diferenciados, e então obteremos o resultado das formas possíveis que podemos reagrupar esses cinco livros:

P5 = 5! = 5.4.3.2.1 = 120

Logo, esses cinco livros poderão ser organizados numa prateleira, de 120 maneiras possíveis.

Permutação com repetição:

Mas, e se dois desses cinco livros tivessem conteúdos idênticos? Fossem iguais? As formas de se organizar esses livros seriam as mesmas, cento e vinte! Mas e se fosse exigido saber apenas a quantidade de maneiras que esses livros possam ser reagrupados, mas sem levar em consideração as ordens que podem se repetir? Como faríamos?

Não conseguiu identificar o problema? Veja bem:

Se desses cinco livros, dois deles forem iguais, então teremos algumas arrumações que iriam se repetir, preste atenção:

Vamos chamar os três livros distintos de livros A, B e C. Os livros com conteúdo repetidos se chamarão livros D.

Dito isso, poderíamos ter as seguintes permutações:

ABCDD ou ABCDD

Por que essa permutação aparece duas vezes? Simples, na primeira vez o primeiro"D" era o livro repetido número 1 e assumia uma posição à frente do outro livro repetido "D".

Na segunda permutação o segundo livro repetido "D" que ficou à frente do livro "D" número 1.

Confundiu? Ok, vamos denominar o primeiro livro repetido de ''D1'' e o segundo livro repetido de ''D2'' (mas considere que ambos são iguais, apesar da diferenciação de nome), logo teríamos:

Viu? A permutação se repete, e isso porque temos algum elemento repetido em meio aos outros elementos.

Quando fizemos P5 = 120, levamos em consideração TODAS as permutações entre esses cinco livros, incluindo as permutações repetidas.

Mas novamente lhe pergunto... E se fosse exigido que apenas fosse levado em conta, o número de permutações sem essas repetições?

Para permutar elementos repetidos, basta fazer uma divisão entre a permutação total de elementos, pela permutação da quantidade de repetições.

Se a permutação total de todos esses livros, levando em conta as repetições, é igual à 5!, e a quantidade de repetições que temos é 2 (Dois livros iguais) então temos:

Desenvolvendo o numerador:

5! = 5.4.3.2.1 = 120

Desenvolvendo o denominador:

2! = 2.1 = 2

Logo teremos:

Portanto, as possibilidades desses cinco livros (sendo que dois deles tem o mesmo conteúdo), serem reagrupados numa prateleira, sem possíveis repetições, é de 60 formas diferentes.

Outros exemplos?

Quantos anagramas (sem repetições) podemos formar com a palavra "PASSEIO''?

Para descobrirmos, basta primeiramente permutar todos os elementos, ou seja, todas as letras, incluindo as repetições ''S''.

Se temos uma palavra contendo sete letras, faremos a permutação de 7:

P7 = 5040

Mas 5040 é o total de anagramas com repetições, para sabermos como ficaria essa permutação sem possíveis repetições, basta dividir a permutação total, no caso 5040, pela a permutação das repetições.

Quantas repetições temos? Duas, certo? S e S.

Então faremos:

Onde:

7! -> Permutação total de todos os elementos, incluindo as repetições.

2! -> A permutação de apenas as repetições.

Desenvolvendo ambos, teríamos:

Ou seja, com a palavra ''PASSEIO'' é possível criar 2250 anagramas sem qualquer repetição!

E se as repetições forem maiores? Por exemplo, com a palavra ''NANICA''.  

Perceba que temos duas repetições ''A'' e duas repetições ''N'', sendo que as únicas letras que não se repetem são ''I'' e ''C''.

Vamos solucionar esse problema, e vamos descobrir quantos anagramas sem repetições podemos formar com a palavra ''NANICA''.

A permutação total de todas as letras é: P6 ou 6!,  pois temos 6 letras aqui.

Agora vamos permutar as letras repetidas. Se temos duas letras ''A''e duas letras ''N'' temos para A: 2! e para N: 2!

Logo, vamos ter:

6! = 720

2! = 2

Logo, podemos obter 180 anagramas sem repetições, com a palavra ''NANICA''.

Outro exemplo? 

Quantos anagramas sem repetições, podemos formar com o nome ''ALESSANDRA''?

Perceba que temos três repetições na letra ''A'' e mais duas na letra ''S''.

O que faremos? Primeiro permutaremos tudo:

O nome ''Alessandra'' possui 10 letras, logo:

P10 = 10!

Agora vamos permutar as repetições:

Para ''A'' temos três repetições, então: 3!

Para ''S'' temos duas repetições, então: 2!

Logo:

10! = 10.9.8.7.6.5.4.3.2.1 = 3.628.800

2! = 2

3! = 3.2.1 = 6

Podemos então obter 302.400 anagramas distintos, com o nome ''Alessandra''.

Perceba que assim iremos obter uma expressão geral para permutações com elementos que se repetem:

Onde ''P'' é a permutação total de elementos, e ''q'', ''r'', ''s'' e etc... São os elementos que se repetem no grupo.

Vejamos agora outras aplicações de permutações com repetições, só que dessa vez, sem envolver anagramas. 

Em uma prova, onde o sistema de respostas utilizado é o sistema de ''Verdadeiro'' ou ''Falso'', determine de quantas formas distintas as respostas "V" possam ser 6 e as respostas "F" possam ser 8.

Para termos uma prova com 6 respostas "V" e 8 respostas "F", vamos ter um total de 14 questões. Logo, o número máximo de permutações de uma prova com esse número de respostas é 14!
Mas não é só isso, "V" se repete 6 vezes e "F" se repete 8 vezes, então teremos:
Para ''V'': 6!
Para ''F'': 8!

Então...



Simplificando:



Eliminando os termos semelhantes:

Multiplicando cada fatorial e realizando a divisão:

Conclusão: Essa prova pode ser organizada de 3003 maneiras distintas, desde que tenha 6  respostas "V" e 8 respostas "F".