Análise combinatória

Prévia do material em texto

Hewlett-Packard 
 
PFC 
Aulas 01 a 
Elson Rodrigues, Gabriel Carvalho e Paulo Luiz 
 
 
Sumário 
FATORIAL ................................................................................................................................................................. 2 
FATORIAL ................................................................................................................................................................. 2 
EXERCÍCIOS FUNDAMENTAIS .............................................................................................................................. 2 
PFC .......................................................................................................................................................................... 3 
PRINCÍPIOS FUNDAMENTAIS DA CONTAGEM (PFC) ............................................................................................... 3 
PRELIMINAR 1 ......................................................................................................................................................... 3 
PRINCÍPIO MULTIPLICATIVO ................................................................................................................................... 3 
PRINCÍPIO ADITIVO ................................................................................................................................................. 3 
EXERCÍCIOS FUNDAMENTAIS .............................................................................................................................. 4 
PROBLEMAS QUE ENVOLVEM PFC .......................................................................................................................... 4 
EXERCÍCIOS FUNDAMENTAIS .............................................................................................................................. 4 
MÉTODO DESTRUTIVO ............................................................................................................................................ 5 
MÉTODO DESTRUTIVO ............................................................................................................................................ 5 
EXERCÍCIOS FUNDAMENTAIS .............................................................................................................................. 6 
 
 
 
Elson Rodrigues, Gabriel Carvalho e Paulo Luiz Página 2 
AULA 01 
FATORIAL 
FATORIAL 
Seja 𝑛𝑛 ∈ ℕ. Define-se o fatorial de 𝑛𝑛, denotado por 𝑛𝑛!, 
como 
 
𝑛𝑛! = 𝑛𝑛 ⋅ (𝑛𝑛 − 1) ⋅ (𝑛𝑛 − 2) ⋅ ⋯ ⋅⋅ 2 ⋅ 1 
 
para 𝑛𝑛 ≥ 2 e define-se, também, que 
 
1! = 1 e 0! = 1. 
 
 
Exemplo 1.1: Tem-se os seguintes resultados de 
fatorais 
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 
Observe que para o fatorial de 6 tem-se a relação 
 
6! = 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1 
 
6! = 6 ⋅ 5! 
Ou mais ainda, 
 
6! = 6 ⋅ 5! = 6 ⋅ 5 ⋅ 4! = 6 ⋅ 5 ⋅ 4 ⋅ 3! 
 
Pode-se agrupar os 𝑛𝑛 − 1 fatores em um único 
fatorial. Assim, 
 
𝑛𝑛! = 𝑛𝑛 ⋅ (𝑛𝑛 − 1)! ;𝑛𝑛 ≥ 2 
 
 
 
 
 
 
 
 
 
 
 
EXERCÍCIOS FUNDAMENTAIS 
1.1. Calcule 
a. 3! − 2! 
b. 7! 
c. 3! ⋅ 2! 
d. 7! − 6! 
e. 5!
6!
 
f. 9!
10!
 
g. 3!
4!
+ 4!
5!
 
h. 8!⋅6!
7!⋅7!
 
i. 11!+9!
10!
 
j. 21!−3⋅20!
19!
 
Obs.1: Em questões que envolvem divisão de fatorial 
com soma no numerador ou denominador, desenvolva 
todos os fatorais envolvidos até o menor entre eles, 
para então cancelar. 
1.2. Satisfeitas as condições de existência, simplifique 
as expressões: 
a. (𝑛𝑛+3)!(𝑛𝑛+1)! 
b. (𝑛𝑛+1)!−𝑛𝑛!
𝑛𝑛!
 
c. (𝑛𝑛+1)!−𝑛𝑛!
𝑛𝑛!−(𝑛𝑛−1)!
 
1.3. Determine o conjunto-solução das equações: 
a. 𝑛𝑛! = 24 
b. (𝑥𝑥 − 5)! = 1 
c. 𝑛𝑛!(𝑛𝑛−1)! = 4 
d. (𝑛𝑛!)2 − 100(𝑛𝑛!) = 2400 
1.4. (UEL) Se o número natural 𝑛𝑛 é tal que 
𝑛𝑛!+2⋅(𝑛𝑛−1)!
(𝑛𝑛−2)!
= 18, então 𝑛𝑛 é um número: 
a. Menor que 3. 
b. Maior que 10. 
c. Divisível por 5. 
d. Divisível por 2. 
e. Múltiplo de 7. 
Obs.2: Nas equações que envolvem fatoriais, lembre-
se de verificar as condições de existência. 
 
 
 
 
 
 
 
Entendendo o fatorial 
 
