ANÁLISE COMBINATÓRIA

Prévia do material em texto

ANÁLISE COMBINATÓRIA
Anagrama
O anagrama é um jogo de palavras que utiliza a transposição ou rearranjo de letras de uma palavra ou frase, com o intuito de formar outras palavras com ou sem sentido. É calculado através da propriedade fundamental da contagem, utilizando o fatorial de um número de acordo com as condições impostas pelo problema. 
Exemplo 1 
Vamos determinar os anagramas da palavra: 
a) ESCOLA 
A palavra possui 6 letras, dessa forma, basta determinarmos o valor de 6! (seis fatorial). 
6! = 6 * 5 * 4 * 3 * 2 * 1 = 720 
b) ESCOLA que inicia com E e termina com A. 
E ___ ___ ___ ___ A 
Vamos permutar as 4 letras não fixas. 
4! = 4 * 3 * 2 * 1 = 24 
Exemplo 2 
a) Determinar os anagramas da palavra REPÚBLICA. 
A palavra possui 9 letras, então devemos calcular 9!. 
9! = 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 362.880 
b) REPÚBLICA que inicia com R e termina com A. 
R ___ ___ ___ ___ ___ ___ ___ A 
Vamos permutar as 7 letras não fixadas. 
7! = 7 * 6 * 5 * 4 * 3 * 2 * 1 = 5040 
Exemplo 3 
Determinar os anagramas da palavra CONQUISTA, que tem as letras CON juntas e na mesma ordem: C O N ___ ___ ___ ___ ___ ___ . 
Temos 6 letras não fixadas que permutarão entre si, e a expressão CON que se unirá às permutações. 
7! = 7 * 6 * 5 * 4 * 3 * 2 * 1 = 5040 
Exemplo 4 
A palavra MATEMÁTICA é formada por 10 letras. Determine o número possível de anagramas dessa palavra. 
Temos 10 letras que serão permutadas entre si, portanto: 
10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 3.628.800 
A palavra MATEMÁTICA possui 3.628.800 anagramas. 
Exemplo 5 
Quantas palavras de 3 letras podemos formar com as letras O, L e A? Quais são essas palavras? As palavras não precisam necessariamente terem siginificado. 
A quantidade de palavras será dada por 3! 
3 * 2 * 1 = 6 palavras 
As palavras são: 
OLA 
OAL 
ALO 
AOL 
LOA 
LAO
Arranjos simples
Os agrupamentos formados nos exercícios de análise combinatória podem ser considerados Arranjos simples. Será assim classificado se levarmos em consideração a ordem de seus elementos, ou seja, se os agrupamentos forem diferentes entre si pela ordem de seus elementos. 
Por exemplo, vamos considerar dois agrupamentos dos números divisíveis por 3, de 5 algarismos formados com os elementos (algarismos) do conjunto A = {1,2,3,4,5,6,7,8,9}. 
Os números 12345 e 54321 são divisíveis por 3 e possuem 5 algarismos do conjunto A. E os algarismos utilizados na construção desses números são iguais, mas estão dispostos em ordens diferentes, tornando-os diferentes entre si. Portanto, esse exercício de análise combinatória é um exemplo de arranjo simples. 
Quando os agrupamentos de um exercício de análise combinatória forem caracterizados como Arranjos simples, para calcular a quantidade de agrupamentos formados não é preciso esquematizar todos eles, basta utilizar a seguinte fórmula: 
A n,p = n! 
 (n – p)! 
n é a quantidade de elementos do conjunto. 
p é um número natural menor ou igual a n, que representa a união dos elementos na formação dos agrupamentos. 
Assim, podemos definir arranjo simples como sendo: 
Dado um conjunto qualquer com n elementos e um valor para natural p. Será formado um arranjo simples de p elementos distintos de um conjunto qualquer seqüência formada por p elementos do conjunto. 
Exemplo: 
Considere o conjunto I = {a,b,c,d}: 
• Quantos são os arranjos simples dos elementos de I, tomados dois a dois? 
Como o exercício já informou que se trata de um arranjo simples, devemos retirar os dados e aplicá-los na fórmula. 
n = 4 
p = 2 
A n,p = n! 
 (n – p)! 
A 4,2 = 4! 
 (4 – 2)! 
