Análise Combinatória: Fórmulas

Cartões · 30

Princípio Multiplicativo (PFC)

Se um evento ocorre em 'n' etapas independentes com 'a', 'b', 'c' opções, o total de possibilidades é a * b * c. Usado para decisões sequenciais.

Princípio Aditivo

Se um evento pode ocorrer de duas maneiras mutuamente exclusivas com 'a' e 'b' opções, o total é a + b. Usado quando há opção de escolha (OU).

Fatorial (n!)

n! = n * (n-1) * ... * 1, com 0! = 1 e 1! = 1. Utilizado para calcular o número de maneiras de ordenar 'n' elementos distintos.

Arranjo Simples: A(n, p)

A(n, p) = n! / (n - p)!. Escolhe e ordena 'p' elementos de um total de 'n'. A ordem dos elementos IMPORTA.

Combinação Simples: C(n, p)

C(n, p) = n! / [p! * (n - p)!]. Escolhe um grupo de 'p' elementos de 'n'. A ordem dos elementos NÃO importa.

Permutação Simples: P(n)

P(n) = n!. Ordena 'n' elementos distintos em uma fila. É um caso particular do Arranjo onde p = n.

Permutação com Repetição: P(n; a, b...)

P = n! / (a! * b!...). Ordena 'n' elementos onde alguns se repetem ('a' vezes, 'b' vezes, etc.). Usado em anagramas com letras repetidas.

Permutação Circular: PC(n)

PC(n) = (n - 1)!. Ordena 'n' elementos distintos ao redor de um círculo. Usado quando a posição relativa importa (mesas, rodas).

Arranjo com Repetição: AR(n, p)

AR(n, p) = n^p. Escolhe e ordena 'p' elementos dentre 'n' disponíveis, podendo repetir elementos. Usado em senhas numeradas.

Combinação com Repetição: CR(n, p)

CR(n, p) = C(n + p - 1, p). Escolhe 'p' itens de 'n' tipos disponíveis, onde a ordem não importa e pode haver repetição. Usado em compras de doces.

Subconjuntos de um Conjunto: 2^n

Total de subconjuntos de um conjunto com 'n' elementos é 2^n. Equivale à soma de C(n, 0) + C(n, 1) + ... + C(n, n).

Triângulo de Pascal: Relação de Stifel

C(n, p) + C(n, p+1) = C(n+1, p+1). A soma de dois elementos adjacentes em uma linha resulta no elemento da linha de baixo.

Triângulo de Pascal: Simetria

C(n, p) = C(n, n - p). Elementos equidistantes dos extremos em uma mesma linha do Triângulo de Pascal são iguais.

Binômio de Newton: Termo Geral

T(k+1) = C(n, k) * a^(n-k) * b^k. Calcula um termo específico na expansão do binômio (a + b)^n sem expandir tudo.

Soma dos Coeficientes Binomiais

Soma dos coeficientes de (a*x + b*y)^n é obtida substituindo as variáveis x e y por 1, resultando em (a + b)^n.

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

|A ∪ B| = |A| + |B| - |A ∩ B|. Conta elementos em pelo menos um dos conjuntos, evitando a contagem dupla da interseção.

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

|A ∪ B ∪ C| = |A|+|B|+|C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|. Utilizado para somar a união de três conjuntos sem duplicar dados.

Princípio das Gavetas de Dirichlet (Casas dos Pombos)

Se 'n' pombos ocupam 'm' casas e n > m, pelo menos uma casa terá mais de um pombo. Usado para provar existência de repetições.

Número de Anagramas Totais

Calculado por P(n) = n! para palavras com letras distintas, ou P(n; a, b...) se houver letras repetidas. Usado para reordenar letras.

Número de Diagonais de um Polígono: D

D = [n * (n - 3)] / 2. Derivado da combinação de 'n' vértices tomados 2 a 2, subtraindo os 'n' lados do polígono.

Apertos de Mão / Jogos de Todos contra Todos

C(n, 2) = [n * (n - 1)] / 2. Calcula o número de conexões únicas entre pares de pessoas ou times em um grupo de 'n' integrantes.

Número de Anagramas com Letras Juntas

Trata as letras que devem ficar juntas como um único elemento 'bloco', calcula a permutação externa e multiplica pela permutação interna do bloco.

Número de Anagramas com Letras Separadas

Posiciona primeiro as outras letras e utiliza os espaços entre elas (método dos traços/espaços) para inserir as letras que devem ficar separadas.

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

C(n + k - 1, k - 1). Usado para encontrar o número de soluções inteiras e não negativas de equações do tipo x1 + x2 + ... + xk = n.

Soluções Inteiras Estritamente Positivas

C(n - 1, k - 1). Usado para calcular o número de soluções de x1 + x2 + ... + xk = n, garantindo que cada variável seja no mínimo 1.

Desarranjo / Permutação Caótica: D(n)

D(n) = n! * Σ [(-1)^k / k!] para k de 0 a n. Calcula o número de permutações em que nenhum elemento permanece em sua posição original.

Lema de Kaplansky

f(n, p) = C(n - p + 1, p). Calcula o número de subconjuntos de 'p' elementos escolhidos de {1, 2, ..., n} sem conter elementos consecutivos.

Combinações Complementares

C(n, p) = C(n, n - p). Escolher 'p' objetos para formar um grupo é o mesmo que escolher 'n - p' objetos para deixar de fora.

Número de Posições em Reta (Pontos Não Colineares)

Triângulos formados por 'n' pontos: C(n, 3). Retas formadas por 'n' pontos: C(n, 2). Requer que não haja 3 pontos colineares.

Comissão com Cargo Específico (Presidente/Vice)

A(n, k) ou C(n, k) * k!. Usado quando se escolhe um grupo de 'k' pessoas e cada uma recebe uma função diferente dentro do grupo.