Análise combinatória

Mostrando postagens com marcador Análise combinatória. Mostrar todas as postagens

Permutação com elementos repetidos

Postado por Ismael Alexandre | Marcadores: Análise combinatória

Quantos anagramas podemos formar a partir das letras da palavra CURIÓ?

Como já vimos, a permutação simples de n elementos distintos é dada por P_n, então como na palavra CURIÓtemos 5 letras distintas, o número de anagramas seria igual a P₅, ou seja, será igual a 5! que é igual a 120.

Quantos anagramas podemos formar a partir das letras da palavra ARARA?

Note que embora esta palavra também tenha cinco letras, agora temos apenas duas letras distintas. A letra A que ocorre 3 vezes e a letra R que ocorre 2 vezes. Como devemos proceder nesta situação?

Vimos no caso da palavra CURIÓ, que a permutação de cinco letras distintas resulta em 120 possibilidades.

Como na palavra ARARA a letra A ocorre três vezes, a permutação destas três letras A é P₃ = 3! = 6, ou seja, se dividirmos 120 por 6 iremos obter 20 que é o número de permutações, já desconsiderando-se as permutações entre as três letras A.

O mesmo iremos fazer em relação à letra R, só que neste caso o número de permutações desta letra éP₂ = 2! = 2, isto é, dividindo-se 20 por 2 temos como resultado 10, que é o número total de permutações das letras da palavra ARARA, sem considerarmos as permutações das letras A entre si, e das letras R também entre elas mesmas.

Permutação com Elementos Repetidos

A cada um dos agrupamentos que podemos formar com certo número de elementos, onde ao menos um deles ocorre mais de uma vez, tal que a diferença entre um agrupamento e outro se dê pela mudança de posição entre seus elementos, damos o nome de permutação com elementos repetidos.

Fórmula da Permutação com Elementos Repetidos

Se em um dado conjunto um elemento é repetido a vezes, outro elemento é repetido b vezes e assim sucessivamente, o número total de permutações que podemos obter é dada por:

A resolução do exemplo com o uso da fórmula é:

Exemplos

Quantos anagramas podemos obter a partir das letras da palavra PARAR?

Como a palavra PARAR possui 5 letras, mas duas delas são repetidas duas vezes cada, na solução do exemplo vamos calcular P₅^{(2, 2)}:

Portanto:

O número de anagramas que podemos formar a partir das letras da palavra PARAR é igual 30.

Possuo 4 bolas amarelas, 3 bolas vermelhas, 2 bolas azuis e 1 bola verde. Pretendo colocá-las em um tubo acrílico translúcido e incolor, onde elas ficarão umas sobre as outras na vertical. De quantas maneiras distintas eu poderei formar esta coluna de bolas?

Neste caso de permutação com elementos repetidos temos um total de 10 bolas de quatro cores diferentes. Segundo a repetição das cores, devemos calcular P₁₀^{(4, 3, 2)}:

Então:

Eu poderei formar esta coluna de bolas de 12600 maneiras diferentes.

Dos números distintos que são formados com todos os algarismos do número 333669, quantos desses são ímpares?

Neste exemplo, número ímpares serão aqueles terminados em 3 ou 9.

No caso dos números terminados em 3 devemos calcular P₅^{(2, 2)}, pois um dos dígitos três será utilizado na última posição e dos 5 dígitos restantes, teremos 2 ocorrências do próprio algarismo 3 e 2 ocorrências do 6:

Agora no caso dos números terminados em 9 devemos calcular P₅^{(3, 2)}, pois o dígito 9 será utilizado na última posição e dos 5 dígitos que sobram, teremos 3 ocorrências do 3 e 2 ocorrências do dígito 6:

Como temos 30 números terminados em 3 e mais 10 terminados em 9, então no total temos 40 números ímpares.

Logo:

Dos números formados, 40 deles são ímpares.

Read User's Comments(0)

Combinação Simples

Postado por Ismael Alexandre | Marcadores: Análise combinatória

