Análise Combinatória

Cartões · 52

Princípio Fundamental da Contagem (Regra do Produto)

Total = n1 * n2 * ... * nk. Aplica-se em decisões sequenciais e independentes, multiplicando as opções de cada etapa.

Princípio Aditivo

Total = n1 + n2 + ... + nk. Aplica-se quando os eventos são mutuamente exclusivos, bastando somar as opções de cada caso.

Fatorial de um número (n!)

n! = n * (n - 1) * ... * 1, com 0! = 1. Mede o número de formas de ordenar n elementos distintos.

Permutação Simples (P_n)

P_n = n!. Usada para ordenar todos os n elementos distintos, onde a ordem de apresentação importa.

Arranjo Simples (A(n, p))

A(n, p) = n! / (n - p)!. Usado para escolher e ordenar p elementos dentre n distintos, onde a ordem importa.

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

C(n, p) = n! / [p! * (n - p)!]. Usada para selecionar subconjuntos de p elementos dentre n distintos, sem importar a ordem.

Permutação com Repetição (P_n^(a, b, ...))

P_n^(a,b,...) = n! / (a! * b! * ...). Usada para ordenar n elementos quando alguns deles se repetem (ex: anagramas).

Permutação Circular (PC_n)

PC_n = (n - 1)!. Usada para dispor n elementos em círculo, eliminando rotações equivalentes.

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

AR(n, p) = n^p. Usado para formar sequências de comprimento p escolhendo entre n tipos com reposição permitida.

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

CR(n, p) = C(n + p - 1, p). Usada na partição de itens idênticos entre recipientes distintos (método dos traços e bolas).

Número de Subconjuntos de um Conjunto (Conjunto das Partes)

Total = 2^n. Cada um dos n elementos tem 2 opções de escolha: pertencer ou não pertencer ao subconjunto.

Propriedade das Combinações Complementares

C(n, p) = C(n, n - p). Escolher p elementos para incluir equivale a escolher (n - p) para excluir.

Relação de Stifel

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

Soma da Linha n do Triângulo de Pascal

Soma = C(n, 0) + C(n, 1) + ... + C(n, n) = 2^n. Representa a soma de todas as combinações possíveis de n elementos.

Teorema das Linhas do Triângulo de Pascal

A soma dos termos da linha n é 2^n. Decorre diretamente da expansão do binômio (1 + 1)^n.

Teorema das Colunas do Triângulo de Pascal

C(p, p) + C(p+1, p) + ... + C(n, p) = C(n + 1, p + 1). A soma dos elementos de uma coluna equivale ao termo abaixo à direita.

Teorema das Diagonais do Triângulo de Pascal

C(n, 0) + C(n+1, 1) + ... + C(n+p, p) = C(n + p + 1, p). A soma em diagonal resulta no elemento imediatamente abaixo.

Binômio de Newton (Expansão Geral)

(x + y)^n = soma de k=0 até n de [C(n, k) * x^(n - k) * y^k]. Usado para expandir potências de binômios.

Termo Geral do Binômio de Newton

T_(k+1) = C(n, k) * x^(n - k) * y^k. Usado para encontrar um termo específico em (x + y)^n sem expandir tudo.

Termo Independente em Binômio de Newton

Iguala-se o expoente da variável a zero no termo geral T_(k+1) e resolve-se para achar o valor de k.

Princípio da Casa dos Pombos (Forma Básica)

Se n itens forem postos em m caixas com n > m, pelo menos uma caixa terá 2 ou mais itens. Garante repetições.

Princípio da Casa dos Pombos (Forma Generalizada)

Se n itens forem postos em m caixas, ao menos uma conterá no mínimo teto(n/m) itens. Avalia mínimos garantidos.

Princípio da Inclusão-Exclusão para 2 Conjuntos

|A U B| = |A| + |B| - |A inter B|. Evita contar elementos repetidos na união de dois conjuntos.

Princípio da Inclusão-Exclusão para 3 Conjuntos

|A U B U C| = |A|+|B|+|C| - (|A inter B|+|A inter C|+|B inter C|) + |A inter B inter C|. Usado para unir 3 conjuntos.

Permutações Caóticas ou Desarranjos (D_n)

D_n = n! * soma de k=0 até n de [(-1)^k / k!]. Conta permutações em que nenhum elemento fica na sua posição original.

Fórmula Recursiva de Desarranjos (D_n)

D_n = (n - 1) * (D_(n-1) + D_(n-2)), com D_1 = 0 e D_2 = 1. Calcula desarranjos a partir de casos menores.

Soluções Inteiras Não Negativas de Equações Lineares