A 4,2 = 4 . 3 . 2! 
 2! 
A4,2 = 4 . 3 
A4,2 = 12
Combinação simples
Combinação simples é um tipo de agrupamento no estudo sobre análise combinatória. Os agrupamentos formados com os elementos de um conjunto serão considerados combinações simples se os elementos dos agrupamentos diferenciarem apenas pela sua natureza. 
Se considerarmos o conjunto B ={A,B,C,D} formados por 4 pontos não colineares (que não pertence a mesma reta), qual a quantidade de triângulos que podemos formar? 
Esse é um problema de análise combinatória, pois iremos formar agrupamentos. Nesse caso o agrupamento é formar triângulos utilizando 4 pontos não colineares. Se destacarmos dois agrupamentos formados teremos: ABC e BCA, esses são triângulos formados com os mesmos pontos, mas em ordens diferentes que torna os triângulos iguais. Portanto, os agrupamentos formados nesse exercício são combinações. 
As combinações simples podem ser consideradas um tipo particular de arranjo simples, pois os agrupamentos formados nos arranjos são diferenciados pela ordem e pela natureza dos seus elementos. A combinação simples são esses arranjos diferenciados apenas pela natureza de seus elementos. 
Considerando o exemplo acima veja todas as possibilidades de triângulos formados com os quatro pontos não colineares: 
ABC, BAC, CAB, DAB 
ABD, BAD, CAD, DAC 
ACB, BCA, CBA, DBA 
ACD, BCD, CBD, DBC 
ADB, BDA, CDA, DCA 
ADC, BDC, CDB, DCB 
Percebemos que há vários agrupamentos que se diferem pela ordem de seus elementos, esses representam o mesmo triângulo, por isso que consideramos esse exercício como sendo uma combinação simples, assim a quantidade de combinações simples que os 4 pontos não colineares (A,B,C,D), tomados 3 a 3 irão formar será 4, pois os seus agrupamentos se diferem pela natureza de seus elementos e não pela ordem. 
Para encontrar essa quantidade de agrupamentos formados em uma combinação simples utilizamos a seguinte fórmula: 
Cn,p = n! 
 p! (n – p) 
n é a quantidade de elementos de um conjunto 
p é um número natural menor ou igual a n, que representa a quantidade de elementos que irão formar os agrupamentos. 
Substituindo os dados acima na fórmula teremos: 
n = 4 
p = 3 
C4,3 = 4! 
 3! (4-3)! 
C4,3 = 4 . 3! 
 3! . 1 
C4,3 = 4
Critérios para identificação de arranjo ou combinação
Os exercícios de análise combinatória podem ser resolvidos por arranjo ou combinação, mas como identificar qual dos dois agrupamentos o exercício está se referindo? Para isso é preciso que coloquemos em prática alguns critérios que ajudarão nessa identificação. 
Esses critérios são aplicados da seguinte forma: Em um problema de análise combinatória iremos encontrar vários agrupamentos, monte pelo menos um deles e modifique a ordem dos elementos desse agrupamento. 
Se depois da mudança tiver formado um agrupamento diferente, esse problema será de arranjo. 
Se depois da mudança tiver formado o mesmo agrupamento, esse problema será de combinação, ou seja, mesmo se os elementos em ordem diferentes continuar identificando o mesmo agrupamento. 
Veja como funciona a aplicação desse critério: 
Considere nove pontos diferentes de uma circunferência, conforme a figura. 
Quantas retas ficam determinadas por esses nove pontos? 
Pra descobrir se o exercício é de arranjo ou combinação é preciso que montemos pelo menos um dos agrupamentos (reta). 
Uma reta é formada por, no mínino, 2 pontos, como os pontos não são colineares podemos unir qualquer ponto, assim podemos dizer que (A,B) é um agrupamento, se trocarmos a ordem dos seus elementos (B,A) a reta (agrupamento) continua sendo a mesma, portanto, esse exercício será resolvido por combinação. 
Assim, aplicamos a fórmula da combinação, sendo que n = 9 e p = 2. 
C9,2 = 9! 
 2! (9-2)! 
C9,2 = 9 . 8 . 7! 
 2 . 1 . 7! 
C9,2 = 72 
 2 