Uma conceituada escola de idiomas está realizando uma promoção onde você escolhe três cursos, dos cinco disponíveis, e paga apenas ²/₃ do valor da mensalidade de cada um dos cursos escolhidos.

Podemos facilmente perceber que alguém que tenha escolhido os cursos de inglês, espanhol e alemão, fez as mesmas escolhas que outro alguém que tenha escolhido alemão, inglês e espanhol, por exemplo, pois a ordem dos cursos de idioma em si, não gera distinção entre uma escolha e outra.

Se alguém escolheu inglês, espanhol e alemão e outra pessoa escolheu inglês, espanhol e francês, também claramente podemos perceber que se tratam de escolhas distintas, pois nem todos os cursos que uma pessoa escolheu, são os mesmos escolhidos pela outra pessoa.

Considerando-se os 5 idiomas disponíveis, qual o número total de possibilidades se escolhermos três idiomas de cada vez?

Neste caso do curso de idiomas, podemos obter o número total de possibilidades, calculando inicialmente oarranjo simples A_5, 3:

Só que fazendo assim, estamos considerando distintos, os agrupamentos ( inglês, espanhol, alemão ) de ( espanhol, inglês, alemão ), por exemplo, e de todas as suas permutações.

Como sabemos, a permutação de 3 elementos, P₃ é igual a 3!, que é igual a 6, portanto se dividirmos 60 por 6, estaremos eliminando as ocorrências duplicadas em função da mera mudança de ordem dos elementos. Assim sendo, 60 : 6 = 10.

Portanto o número de opções possíveis é igual a 10.

Combinação Simples

Este exemplo é o típico caso, onde agrupamentos com elementos distintos, não se alteram mudando-se apenas a ordem de posicionamento dos elementos no grupo. A diferenciação ocorre apenas, quanto à natureza dos elementos, quando há mudança de elementos. Neste caso estamos tratando de combinação simples.

Fórmula da Combinação Simples

Ao trabalharmos com combinações simples, com n elementos distintos, agrupados p a p, com p ≤ n, podemos recorrer à seguinte fórmula:

Ao utilizarmos a fórmula neste nosso exemplo, temos:

Exemplos

Com 12 bolas de cores distintas, posso separá-las de quantos modos diferentes em saquinhos, se o fizer colocando 4 bolas em cada saco?

Como a ordem das bolas não causa distinção entre os agrupamentos, este é um caso de combinação simples. Vamos então calcular C_12, 4:

Portanto:

Posso separá-las de 495 modos diferentes.

Um fabricante de sorvetes possui a disposição 7 variedades de frutas tropicais do nordeste brasileiro e pretende misturá-las duas a duas na fabricação de sorvetes. Quantos serão os tipos de sorvete disponíveis?

Os sorvetes de umbu com siriguela e de siriguela com umbu, na verdade tratam-se de um mesmo tipo de sorvete, não havendo distinção apenas pela ordem da escolha das frutas utilizadas. Temos um caso de combinação simples que será resolvido através do cálculo de C_7, 2:

Logo:

Serão disponíveis 21 sabores diferentes.

As 14 crianças de uma família serão separadas em grupos de 5, para que elas arrecadem prendas para a quermesse da fazenda onde vivem. De quantas maneiras as crianças poderão ser agrupadas?

Identificamos neste exemplo um caso de combinação simples, pois a ordem das crianças é irrelevante, não causando distinção entre os agrupamentos com elementos distintos. Vamos calcular C_14, 5:

Então:

As crianças poderão ser agrupadas de 2002 maneiras diferentes.

Read User's Comments(0)

Permutação Simples

Postado por Ismael Alexandre | Marcadores: Análise combinatória

Quando estudamos o princípio fundamental da contagem tínhamos quatro livros (português, matemática,história e geografia) e calculamos o número total de formas que poderíamos empilhá-los em uma carteira escolar. Em outras palavras, fazíamos uma permutação no posicionamento destes livros na pilha sobre a carteira.

Permutação Simples

A cada um dos agrupamentos que podemos formar com certo número de elementos distintos, tal que a diferença entre um agrupamento e outro se dê apenas pela mudança de posição entre seus elementos, damos o nome depermutação simples.

