Análise Combinatória

Cartões · 30

Permutação Caótica (Desarranjo)

Permutação de elementos onde nenhum elemento permanece em sua posição original.

Princípio Fundamental da Contagem (PFC)

Se um evento A pode ocorrer de 'm' maneiras e B de 'n' maneiras independentes, a ocorrência sucessiva de A e B ocorre de m * n maneiras.

Arranjo Simples (A_n,k)

Agrupamentos onde a ordem dos elementos IMPORTA e NÃO há repetição. Fórmula: A(n,k) = n! / (n - k)!

Combinação Simples (C_n,k)

Agrupamentos onde a ordem dos elementos NÃO importa e NÃO há repetição. Fórmula: C(n,k) = n! / (k! * (n - k)!)

Permutação Simples (P_n)

Caso particular do arranjo onde todos os 'n' elementos são utilizados e a ordem IMPORTA. Fórmula: P_n = n!

Permutação com Repetição

Permutação de 'n' elementos onde alguns se repetem a, b, c vezes. Fórmula: P_n^(a,b,c) = n! / (a! * b! * c!)

Permutação Circular (PC_n)

Disposição de 'n' elementos distintos ao redor de um círculo. A ordem relativa importa. Fórmula: PC_n = (n - 1)!

Arranjo com Repetição

Agrupamentos de 'k' elementos escolhidos de 'n' disponíveis, onde a ordem IMPORTA e PODE haver repetição. Fórmula: n^k

Combinação com Repetição (CR_n,k)

Escolha de 'k' elementos entre 'n' tipos, onde a ordem NÃO importa e PODE haver repetição. Fórmula: CR(n,k) = C(n+k-1, k)

Fatorial (n!)

Produto de todos os inteiros positivos menores ou iguais a n. Por definição, 0! = 1 e 1! = 1.

Diferença principal: Arranjo vs Combinação

No Arranjo, trocar a ordem dos elementos gera um novo grupo. Na Combinação, trocar a ordem resulta no mesmo grupo.

Quando a ordem dos elementos importa?

Em senhas, pódios de corrida, números de telefone, filas e cargos específicos (ex: presidente e vice). Use Arranjo ou Permutação.

Quando a ordem dos elementos NÃO importa?

Em comissões de pessoas, jogos de loteria, saladas de frutas e escolhas de times. Use Combinação.

A repetição de elementos é permitida?

Depende do problema: se puder repetir elementos (ex: dígitos em senha), usam-se fórmulas com repetição (ex: n^k).

Triângulo de Pascal

Disposição triangular dos números binomiais C(n,k), onde a soma de dois elementos adjacentes gera o elemento abaixo.

Relação de Stifel

Propriedade do Triângulo de Pascal: C(n,k) + C(n, k+1) = C(n+1, k+1).

Binômio de Newton

Fórmula para expandir potências da forma (a + b)^n usando combinações simples como coeficientes binomiais.

Termo Geral do Binômio de Newton

T_(k+1) = C(n,k) * a^(n-k) * b^k, usado para encontrar um termo específico da expansão sem desenvolver tudo.

Soma dos coeficientes do Binômio de Newton

Obtida substituindo as variáveis por 1. Para (a + b)^n com coeficientes 1, a soma é igual a 2^n.

Princípio da Inclusão-Exclusão (2 conjuntos)

|A ∪ B| = |A| + |B| - |A ∩ B|. Evita contar elementos da intersecção duas vezes.

Princípio das Gavetas de Dirichlet (Pombos)

Se 'n' pombos são colocados em 'm' gavetas e n > m, pelo menos uma gaveta conterá mais de um pombo.

Número de subconjuntos de um conjunto de 'n' elementos

Um conjunto com 'n' elementos possui 2^n subconjuntos no total (soma das combinações C(n,0) a C(n,n)).

Anagramas

Rearranjo das letras de uma palavra. Se não houver letras repetidas, usa-se P_n; se houver, usa-se Permutação com Repetição.

Agrupamento com elementos juntos

Para manter certos elementos sempre juntos, trate-os como um único 'bloco' e depois multiplique pelas permutações internas do bloco.

Partição de inteiros (Método Traços e Pontos)

Técnica gráfica para resolver equações diofantinas lineares com soluções inteiras não-negativas, equivalente à Combinação com Repetição.

Número Binomial C(n,k)

Representado por (n sobre k), equivale a n! / (k!(n-k)!). Indica de quantas formas escolher k itens de n.

Simetria dos Números Binomiais

C(n,k) = C(n, n-k). Escolher 'k' elementos para entrar é o mesmo que escolher 'n-k' para ficar de fora.

Soma de uma linha do Triângulo de Pascal

A soma de todos os elementos da linha 'n' do Triângulo de Pascal é igual a 2^n.

Quando usar o Princípio Aditivo?

Usa-se a soma quando as opções são mutuamente exclusivas (ou ocorre a opção A 'OU' a opção B).

Quando usar o Princípio Multiplicativo?

Usa-se a multiplicação quando o processo ocorre em etapas sucessivas e independentes (ocorre A 'E' B).