Entenda o fatorial de um número 𝑛𝑛 como o 
produto dos números naturais não nulos até 𝑛𝑛 
(considerando o próprio 𝑛𝑛). 
O fato de podermos agrupar uma subparte do 
fatorial em um outro fatorial é muito importante em 
questões de simplificação, para assim evitarmos 
contas exaustivas 
v 
v 
 
Elson Rodrigues, Gabriel Carvalho e Paulo Luiz Página 3 
AULA 02 
PFC 
PRINCÍPIOS FUNDAMENTAIS DA 
CONTAGEM (PFC) 
PRELIMINAR 1 
Na montagem de um combo em uma determinada 
lanchonete, um cliente possui três opções de 
sanduíche (frango, presunto e atum) e duas opções de 
suco (laranja e uva). De quantas maneiras distintas o 
combo pode ser montado? 
 
 
Obs.3: A organização acima é chamada de diagrama 
de flechas. 
Perceba que pode-se montar 6 combos distintos. Por 
outro lado 
 
3 ⋅ 2 = 6, 
 
onde 3 é o número de escolhas de sanduíche e 2 de 
sucos. 
• Se fosse dado mais uma opção de sanduíche, 
seria possível formar 4 ⋅ 2 = 8 combos 
distintos. 
• Se fosse dado, além de mais uma opção de 
sanduíche, duas opções de sobremesa, seria 
possível formar 4 ⋅ 2 ⋅ 2 = 16 combos 
distintos. 
 
 
 
PRINCÍPIO MULTIPLICATIVO 
O princípio multiplicativo para duas decisões pode ser 
descrito como segue: 
 
Se uma decisão d1 pode ser tomada de x maneiras e 
se, uma vez tomada a decisão d1, a decisão d2 puder 
ser tomada de y maneiras, então o número de 
maneiras de se tomarem as decisões d1 e d2 é x y⋅ . 
 
Este princípio pode ser estendido para n decisões. 
 
 
 
 
 
 
 
 
 
 
 
 
PRINCÍPIO ADITIVO 
Sejam 𝐴𝐴 e 𝐵𝐵 dois conjuntos disjuntos (𝐴𝐴 ∩ 𝐵𝐵 = ∅). 
Tem-se que 
 
𝑛𝑛(𝐴𝐴 ∪ 𝐵𝐵) = 𝑛𝑛(𝐴𝐴) + 𝑛𝑛(𝐵𝐵) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Obs.4: O conectivo “ou” geralmente indica método 
aditivo. 
Como resolver um problema de PFC? 
1º - Se coloque no lugar de quem monta a sequência 
2- Determine o número de decisões a se tomar para 
que a sequência seja montada 
3º- Determine quantas possiblidades existem em cada 
decisão levando em conta as decisões já tomadas. 
Entendendo o princípio aditivo 
O princípio aditivo garante, basicamente, que para 
calcular o número de elementos de um conjunto 
podemos o particionar em dois subconjuntos 
disjuntos e fazer a contagem separadamente, ou 
seja, em um problema de contagem, se necessário, é 
possível fazer a contagem em subcasos. 
Por exemplo, se é desejado contar quantos são os 
números pares, podemos calcular separadamente o 
número de casos que terminam em 𝟎𝟎, depois em 𝟐𝟐, 
em 𝟒𝟒, em 𝟔𝟔, em 𝟖𝟖 e finalmente, somar os valores 
obtidos. 
 
Elson Rodrigues, Gabriel Carvalho e Paulo Luiz Página 4 
EXERCÍCIOS FUNDAMENTAIS 
2.1 Uma senha bancária é composta de duas letras 
distintas seguidas por quatro algarismos. 
a) Quantas senhas podem ser formadas? 
b) Quantas senhas contém apenas algarismos 
ímpares? 
2.2 A senha de um cadeado é formada por uma 
sequência de quatro letras, escolhidas entre as 26 do 
alfabeto. 
a) Quantas senhas podemos formar? 
b) Quantas senhas com quatro letras distintas 
podemos formar? 
c) Quantas senhas começando por vogal podem ser 
formadas? 
2.3 Em uma excursão, o passageiro deve escolher a 
categoria de hotel em que se hospedará (turística, 
turística superior, primeira ou luxo) e o regime de 
alimentação (só café da manhã ou café da manhã + 
jantar). De quantos distintos o turista poderá fazer a 
escolha, se os hotéis de luxo só oferecem café da 
manhã? 
 
