Análise Combinatória

Cartões · 52

Princípio Fundamental da Contagem (PFC)

Se uma decisão pode ser tomada de m modos e outra de n modos, ambas podem ser tomadas sucessivamente de m vezes n modos. Fórmula: N = n1 * n2 * ... * nk.

Princípio Aditivo

Se um evento pode ocorrer de m maneiras ou de n maneiras mutuamente exclusivas, o total de maneiras é a soma. Fórmula: N = m + n.

Fatorial de um número natural (n!)

Produto de todos os inteiros positivos menores ou iguais a n, com 0! = 1. Fórmula: n! = n * (n - 1) * ... * 1.

Fatorial de zero (0!)

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

Fatorial de um (1!)

Produto unitário de base. Valor: 1! = 1.

Permutação Simples

Reordenamento de todos os n elementos distintos de um conjunto onde a ordem importa. Fórmula: P(n) = n!.

Permutação com Repetição

Reordenamento de n elementos onde alguns se repetem k1, k2 vezes. Fórmula: P(n; k1, k2, ...) = n! / (k1! * k2! * ...).

Permutação Circular

Disposição de n elementos distintos ao redor de um círculo onde rotações contam como iguais. Fórmula: PC(n) = (n - 1)!.

Arranjo Simples

Seleção ordenada de p elementos distintos escolhidos de um total de n, onde a ordem importa. Fórmula: A(n, p) = n! / (n - p)!.

Arranjo com Repetição

Sequência ordenada de p elementos escolhidos de n opções podendo repetir elementos. Fórmula: AR(n, p) = n^p.

Combinação Simples

Seleção de p elementos dentre n distintos onde a ordem de escolha não importa. Fórmula: C(n, p) = n! / (p! * (n - p)!).

Combinação com Repetição (Combinação Completa)

Seleção não ordenada de p elementos dentre n tipos com repetições permitidas. Fórmula: CR(n, p) = C(n + p - 1, p) = (n + p - 1)! / (p! * (n - 1)!).

Número Binomial

Expressão algébrica equivalente à combinação simples de n elementos tomados p a p. Fórmula: (n sobre p) = n! / (p! * (n - p)!).

Binômio de Newton

Expansão de uma potência de binômio em somatório de coeficientes binomiais. Fórmula: (x + y)^n = soma de p=0 até n de C(n, p) * x^(n - p) * y^p.

Termo Geral do Binômio de Newton

Expressão do termo na posição (p + 1) na expansão binomial. Fórmula: T(p + 1) = C(n, p) * x^(n - p) * y^p.

Soma dos Coeficientes Binomiais

Soma de todas as combinações de n tomadas de 0 a n. Fórmula: soma de C(n, p) para p de 0 a n = 2^n.

Triângulo de Pascal

Tabela triangular formada pelos números binomiais onde cada linha n contém os termos C(n, p). Linha n: C(n, 0), C(n, 1), ..., C(n, n).

Relação de Stifel

Propriedade fundamental do Triângulo de Pascal somando dois termos adjacentes da mesma linha. Fórmula: C(n - 1, p - 1) + C(n - 1, p) = C(n, p).

Teorema das Linhas no Triângulo de Pascal

A soma dos termos de qualquer linha n do Triângulo de Pascal é potência de base 2. Fórmula: C(n, 0) + C(n, 1) + ... + C(n, n) = 2^n.

Teorema das Colunas no Triângulo de Pascal

A soma dos elementos de uma coluna p do início até a linha n resulta no elemento abaixo à direita. Fórmula: soma de C(i, p) com i de p até n = C(n + 1, p + 1).

Teorema das Diagonais no Triângulo de Pascal

A soma dos elementos ao longo de uma diagonal equivale ao elemento diretamente abaixo do último somado. Fórmula: soma de C(p + i, i) com i de 0 até k = C(p + k + 1, k).

Princípio da Casa dos Pombos (PCP)

Se n itens são colocados em m recipientes e n > m, pelo menos um recipiente contém mais de um item. Regra: se n > m, existe recipiente com pelo menos ceil(n/m) itens.

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

Cálculo do número de elementos da união de dois conjuntos finitos. Fórmula: n(A U B) = n(A) + n(B) - n(A ∩ B).

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

Cálculo da união de 3 conjuntos subtraindo interseções duplas e somando a tripla. Fórmula: n(A U B U C) = n(A)+n(B)+n(C) - n(AB)-n(AC)-n(BC) + n(ABC).

Desarranjo (Permutação Caótica)

Permutação de n elementos onde nenhum elemento permanece em sua posição original. Fórmula: D(n) = n! * soma de k=0 até n de ((-1)^k / k!).

Fórmula Recurrente dos Desarranjos

Relação recursiva para calcular permutações caóticas a partir de ordens anteriores. Fórmula: D(n) = (n - 1) * [D(n - 1) + D(n - 2)].

