Análise Combinatória

Cartões · 53

Princípio Fundamental da Contagem (PFC)

Se uma decisão pode ser tomada de m modos e outra de n modos, ambas consecutivas podem ocorrer de m x n modos.

Fatorial de um número natural (n!)

n! = n x (n-1) x ... x 2 x 1, com a convenção de que 0! = 1 e 1! = 1.

Fatorial de zero (0!)

0! = 1. Convenção matemática necessária para consistência das fórmulas combinatórias.

Fatorial de um (1!)

1! = 1. Produto de um único fator igual a 1.

Propriedade recursiva do fatorial

n! = n x (n-1)!, válida para todo n >= 1.

Permutação Simples

Pn = n!. Reordenação de todos os n elementos distintos disponíveis, onde a ordem importa.

Fórmula da Permutação Simples

Pn = n!.

Permutação com Repetição

P_n^(a,b,...) = n! / (a! x b! x ...). Ordenação de n elementos onde alguns se repetem a, b vezes.

Fórmula da Permutação com Repetição

P_n^(a,b,...) = n! / (a! x b! x ... x k!).

Permutação Circular

PC(n) = (n - 1)!. Maneiras de dispor n elementos distintos em torno de um círculo fechado.

Fórmula da Permutação Circular

PC(n) = (n - 1)!.

Arranjo Simples

Agrupamento ordenado de p elementos escolhidos dentre n elementos distintos, onde a ordem importa e p <= n.

Fórmula do Arranjo Simples

A(n, p) = n! / (n - p)!.

Arranjo com Repetição

AR(n, p) = n^p. Escolha ordenada de p elementos dentre n tipos disponíveis, permitindo repetições.

Fórmula do Arranjo com Repetição

AR(n, p) = n^p.

Combinação Simples

C(n, p) = n! / [p! x (n - p)!]. Subconjunto não ordenado de p elementos distintos escolhidos de n.

Fórmula da Combinação Simples

C(n, p) = n! / [p! x (n - p)!].

Combinação com Repetição

CR(n, p) = C(n + p - 1, p). Escolha não ordenada de p elementos dentre n tipos, com repetição.

Fórmula da Combinação com Repetição

CR(n, p) = (n + p - 1)! / [p! x (n - 1)!].

Diferença entre Arranjo e Combinação

No arranjo, a mudança de ordem gera um grupo diferente; na combinação, a ordem dos elementos não altera o grupo.

Papel da ordem na Permutação

A ordem importa e todos os elementos do conjunto original são utilizados simultaneamente.

Anagrama

Palavra formada pela transposição das letras de outra palavra; calcula-se via permutação simples ou com repetição.

Número de anagramas de palavra sem letras repetidas

Calcula-se por Pn = n!, onde n é o total de letras distintas da palavra.

Número de anagramas com letras repetidas

Calcula-se por n! dividido pelo produto dos fatoriais do número de repetições de cada letra.

Combinações Complementares

C(n, p) = C(n, n - p). Escolher p elementos equivale a rejeitar (n - p) elementos.

Fórmula das Combinações Complementares

C(n, p) = C(n, n - p).

Relação de Stifel

C(n - 1, p - 1) + C(n - 1, p) = C(n, p). Base para a construção do Triângulo de Pascal.

Triângulo de Pascal

Tabela triangular formada pelos coeficientes binomiais C(n, p), onde n é a linha e p é a coluna.

Soma dos elementos da linha n do Triângulo de Pascal

S = 2^n. Equivale ao número total de subconjuntos de um conjunto de n elementos.

Teorema do Binômio de Newton

(x + y)^n = soma de p=0 até n de C(n, p) x x^(n-p) x y^p.

Termo geral do Binômio de Newton

T(p + 1) = C(n, p) x a^(n - p) x b^p na expansão de (a + b)^n.

Permutação Caótica (Desarranjo)

Permutação de n elementos em que nenhum elemento ocupa sua posição original inicial.

Fórmula do Desarranjo (!n)

!n = n! x [1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n / n!].

Número de subconjuntos de um conjunto com n elementos

2^n, incluindo o conjunto vazio e o próprio conjunto.

Princípio da Inclusão-Exclusão para dois conjuntos

n(A U B) = n(A) + n(B) - n(A ∩ B). Evita a contagem dupla da interseção.

Princípio da Inclusão-Exclusão para três conjuntos

n(A U B U C) = n(A)+n(B)+n(C) - [n(A∩B)+n(A∩C)+n(B∩C)] + n(A∩B∩C).

Princípio das Gavetas de Dirichlet (Pigeonhole)

Se n itens forem colocados em m gavetas e n > m, pelo menos uma gaveta terá mais de um item.

A(n, 1)

A(n, 1) = n. Há n maneiras de escolher e ordenar 1 elemento a partir de n.

A(n, n)

A(n, n) = n! = Pn. Arranjar n elementos tomados n a n é equivalente à permutação simples.

C(n, 0)

C(n, 0) = 1. Há exatamente 1 subconjunto com zero elementos (o conjunto vazio).

C(n, 1)

C(n, 1) = n. Há n subconjuntos unitários formados a partir de n elementos.

C(n, n)

C(n, n) = 1. Há apenas 1 forma de escolher todos os n elementos disponíveis.

Relação entre Arranjo e Combinação

A(n, p) = C(n, p) x p!. O arranjo ordena os grupos formados pela combinação.

Cálculo de número de diagonais de um polígono

d = C(n, 2) - n = [n x (n - 3)] / 2, onde n é o número de vértices.

Número de triângulos formados por n pontos não colineares

C(n, 3) = n! / [3! x (n - 3)!]. Qualquer trio de vértices forma um triângulo.

Número de retas determinadas por n pontos não colineares

C(n, 2) = n! / [2! x (n - 2)!]. Dois pontos distintos determinam uma reta.

Soluções inteiras não negativas de x1 + x2 + ... + xn = k

Calcula-se por Combinação com Repetição: CR(n, k) = C(n + k - 1, k).

Soluções inteiras estritamente positivas de x1 + ... + xn = k

Calcula-se por C(k - 1, n - 1), com k >= n.

Método dos Traços e Bolinhas (Paus e Pedras)

Técnica visual usada para resolver problemas de partição e combinação com repetição.

Permutação de elementos dispostos em fila com restrição de vizinhança

Tratam-se os elementos obrigados a ficarem juntos como um único bloco móvel.

Permutação de elementos dispostos em fila que não podem ficar juntos

Calcula-se o total irrestrito de permutações e subtrai-se os casos em que ficam juntos.

Comissão sem distinção de cargos

Utiliza-se Combinação Simples, pois a ordem dos membros escolhidos não altera a comissão.

Comissão com distinção de cargos (Presidente, Tesoureiro)

Utiliza-se Arranjo Simples ou PFC, pois a função atribuída diferencia o grupo formado.