Análise combinatória

Prévia do material em texto

Análise 
combinatória 
Consiste no conjunto de técnicas de contagem que 
permite determinar de quantas formas ocorre um evento, 
sem que seja necessário listar todas as possibilidades. 
PRINCÍPIO FUNDAMENTAL DA CONTAGEM 
(PRINCÍPIO MULTIPLICATIVO) 
Se há x modos de tomar uma decisão D1 e, depois de 
tomada a decisão D1, há y modos de tomar a decisão D2, 
então o total modos de tomar as decisões D1 e D2 é 𝑥 · 𝑦. 
ESTRATÉGIAS PARA RESOLUÇÃO DE PROBLEMAS 
DE CONTAGEM 
• PRIMEIRA ESTRATÉGIA: É preciso se colocar no 
papel da pessoa que deve fazer a ação solicitada 
pelo problema e verificar as decisões que devem 
ser tomadas. 
• SEGUNDA ESTRATÉGIA: Deve-se, sempre que 
possível, dividir as decisões a serem tomadas em 
decisões mais simples. 
• TERCEIRA ESTRATÉGIA: Se uma das decisões a 
serem tomadas for mais restrita que as demais, 
essa é a decisão que deve ser executada em 
primeiro lugar. 
PRINCÍPIO ADITIVO 
Se X e Y forem dois conjuntos disjuntos com quantidades a 
e b de elementos, respectivamente. O total de modos de 
se escolher um elemento de X ou de Y é dado por 𝑎 + 𝑏. 
FATORIAL 
n! = n · (n – 1)! n ∈  N ∗ e n ≥ 2 
❖ Multiplica do n até o 1. 
 
❖ Para resolver divisão tentar sempre deixar dois 
fatoriais iguais para resolver o resto. 
 
 
 
 
 
PERMUTAÇÃO SIMPLES 
Dados n objetos distintos, o total de formas de ordená-los 
é dado por: 
Pn = n! 
 
Total de permutações circulares de n objetos distintos: 
PCn =
n!
𝑛
= (𝑛 − 1)! 
PERMUTAÇÃO COM REPETIÇÃO 
O total de permutações de n objetos, nem todos distintos 
entre si, em que cada um deles aparece 𝛼, 𝛽, . . . , 𝛾 vezes, 
com 𝛼 + 𝛽 + . . . + 𝛾 = 𝑛, é dado por: 
𝑃𝑛
α,β,...,γ
=
𝑛!
α! β!. . . γ!
 
 
ARRANJO SIMPLES 
Dado um conjunto de n objetos, o total de escolhas 
ordenadas de p objetos, ou seja, o número de arranjos 
simples de classe p dos n objetos pode ser calculado 
por meio da seguinte relação: 
𝐴𝑛
p
=
𝑛!
(n − p)!
 
 
RELAÇÃO ENTRE A PERMUTAÇÃO, A COMBINAÇÃO 
E O ARRANJO 
𝐴𝑛
𝑘 = 𝑃𝑘 ∙ 𝐶𝑛
𝑘 
 
COMBINAÇÃO SIMPLES 
Cálculo do número de formas como se pode escolher 
alguns objetos distintos dentre um conjunto de objetos 
dados, sem considerar as diferentes ordenações. O 
número de modos com que se pode escolher p objetos 
distintos dentre um conjunto com n objetos é chamado 
número de combinações simples de classe p de n objetos e 
é calculado por meio da seguinte relação: 
𝐶𝑛
p
=
𝑛!
p! (n − p)!
 
 
COMBINAÇÃO COM REPETIÇÃO 
𝐶𝑅𝑛
p
=
(𝑛 + 𝑝 − 1)!
p! (n − 1)!