Neste caso o agrupamento de livros ( português, matemática, história, geografia ), difere do agrupamento ( matemática, história, português, geografia ), pois embora os elementos de ambos os grupos sejam os mesmos, há mudança no posicionamento de ao menos um dos seus elementos.

Fórmula da Permutação Simples

Segundo o princípio fundamental da contagem vimos que o número de agrupamentos possíveis deste exemplo era dado por:

4 . 3 . 2 . 1 = 24

Na página sobre fatoriais vimos que 4 . 3 . 2 . 1 é igual a 4!, então se chamarmos de P_n a permutação simples den elementos distintos, podemos calculá-la através da seguinte fórmula:

P_n = n!

Resolvendo o exemplo com o uso da fórmula temos:

Exemplos

Quantos anagramas podemos formar a partir da palavra ORDEM?

Um anagrama é uma palavra ou frase formada com todas as letras de uma outra palavra ou frase. Normalmente as palavras ou frases resultantes são sem significado, como já era de se esperar.

Como a palavra ORDEM possui 5 letras distintas, devemos calcular o número de permutações calculando P₅. Temos então:

P₅ = 5! = 5 . 4 . 3 . 2 . 1 = 120

Portanto:

O número de anagramas que podemos formar a partir da palavra ORDEM é igual 120.

Na fila do caixa de uma padaria estão três pessoas. De quantas maneiras elas podem estar posicionadas nesta fila?

Temos que calcular P₃, então:

P₃ = 3! = 3 . 2 . 1 = 6

Logo:

As três pessoas podem estar posicionas de seis maneiras diferentes na fila.

Quantos são os anagramas que podemos formar a partir das letras da palavra ERVILHAS, sendo que eles comecem com a letra E e terminem com vogal?

Como na primeira posição sempre teremos a letra E, o número de possibilidades nesta posição é igual a 1, podemos até dizer que é igual a P₁.

Para a última posição temos disponíveis as letras I e A, pois a letra E já está sendo utilizada no começo, então para a oitava letra temos que calcular P₂:

P₂ = 2! = 2 . 1 = 2

Como para as demais posições temos 6 letras disponíveis, calculemos então P₆:

P₆ = 6! = 6 . 5 . 4 . 3 . 2 . 1 = 720

Multiplicando tudo:

1 . 720 . 2 = 1440

Então:

A partir da palavra ERVILHAS podemos formar 1440 anagramas que comecem com a letra E e terminem em vogal.

Read User's Comments(0)

Arranjos Simples

Postado por Ismael Alexandre | Marcadores: Análise combinatória

No campeonato mundial de Fórmula 1 de 2009, participaram 25 pilotos, dos quais se destacaram o inglês Jenson Button, que foi o campeão, o alemão Sebastian Vettel, que foi o vice-campeão e o brasileiro Rubens Barrichello, que ficou com a terceira colocação.

Obviamente o agrupamento ( Jenson Button, Sebastian Vettel, Rubens Barrichello ) difere do agrupamento ( Sebastian Vettel, Jenson Button, Rubens Barrichello ), pois neste caso a ordem no grupo é um fator que o diferencia.

Se ao invés do brasileiro Rubens Barrichello, o terceiro colocado tivesse sido o australiano Mark Webber, o agrupamento ( Jenson Button, Sebastian Vettel, Mark Webber ) seria distinto do agrupamento ( Jenson Button, Sebastian Vettel, Rubens Barrichello ), pois teríamos participantes diferentes nestes agrupamentos.

Arranjo Simples

Em casos como este, com elementos distintos, onde tanto a ordem de posicionamento no grupo, quanto a natureza dos elementos, os elementos em si, causam diferenciação entre os agrupamentos, estamos diante de um caso de arranjos simples.

Considerando-se os 25 pilotos participantes, qual o número total de possibilidades para os três primeiros colocados?

Para o campeão teríamos 25 possibilidades. Para o vice-campeão e para o terceiro colocado, teríamos respectivamente 24 e 23 possibilidades. Pelo princípio fundamental da contagem teríamos:

