Métodos Quantitativos
Prof. Ms. Osmar Pastore e Prof. Ms. Francisco Merlo
Introdução à Análise Combinatória
Introdução à Análise Combinatória
Introdução
Foi a necessidade de calcular o número de possibilidades existentes nos chamados jogos
de azar que levou ao desenvolvimento da Análise Combinatória, uma parte da Matemática
que estuda os métodos de contagem. Esses estudos foram iniciados já no século XVI, pelo
matemático italiano Niccollo Fontana (1500-1557), conhecido como Tartaglia. Depois vieram
os franceses Pierre de Fermat (1601-1665) e Blaise Pascal (1623-1662). Mas chega de história
e vamos ao estudo propriamente dito!
A Análise Combinatória visa desenvolver métodos que permitam contar - de uma forma
indireta - o número de elementos de um conjunto, estando esses elementos agrupados sob
certas condições.
Fatorial
Seja “n” um número inteiro não negativo. Definimos o fatorial de “n” (indicado pelo símbolo
n! ) como sendo:
Para n = 0, teremos: 0! = 1.
Para n = 1, teremos: 1! = 1
Exemplos:
6! = 6.5.4.3.2.1 = 720
4! = 4.3.2.1 = 24
10! = 10.9.8.7.6.5.4.3.2.1
2
Introdução à Análise Combinatória
Universidade Anhembi Morumbi
Existe uma propriedade fundamental do fatorial: o fatorial de um número “n” é igual a este
número multiplicado pelo fatorial do número imediatamente anterior.
Curiosidade
Se você somar 1 ao produto de quatro
números inteiros consecutivos, o resultado
sempre será um quadrado perfeito.
n!=n×(n-1)!
Exemplo: 4!=4×3!=4×3×2×1=24
Princípio fundamental da contagem - PFC
Se determinado acontecimento ocorre em “n” etapas diferentes; e se a primeira etapa pode
ocorrer de k1 maneiras diferentes, a segunda de k2 maneiras diferentes – e assim sucessivamente,
então o número total “T” de maneiras de ocorrer o acontecimento é dado por:
Se determinado acontecimento ocorre em “n” etapas diferentes; e se a primeira etapa pode
ocorrer de k1 maneiras diferentes, a segunda de k2 maneiras diferentes – e assim sucessivamente,
então o número total “T” de maneiras de ocorrer o acontecimento é dado por:
Exemplo:
O DETRAN decidiu que as placas dos veículos do Brasil serão codificadas usando-se 3 letras
do alfabeto e 4 algarismos. Qual o número máximo de veículos que poderá ser licenciado?
Solução:
Usando o raciocínio anterior, imaginemos uma placa genérica do tipo PWR-USTZ.
Como o alfabeto possui 26 letras e nosso sistema numérico possui 10 algarismos (de 0 a 9),
podemos concluir que:
•Para a 1ª posição, temos 26 alternativas, e como pode haver repetição, para a 2ª, e
3ª também teremos 26 alternativas.
3
Introdução à Análise Combinatória
Universidade Anhembi Morumbi
•Com relação aos algarismos, concluímos facilmente que temos 10 alternativas para
cada um dos 4 lugares.
Curiosidade
Dado qualquer número com três
algarismos, repita este número em sua
frente e divida o número assim construído
por 13. Em seguida, pegue o resultado
da divisão e divida por 11, e, novamente,
divida o resultado obtido por 7.
O resultado final será sempre o número
inicialmente escolhido.
Podemos então afirmar que o número total de veículos que podem ser licenciados será igual
a: 26.26.26.10.10.10.10 que resulta em 175.760.000.
Observe que se no país existissem 175.760.001 veículos, o sistema de códigos de emplacamento
teria que ser modificado, já que não existiriam números suficientes para codificar todos os
veículos. Perceberam?
Permutações Simples
Permutações simples de “n” elementos distintos são os agrupamentos formados com todos os
“n” elementos e que diferem uns dos outros pela ordem de seus elementos.
Exemplo: com os elementos A, B, C são possíveis as seguintes permutações:
ABC, ACB, BAC, BCA, CAB e CBA.
O número total de permutações simples de “n” elementos distintos é dado por “n!”, isto é:
Exemplos:
•P6 = 6! = 6.5.4.3.2.1 = 720
•Calcule o número de formas distintas de 5 pessoas ocuparem os lugares de um
banco retangular de cinco lugares.
4
P5 = 5! = 5.4.3.2.1 = 120
Introdução à Análise Combinatória
Universidade Anhembi Morumbi
Anagramas
Denomina-se ANAGRAMA o agrupamento formado pelas letras de uma palavra, que podem
ter ou não significado na linguagem comum.
Por exemplo, os possíveis anagramas da palavra REI são:
REI, RIE, ERI, EIR, IRE e IER.
Definir a quantidade de anagramas de certa palavra ou sequência de letras é um problema
típico de permutações.
• Permutações Com Elementos Repetidos
Se entre os “n” elementos de um conjunto, existem “a” elementos repetidos de um mesmo
tipo, “b” elementos repetidos de outro tipo, “c” elementos repetidos de um terceiro tipo e
assim sucessivamente, o número total de permutações que podemos formar é dado por:
Exemplo:
Determine o número de anagramas da palavra MATEMÁTICA. (não considere o acento)
Temos 10 elementos, com repetição. Observe que a letra “M” está repetida duas vezes, a letra
“A” três, a letra “T”, duas vezes. Na fórmula anterior, teremos: n=10, a=2, b=3 e c=2. Sendo
“K” o número procurado, podemos escrever:
Então, temos 151.200 anagramas possíveis.
5
Introdução à Análise Combinatória
Universidade Anhembi Morumbi
• Arranjos Simples
Dado um conjunto com “n” elementos, chama-se arranjo simples de taxa “k”, a todo
agrupamento de “k” elementos distintos dispostos numa certa ordem. Dois arranjos são
diferem entre si, neste caso, se a ordem de colocação dos elementos for alterada.
Este é um problema típico da montagem de uma fila, em que a alteração da ordem das
pessoas torna a fila diferente.
Assim, no conjunto E = {a, b, c}, teremos:
•Arranjos de taxa 2: ab, ac, bc, ba, ca, cb.
•Arranjos de taxa 3: abc, acb, bac, bca, cab, cba.
Representando o número total de arranjos de “n” elementos tomados “k a k” (taxa “k”) por
As(n, k), teremos a seguinte fórmula:
Observação: é fácil perceber que As(n, n) = n! = Pn, isto é, neste caso o número de arranjos
é igual à permutação de todos os elementos disponíveis.
Exemplo:
Um cofre possui um disco marcado com os dígitos 0, 1, 2, ... 9. O segredo do cofre é
marcado por uma sequência de 3 dígitos distintos. Se uma pessoa tentar abrir o cofre,
quantas tentativas ela deverá fazer (no máximo) para conseguir abri-lo?
6
Introdução à Análise Combinatória
Universidade Anhembi Morumbi
As sequências serão do tipo “xyz”. Para a primeira posição teremos 10 alternativas, para a
segunda, 9 e para a terceira, 8. Podemos aplicar a fórmula de arranjos, mas pelo princípio
fundamental de contagem, chegaremos ao mesmo resultado:
10×9×8=720
Observe que 720 é exatamente igual a As(10,3).
Arranjos Com Repetição
Neste caso, todos os elementos podem aparecer repetidos em cada grupo de p elementos.
A fórmula é mais simples. Para “m” elementos totais, agrupados “p a p”, com possibilidade
de repetição, temos:
Exemplo:
Seja C={A, B, C, D}, m=4 e p=2. Os arranjos com repetição desses 4 elementos tomados
2 a 2 são 16 grupos que onde aparecem elementos repetidos em cada grupo. Todos os
agrupamentos estão no conjunto:
Ar={AA, AB, AC, AD, BA, BB, BC, BD, CA, CB, CC, CD, DA, DB, DC, DD}
7
Introdução à Análise Combinatória
Universidade Anhembi Morumbi
O cálculo seria:
Pelo PFC teríamos que para a primeira opção de posição estão disponíveis 4 letras e para a
segunda posição também, porque as letras podem se repetir. Logo o cálculo seria:
Combinações Simples
Denominamos combinações simples de “n” elementos distintos tomados “k a k” (taxa “k”) aos
subconjuntos formados por “k” elementos distintos escolhidos entre os “n” elementos dados.
Observe que duas combinações são diferentes quando possuem elementos distintos, não
importando a ordem em que os elementos são colocados.
Este é um problema típico da montagem de uma equipe de trabalho, onde todas as pessoas
têm o mesmo perfil. Assim sendo, a ordem da escolha destas pessoas não altera a equipe
formada.
Por exemplo, no conjunto E= {a, b, c, d} podemos considerar:
• Combinações de taxa 2: ab, ac, ad, bc, bd, cd.
• Combinações de taxa 3: abc, abd, acd, bcd.
Combinações de taxa 4: abcd.
Representando por C(n, k) o número total de combinações de “n” elementos tomados “k a k”
(taxa “k”), temos a seguinte fórmula:
8
Introdução à Análise Combinatória
Universidade Anhembi Morumbi
Nota: o número acima é também conhecido como Número Binomial e pode também ser
representado por:
Exemplo:
Uma prova consta de 15 questões das quais o aluno deve resolver 10. De quantas formas
ele poderá escolher as 10 questões?
Observe que a ordem das questões não muda o teste. Logo, podemos concluir que se trata de
um problema de combinação de 15 elementos com taxa 10.
Aplicando simplesmente a fórmula chegaremos a:
O raciocínio pelo PFC é o seguinte:
• Para a primeira escolha o aluno tem 15 opções; para a segunda 14 e assim por
diante (devem ser desconsideradas as perguntas já escolhidas).
• Mas a ordem das perguntas escolhidas não afeta a escolha, logo se deve dividir o
cálculo pelo fatorial de 5, que representa quantas vezes se repete a mesma escolha,
embora com ordenamento diferente.
O resultado seria:
9
Introdução à Análise Combinatória
Universidade Anhembi Morumbi
Propriedade das Combinações Simples
Lembre-se: o número de
combinações com taxas
complementares têm valores iguais.
A propriedade das combinações simples diz respeito ao cálculo de combinações com taxas
complementares:
A demonstração disto é simples:
As expressões finais, em ambos os casos, são as mesmas.
Uma forma de se entender isto – de maneira intuitiva – é se considerar que dentro de um
grupo de 10 pessoas as possibilidades de se escolher 4 pessoas para formar uma equipe de
trabalho são iguais às possibilidades de se deixar 6 pessoas de fora da escolha.
Assim teríamos que:
Combinações Com Repetição
Neste caso, todos os elementos podem aparecer repetidos em cada grupo até “p” vezes.
A fórmula a ser usada é:
10
Introdução à Análise Combinatória
Universidade Anhembi Morumbi
Exemplo:
Seja C={A, B, C, D}
As combinações com repetição desses 4 elementos tomados 2 a 2 são 10 grupos que têm
todas as repetições possíveis de elementos em grupos de 2 elementos, não podendo aparecer
o mesmo grupo com a ordem trocada.
De um modo geral neste caso, todos os agrupamentos com 2 elementos formam um conjunto
com 16 elementos:
Mas para obter as combinações com repetição, deveremos excluir deste conjunto os 6 grupos
que já apareceram antes, pois:
Assim, as combinações com repetição dos elementos tomados 2 a 2, são:
Com o uso da fórmula, temos:
Arranjo ou Combinação
Ao resolvermos uma situação problema de análise combinatória encontraremos um
agrupamento. É nesse momento que aparece a seguinte dúvida: “esse agrupamento é uma
combinação ou um arranjo?”.
11
Introdução à Análise Combinatória
Universidade Anhembi Morumbi
É preciso identificar corretamente que tipo de agrupamento o exercício está trabalhando e
para isso é possível utilizar o seguinte critério:
Escrevemos um dos agrupamentos que o exercício sugere, mudamos a ordem dos seus
elementos. A partir dessa mudança iremos concluir que:
•Será um arranjo se essa mudança alterar o agrupamento original, pois sabemos que
um arranjo pode ser diferenciado tanto pela natureza de seus elementos como pela
ordem desses elementos.
•Será uma combinação se essa mudança não alterar o agrupamento original, pois
sabemos que uma combinação é um arranjo que se difere apenas pela alteração na
natureza de seus elementos.
Exemplo 1:
Um pintor, dispondo de cinco cores diferentes de tinta pretende misturar três delas, em
quantidades iguais, para obter uma nova cor. Quantas novas cores ele poderá obter?
Para verificarmos se os agrupamentos sugeridos são arranjos ou combinações, vamos supor
que as 5 cores que o pedreiro possui são: amarelo, branco, verde, vermelho, azul.
Escolhendo um dos agrupamentos formados pela combinação de 3 tintas teremos:
{azul, amarelo, branco}
Se mudarmos a ordem desses elementos {amarelo, branco, azul} não se irá alterar o
agrupamento, portanto os agrupamentos montados serão combinações simples.
Pra encontrar a quantidade de combinações possíveis basta aplicar a fórmula:
Portanto, é possível montar 10 combinações de 3 tintas com o grupo de 5 tintas.
12
Introdução à Análise Combinatória
Universidade Anhembi Morumbi
Exemplo 2:
O Conselho de Administração de uma empresa precisa nomear nomes para os cargos de
diretoria de três unidades operacionais distintas. Existem 5 candidatos a estas posições.
Quantas opções de nomeação o Conselho Diretor tem?
Para verificarmos se os agrupamentos sugeridos são arranjos ou combinações, vamos supor
que os 5 diretores são: Antônio, Carlos, Jorge, Marcos e João.
Escolhendo um dos agrupamentos formados pela combinação de 3 nomes teremos:
{Unidade 1: Carlos, Unidade 2: José, Unidade 3: João}
Se mudarmos a ordem desses elementos, se irá alterar a nomeação, porque as pessoas
estarão ocupando unidades distintas, embora sejam os mesmos nomes escolhidos. Portanto,
os agrupamentos montados serão arranjos simples.
Pra encontrar a quantidade de arranjos possíveis basta aplicar a fórmula:
Portanto, é possível montar 60 combinações (nomeações) de 3 pessoas escolhidas em um
grupo com 5 pessoas no total.
Mas, se as posições ou cargos fossem totalmente equivalentes, isto é, não houvesse distinção
entre os cargos, se voltaria a ter um problema de combinações.
Agora que você viu o resumo da teoria, vamos resolver os problemas seguintes.
13
Introdução à Análise Combinatória
Universidade Anhembi Morumbi
Exercícios Resolvidos
1. Um coquetel é preparado com duas ou mais bebidas distintas. Se existem 7 bebidas
distintas, quantos coquetéis diferentes podem ser preparados?
Devemos dividir este problema em coquetéis com número de bebidas diferentes e somar o
resultado para cada opção.
•Com 7 bebidas: 1 opção (usamos todas e a ordem não importa, porque todas serão
misturadas).
•Com 6 bebidas: fica 1 de fora. Então basta se analisar quantas opções temos para
tirar uma bebida: 7 opções.
•Com 5 bebidas: é uma combinação simples Cs(7,5): 21 opções.
•Com 4 bebidas: é uma combinação simples Cs(7,4): 35 opções.
•Com três bebidas: é uma combinação simples Cs(7,3): 35 opções.
•Com duas bebidas: é uma combinação simples Cs(7,2): 21 opções.
Total: 1 + 7 + 21 + 35 + 35 + 21 = 120 opções.
2. Sobre uma circunferência são marcados 9 pontos distintos. Quantos triângulos
podem ser construídos com vértices nos 9 pontos marcados?
Trata-se de uma combinação simples, porque a ordem dos pontos não irá alterar o triângulo
formado ao final:
14
Introdução à Análise Combinatória
Universidade Anhembi Morumbi
3. Uma família com 5 pessoas possui um automóvel de 5 lugares. Sabendo que
somente 2 pessoas sabem dirigir, de quantos modos poderão se acomodar para uma
viagem?
Pelo princípio fundamental da contagem teremos:
2 opções para o motorista
4 opções para o banco da frente
3 opções para o canto esquerdo de trás
2 opções para o meio do banco de trás
1 opção para o canto direito de trás
Multiplicando tudo, temos: 2 x 4 x 3 x 2 x 1 = 48 opções.
4. Um salão tem 6 portas. De quantos modos distintos esse salão pode estar aberto?
Para a primeira porta temos duas opções: aberta ou fechada
Para a segunda porta temos também, duas opções, e assim sucessivamente.
Para as seis portas, teremos então, pelo Princípio Fundamental da Contagem - PFC:
Lembrando que uma dessas opções corresponde a todas as duas portas fechadas, teremos
então que o número procurado é igual a 64 - 1 = 63.
A resposta será que o salão pode estar aberto de 63 modos possíveis.
15
Introdução à Análise Combinatória
Universidade Anhembi Morumbi
5. Uma caixa automática de banco só trabalha com notas de 5 e de 10 reais. Um
usuário deseja fazer um saque de R$100,00. De quantas maneiras distintas a caixa
eletrônica poderá fazer esse pagamento?
Este problema é simples, desde que se pense nas possibilidades que se tem de aparecimento
de notas de 10.
• Na pior hipótese, não temos notas de 10.
• Na melhor hipótese, temos 10 notas de 10.
Assim, as possibilidades são de se ter de 0 a 10 notas de 10, isto é, 11 opções.
6. Em uma sala estão 6 rapazes e 5 moças. Quantas comissões nós podemos formar,
tendo em cada comissão 3 rapazes e 2 moças?
Neste problema se precisa perceber que temos duas condições a serem tratadas e que podem
ser combinadas entre si: o grupo de rapazes e o grupo de moças.
Para o grupo de rapazes temos combinações simples de 6, 3 a 3; para as moças, temos
combinações simples de 5, 2 a 2.
O resultado será:
16
Introdução à Análise Combinatória
Universidade Anhembi Morumbi
Exercícios de Fixação
1. Thiago possui 3 blusas diferentes e 2 calças diferentes. De quantas maneiras ele poderá
escolher uma blusa e uma calça para se vestir?
2. Quantos números de dois algarismos podem ser formados utilizando elementos do
conjunto {1, 2, 3}?
3. Quantos números de dois algarismos diferentes (distintos) podem ser formados utilizando
elementos do conjunto {1, 2, 3}?
Quantos números de três algarismos podem ser formados utilizando elementos do
conjunto {1, 2, 3}?
Quantos números de três algarismos diferentes (distintos) podem ser formados utilizando
elementos do conjunto {1, 2, 3}?
Um estádio possui 4 portões. De quantas maneiras diferentes um torcedor pode entrar e
sair desse estádio?
Um estádio possui 4 portões. De quantas maneiras diferentes um torcedor pode entrar e
sair desse estádio utilizando, para sair, um portão diferente do que entrou?
Mariana desenhou uma bandeira retangular de 3 listras e deseja pintá-la, de modo que
duas listras consecutivas não sejam pintadas da mesma cor. Se ela possui 4 lápis de
cores diferentes, de quantas maneiras poderá pintar sua bandeira?
Numa prova havia 4 itens para que os alunos respondessem V (verdadeiro) ou F (falso).
De quantas maneiras diferentes um aluno que vai “chutar” todas as repostas poderá
responder esses itens?
17
Introdução à Análise Combinatória
Universidade Anhembi Morumbi
Um painel luminoso retangular é composto por 5 lâmpadas. De quantas maneiras
diferentes esse painel pode estar iluminado? (considera-se o painel iluminado se, pelo
menos, uma de suas lâmpadas estiver acesa).
Um estudante possui um livro de Matemática, um de Biologia, um de Física, um de
Química, um de História e um de Geografia. Desejando organizá-los lado a lado em uma
instante, de quantos modos poderá fazê-lo?
Considerando os numerais 1, 2, 3, 4, 5 e 6, quantos números de 4 algarismos poderão
ser formados?
Seis amigos decidiram formar uma chapa para concorrer na eleição para a Diretoria
do seu clube. Sabe-se que a Diretoria é formada por um Presidente, um Vice-Presidente,
um Secretário e um Tesoureiro. De quantas maneiras distintas eles poderão formar sua
chapa?(Considere que, se as mesmas pessoas ocuparem cargos diferentes, a chapa não
será a mesma).
De quantas maneiras diferentes um professor poderá formar um grupo de 3 alunos,
escolhidos a partir de um grupo de 6 alunos?
Num grupo onde há 4 médicos e 5 professores, quantas comissões podem ser formadas
com 4 desses profissionais?
Respostas dos Exercício
6 maneiras.
2. 9 números.
3. 6 números.
4. 27 números
18
Introdução à Análise Combinatória
Universidade Anhembi Morumbi
6 números
16 maneiras
12 maneiras
8. 36 maneiras
9.16 maneiras
10. 31 maneiras
11. 720 modos
12. 1296 números
13. 360 maneiras
14. 20 maneiras
15. 126 comissões
Bibliografia
IEZZI, G. Fundamentos da Matemática Elementar, São Paulo, 1993.
IEZZI, G. et al. Matemática, São Paulo, 1995.
SILVA, S. M. D. Matemática Básica Para Cursos Superiores, São Paulo, 2002.
ZOLD, H. H. N.; CORRÊA, S. Novíssimo Curso Vestibular, São Paulo, I e II, 1991.
19
Introdução à Análise Combinatória
Universidade Anhembi Morumbi
Este documento é de uso exclusivo da Universidade
Anhembi Morumbi, está protegido pelas leis de
Direito Autoral e não deve ser copiado, divulgado
ou utilizado para outros fins que não os pretendidos
pelo autor ou por ele expressamente autorizados.
20
Introdução à Análise Combinatória
Universidade Anhembi Morumbi
Download

Introdução à Análise Combinatória