C9,2 = 36 
Serão formados com os 9 pontos da circunferências 36 retas.
Equações envolvendo o fatorial
O número fatorial está presente na maioria dos problemas de análise combinatória, portanto, é importante que saibamos manipular essa ferramenta em diversas situações. Sendo assim, estudaremos as maneiras de se manipular números fatoriais de maneira algébrica para solucionar equações.
O fatorial de um número consiste na multiplicação sucessiva desse número por todos os seus antecessores naturais. Portanto, quando se têm umaequação na qual a incógnita acompanha um fatorial, o caminho para obtermos a solução é conseguirmos simplificar este fatorial ou reescrever a equação de modo que o fatorial não interfira, ou esteja de uma maneira que nos possibilita utilizar alguma ferramenta matemática para resolução de equações, sejam elas de primeiro ou segundo grau.
Veremos exemplos que permeiam essas manipulações algébricas com o fatorial para melhor compreender esses procedimentos.
1) Resolva as equações a seguir:
Veja que temos uma fração de fatoriais, em frações sempre buscamos elementos iguais para podermos cancelar. Note que o n! pode ser desenvolvido até o fator (n-2)! fazendo com que tenhamos números iguais no numerador e no denominador.
 
O fatorial foi eliminado de nossa equação, ficando apenas a incógnita. Portanto, obteremos uma equação do segundo grau na incógnita n. Resolvendo essa equação iremos obter as seguintes soluções.
Lembre-se que o fatorial só está definido para números naturais, ou seja, apenas para os inteiros positivos, portanto, a solução n = – 6 é inválida para a nossa equação fatorial.
Novamente devemos buscar uma maneira de manipular os números fatoriais para que possamos simplificá-los nesta equação. Busque sempre desmembrar o maior número fatorial da expressão, em nosso exemplo é o (n+1)!
Substituindo na equação, temos:
Agora, falta apenas simplificar o fatorial (n-1)! e n!. Novamente desenvolveremos o maior número fatorial, que é o n!
Substituindo na equação:
2) Resolva a equação:
 Não existe a possibilidade de simplificarmos estes fatoriais, contudo, note que podemos construir uma equação do segundo grau na qual a incógnita é n!. Para melhor visualizarmos, façamos a seguinte substituição: chame n! por outra letra, por exemplo x.
Ou seja, x = n!
Obtemos uma nova equação:
O x está relacionado ao resultado do n! (Lembre-se n! = x), portanto, a segunda solução não satisfaz nossa equação. Devemos relacionar agora a primeira solução com o fatorial.
3) (Unitau – SP – Adaptada) Sendo n ≠ 0, assinale a alternativa que possui o(s) valor(es) que satisfaz(em) a equação abaixo:
a. 7 b. 0 e 7 c. 0 e 10
d. 1 e. 0 e 2 
Note que no numerador temos dois termos, portando, dividiremos essa fração em duas para facilitar a simplificação dos fatoriais.
Devemos obter no numerador um número fatorial que simplifique com (n-1)!. Portanto:
Determinamos dois valores para a incógnita do fatorial, contudo a condição inicial do problema é: n ≠ 0. Portanto, a única solução que podemos utilizar é n=7.
Permutação Envolvendo Elementos Repetidos
Entendemos por permutações uma sequência ordenada, construída por elementos disponíveis. O número de permutações de n elementos é dado pelo fatorial de n, isto é, basta calcularmos o fatorial do número de elementos do conjunto fornecido. Para o melhor entendimento vamos considerar os anagramas da palavra LUA. Lembrando que anagrama de uma palavra corresponde à permutação das letras de uma palavra, formando ou não outra palavra. Observe: 
 