25 . 24 . 23 = 13800

Isto é, 13800 possibilidades.

Fórmula do Arranjo Simples

Ao trabalharmos com arranjos simples, com n elementos distintos, agrupados p a p, com p ≤ n, podemos recorrer à seguinte fórmula:

Neste mesmo exemplo, utilizando a fórmula temos:

Exemplos

Qual o número de anagramas que podemos formar com as letras da palavra PADRINHO?

Neste exemplo temos um arranjo simples com 8 elementos agrupados 8 a 8. Calculemos então A_8, 8:

Portanto:

Podemos formar 40320 anagramas com as letras da palavra PADRINHO.

Em uma escola está sendo realizado um torneio de futebol de salão, no qual dez times estão participando. Quantos jogos podem ser realizados entre os times participantes em turno e returno?

Como o campeonato possui dois turnos, os jogos Equipe A x Equipe B e Equipe B x Equipe A tratam-se de partidas distintas, então estamos trabalhando com arranjos simples onde importa a ordem dos elementos. Devemos calcular A_10, 2:

Então:

Podem ser realizados 90 jogos entre os times participantes.

Otávio, João, Mário, Luís, Pedro, Roberto e Fábio estão apostando corrida. Quantos são os agrupamentos possíveis para os três primeiros colocados?

Obviamente, como em qualquer corrida, a ordem de chegada é um fator diferenciador dos agrupamentos. Como temos 7 corredores e queremos saber o número de possibilidades de chegada até a terceira posição, devemos calcular A_7, 3:

Logo:

210 são os agrupamentos possíveis para os três primeiros colocados.

Read User's Comments(0)

Fatorial

Postado por Ismael Alexandre | Marcadores: Análise combinatória

Ao produto dos números naturais começando em n e decrescendo até 1 denominamos de fatorial de n e representamos por n!.

Segundo tal definição, o fatorial de 5 é representado por 5! e lê-se 5 fatorial.

5! é igual a 5 . 4 . 3 . 2 . 1 que é igual a 120, assim como 4! é igual a 4 . 3 . 2 . 1 que é igual a 24, como 3! é igual a 3 . 2 . 1 que é igual a 6 e que 2! é igual a 2 . 1 que é igual a 2.

Por definição tanto 0!, quanto 1! são iguais a 1.

Abaixo, no final da página, temos uma tabela com os 28 primeiros fatoriais. Repare que apesar do número 27 ser relativamente baixo, o seu fatorial possui 29 dígitos!

Escrevendo um fatorial a partir de um outro fatorial menor

Vimos que 5! é equivalente a 5 . 4 . 3 . 2 . 1, mas note que também podemos escrevê-lo de outras formas, em função de fatoriais menores, tais como 4!, 3! e 2!:

5! = 5 . 4!
5! = 5 . 4 . 3!
5! = 5 . 4 . 3 . 2!

Para um fatorial genérico temos:

n! = n . (n - 1)! = n . (n - 1) . (n - 2)! = n . (n - 1) . (n - 2) . (n - 3) . ... . 1!

Observe atentamente os exemplos seguintes:

(n + 3)! = (n + 3) . (n + 2)!
(n + 3)! = (n + 3) . (n + 2) . (n + 1)!
(n + 1)! = (n + 1) . n!

Vamos atribuir a n o valor numérico 6, para termos uma visão mais clara destas sentenças:

9! = 9 . 8!
9! = 9 . 8 . 7!
7! = 7 . 6!

Estes conceitos são utilizados em muitos dos problemas envolvendo fatoriais.

Simplificação envolvendo fatoriais

Observe a fração abaixo:

Vimos que 5! é equivalente a 5! = 5 . 4 . 3!. Então podemos escrever a fração da seguinte forma:

Agora podemos simplificar o 3! do numerador com o 3! do denominador. Temos então:

Veja outros exemplos:

Gerando uma sequência de números compostos consecutivos a partir de um fatorial

