Anagramas e Permutações

Prévia do material em texto

*
*
*
Análise Combinatória
Desenvolvido por:
Cristiano De Angelis
Jorge Cunha
Adélson Jardim
*
*
*
Anagrama é a alteração da posição das
letras de uma mesma palavra. 
Vejamos quantos anagramas tem a palavra CHÁ:
C
H
A
1º- CHA
A
H
2º - CAH
H
A
C
3º - HAC
C
A
4º - HCA
A
C
H
5º - ACH
H
C
6º - AHC
*
*
*
Ao considerarmos três espaços, temos:
3letras
c,h ou a
 No primeiro espaço podemos considerar três letras - C, H ou A 
2letras
uma que
 não tenha
 sido usada
No segundo espaço temos somente duas opções. (caso contrário repetiremos a primeira letra)
1letra
a 
restante
No terceiro espaço teremos somente uma opção, a letra restante.
3.2.1 = 3! = 6
*
*
*
Vejamos agora quantos anagramas tem a palavra CAFÉ.
C
A
F
E
1º- CAFE
E
F
2º - CAEF
F
E
A
3º - CFEA
A
E
4º - CFAE
E
A
F
5º - CEAF
F
A
6º - CEFA...
Puts !!!
Isto somente começando com a letra C ! Mas, como existem só mais três letras que podem começar os anagramas da palavra café, temos: 
4 . 3! = 4! = 24
*
*
*
No primeiro anagrama temos:	3! = 3.2.1 = 6 No segundo anagrama temos:	4! = 4.3.2.1 = 24
Definição:
Quando o número de elementos “n” é igual ao número de vagas, teremos: 
n!
Isto quer dizer:
*
*
*
Existe um grupo de 5 estudantes (Cristiano, Jorge, Adélson, Marina, Raquel) para concorrer ao Daema, sendo a chapa formada por presidente e vice. Quantas serão as chapas possíveis?
Vamos fazer inicialmente todas as permutações possíveis.
*
*
*
CJAMR	CAMRJ	CMRJA	CRJAM CJARM		CAMJR		CMRAJ		CRJMA
CJMRA		CAJMR		CMJAR		CRMJA
CJMAR		CAJRM		CMJRA		CRMAJ
CJRMA		CARJM		CMAJR		CRAJM
CJRAM		CARMJ		CMARJ		CRAMJ
Cristiano Presidente !!
JAMRC	JMRCA	JRCAM	JCAMR JAMCR		JMRAC		JRCMA		JCARM 
JARCM		JMCAR		JRAMC		JCMRA 
JARMC		JMCRA		JRACM		JCMAR 
JACMR		JMARC		JRMAC		JCRMA 
JACRM		JMACR		JRMCA		JCRAM
Jorge Presidente !!
AMRCJ	ARCJM	AC MRJ	AJMRC AMRJC		ARCMJ		AC MJR		AJMCR
AMCJR		ARJMC		AC JMR		AJRCM
AMCRJ		ARJCM		AC JRM		AJRMC
AMJRC		ARMCJ		AC RJM		AJCMR
AMJCR		ARMJC		AC RMJ		AJCRM
Adélson Presidente !!
MRCJA	MCRJA	MJRCA	MARCJ MRCAJ		MCRAJ		MJRAC		MARJC	
MRJAC		MCJAR		MJCAR		MACJR MRJCA		MCJRA		MJCRA		MACRJ MRAJC		MCAJR		MJARC		MAJRC MRACJ		MCARJ		MJACR		MAJCR
Marina Presidente !!
RCJAM	RJCAM	RACJM	RMCJA RCJMA		RJCMA		RACMJ		RMCAJ RCAMJ		RJAMC		RAJMC		RMJAC RCAJM		RJACM		RAJCM		RMJCA RCMJA		RJMAC		RAMCJ		RMAJC RCMAJ		RJMCA		RAMJC		RMACJ
Raquel Presidente !!
*
*
*
O resultado das permutações será: 5! = 5.4.3.2.1 = 120,
mas existem vários resultados repetidos que consideram o mesmo presidente com o mesmo vice:
CJAMR CJARM CJMRA CJMAR CJRMA CJRAM	
Quais resultados serão estes?
A permutação de todos os elementos que não influenciam na formação da chapa!
*
*
*
Temos então, a permutação de “n” objetos, mas precisamos excluir a permutação dos objetos que não influenciam no resultado.
5!
ou 
5 . 4 . 3 . 2 . 1
Precisamos excluir a permutação dos três objetos sem influência. 
3!
3.2.1
Agora podemos simplificar !!
*
*
*
Isto é:
*
*
*
Arranjo aparece quando temos um universo de “n” objetos agrupados em “p” vagas em que a ordem
 interessa!