No caso da palavra LUA, não existe repetição de letras, então podemos determinar os anagramas através da seguinte expressão matemática: Pn = n! 
P3 = 3! = 3*2*1 = 6 
A palavra LUA possui 6 anagramas. 
Permutação envolvendo um elemento repetido 
Determinar os anagramas da palavra MORANGO. 
Os anagramas serão formados a partir de uma sequência de 7 letras, das quais duas são iguais a O. Dessa forma temos: 
Permutação envolvendo dois elementos diferentes repetidos 
Determine os anagramas da palavra MARROCOS. 
Os anagramas serão formados a partir da sequência de 8 letras, das quais duas são iguais a R e duas iguais a O. Temos que: 
Outras situações envolvendo elementos repetidos 
Anagramas da palavra MATEMÁTICA. 
Nesse caso temos 10 letras, onde ocorrem as seguintes repetições: duas letras M, três letras A e duas letras T. Então:
Permutação simples
Este texto apresentará uma explicação diferenciada para o conceito de permutação. Assim como você já deve ter lido nos outros artigos de análise combinatória, permutação é uma das formas de se combinar os elementos de um determinado grupo, combinação esta que se assemelha à expressão do Arranjo Simples. 
Nesse artigo mostraremos para você, estudante, que não é preciso sair decorando diversas fórmulas, pois muitas delas são idênticas, apenas com uma interpretação diferente. 
Vejamos a expressão para o arranjo simples e analisemos suas informações.
Note que n é a quantidade de elementos que você tem para combinar e k é a quantidade de posições que estes elementos podem ocupar, ou seja, tudo indica que a quantidade k seja menor do que a quantidade de elementos que serão trocados. 
O que aconteceria se tivéssemos posições para todos os elementos (n)? Em outras palavras, o que aconteceria se k fosse igual a n? Ao respondermos esta pergunta utilizando a expressão do arranjo, iremos obter uma expressão que corresponderá à permutação simples. Pois ela consiste em você organizar n elementos distintos, entre n posições distintas. Vejamos então esta expressão:
Por sua vez, como permutamos n elementos, todos eles em n posições distintas, podemos afirmar que esta expressão obtida remete à expressão da permutação simples. 
Sendo assim, a expressão da permutação é dada da seguinte forma:
Veja que não é necessário sair decorando diversas fórmulas na matemática, pois muitas destas são apenas um caso específico de uma expressão mais abrangente. Caso um dia você se esqueça de como é que se calcula uma permutação simples, basta lembrar que só é preciso pegar a expressão do arranjo e permutar os elementos em todas as posições.
Princípio Fundamental da Contagem e Fatorial
Para entendermos o princípio fundamental da contagem vamos analisar a seguinte situação: João possui 4 camisas, 3 calças, 2 pares de meia e 2 pares de sapatos. De quantas maneiras diferentes ele pode se vestir? 
Observe os esquemas a seguir:
Cada esquema representa todas as possíveis combinações envolvendo os objetos do vestuário de João. Uma maneira mais simplificada e eficaz de resolver tal situação consiste em determinar a multiplicação entre a quantidade de elementos de cada conjunto. Observe: 
4 * 3 * 2 * 2 = 48 combinações. 
De acordo com o princípio fundamental da contagem, se um evento é composto por duas ou mais etapas sucessivas e independentes, o número de combinações será determinado pelo produto entre as possibilidades de cada conjunto. 
Observe outro exemplo: 
Numa lanchonete há 8 tipos de sanduíche, 5 tipos de sucos e 6 tipos de sorvetes. Quantas são as possíveis combinações de um lanche nessa lanchonete? 
Utilizando o princípio fundamental da contagem temos: 
8 * 5 * 6 = 240 maneiras de realizar um lanche. 
Fatorial 
O fatorial é uma ferramenta matemática utilizada na análise combinatória, na determinação do produto dos antecessores de um número maior que 1. Por exemplo: 
1! = 1 
2! = 2 * 1 = 2 
3! = 3 * 2 *1 = 6 
4! = 4 * 3 * 2 * 1 = 24 
5! = 5 * 4 * 3 * 2 * 1 = 120 
6! = 6 * 5 *4 * 3 * 2 * 1 = 720 
7! = 7 * 6 * 5 * 4 * 3 * 2 * 1 = 5 040 
8! = 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 40 320 
9! = 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 362 880 
10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 3 628 800 
E assim sucessivamente. 
Um exemplo de utilização de fatorial está presente no cálculo de anagramas de uma palavra. Lembrando que anagrama é a quantidade de novas palavras formadas com ou sem sentido, utilizando as letras de outra palavra. Por exemplo, vamos determinar os anagramas da palavra AMOR. 
A palavra AMOR é formada por quatro letras, portanto: 
4! = 4 * 3 * 2 * 1 = 24 palavras 
Determinando os anagramas da palavra MATEMÁTICA. 
10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 3 628 800 palavras formadas.
10