x1 + x2 + ... + xn = C (xi >= 0): Total = C(C + n - 1, n - 1). Modelo de bolas e traços para distribuir recursos.

Soluções Inteiras Estritamente Positivas

x1 + x2 + ... + xn = C (xi >= 1): Total = C(C - 1, n - 1). Garante que cada variável receba ao menos 1 unidade.

Cálculo de Diagonais de um Polígono Convexo

d = C(n, 2) - n = [n * (n - 3)] / 2. Liga-se pares de vértices subtraindo os lados que formam o contorno.

Triângulos Formados por Vértices de um Polígono

Total = C(n, 3). Conta triângulos possíveis escolhendo 3 vértices quaisquer entre os n disponíveis.

Interseções Máximas entre R Diagonais de um Polígono

Max = C(n, 4). Cada conjunto de 4 vértices forma exatamente um par de diagonais que se cruzam no interior.

Número de Retângulos em uma Malha m x n

Total = C(m + 1, 2) * C(n + 1, 2). Escolhem-se 2 linhas horizontais e 2 verticais para delimitar cada retângulo.

Caminhos em Malha Quadriculada (L passos direita, A passos cima)

Total = C(L + A, L) = (L + A)! / (L! * A!). Permutação de passos com repetição em uma grade bidimensional.

Lema de Kaplansky (1º Lema - Linha)

K(n, p) = C(n - p + 1, p). Número de subconjuntos de p elementos de {1,...,n} sem conter elementos consecutivos.

Lema de Kaplansky (2º Lema - Círculo)

KC(n, p) = [n / (n - p)] * C(n - p, p). Subconjuntos de p elementos de n dispostos em círculo sem elementos vizinhos.

Número de Subconjuntos de Tamanho Par

Total = 2^(n - 1). Em qualquer conjunto de n elementos (n >= 1), metade dos subconjuntos tem tamanho par.

Número de Subconjuntos de Tamanho Ímpar

Total = 2^(n - 1). Equivale exatamente à metade de todos os 2^n subconjuntos gerados por n elementos.

Partição de n Elementos em k Grupos Não Rotulados Iguais

Total = [n! / (p!)^k] / k!. Usado ao dividir n itens em k equipes idênticas de tamanho p, onde n = k * p.

Partição de n Elementos em k Grupos Rotulados

Total = n! / (p1! * p2! * ... * pk!). Distribui n elementos em grupos de tamanhos pré-definidos e distintos entre si.

Coeficiente Multinomial

(n escolhe n1, ..., nk) = n! / (n1! * ... * nk!). Usado no termo geral da expansão de (x1 + x2 + ... + xk)^n.

Número de Funções de A para B

Total = |B|^|A|. Cada elemento do domínio A possui |B| opções independentes no contradomínio B.

Número de Funções Injetoras de A para B (|B| >= |A|)

Total = A(|B|, |A|) = |B|! / (|B| - |A|)!. Cada elemento de A deve mapear para um elemento distinto em B.

Número de Funções Bijetoras de A para B (|A| = |B| = n)

Total = n!. Mapeamento um a um entre conjuntos com mesma cardinalidade (permutação de n).

Número de Funções Estritamente Crescentes (A para B ordenados)

Total = C(|B|, |A|). Basta selecionar |A| valores distintos em B; a ordem crescente é única e automática.

Relação entre Arranjo e Combinação

A(n, p) = C(n, p) * p!. Um arranjo equivale a selecionar os elementos (combinação) e ordená-los (permutação).

Permutação de Elementos que Devem Ficar Juntos

Trata-se o bloco junto como 1 único item fictício, multiplica-se pela permutação interna dos itens do bloco.

Permutação de Elementos que Não Podem Ficar Juntos (Método dos Espaços)

Organizam-se os outros elementos primeiro e inserem-se os itens restritos nos espaços vazios gerados entre eles.

Contagem por Complementar

Favoráveis = Total irrestrito - Casos desfavoráveis. Muito útil quando a restrição contém 'ao menos um'.

Número de Divisores Positivos de um Inteiro

Se N = p1^a * p2^b ..., d(N) = (a + 1) * (b + 1) * ... Cada primo pode aparecer de 0 até o expoente máximo.

Anagramas com Letras Específicas em Ordem Fixa

Total = n! / k!. Se k letras devem manter uma ordem fixa pré-determinada, divide-se pela permutação delas.

Número de Polígonos de k Vértices em um Conjunto de n Pontos

Total = C(n, k), assumindo que não há 3 pontos colineares no conjunto. Cada escolha gera 1 polígono convexo.

Permutação Circular com Sentido Não Diferenciável (Colar)

Total = (n - 1)! / 2. Usada para contas em um colar ou pulseira, onde virar a peça reflete a mesma ordem.