aula_analise_combinatoria

Prévia do material em texto

Análise combinatória
Princípios aditivo e multiplicativo, fatorial, permutação, arranjo e combinação.
Prof. Edvaldo Reis
1 Resumo
Princípio Aditivo
O princípio aditivo afirma que, se uma tarefa pode ser realizada de m maneiras e uma segunda tarefa
pode ser realizada de n maneiras, e as duas tarefas não podem ser realizadas simultaneamente, então há
m+ n maneiras de realizar uma das tarefas.
Exemplo:
Uma pessoa pode escolher entre 3 tipos de sobremesa ou 4 tipos de bebida em um restaurante.
Quantas escolhas diferentes essa pessoa tem?
3 + 4 = 7 maneiras
Princípio Fundamental da Contagem
O princípio fundamental da contagem afirma que, se uma tarefa pode ser realizada em m maneiras
e uma segunda tarefa pode ser realizada em n maneiras, então há m × n maneiras de realizar ambas as
tarefas.
Generalizando, se um evento ocorre em n etapas sucessivas, sendo k1 o número de possibilidades de
ocorrência da primeira etapa e, para cada ocorrência da primeira etapa, são possíveis k2 modos de ocorrência
da segunda etapa; para cada ocorrência da primeira e da segunda etapa são possíveis k3 modos de ocorrência
da terceira etapa, e assim por diante até a etapa de ordem n, que pode ocorrer de kn modos, então o número
de modos pelos quais o evento pode ocorrer é dado por:
k1 · k2 · k3 · ... · kn
Exemplo:
Uma pessoa pode escolher entre 3 tipos de entrada e 4 tipos de prato principal em um restau-
rante. Quantas combinações diferentes essa pessoa pode escolher?
3× 4 = 12 combinações
Fatorial
O fatorial de um número natural n é o produto de todos os inteiros positivos menores ou iguais a n.
Denotado por n!.
Dado um número natural n, n > 1, definimos:
1
n! = n · (n− 1) · (n− 2) · ... · 3 · 2 · 1
Definimos, ainda:
1! = 1 e 0! = 1
Exemplo:
Calcule 5!:
5! = 5× 4× 3× 2× 1 = 120
Permutação Simples
Permutação simples é o número de maneiras de ordenar n objetos distintos. Denotado por P (n) = n!.
Exemplo:
Quantas maneiras diferentes podemos ordenar as letras A, B e C?
P (3) = 3! = 6 maneiras
Permutação com Repetição
Quando em uma permutação de n termos tem-se a elementos repetidos de um tipo, b elementos
repetidos de um outro tipo, c elementos repetidos de um terceiro tipo e assim sucessivamente, o número
de permutações com elementos repetidos que podemos formar é dado por:
P a,b,c,...
n =
n!
a! · b! · c! · ...
Exemplo:
Quantas maneiras diferentes podemos ordenar as letras A, A e B?
P 2
3 =
3!
2!
=
6
2
= 3 maneiras
Arranjo
Arranjo é o número de maneiras de escolher e ordenar k objetos de um conjunto de n objetos distintos.
Denotado por A(n, k). Calculamos An,k =
n!
(n− k)!
.
Exemplo:
Quantas maneiras diferentes podemos escolher e ordenar 2 letras do conjunto {A, B, C}?
A(3, 2) =
3!
(3− 2)!
=
3× 2× 1
1
= 6 maneiras
2
Combinação
Combinação é o número de maneiras de escolher k objetos de um conjunto de n objetos distintos, sem
se importar com a ordem. Denotado por C(n, k) ou
(
n
k
)
. Cn,k =
n!
k! · (n− k)!
Exemplo:
Quantas maneiras diferentes podemos escolher 2 letras do conjunto {A, B, C}?
C(3, 2) =
(
3
2
)
=
3!
2!× (3− 2)!
=
3× 2× 1
2× 1× 1
= 3 maneiras
2 Exercícios
1. (ENEM-PPL/2020-adaptada) A prefeitura de
uma cidade está renovando os canteiros de flo-
res de suas praças. Entre as possíveis varieda-
des que poderiam ser plantadas, foram esco-
lhidas cinco: amor-perfeito, cravina, petúnia,
margarida e lírio. Em cada um dos canteiros,
todos com composições diferentes, serão utili-
zadas somente três variedades distintas, não
importando como elas serão dispostas. Um
funcionário deve determinar os trios de varie-
dades de flores que irão compor cada canteiro.
De acordo com o disposto, a quantidade de
trios possíveis é dada por
A) 5
B) 5 · 3
C)
5!
(5− 3)!
D)
5!
(5− 3)!
· 2!
E)
5!
(5− 3)!
· 3!
2. (ENEM/2019) Durante suas férias, oito ami-
gos, dos quais dois são canhotos, decidem re-
alizar um torneio de vôlei de praia. Eles preci-
sam formar quatro duplas para a realização do
torneio. Nenhuma dupla pode ser formada por
dois jogadores canhotos.
De quantas maneiras diferentes podem ser for-
madas essas quatro duplas?
(A) 69
(B) 70
(C) 90
(D) 104
(E) 105
3. Uma empresa confecciona e comercializa um
brinquedo formado por uma locomotiva, pin-
tada na cor preta, mais 12 vagões de iguais
formato e tamanho, numerados de 1 a 12. Dos
12 vagões, 4 são pintados na cor vermelha, 3
na cor azul, 3 na cor verde e 2 na cor amarela.
O trem é montado utilizando-se uma locomo-
tiva e 12 vagões, ordenados crescentemente se-
gundo suas numerações, conforme ilustrado na
figura.
De acordo com as possíveis variações nas colo-
rações dos vagões, a quantidade de trens que
podem ser montados, expressa por meio de
combinações, é dada por:
a) C12
4 × C12
3 × C12
3 × C12
2
b) C12
4 + C8
3 + C5
3 + C2
2
c) C12
4 × 2× C8
3 × C5
2
d) C12
4 + 2 + C12
3 + C12
3
e) C12
4 × C8
3 × C5
3 × C2
2
4. O Salão do Automóvel de São Paulo é um
evento no qual vários fabricantes expõem seus
modelos mais recentes de veículos, mostrando,
principalmente, suas inovações em design e
tecnologia.
Disponível em: http://g1.globo.com. Acesso
em: 4 fev. 2015 (adaptado).
Uma montadora pretende participar desse
evento com dois estandes, um na entrada e
outro na região central do salão, expondo, em
cada um deles, um carro compacto e uma ca-
minhonete.
3
Para compor os estandes, foram disponibiliza-
dos pela montadora quatro carros compactos,
de modelos distintos, e seis caminhonetes de
diferentes cores para serem escolhidos aqueles
que serão expostos. A posição dos carros den-
tro de cada estande é irrelevante.
Uma expressão que fornece a quantidade de
maneiras diferentes que os estandes podem ser
compostos é:
A) A10
4
B) C10
4
C) C4
2 × C6
2 × 2× 2
D) A4
2 × A6
2 × 2× 2
E) C4
2 × C6
2
5. Em uma Olimpíada de Matemática, foram dis-
tribuídas várias medalhas de ouro, várias de
prata e várias de bronze. Cada participante
premiado pôde receber uma única medalha.
Aldo, Beto, Carlos, Diogo e Elvis participaram
dessa olimpíada e apenas dois deles foram pre-
miados. De quantas formas diferentes pode ter
acontecido essa premiação?
6. De quantas maneiras três casais podem se sen-
tar em um banco de modo que cada marido
fique sempre ao lado de sua mulher?
7. Após digitar um número de seis algarismos em
sua calculadora, Cecília observou que dois al-
garismos 9 que ela havia digitado não aparece-
ram no visor; o que apareceu foi 2017. Quan-
tas são as possibilidades para o número que ela
digitou?
8. Cristina gosta de adivinhar em quais casinhas
seus ratinhos Mingo, Lingo e Tingo irão se es-
conder, após ser aberta a gaiola em que eles
moram. As casinhas são numeradas de 1 a 6
e dois ou mais ratinhos podem se esconder na
mesma casinha. Ela registra suas previsões em
cartões como os da figura, marcando um X em
cada linha.
(A) De quantas maneiras Cristina pode preen-
cher um cartão?
(B) De quantas maneiras ela pode preencher
um cartão, supondo que os ratinhos se escon-
derão em três casinhas diferentes?
(C) De quantas maneiras ela pode preencher
um cartão, supondo que dois ratinhos se es-
conderão em uma mesma casinha e o terceiro
em uma casinha diferente?
9. (ENEM - 2017) Para cadastrar-se em um site,
uma pessoa precisa escolher uma senha com-
posta por quatro caracteres, sendo dois alga-
rismos e duas letras (maiúsculas ou minúscu-
las). As letras e os algarismos podem estar
em qualquer posição. Essa pessoa sabe que o
alfabeto é composto por 26 letras e que uma
letra maiúscula difere da minúscula em uma
senha.
O número total de senhas possíveis para o ca-
dastramento nesse site é dado por:
a) 102 · 262
b) 10 · 522
c) 102 · 522 · 4!
2!
d) 102 · 262 · 4!
2! · 2!
e) 102 · 522 4!
2! · 2!
10. O designer português Miguel Neiva criou um
sistema de símbolos que permite que pessoas
daltônicas identifiquem cores. O sistema con-
siste na utilização de símbolos que identifi-
cam as cores primárias (azul, amarelo e verme-
lho). Além disso, a justaposição de dois desses
simbolos permite identificarcores secundárias
(como o verde, que é o amarelo combinado
4
com o azul). O preto e o branco são identifica-
dos por pequenos quadrados: o que simboliza
o preto é cheio, enquanto o que simboliza o
branco é vazio. Os símbolos que representam
preto e branco também podem estar associa-
dos aos simbolos que identificam cores, signi-
ficando se estas são claras ou escuras.
Folha de São Paulo
De acordo com o texto, quantas cores podem
ser representadas pelo sistema proposto?
a) 14
b) 18
c) 2
d) 21
e) 23
11. Os bilhetes de uma rifa são numerados de 1000
a 9999. Marcelo comprou todos os bilhetes nos
quais o algarismo sete aparece exatamente três
vezes e o zero não aparece. Quantos bilhetes
Marcelo comprou?
12. Uma família composta por sete pessoas adul-
tas, após decidir o itinerário de sua viagem,
consultou o site de uma empresa aérea e cons-
tatou que o voo para a data escolhida estava
quase lotado. Na figura, disponibilizada pelo
site, as poltronas ocupadas estão marcadas
com X e as únicas poltronas disponíveis são
as mostradas em branco.
O número de formas distintas de se acomodar
a família nesse voo é calculado por
a)
9!
2!
b)
9!
7!× 2!
c) 7!
d)
5!
2!
× 4!
e)
5!
4!
× 4!
3!
13. Vítor tem 24 cartões, sendo oito azuis, oito
brancos e oito verdes. Para cada cor, ele nu-
merou os cartões de 1 a 8.
A) De quantas maneiras Vítor pode escolher
2 cartões azuis de modo que a soma de seus
números seja igual a 9?
B) De quantas maneiras Vítor pode escolher 2
cartões de modo que a soma de seus números
seja igual a 9?
C) De quantas maneiras Vítor pode escolher 3
cartões de modo que a soma de seus números
seja igual a 9?
14. (Enem 2017) Uma empresa construirá sua pá-
gina na internet e espera atrair um público de
aproximadamente um milhão de clientes. Para
acessar essa página, será necessária uma se-
nha com formato a ser definido pela empresa.
Existem cinco opções de formato oferecidas
pelo programador, descritas no quadro, em que
"L"e "D"representam, respectivamente, letra
maiúscula e dígito.
Opção Formato
I LDDDDD
II DDDDDD
III LLDDDD
IV DDDDD
V LLLDD
As letras do alfabeto, entre as 26 possíveis,
bem como os dígitos, entre os 10 possíveis,
podem se repetir em qualquer das opções.
A empresa quer escolher uma opção de formato
cujo número de senhas distintas possíveis seja
superior ao número esperado de clientes, mas
que esse número não seja superior ao dobro do
número esperado de clientes.
A opção que mais se adéqua às condições da
empresa é
a) I.
b) II.
c) III.
d) IV.
e) V.
15. Torneios de tênis, em geral, são disputados em
sistema de eliminatória simples. Nesse sistema,
são disputadas partidas entre dois competido-
res, com a eliminação do perdedor e promoção
do vencedor para a fase seguinte. Dessa forma,
5
se na 1ª fase o torneio conta com 2n competi-
dores, então na 2ª fase restarão 2n−1 compe-
tidores, e assim sucessivamente até a partida
final.
Em um torneio de tênis, disputado nesse sis-
tema, participam 128 tenistas.
Para definir o campeão desse torneio, o número
de partidas necessárias é dado por A) 2× 128
B) 64 + 32 + 16 + 8 + 4 + 2
C) 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1
D) 128 + 64 + 32 + 16 + 8 + 4 + 2
E) 64 + 32 + 16 + 8 + 4 + 2 + 1
16. (Enem 2017) Como não são adeptos da prá-
tica de esportes, um grupo de amigos resolveu
fazer um torneio de futebol utilizando video-
game. Decidiram que cada jogador joga uma
única vez com cada um dos outros jogadores.
O campeão será aquele que conseguir o maior
número de pontos. Observaram que o número
de partidas jogadas depende do número de jo-
gadores, como mostra o quadro:
Quantidade de
jogadores
Número de parti-
das
2 1
3 3
4 6
5 10
6 15
7 21
Se a quantidade de jogadores for 8, quantas
partidas serão realizadas?
A) 64
B) 56
C) 49
D) 36
E) 28
17. (Enem 2013) Um banco solicitou aos seus cli-
entes a criação de uma senha pessoal de seis
dígitos, formada somente por algarismos de 0
a 9, para acesso à conta-corrente pela inter-
net. Entretanto, um especialista em sistemas
de segurança eletrônica recomendou à direção
do banco recadastrar seus usuários, solicitando,
para cada um deles, a criação de uma nova se-
nha com seis dígitos, permitindo agora o uso
das 26 letras do alfabeto, além dos algarismos
de 0 a 9. Nesse novo sistema, cada letra maiús-
cula era considerada distinta de sua versão mi-
núscula. Além disso, era proibido o uso de ou-
tros tipos de caracteres.
Uma forma de avaliar uma alteração no sis-
tema de senhas é a verificação do coeficiente
de melhora, que é a razão do novo número de
possibilidades de senhas em relação ao antigo.
O coeficiente de melhora da alteração reco-
mendada é
A)
626
106
B)
62!
10!
C)
62! · 4!
10! · 56!
D) 62!− 10!
E) 626 − 106
18. Quantas senhas com 4 algarismos diferentes
podemos escrever com os algarismos 1, 2, 3,
4, 5, 6, 7, 8,e 9?
19. Um técnico de um time de voleibol possui a
sua disposição 15 jogadores que podem jogar
em qualquer posição. De quantas maneiras ele
poderá escalar seu time de 6 jogadores?
20. De quantas maneiras diferentes, uma pessoa
pode se vestir tendo 6 camisas e 4 calças?
21. De quantas maneiras diferentes 6 amigos po-
dem sentar em um banco para tirar uma foto?
22. Em uma competição de xadrez existem 8 joga-
dores. De quantas formas diferentes poderá ser
formado o pódio (primeiro, segundo e terceiro
lugares)?
23. Uma equipe de trabalho é formada por 6 mu-
lheres e 5 homens. Eles pretendem se organi-
zar em grupo de 6 pessoas, com 4 mulheres e 2
homens, para compor uma comissão. Quantas
comissões podem ser formadas?
6