Partição de um Inteiro

Maneiras de escrever um número n como soma de inteiros positivos desconsiderando a ordem. Notação: p(n), sem fórmula fechada simples; usa funções geradoras.

Problema dos Palitos e Bolinhas (Barras e Estrelas)

Método para encontrar o número de soluções inteiras não negativas de x1 + x2 + ... + xn = k. Fórmula: C(k + n - 1, n - 1).

Soluções Inteiras Positivas de Equação Linear

Número de soluções com xi >= 1 para x1 + x2 + ... + xn = k, onde k >= n. Fórmula: C(k - 1, n - 1).

Anagrama

Transposição de letras de uma palavra para formar outra com ou sem sentido; caso de permutação. Fórmula: P(n) ou P(n; k1, k2, ...).

Combinações Complementares

Igualdade entre combinações simétricas em um conjunto de n elementos. Fórmula: C(n, p) = C(n, n - p).

Coeficiente Multinomial

Generalização do coeficiente binomial para a divisão de n elementos em múltiplos grupos de tamanhos k1, k2, ..., km. Fórmula: n! / (k1! * k2! * ... * km!).

Teorema Multinomial

Expansão algébrica de uma potência de soma com mais de dois termos. Fórmula: (x1 + ... + xm)^n = soma de [n! / (k1! * ... * km!)] * x1^k1 * ... * xm^km com soma(ki)=n.

Permutação Caótica de 2 elementos [D(2)]

Número de desarranjos de conjunto de 2 elementos. Valor: D(2) = 1.

Permutação Caótica de 3 elementos [D(3)]

Número de desarranjos de conjunto de 3 elementos. Valor: D(3) = 2.

Permutação Caótica de 4 elementos [D(4)]

Número de desarranjos de conjunto de 4 elementos. Valor: D(4) = 9.

Permutação Caótica de 5 elementos [D(5)]

Número de desarranjos de conjunto de 5 elementos. Valor: D(5) = 44.

Relação entre Arranjo e Combinação

Expressa arranjo como o produto de combinação pelo número de permutações do subconjunto. Fórmula: A(n, p) = C(n, p) * p!.

Subconjuntos de um Conjunto Finito

Quantidade total de subconjuntos possíveis formados a partir de um conjunto com n elementos. Fórmula: P(A) = 2^n.

Subconjuntos Próprios de um Conjunto Finito

Número de subconjuntos de um conjunto com n elementos excluindo o próprio conjunto original. Fórmula: 2^n - 1.

Grafo Completo - Contagem de Arestas

Número de arestas conectando todos os pares possíveis de n vértices distintos. Fórmula: C(n, 2) = n * (n - 1) / 2.

Diagonais de um Polígono Convexo

Número de segmentos que unem dois vértices não adjacentes de um polígono de n lados. Fórmula: d = n * (n - 3) / 2 = C(n, 2) - n.

Aperto de Mãos (Handshake Problem)

Total de interações entre pares distintos em um grupo de n pessoas. Fórmula: C(n, 2) = n * (n - 1) / 2.

Caminhos em uma Malha Quadriculada (Grid)

Maneiras de ir de (0,0) a (x,y) movendo-se apenas para a direita e para cima. Fórmula: C(x + y, x) = (x + y)! / (x! * y!).

Número de Stirling do Segundo Tipo

Número de maneiras de particionar um conjunto de n elementos em k subconjuntos não vazios. Notação: S(n, k) = (1/k!) * soma de j=0 a k de (-1)^(k-j) * C(k, j) * j^n.

Número de Bell

Número total de partições possíveis de um conjunto com n elementos distintos. Fórmula: B(n) = soma de k=0 até n de S(n, k).

Número de Catalan (Cn)

Contagem de estruturas discretas como árvores binárias e caminhos de Dyck. Fórmula: C_n = C(2n, n) / (n + 1) = (2n)! / ((n + 1)! * n!).

Permutação Caótica Assintótica

Proporção de permutações que são caóticas à medida que n tende ao infinito. Fórmula: D(n) / n! ≈ 1 / e ≈ 0,3679.

Lema de Kaplansky (1º Lema)

Número de subconjuntos com p elementos de {1, 2, ..., n} sem elementos consecutivos. Fórmula: K(n, p) = C(n - p + 1, p).

Lema de Kaplansky Circular (2º Lema)

Número de subconjuntos com p elementos de n organizados em círculo sem elementos consecutivos. Fórmula: KC(n, p) = [n / (n - p)] * C(n - p, p).

Identidade de Vandermonde

Identidade combinatorial para convolução de coeficientes binomiais. Fórmula: soma de k=0 a r de C(m, k) * C(n, r - k) = C(m + n, r).

Identidade de Pascal (Recorrência)

Propriedade básica de formação dos números binomiais. Fórmula: C(n, k) = C(n - 1, k - 1) + C(n - 1, k).