Analise Combinatória Flashcards
Permutação (Ordenação)
Permutação Simples
Elementos todos distintos Possibilidades: n!
Permutação Simples com Restrição (n elementos que estejam fixos em determinada posição)
P = (n-p)!
Que estejam fixos mas não esteja determinado a posição:
P = (n-p) x p!
Permutação com repetição
P = n! / k1! K2!…
k corresponde ao número de elementos que se repetem
Permutação Elementos Juntos
j (elementos que devem ficar juntos)
P = (n - j + 1)! x j!
Permutação circular
Não há posições fixas. Assim devemos fixar uma.
Pc = (n-1)!
Permutação circular com restrições
Resolve em 2 etapas:
1o evento fixamos o elemento e permutamos os demais
P = (n-1)!
2o evento permutamos os demais, numa permutação simples
Total = (n-1) x n!
Arranjo e Combinação - Conceito
Técnicas que trabalham com a seleção de um subconjunto dos elementos.
Ordem relevante = arranjo
Ordem não é relevante = combinação
Arranjo Simples
Arranjo sem reposição de K elementos, em um conjunto de n elementos distintos
A = n! / (n-k)!
Ex: sorteio 5 pessoas dentre 8, para prêmios distintos
Combinação Simples
Selecionar elementos de um modo que a ordem não importa
C = n! / (n-k) x k!
Como resolver problemas de combinação, quando tiver “pelo menos um”
Calcula-se todas as possibilidades de grupos, desconsiderando-se a restrição imposta, em seguida subtrair o número de possibilidades que não atendem a restrição
Ex: 4 h e 5 mulheres. Quantos grupos de 3 que tenham pelo menos 1 mulher.
Calcula-se todos 9!/(9-3)3!
Menos os de só homens 4/(4-3)3!
Casos especiais de combinação
C n,n = 1
C n,0 = 1
C n,1 = n
C n, n-1 = n
C n,k = C n,n-k
Somatório de todas as combinações possíveis de n elementos é 2^n
C n,0 + Cn,1 + …+ Cn,n-1, + C n,0
Combinação Completa
Selecionar k objetos, iguais ou diferentes, de n tipos diferentes
Ex: escolher 3 potes de 5 marcas
C = (n -1 + p)! / (n-1)! x p!
Combinação Completa tipo equação
X1 + X2 + … + Xn = p
(n - 1 + p)! / (n - 1) x p!
Resultado da equação = número de objetos: p
Número de variáveis corresponde ao número de fatores : n
Partição Ordenada
Representa a separação de um conjunto de elementos em subconjuntos distintos entre si (de modo que a soma dos elementos dos subconjuntos seja equivalente ao total de elementos do conjunto original)
C = n! / p1 ! x p2! x p3!
Partição não-ordenada
Representa a separação de um conjunto de elementos em subconjuntos equivalentes entre si. A ordem dos conjuntos não importa.
Ex: particionar 6 profissionais em 3 duplas, que deverão realizar o mesmo trabalho
(m subconjuntos com p elementos cada), total de m x p elementos
então substituímos n por m x p
= (m x p) / m! x (p! ^m)
