1) O documento apresenta 7 problemas sobre combinatória e permutações. As respostas envolvem contar de quantas maneiras elementos podem ser ordenados ou combinados respeitando certas restrições.
Direitos autorais:
Attribution Non-Commercial (BY-NC)
Formatos disponíveis
Baixe no formato PDF, TXT ou leia online no Scribd
1) O documento apresenta 7 problemas sobre combinatória e permutações. As respostas envolvem contar de quantas maneiras elementos podem ser ordenados ou combinados respeitando certas restrições.
1) O documento apresenta 7 problemas sobre combinatória e permutações. As respostas envolvem contar de quantas maneiras elementos podem ser ordenados ou combinados respeitando certas restrições.
Direitos autorais:
Attribution Non-Commercial (BY-NC)
Formatos disponíveis
Baixe no formato PDF, TXT ou leia online no Scribd
1) O documento apresenta 7 problemas sobre combinatória e permutações. As respostas envolvem contar de quantas maneiras elementos podem ser ordenados ou combinados respeitando certas restrições.
Direitos autorais:
Attribution Non-Commercial (BY-NC)
Formatos disponíveis
Baixe no formato PDF, TXT ou leia online no Scribd
Fazer download em pdf ou txt
Você está na página 1/ 3
Lista 2
1) De quantos modos 5 mulheres e 6 homens podem formar uma roda de ciranda de
modo que as mulheres permaneçam juntas?
Fica mais fácil resolvermos esta questão se pensarmos em 2 problemas
de forma separada, o primeiro é de quantas formas podemos permutar as mulheres, o segundo de quantas formas podemos permutá-las junto com os homens (sem esquecer que elas devem permanecer juntas). Se temos 5 mulheres temos uma permutação de 5, o que nos dá 5! possibilidades, agora devemos considerar as mulheres como ‘um’ elemento na ciranda, o total de posições será dado pela permutação circular de 7 elementos (6 homens + elemento bloco de mulheres). Portanto, a resposta é 5!.6!.
2) De quantos modos 5 casais podem formar uma roda de ciranda de modo que cada homem fique ao lado de sua mulher e que pessoas do mesmo sexo não fiquem juntas?
Cada casal deve ser visto como ‘um’ elemento do tipo H M ou então M H sendo este casal “inseparável”, quando montarmos a ciranda teremos vários pares de H M H M H M H M H M e se pensarmos que isto é um círculo teremos a “última mulher” ao lado do “primeiro homem”, devemos fazer o mesmo para a possibilidade M H, assim temos permutação de 5 + permutação de 5 o que nos dá 5! + 5!
3) Uma partícula, estando no ponto (x;y), pode mover-se para o ponto (x+1;y) ou para o ponto (x;y+1). Quantos são os caminhos que a partícula pode tomar para, partindo do ponto (0;0), chegar ao ponto (6; 9)?
Para a partícula chegar ao ponto (6;9) saindo do ponto (0;0) ela deve andar 6 vezes para a direita e 9 vezes para cima totalizando 15 movimentos sendo que eles podem ser alternados (cima, direita, direita, direita, cima,....) ou (cima, direita, direita, cima,cima....) etc. Ou seja, cada caminho é uma ordenação de 6 Direita e 9 Cima. Assim, o número de maneiras de se ordenar 9 C (corresponde a andar pra cima) e 6 D (corresponde a andar pra direita) é dado por 15!/6!9!.
4) Quantos são os anagramas de MATEMATICA?
Para calcularmos os anagramas de uma palavra fazemos permutação do
número de letras, é simples, descobrimos de quantas formas diferentes podemos “embaralhar” as n letras da palavra, quando a palavra possui letras repetidas a solução continua sendo simples porém um pouquinho mais rebuscada pois devemos eliminar as repetições por exemplo MATEMAATIC é o mesmo anagrama que MATEMAATIC mas quando fazemos simplesmente 10! nós admitimos que estes 2 anagramas são diferentes (observem que mudei os A de lugar mas ainda assim é um A portanto o mesmo anagrama), assim sendo para obter a quantidade correta de anagramas devemos dividir o total de anagramas considerando todas as letras como se fossem distintas, isto é, 10!. Pelo número de repetições indesejadas que nos é dado por 3! 2! 2!. Pois temos 3 letras A, 2 letras T e 2 letras M que foram embaralhadas como se fossem diferentes.
5) De quantas maneiras podemos comprar 4 sorvetes de uma bola em uma loja que oferece 7 sabores diferentes?
Utilizando combinação com repetição temos a ideia de poder escolher 4
sabores (entre os 7 oferecidos) podendo repetir os sabores, logo a solução é combinação com repetição (representado por CR) de 7 (4 a 4), a fórmula pode ser encontrada no caderno.
Uma solução mais elegante seria: Seja x1 o número de sorvetes que
compramos do 1º sabor, x2 o número de sorvetes que compramos do 2º sabor, …, x7 o número de sorvetes que compramos do 7º sabor. Observe que x1 + x2 + x3+ x4+ x5+ x6+ x7 = 4.* Pois compramos só quatro sorvetes.
O número de maneiras de se comprar 4 sorvetes quando são 7 as opções
de sabores é o número de soluções, em inteiros não negativos da equação *. O número de soluções em inteiros não negativos da equação * é o número de maneiras de se ordenar 1111bbbbbb, onde b é a barra que indica que passamos para a próxima variável. O número de maneiras de se ordenar tais objetos é (4+6)!/ 4!.6!
6) A fábrica X produz 8 tipos de bombons que são vendidos em caixas de 30
bombons (de um mesmo tipo ou sortidos). Quantas caixas diferentes podem ser formadas?
Esta questão utiliza a mesma ideia da questão anterior, temos 8 tipos de
bombons e podemos (devemos) repeti-los para encher as caixas com 30 bombons, de quantas formas diferentes podemos obter os 30 bombons partindo de 8 tipos diferentes de bombons? Combinação com repetição de 8 (30 a 30).
Solução 2: Seja xj o número de bombons do tipo j. Como são 30
bombons na caixa temos que x1+ x2+ x3+ x4+ x5+ x6+ x7+ x8=30. Procuramos o número de soluções em inteiros não negativos para esta equação. Isto é o mesmo que o número de maneiras de se ordenar trinta algarismos 1 e 7 letras b iguais, que indicam a mudança da contagem pra variável seguinte. O número de permutações de elementos nem todos distintos com 30 uns e 7 b's, é (30 + 7)! / 30! 7! 7) Quantas são as soluções em inteiros não-negativos de x + y + z + w < 6?
Esta questão pode ser facilmente resolvida por combinação com repetição, a equação que temos pode ser representada por x+y+z+w <= 5, temos 4 variáveis e 5 igualdades possíveis, logo temos que combinar as variáveis de forma a obter todas as 5 igualdades. O número de soluções em inteiros não negativos é a soma do número de soluções em inteiros não negativos das equações:
x+y+z+w=0 x+y+z+w=1 x+y+z+w=2 x+y+z+w=3 x+y+z+w=4 x+y+z+w=5 Cada uma das quais sabemos contar.
