Lista Análise combinatória permutações e combinações

Prévia do material em texto

1 
 
Permutações e Combinações 
Professor: Robson Coelho Neves 
 
Dois Problemas Comuns de Contagens 
 
I) Problema das Permutações Simples: De quantos modos podemos ordenar em fila n objetos 
distintos? 
 
Solução: 
1D
 : Escolha do objeto que ocupará o 1º lugar da fila => 
1x
n. 
2D
 : Escolha do objeto que ocupará o 2º lugar da fila => 
2x
n-1. 
3D
 : Escolha do objeto que ocupará o 3º lugar da fila => 
3x
n-2. 
.................................................................................................... 
 
nD
 : Escolha do objeto que ocupará o nº lugar da fila => 
nx
n-(n-1) = 1. 
 Pelo PFC, a resposta é 
   1...2n.1n.n 
. 
 
 Cada ordem que se dá aos n objetos é chamada de uma Permutação Simples. Fazendo 
nP
= total 
de possibilidades de ordenações, tem-se que 
    .1...2n1nnPn 
 Esse produto, cujos fatores 
variam sucessivamente de 1 a n, são comuns em modelos de contagem e são denotados por 
!n
(lê-se: 
n fatorial). Assim, 
 
!nPn  
 
Observação: Como veremos mais adiante, é conveniente adotarmos a seguinte definição:
.1!0  
 
Exemplo 1) Quantos são os anagramas da palavra “calor”? Quantos começam por consoante? 
 
Solução: 
 Cada anagrama corresponde a uma ordenação das 5 letras. Logo, 120!5P5 
= total de 
anagramas. Dentre esses, 
72!4.3 
 começam por consoante (entendeu o cálculo?). 
 
Exemplo 2) De quantos modos podemos arrumar em fila, numa prateleira de uma estante, 5 livros 
diferentes de Matemática, 4 livros diferentes de Estatística e 2 livros diferentes de Cálculo, de modo que 
livros da mesma matéria permaneçam juntos? 
 
Solução: 
1D
 : Ordenação dos 3 conjuntos de livros => 
31 Px 
. 
2D
 : Ordenação dos 5 livros de Matemática => 
.Px 52 
 
3D
 : Ordenação dos 4 livros de Estatística => 
.Px 43 
. 
4D
 : Ordenação dos 2 livros de Cálculo => 
.Px 24 
 
 
 Pelo PFC, tem-se que o total é 
.34560PPPP 2453  
 
 
 
 
 
 
 2 
Exemplo 3) Quantos são os anagramas da palavra “BOTAFOGO”? 
 
Solução: 
 Se considerarmos que as 3 letras “O” são diferentes, teremos que  !8P8 total de anagramas. 
Ocorre que esses 
!8
anagramas é composto de grupos de 
!3
 anagramas repetidos, pois a permutação 
entre si das letras “O” não geram novos anagramas. Por exemplo, representando por 
321 O,O,O
as três 
letras “O”, tem-se que os 
6!3 
 anagramas 
TABOGOFO 321
, 
,TABOGOFO 231
 
TABOGOFO 312
, 
TABOGOFO 132
, 
TABOGOFO 213
e 
TABOGOFO 123
são iguais. 
 Assim, fazendo t= total de anagramas, tem-se que 
.6720
!3
!8
tt!3!8 
 
 Podemos generalizar o exemplo 3 e a sua solução da seguinte maneira: 
 
Teorema 1) O total de ordenações possíveis de n objetos, dentre os quais 1n são iguais a 1 , 2n são 
iguais a 
2
,..., 
kn
são iguais a 
k
, que será simbolizado por 
k21 n,,n,n
nP

, é dado por 
.
!n...!n!.n
!n
P
k21
n,,n,n
n
k21


 
 
 
Exemplo 4) De quantos modos 5 crianças podem formar uma roda de ciranda? 
 
Solução: Representemos as 5 crianças por A,B,C,D,E. 
 Se considerarmos que cada permutação das 5 crianças gera uma roda (peça a 1ª criança de uma 
fila (permutação) qualquer fechar a roda com a 5ª criança dessa mesma fila), tem-se que 
!5P5 
 é o 
total de rodas. Ocorre que essas 5! permutações são compostas de grupos de 5 rodas repetidas pois, 
por exemplo, a permutação BACDE resulta também nas rodas ACDEB, CDEBA, DEBAC e EBACD, que 
são a mesma roda. 
 Assim, fazendo t=total de rodas, tem-se que 
24!4
5
!45
5
!5
tt5!5 


. 
 Podemos generalizar o exemplo 4 e a sua solução da seguinte maneira: 
 
Teorema 2) Cada possível ordenação em círculo de n objetos, de modo que disposições que possam 
coincidir por rotação sejam consideradas iguais, é chamada de uma Permutação Circular. O total de 
permutações circulares de n objetos distintos é notado por 
 nPC
 e é dado por 
   !1n
n
!n
PC n 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 3 
II) Problema das Combinações Simples: De quantos modos podemos selecionar p objetos
 np0 
distintos entre n objetos distintos dados? 
 
Solução: Comecemos ordenando os p objetos. 
 
1D
 : Escolha do objeto que ocupará o 1º lugar => 
1x
n. 
2D
 : Escolha do objeto que ocupará o 2º lugar => 
2x
n-1. 
3D
 : Escolha do objeto que ocupará o 3º lugar => 
