• Na Mecânica Estatística, será muito útil a utilização dos
conceitos básicos de Análise Combinatória e Probabilidade.
• Por ex., uma garota vai sair com suas amigas e, para
escolher a roupa que usará, separou 2 saias e 3 blusas. De
quantas maneiras diferentes ela pode se vestir?
• Decisões a serem tomadas:
d1: escolher uma dentre 3 blusas
d2: escolher uma dentre 2 saias
Total de opções: 3 x 2 = 6
• Restaurante prepara 4 pratos quentes (frango, peixe, carne
assada, salsichão), 2 saladas (verde e russa) e 3 sobremesas
(sorvete, romeu e julieta, fruta). De quantas maneiras
diferentes um freguês pode se servir consumindo um prato
quente, uma salada e uma sobremesa?
• Observe que agora temos 3 níveis de decisão:
d1: escolher um dentre os 4 tipo de pratos quentes.
d2: escolher uma dentre as 2 variedades de salada.
d3: escolher uma das 3 sobremesas oferecidas.
• Contando, temos: 4 · 2 · 3 = 24 opções de cardápio.
• A representação gráfica é ilustrativa: nota-se claramente os
três níveis de decisão d1, d2 e d3, com os vários cardápios.
• Objetivo: saber as combinações possíveis e calcular todas as
possibilidades sem precisar enumerá-las. Principalmente
quando for muito grande o número de possibilidades!
• As técnicas da análise combinatória nos ajudam a resolver
problemas deste tipo.
• Porém é preciso plena compreensão da situação descrita e
saber exatamente o que se busca.
• Por exemplo, no problema anterior, supor que o restaurante
possua um preço mais barato para quem escolher frango ou
salsichão, com salada verde. De quantas maneiras diferentes se
pode almoçar pagando menos?
• Temos agora restrições sobre as decisões d1 e d2 anteriores:
d1: escolher um dentre 2 pratos quentes (frango ou salsichão).
d2: escolher salada verde (apenas uma opção).
d3: escolher uma das 3 sobremesas oferecidas.
• Há 2 · 1 · 3 = 6 maneiras de montar cardápios econômicos.
• Outro ex.: Quantos números naturais, com 3 algarismos
distintos __ __ __ existem (entre 100 e 999)?
• Observando que o algarismo da ordem das centenas não
pode ser zero, temos então três decisões a serem tomadas:
d1: escolher o algarismo da centena diferente de zero
(9 opções).
• Portanto, o total de números formados será 9 · 9 · 8 = 648
C D U
d2: escolher o algarismo da dezena diferente do que já foi
escolhido para ocupar a centena (9 opções).
d3: escolher o algarismo da unidade diferente dos que já foram
utilizados (8 opções).
• Supor que agora, no exemplo anterior, desejássemos contar,
dentre os 648 números de 3 algarismos distintos, apenas os
pares (terminados em 0, 2, 4, 6 e 8). Como proceder?
• Note que o algarismo da unidade tem 5 possibilidades (0, 2,
4, 6 e 8). Agora, se o último algarismo for zero então o
primeiro algarismo poderá ser escolhido de 9 modos. Se o zero
não foi usado como último algarismo, o primeiro terá 8
possibilidades (porque não podemos usar o zero na primeira
casa, nem o algarismo já empregado na última casa).
• Como resolver o problema? Há 3 maneiras de se fazer isto:
__ __ __
C D U
a) Verificar separadamente as possibilidades,
com o último algarismo (da unidade) sendo
zero ou não:
• Terminando em zero temos 9 modos de escolher o algarismo
da centena e 8 modos de escolher o algarismo da dezena, num
total de 9 · 8 · 1 = 72 números.
• Não terminando zero temos 4 alternativas para o último
algarismo (2, 4, 6, ou 8), 8 para o primeiro algarismo (não
podemos usar o zero, nem o algarismo já usado na última
casa) e 8 para o algarismo do meio (não podemos usar os dois
algarismos já empregados). Logo, temos 8 · 8 · 4 = 256
números terminados em um algarismo diferente de zero
• A resposta final será, portanto, 72 + 256 = 328 números.
__ __ __
C D U
b) Ignorando restrições
• Ignorando o fato de zero não poder ocupar a casa da
centena, temos 5 modos de escolher o último algarismo,
9 modos de escolher o primeiro e 8 modos de escolher o
do meio, num total 5 · 8 · 9 = 360 números.
• Estas 360 possibilidades incluem números começados por
zero, que devem ser descontados.
• Começando em zero temos 1 modo de escolher o primeiro
algarismo (0), 4 modos de escolher o último (2, 4, 6 ou 8) e 8
modos de escolher o do meio (não podemos usar os dois
algarismos já empregados nas casas extremas), num total de
1 · 4 · 8 = 32 números.
• A resposta é, portanto, 360 - 32 = 328 números.
c) É claro que também podemos resolver o problema
determinando todos os números de 3 algarismos distintos
(c.d.u. 9 · 9 · 8 = 648 números, como no início) e subtrair os
ímpares de 3 algarismos distintos (5 na última casa, 8 na
primeira e 8 na segunda), num total de 5 · 8 · 8 = 320 números.
• Assim, a resposta final seria: 648 - 320 = 328 números
__ __ __
C D U
PERMUTAÇÃO
• Muitas vezes precisamos saber de quantas maneiras
podemos arrumar os elementos de um dado conjunto. Como,
então, determinar o número total de possibilidades?
• Por exemplo, de quantas maneiras podemos arranjar 5
pessoas P1, P2, P3, P4 e P5 em fila indiana?
• As soluções serão do tipo:
... etc.
• Na escolha de uma pessoa para a 1ª posição temos 5 opções.
Para o 2º lugar, como uma já foi escolhida, temos 4 opções.
Para o 3º lugar sobram 3 pessoas a serem escolhidas. Para o 4º
lugar 2 pessoas e, para o último lugar na fila, sobra apenas a
pessoa que ainda não foi escolhida.
• Ou seja, teremos: 5 · 4 · 3 · 2 · 1 = 120 opções.
Definição: Dado um conjunto formado por n elementos,
chama-se permutação desses n elementos qualquer seqüência
na qual apareçam todos os componentes do conjunto.
• Cálculo do número de
permutações: o número de modos
de ordenar n objetos distintos é: ( n!)
(iv)
• Lembrando algumas regras básicas:
(iii)
(i)
(ii)
Ex.: Quantos são os anagramas da palavra MARTELO?
• Cada anagrama da palavra MARTELO é uma ordenação
das letras M, A, R, T, E, L, O (como as pessoas na fila);
assim, o número de anagramas são as permutações possíveis.
• Ou seja: 7! = 7 · 6 · 5 · 4 · 3 · 2 · 1 = 5040
(v) 0! = 1
• Novamente, observe que em alguns problemas (os quais
envolvem permutações dos elementos de um conjunto) podem
existir restrições que devem ser levadas em conta.
Ex.: Quantos anagramas, que começam e terminam com
consoantes, podemos formar a partir da palavra MARTELO?
• A consoante inicial pode ser escolhida de 4 maneiras e a
consoante final de 3 maneiras. As 5 letras restantes serão
permutadas no espaço entre as duas consoantes já escolhidas.
Portanto, a resposta é 4 · 3 · 5! = 1440 anagramas.
• Outro ex.: Um grupo de cinco pessoas decide viajar de
carro, mas apenas duas sabem dirigir. De quantas maneiras é
possível dispor as cinco pessoas durante a viagem?
• O banco do motorista pode ser ocupado por uma das 2
pessoas que sabem guiar o carro e as outras 4 podem ser
permutadas pelos quatro lugares restantes, então teremos:
2 · 4! = 2 · 24 = 48 maneiras
• Por estes exemplos vemos que em problemas envolvendo
permutações dos elementos de um conjunto, com restrições,
deve-se ter o cuidado de leva-las corretamente em conta.
Elementos distinguíveis e indistinguíves
Permutação circular
• Ex. A palavra MADEIRA possui sete letras, sendo duas
letras A e cinco letras distintas: M, D, E, I, R. Quantos
anagramas diferentes podemos formar com a palavra?
• Agora, para localizar as duas letras A, precisamos de 2
posições; sendo, para a primeira letra A, 7 posições
disponíveis, e 6 posições disponíveis para a segunda letra A
(pois uma das 7 posições disponiveis já foi ocupada).
• Nas 5 posições restantes devemos permutar as outras 5 letras
distintas, ou seja, 5! = 120 possibilidades.
• Se desconsiderássemos o fato que, no caso, temos 2
elementos indistinguíveis, a resolução seria: 7! = 5040
• Agora, como as 2 letras A são indistinguíveis, para não
contarmos duas vezes as posições que formam o mesmo
anagrama (como, por exemplo, escolher a 2ª e 5ª posições e
a 5ª e 2ª posições), uma divisão por 2 se faz necessária:
anagramas da palavra MADEIRA
• Sendo que poderíamos trocar o numerador: 7 · 6 · 5! = 7!
• Mas, e no caso de termos mais elementos indistinguíveis no
conjunto, como na determinação dos anagramas da palavra
PROPRIO (que também possui 7 letras, mas com os P, R e O
repetidos)? Veremos isto na próxima aula.