A.Combinatória - Permutações
2 participantes
Página 1 de 1
A.Combinatória - Permutações
Quantas permutações de 7 letras A e 7 letras B, nas quais não há 3 letras A adjacentes, existem?
R. 1016
R. 1016
Luck- Grupo
Velhos amigos do Fórum - Mensagens : 5322
Data de inscrição : 20/09/2009
Idade : 31
Localização : RJ
Resolução do problema.
Tentei resolver de maneira mais simples, mas, não consegui. Utilizei uma divisão do problema em quatro etapas.
Como não podemos ter 3 letras A juntas, então vamos fazer os seguintes grupos:
Etapa (i): _AA_AA_AA_A_;
Etapa (ii): _AA_AA_A_A_A_;
Etapa (iii): _AA_A_A_A_A_A_ e
Etapa (iv): _A_A_A_A_A_A_A_.
Note que cada grupo possui 7 tetras A. Vamos colocar uma letra B nos espaços “_” que se encontram entre as duplas de A’s e/ou entre o(s) A(‘s) sozinhos para garantir que haja 3 A’s adjacentes.
.
Caso (i) _AABAABAABA_.
Sobrou 4 B’s para distribuir e 5 espaços para colocá-las. Obs.: considere os B’s já dispostos como espaços. Primeiro vamos calcular as permutações entre as 3 duplas de letras A e o A sozinho. É uma permutação de 4 com repetição de 3.
P 4, 3 = 4!/3! = 4*3!/3! = 4.
Novamente vamos ter que dividir em etapas, pois os B’s podem ser dispostos das maneiras seguintes:
(i1) B_B_B_B;
(i2) BB_B_B;
(i3) BB_BB;
(i4) BBB_B e
(i5) BBBB.
Caso (i1) B_B_B_B: C 5, 4 = 5.
Caso (i2) BB_B_B: (C 5, 3)*(P 3, 2) = 10*3 = 30.
Caso (i3) BB_BB: C 5, 2 = 10.
Caso (i4) BBB_B: (C 5, 2)*2! = 10*2 = 20.
Caso (i5) BBBB: C 5, 1 = 5.
Total de (i): 4*(5 + 30 + 10 + 20 + 5) = 4*70 = 280.
.
Caso (ii) _AABAABABABA_.
Sobrou 3 B’s para distribuir e 6 espaços para colocá-las. Primeiro vamos calcular as permutações entre as 2 duplas de letras A e os 3 A’s sozinhos. É uma permutação de 5 com repetição de 2 e 3.
P 5, 2, 3 = 5!/(2!3!) = (5*4*3!)/(2*1*3!) = 20/2 = 10.
Mais uma vez vamos dividir em etapas. Os 3 B’s podem ser dispostos das maneiras seguintes:
(ii1) B_B_B;
(ii2) BB_B e
(ii3) BBB.
Caso (ii1) B_B_B: C 6, 3 = 20.
Caso (ii2) BB_B: (C 6, 2)*2! = 15*2 = 30.
Caso (ii3) BBB: C 6, 1 = 6.
Total de (ii): 10*(20 + 30 + 6) = 10*56 = 560.
.
Caso (iii) _AABABABABABA_.
Sobrou 2 B’s para distribuir e 7 espaços para colocá-las. Primeiro vamos calcular as permutações entre a dupla de letras A e os 5 A’s sozinhos. É uma permutação de 6 com repetição de 5.
P 6, 5 = 6!/5! = (6*5!)/5! = 6.
Dividindo em etapas temos que os 2 B’s restantes podem ser dispostos das duas maneiras a seguir:
(iii1) B_B e
(iii2) BB.
Caso (iii1) B_B: C 7, 2 = 21.
Caso (iii2) BB: C 7, 1 = 7.
Total de (iii): 6*(21 + 7) = 6*28 = 168.
.
Caso (iv) _ABABABABABABA_.
Sobrou um (1) B para distribuir e 8 espaços para colocá-lo.
Temos apenas o caso (iv1) B, então basta calcular a combinação de 8 elementos 1 a 1.
C 8, 1 = 8.
Total de (iv): 8.
.
Total geral: 280 + 560 + 168 + 8 = 1016.
Resposta: 1016 permutações.
Como não podemos ter 3 letras A juntas, então vamos fazer os seguintes grupos:
Etapa (i): _AA_AA_AA_A_;
Etapa (ii): _AA_AA_A_A_A_;
Etapa (iii): _AA_A_A_A_A_A_ e
Etapa (iv): _A_A_A_A_A_A_A_.
Note que cada grupo possui 7 tetras A. Vamos colocar uma letra B nos espaços “_” que se encontram entre as duplas de A’s e/ou entre o(s) A(‘s) sozinhos para garantir que haja 3 A’s adjacentes.
.
Caso (i) _AABAABAABA_.
Sobrou 4 B’s para distribuir e 5 espaços para colocá-las. Obs.: considere os B’s já dispostos como espaços. Primeiro vamos calcular as permutações entre as 3 duplas de letras A e o A sozinho. É uma permutação de 4 com repetição de 3.
P 4, 3 = 4!/3! = 4*3!/3! = 4.
Novamente vamos ter que dividir em etapas, pois os B’s podem ser dispostos das maneiras seguintes:
(i1) B_B_B_B;
(i2) BB_B_B;
(i3) BB_BB;
(i4) BBB_B e
(i5) BBBB.
Caso (i1) B_B_B_B: C 5, 4 = 5.
Caso (i2) BB_B_B: (C 5, 3)*(P 3, 2) = 10*3 = 30.
Caso (i3) BB_BB: C 5, 2 = 10.
Caso (i4) BBB_B: (C 5, 2)*2! = 10*2 = 20.
Caso (i5) BBBB: C 5, 1 = 5.
Total de (i): 4*(5 + 30 + 10 + 20 + 5) = 4*70 = 280.
.
Caso (ii) _AABAABABABA_.
Sobrou 3 B’s para distribuir e 6 espaços para colocá-las. Primeiro vamos calcular as permutações entre as 2 duplas de letras A e os 3 A’s sozinhos. É uma permutação de 5 com repetição de 2 e 3.
P 5, 2, 3 = 5!/(2!3!) = (5*4*3!)/(2*1*3!) = 20/2 = 10.
Mais uma vez vamos dividir em etapas. Os 3 B’s podem ser dispostos das maneiras seguintes:
(ii1) B_B_B;
(ii2) BB_B e
(ii3) BBB.
Caso (ii1) B_B_B: C 6, 3 = 20.
Caso (ii2) BB_B: (C 6, 2)*2! = 15*2 = 30.
Caso (ii3) BBB: C 6, 1 = 6.
Total de (ii): 10*(20 + 30 + 6) = 10*56 = 560.
.
Caso (iii) _AABABABABABA_.
Sobrou 2 B’s para distribuir e 7 espaços para colocá-las. Primeiro vamos calcular as permutações entre a dupla de letras A e os 5 A’s sozinhos. É uma permutação de 6 com repetição de 5.
P 6, 5 = 6!/5! = (6*5!)/5! = 6.
Dividindo em etapas temos que os 2 B’s restantes podem ser dispostos das duas maneiras a seguir:
(iii1) B_B e
(iii2) BB.
Caso (iii1) B_B: C 7, 2 = 21.
Caso (iii2) BB: C 7, 1 = 7.
Total de (iii): 6*(21 + 7) = 6*28 = 168.
.
Caso (iv) _ABABABABABABA_.
Sobrou um (1) B para distribuir e 8 espaços para colocá-lo.
Temos apenas o caso (iv1) B, então basta calcular a combinação de 8 elementos 1 a 1.
C 8, 1 = 8.
Total de (iv): 8.
.
Total geral: 280 + 560 + 168 + 8 = 1016.
Resposta: 1016 permutações.
Carlos Eustáquio pinto- Iniciante
- Mensagens : 22
Data de inscrição : 09/07/2011
Idade : 45
Localização : Sarzedo, Minas Gerais, Brasil
Re: A.Combinatória - Permutações
Noss , parabéns Carlos ótima solução! Deu trabalho essa, obg por postar. Estava procurando outras soluções para essa questão que me enrolei pra entender...
Aí esta outra solução proposta pelo autor César Morgado:
Começamos formando uma fila com as letras B, o que só pode ser feito de 1 modo. Em seguida, devemos colocar as letras A nos oito espaços existentes entre as letras b, antes do primeiro B e depois do último. Para decidir quantas letras A colocaremos em cada espaço, devemos resolver a equação x1 + x2 + ... + x8 = 7, com x1,x2, ... ,x8 є {0,1,2}. As soluções desta equação são:
i) três incógnitas iguais a 2, uma igual a 1 e quatro iguais a 0;
ii) duas incógnitas iguais a 2, três iguais a 1 e três iguais a 0;
iii) uma incógnita igual a 2, cinco iguais a 1 e duas iguais a 0;
iv) zero incógnita igual a 2, sete iguais a 1 e uma igual a 0.
A resposta é P[8;(4,3,1)] + P[8;(3,3,3)] + P[8;(5,2,1)] + P[8;(7,1)] = 280 + 560 + 158 + 8 = 1016
Aí esta outra solução proposta pelo autor César Morgado:
Começamos formando uma fila com as letras B, o que só pode ser feito de 1 modo. Em seguida, devemos colocar as letras A nos oito espaços existentes entre as letras b, antes do primeiro B e depois do último. Para decidir quantas letras A colocaremos em cada espaço, devemos resolver a equação x1 + x2 + ... + x8 = 7, com x1,x2, ... ,x8 є {0,1,2}. As soluções desta equação são:
i) três incógnitas iguais a 2, uma igual a 1 e quatro iguais a 0;
ii) duas incógnitas iguais a 2, três iguais a 1 e três iguais a 0;
iii) uma incógnita igual a 2, cinco iguais a 1 e duas iguais a 0;
iv) zero incógnita igual a 2, sete iguais a 1 e uma igual a 0.
A resposta é P[8;(4,3,1)] + P[8;(3,3,3)] + P[8;(5,2,1)] + P[8;(7,1)] = 280 + 560 + 158 + 8 = 1016
Luck- Grupo
Velhos amigos do Fórum - Mensagens : 5322
Data de inscrição : 20/09/2009
Idade : 31
Localização : RJ
Resposta ao comentário do colega Luck.
Luck, o professor Morgado foi um professor espetacular. Nunca poderia pensar nesta "solução obra de arte" deixada por ele. Uma coisa você pode ter certeza, eu não conseguiria resolver o problema se não fosse as aulas em vídeo e os livros deixados pelo professor Morgado!
Carlos Eustáquio pinto- Iniciante
- Mensagens : 22
Data de inscrição : 09/07/2011
Idade : 45
Localização : Sarzedo, Minas Gerais, Brasil
Outra solução.
Luck, o professor Morgado ainda nos ensina, mesmo não estando mais entre nós.
Após ver a solução, proposta por ele, que você postou, pensei nesta outra.
Primeiro enfileiramos as 7 letras B e notamos que há 8 espaços para dispormos as 7 letras A na fileira.
_B_B_B_B_B_B_B_
Dividimos as 7 letras A em 4 grupos para colocar nos 8 espaços.
AA-AA-AA-A
(C 8, 4)(P 4, 3) = 70*4 = 280.
AA-AA-A-A-A
(C 8, 5)(P 5, 3, 2) = 56*10 = 560.
AA-A-A-A-A-A
(C 8, 6)(P 6, 5) = 28*6 = 168.
A-A-A-A-A-A-A
(C 8, 7) = 8.
Total: 280 + 560 + 168 + 8 = 1016.
Esta fica como uma humilde homenagem minha ao Professor Augusto Cézar Morgado.
Após ver a solução, proposta por ele, que você postou, pensei nesta outra.
Primeiro enfileiramos as 7 letras B e notamos que há 8 espaços para dispormos as 7 letras A na fileira.
_B_B_B_B_B_B_B_
Dividimos as 7 letras A em 4 grupos para colocar nos 8 espaços.
AA-AA-AA-A
(C 8, 4)(P 4, 3) = 70*4 = 280.
AA-AA-A-A-A
(C 8, 5)(P 5, 3, 2) = 56*10 = 560.
AA-A-A-A-A-A
(C 8, 6)(P 6, 5) = 28*6 = 168.
A-A-A-A-A-A-A
(C 8, 7) = 8.
Total: 280 + 560 + 168 + 8 = 1016.
Esta fica como uma humilde homenagem minha ao Professor Augusto Cézar Morgado.
Carlos Eustáquio pinto- Iniciante
- Mensagens : 22
Data de inscrição : 09/07/2011
Idade : 45
Localização : Sarzedo, Minas Gerais, Brasil
ALEXANDRE RESENDE DE SOUZ gosta desta mensagem
Página 1 de 1
Permissões neste sub-fórum
Não podes responder a tópicos
|
|