3x
n-2. 
................................................................................................ 
 
1pD 
 : Escolha do objeto que ocupará o (p-1)º lugar => 
   .2pn2pnx 1p 
 
 
pD
 : Escolha do objeto que ocupará o pº lugar => 
   .1pn1pnxp 
 
 Pelo PFC, tem-se que existem 
    1pn...2n.1n.n 
 ordenações possíveis para os p 
objetos. Ocorre que esse total de ordenações é composta de 
!p
seleções iguais, pois quando 
permutamos os p elementos de uma ordenação não estamos definindo seleções diferentes. Assim, 
fazendo t=total de seleções, tem-se que 
    
    
.
!p
1pn...2n.1n.n
tt!p1pn...2n.1n.n


 
 
 Cada uma dessas seleções é o que chamamos de uma Combinação Simples de classe p dos n 
objetos. O total de combinações, que é denotado por 
p
nC
 ou 






p
n
, em linguagem de fatorial pode ser 
escrito como segue: 
 
 
           
   
.
!p!pn
!n
C
!pn!p
!pn1pn...2n.1n.n
!p
1pn...2n.1n.n
C pn
p
n







 
 
 
Observação: Como 
1CC nn
0
n 
, segue que para o resultado acima valer mesmo quando p = 0 e 
p = n, é necessário que fatorial de zero seja 1 (tal como foi observado quando definimos fatorial) pois 
 
   
.1!01
!0!n
!n
!n!nn
!n
!0!0n
!n
n
n
0
n CC





 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 4 
Exemplo 5) Com 5 homens e 4 mulheres, quantas comissões de 5 pessoas, com pelo menos 3 
homens, podem ser formadas? 
 
Solução: Precisaremos considerar três hipóteses distintas. 
Hipótese I) A comissão tem 3 homens e duas mulheres. 
1D
 : Seleção dos 3 homens => 
3
51 Cx 
. 
2D
 : Seleção das 2 mulheres => 
2
42 Cx 
. 
 Pelo PFC, tem-se um total 
2
4
3
5 CC 
 de comissões desse tipo. 
 
Hipótese II) A comissão tem 4 homens e 1 mulher. 
1D
 : Seleção dos 4 homens => 
4
51 Cx 
. 
2D
 : Seleção da mulher => 
1
42 Cx 
. 
 Pelo PFC, tem-se um total 
1
4
4
5 CC 
 de comissões desse tipo. 
 
Hipótese III) A comissão tem 5 homens e nenhuma mulher, o que pode ser selecionada de 
0
4
5
5 CC 
 
modos. 
 
 Concluindo, o total de comissões é 
.81CCCCCC 04
5
5
1
4
4
5
2
4
3
5 
 
 
 
Exemplo 6) Tem-se 5 pontos sobre uma reta r e 8 pontos sobre uma reta s paralela a r. a) Quantos 
triângulos e b) quantos quadriláteros convexos podem ser formados com vértices nesses pontos? 
Soluções: 
a) Selecionando 1 ponto em r e 2 em s, podemos formar 
2
8
1
5 CC 
 triângulos e, selecionando 2 pontos 
em r e 1 em s, podemos formar 
1
8
2
5 CC 
. Assim, 
2
8
1
5 CC 
+
1
8
2
5 CC 
=220 é o total de triângulos. 
 
b) Selecionando 2 pontos em r e 2 em s, podemos formar 
280CC 28
2
5 
 quadriláteros convexos. 
 
Exercícios 
1) Quantas são as soluções inteiras e não negativas da equação 
?5zyx 
E da inequação 
?5zyx  
 
2) De quantos modospodemos comprar 3 sorvetes em um padaria que os oferece em 6 sabores 
distintos? 
 
3) De quantos modos é possível colocar 8 pessoas em fila de modo que duas dessas pessoas, Vera e 
Paulo, não fiquem juntas? 
 
4) De quantos modos é possível dividir 15 atletas em três times de 5 atletas, denominados Esporte, Tupi 
e Minas? 
 
5) Um campeonato é disputado por 12 clubes em rodadas de 6 jogos cada. De quantos modos é 
possível selecionar os jogos da primeira rodada? 
 
6) Uma fila de assentos no cinema tem 10 poltronas de 2 lugares. De quantos modos 3 casais podem 
se sentar nessas poltronas de modo que nenhum marido se sente separado de sua mulher? 
 
7) Quantos são os anagramas da palavra “paraguaio” que não possuem consoantes adjacentes? 
 
8) De quantos modos podemos formar uma roda de ciranda com 5 meninos e 5 meninas de modo que 
pessoas do mesmo sexo não fiquem juntas? 
 5 
9) Uma indústria fabrica 5 tipos de balas que são vendidas em caixas de 20 balas, de um só tipo ou 
sortidas. Quantos tipos de caixas podem ser montadas? 
 
10) Num concurso com 12 candidatos serão distribuídos prêmios de R$ 100,00, R$ 600,00 e R$ 250,00 
aos primeiros colocados. De quantos modos o prêmio pode ser distribuído? 
 
11) Num vagão de trem, existem um banco a esquerda com 5 lugares e um banco a direita também 
com 5 lugares. De quantas maneiras 8 pessoas podem se sentar nesses lugares respeitando as 
seguintes preferências: 3 deles preferem sentar no banco a esquerda, 2 preferem sentar no banco a 
direita e 3 não tem preferência?