Na página onde falamos sobre múltiplos de um número natural foi explicado que se a um número que é múltiplo de n, somarmos n ou qualquer um dos seus múltiplos, iremos obter como resultado um número que também é múltiplo de n.

3! + 2 = 3 . 2 . 1 + 2 = 6 + 2 = 8

3! + 3 = 3 . 2 . 1 + 3 = 6 + 3 = 9

Repare que 8, resultado da soma de 6 com 2, é divisível por 2, assim como 6. O mesmo ocorrendo com 9, resultado da soma de 6 com 3, que também é divisível por 3.

Como 8 e 9 são múltiplos de algum fator de 3!, temos que eles formam uma sequência de dois números compostos (não primos) consecutivos a partir do fatorial de três.

3! possui três fatores, mas só podemos considerar os fatores maiores que 1, por isto só pudemos somar dois e três. Note neste exemplo, que se somássemos 3! + 1, iríamos obter 7, que não é um número composto. Sete é um número primo.

Exemplos de problemas envolvendo fatoriais

Qual deve ser o valor numérico de n para que a equação (n + 2)! = 20 . n! seja verdadeira?

O primeiro passo na resolução deste problema consiste em escrevermos (n + 2)! em função de n!, em busca de uma equação que não mais contenha fatoriais:

Conforme explicado na página onde tratamos sobre o cálculo rápido das raízes de equações do segundo grau, podemos resolver rapidamente esta equação respondendo à seguinte pergunta: Quais são os dois números cuja soma é igual a -3 e cujo produto é igual -18?

Rapidamente concluímos que as raízes procuradas são -6 e 3, mas como não existe fatorial de números negativos, já que eles não pertencem ao conjunto dos números naturais, ficamos apenas com a raiz igual a 3.

Portanto:

O valor numérico de n para que a equação seja verdadeira é igual a 3.

A partir de fatoriais, obtenha uma sequência com sete números compostos consecutivos.

Como eu devo obter 7 números compostos consecutivos na sequência, eu preciso partir ao menos de 8!:

8! = 8 . 7 . 6. 5 . 4 . 3 . 2 . 1 = 40320

Como 8! é igual a 40320, o primeiro número da sequência será 40320 + 2 = 40322 e o último será 40320 + 8 = 40328.

Logo:

A sequência 40322, 40323, 40324, 40325, 40326, 40327 e 40328 satisfaz as condições do enunciado.

Tabela com os fatorais de 0 a 27

n	n!
0	1
1	1
2	2
3	6
4	24
5	120
6	720
7	5040
8	40320
9	362880
10	3628800
11	39916800
12	479001600
13	6227020800
14	87178291200
15	1307674368000
16	20922789888000
17	355687428096000
18	6402373705728000
19	121645100408832000
20	2432902008176640000
21	51090942171709440000
22	1124000727777607680000
23	25852016738884976640000
24	620448401733239439360000
25	15511210043330985984000000
26	403291461126605635584000000
27	10888869450418352160768000000

Read User's Comments(0)

Matemática

Archives

Permutação com elementos repetidos

Quantos anagramas podemos formar a partir das letras da palavra CURIÓ?

Quantos anagramas podemos formar a partir das letras da palavra ARARA?

Permutação com Elementos Repetidos

Fórmula da Permutação com Elementos Repetidos

Exemplos

Combinação Simples

Considerando-se os 5 idiomas disponíveis, qual o número total de possibilidades se escolhermos três idiomas de cada vez?

Combinação Simples

Fórmula da Combinação Simples

Exemplos

Permutação Simples

Permutação Simples

Fórmula da Permutação Simples

Exemplos

Arranjos Simples

Arranjo Simples

Considerando-se os 25 pilotos participantes, qual o número total de possibilidades para os três primeiros colocados?

Fórmula do Arranjo Simples

Exemplos

Fatorial

Escrevendo um fatorial a partir de um outro fatorial menor

Simplificação envolvendo fatoriais

Gerando uma sequência de números compostos consecutivos a partir de um fatorial

Exemplos de problemas envolvendo fatoriais

Tabela com os fatorais de 0 a 27