2.4 (UFRJ) Um construtor dispõe de quatro cores 
(verde, amarelo, cinza e bege) para pintar cinco casas 
dispostas lado a lado. Ele deseja que cada casa seja 
pintada com apenas uma cor e que duas casas 
consecutivas não possuam a mesma cor. Por exemplo, 
duas possibilidades diferentes de pintura seriam 
Primeira 
 
Determine o número de possibilidades diferentes de 
pintura. 
 
 
2.5 Utilizando os algarismos do sistema decimaldetermine: 
a) Quantos números de quatro algarismos 
podem ser formados? 
b) Quantos números de quatro algarismos 
distintos podem ser formados? 
c) Quantos números pares de quatro algarismos 
podem ser formados? 
d) Quantos números pares de quatro algarismos 
distintos podem ser formados? 
e) Quantos números divisíveis por 5 de quatro 
algarismos podem ser formados? 
f) Quantos números divisíveis por 5 de quatro 
algarismos distintos podem ser formados? 
g) Quantos números de quatro algarismos tem 
pelo menos dois algarismos repetidos? 
h) Quantos números de quatro algarismos 
distintos são maiores que 4326? 
 
AULA 03 
PROBLEMAS QUE ENVOLVEM PFC 
 
EXERCÍCIOS FUNDAMENTAIS 
3.1 Um encontro anual de pecuaristas será realizado 
durante 5 anos consecutivos. A sede do encontro, em 
cada ano, deverá ser escolhida entre 7 cidades. 
a) De quantas formas distintas podem ser escolhidas 
as sedes se a organização não pretende realizar o 
encontro em uma mesma sede mais de uma vez? 
b) De quantas formas distintas pode ser feita a 
escolha se a sede de um ano não pode ser igual a do 
ano anterior? 
3.2 (UnB) Para ir de um acampamento 𝐴𝐴 para um 
acampamento 𝐵𝐵, um escoteiro dispõe de 4 trilhas 
diferentes, enquanto para ir de 𝐵𝐵 para 𝐶𝐶 existem 6 
trilhas distintas (qualquer trajeto de 𝐴𝐴 a 𝐶𝐶, ou vice-
versa, deve passar por 𝐵𝐵. Com base nisso, julgue os 
itens. 
(A) Se um escoteiro pretende ir de 𝐴𝐴 até 𝐶𝐶 e 
voltar a A sem utilizar, no percurso de volta, 
qualquer trecho do trajeto utilizado na ida, 
então ele dispõe de 360 maneiras distintas de 
fazer o percurso. 
 
Elson Rodrigues, Gabriel Carvalho e Paulo Luiz Página 5 
(B) Se o escoteiro deseja fazer o percurso de ida e 
volta de 𝐴𝐴 a 𝐶𝐶, podendo repetir na volta a 
mesma trilha entre 𝐵𝐵 e 𝐶𝐶 utilizada na ida, mas 
não a trilha para ir de 𝐴𝐴 a 𝐵𝐵, então o número 
de possíveis trajetos é 576. 
(C) Admitindo que as trilhas de 𝐵𝐵 a 𝐶𝐶 estejam 
numeradas de 1 a 6 e que o escoteiro deseja 
fazer o percurso de 𝐴𝐴 até 𝐶𝐶 e voltar até 𝐵𝐵, 
sem repetir na volta a paridade da trilha de 𝐵𝐵 
a 𝐶𝐶 usada na ida, então o número de trajetos 
é igual a 48. 
3.3 De quantas maneiras podemos classificar os 
quatro empregados de uma microempresa nas 
categorias A e/ou B, se cada empregado pode 
pertencer às duas categorias? 
3.4 (UFTM) Um cartógrafo, para fazer o mapa do 
sudeste brasileiro mostrado na figura, deverá colorir 
cada estado com uma cor, tendo disponíveis 4 cores e 
podendo repeti-las no mapa. Estados que fazem divisa 
entre si devem ter cores distintas. Sabendo que 
somente SP e ES não fazem divisa entre si, o número 
de formas distintas de colorir o mapa é 
 
(A) 12. 
(B) 24. 
(C) 36. 
(D) 48. 
(E) 60. 
 
 
3.5. Esmeralda possui 8 livros de matemática, 6 de 
física e 3 de química. De quantas formas ela pode 
escolher dois deles com matérias distintas para 
estudar? 
3.6. Considere três acampamentos 𝐴𝐴,𝐵𝐵 e 𝐶𝐶. Existem 5 
trilhas de 𝐴𝐴 para 𝐵𝐵, 3 trilhas de 𝐵𝐵 para 𝐶𝐶 e 2 trilhas de 
𝐴𝐴 para 𝐶𝐶. De quantas maneiras distintas pode-se ir de 
𝐴𝐴 até 𝐶𝐶, passando ou não por 𝐵𝐵. 
d) Quantas senhas de letras distintas podem ser 
formadas começando e terminando por vogal? 
3.7 Quantos divisores naturais o número 3780 
possui? 
3.8 Considere o número 8400 e faça o que se pede em 
cada item a seguir. 
a) Determine o número de divisores naturais. 
b) Determine o número de divisores inteiros. 
c) Determine o número de divisores naturais pares. 
d) Determine o número de divisores naturais 
múltiplos de 20. 
e) Determine o número de divisores naturais que não 
são múltiplos de 28. 
f) Determine o número de divisores naturais que são 
quadrados perfeitos. 
3.9 O número 𝑁𝑁 = 23 ⋅ 32 ⋅ 6𝑥𝑥 possui 30 divisores 
naturais. Determine o valor natural de 𝑥𝑥. 
 