*
*
*
Existe um grupo de 5 estudantes (Cristiano, Jorge, Adélson, Marina, Raquel) para formar uma dupla de representantes de turma.
 Quantas serão as duplas possíveis?
*
*
*
CJAMR	CAMRJ	CMRJA	CRJAM CJARM		CAMJR		CMRAJ		CRJMA
CJMRA		CAJMR		CMJAR		CRMJA
CJMAR		CAJRM		CMJRA		CRMAJ
CJRMA		CARJM		CMAJR		CRAJM
CJRAM		CARMJ		CMARJ		CRAMJ
JAMRC	JMRCA	JRCAM	JCAMR JAMCR		JMRAC		JRCMA		JCARM 
JARCM		JMCAR		JRAMC		JCMRA 
JARMC		JMCRA		JRACM		JCMAR 
JACMR		JMARC		JRMAC		JCRMA 
JACRM		JMACR		JRMCA		JCRAM
AMRCJ	ARCJM	AC MRJ	AJMRC AMRJC		ARCMJ		AC MJR		AJMCR
AMCJR		ARJMC		AC JMR		AJRCM
AMCRJ		ARJCM		AC JRM		AJRMC
AMJRC		ARMCJ		AC RJM		AJCMR
AMJCR		ARMJC		AC RMJ		AJCRM
MRCJA	MCRJA	MJRCA	MARCJ MRCAJ		MCRAJ		MJRAC		MARJC	
MRJAC		MCJAR		MJCAR		MACJR MRJCA		MCJRA		MJCRA		MACRJ MRAJC		MCAJR		MJARC		MAJRC MRACJ		MCARJ		MJACR		MAJCR
RCJAM	RJCAM	RACJM	RMCJA RCJMA		RJCMA		RACMJ		RMCAJ RCAMJ		RJAMC		RAJMC		RMJAC RCAJM		RJACM		RAJCM		RMJCA RCMJA		RJMAC		RAMCJ		RMAJC RCMAJ		RJMCA		RAMJC		RMACJ
*
*
*
Mas, agora todas as permutações com CJ e JC , por exemplo, são desnecessárias pois a dupla não tem ordem.
CJAMR
CJARM
CJMRA
CJMAR
CJRMA
CJRAM
JCAMR
JCARM 
JCMRA 
JCMAR 
JCRMA
JCRAM
*
*
*
Novamente, temos a permutação de “n” objetos, precisamos excluir a permutação dos objetos que não influenciam no resultado, e ainda excluir a permutação possível entre as vagas.
5 . 4 . 3 . 2 . 1
3.2.1
= 5 . 4
 5 . 4
 2!
= 10
*
*
*
*
*
*
Problemas
*
*
*
UFRGS/ 95-2) Com 4 lápis de cores diferentes, quantas são as maneiras de pintar o seguinte mapa, de modo que as regiões que tem fronteira comum fiquem com cores distintas?
(A) 96
(B) 60
(C) 48
(D) 36
(E) Não é possível
*
*
*
Unisinos-97/2- Luciane estuda na Unisinos, de segunda a quarta, no turno da noite. Para vir à Unisinos e dela regressar para casa, Luciane costuma utilizar o seu próprio carro, ônibus ou mesmo carona. Quando ela vai no próprio carro, é claro que ela também volta de carro. O número de opções que Luciane tem para vir a Unisinos e dela voltar, nesses três dias é:
a) 5
b) 25
c) 125
d) 300
e) 500
*
*
*
Clóvis- 95/2) Um pintor tem 6 tintas para pintar 7 peças. Quer usar todas as tintas. Uma cor em cada peça. De quantos modos pode fazê-lo ?
Solução do Clóvis:
*
*
*
Solução
Vamos tentar com um universo menor, 3 tintas e 4 peças. 
B
B
B
B
B
B
B
B
B
B
B
B
C4,2		.3		.2!
nº de cores
permutação de 2 cores restantes
Cn+1,2	.n		.(n-1)!
C7,2		.6		.5! = 15120
*
*
*
c.q.d