AULA 04 
MÉTODO DESTRUTIVO 
MÉTODO DESTRUTIVO 
Pelo princípio aditivo, temos que 
 
𝑛𝑛(Ω) = 𝑛𝑛(𝐴𝐴) + 𝑛𝑛(𝐴𝐴𝑐𝑐). 
 
O termo 𝑛𝑛(Ω) simboliza o total de elementos do 
nosso problema e 𝐴𝐴𝑐𝑐 é o complementar de 𝐴𝐴. 
Isolando qualquer um dos termos do 2º membro, 
temos que 
 
𝑛𝑛(𝐴𝐴) = 𝑛𝑛(Ω) − 𝑛𝑛(𝐴𝐴𝑐𝑐). 
 
Assim, o número de elementos do conjunto 𝐴𝐴 pode 
ser obtido pegando o total de elementos e retirando 
tudo que não está em 𝐴𝐴. 
 
 
Elson Rodrigues, Gabriel Carvalho e Paulo Luiz Página 6 
EXERCÍCIOS FUNDAMENTAIS 
4.1 (PUC) Uma sala tem 6 lâmpadas com interruptores 
independentes. O número de modos de iluminar a 
sala, acendendo pelo menos uma lâmpada é 
a) 63. 
b) 79. 
c) 127. 
d) 182. 
e) 201. 
Obs.5: Os termos pelo menos, no máximo e no mínimo 
costumam indicar questões de método destrutivo. 
4.2 Ana, Bernardo, Carlos, Daniel e Eduardo vão a 
uma montanha russa, onde devem se sentar 
formando uma fila. De quantos modos podemos 
formar essa fila, sendo que Ana e Bernardo não 
podem ficar lado a lado, pois acabaram de ter uma 
briga feia. 
 
EXTRA 
QUESTÕES EXTRAS 
1. Calcule a expressão 
4 ⋅ 31! − 6 ⋅ 30!
118 ⋅ 29!
 
2. Satisfeitas as condições de existência, simplifique 
as expressões 
a) 𝑛𝑛!−(𝑛𝑛+1)!
𝑛𝑛!
 
b) 𝑛𝑛!−(𝑛𝑛−1)!(𝑛𝑛+1)!+(𝑛𝑛+2)! 
3. Resolva a equação 
(𝑛𝑛 − 1)! ⋅ (𝑛𝑛 + 1)!
(𝑛𝑛!)2 
 
 
 
GABARITO 
EXERCÍCIOS FUNDAMENTAIS 
1.1. 
QUESTÕES EXTRAS 
1. 30 
2. a) −𝑛𝑛 b) (𝑛𝑛−1)
2
𝑛𝑛
 
3. {4} 
 
 
 
 
 
 
 
 
 
 
TAREFA 1 – Na Unidade 17, capítulo 65 “Análise 
combinatória 1”, fazer as questões do Praticando em 
Sala de Aula (PSA) de 1 a 10. 
 
 
	FATORIAL
	FATORIAL
	EXERCÍCIOS FUNDAMENTAIS
	PFC
	PRINCÍPIOS FUNDAMENTAIS DA CONTAGEM (PFC)
	PRELIMINAR 1
	PRINCÍPIO MULTIPLICATIVO
	PRINCÍPIO ADITIVO
	EXERCÍCIOS FUNDAMENTAIS
	PROBLEMAS QUE ENVOLVEM PFC
	EXERCÍCIOS FUNDAMENTAIS
	MÉTODO DESTRUTIVO
	MÉTODO DESTRUTIVO
	EXERCÍCIOS FUNDAMENTAIS
	QUESTÕES EXTRAS
	GABARITO
	EXERCÍCIOS FUNDAMENTAIS
	QUESTÕES EXTRAS