Análise Combinatória

Cartões · 59

Princípio Fundamental da Contagem (Regra do Produto)

Se uma decisão pode ser tomada de m modos e uma segunda de n modos, o total de decisões sucessivas é m × n.

Princípio Aditivo

Se dois conjuntos de eventos A e B são mutuamente exclusivos, o número de maneiras de A ou B ocorrer é n(A) + n(B).

Fatorial de n (n!)

Produto de todos os inteiros positivos de 1 até n. Exemplo: n! = n × (n - 1) × ... × 2 × 1.

Fatorial de 0 (0!)

Por definição matemática e consistência combinatória, 0! = 1.

Fatorial de 1 (1!)

1! = 1.

Relação recursiva do Fatorial

n! = n × (n - 1)!, válida para todo n maior ou igual a 1.

Permutação Simples (definição)

Reagrupamento ordenado de todos os n elementos distintos de um conjunto.

Fórmula da Permutação Simples

Pn = n!

Anagrama

Qualquer transposição ou rearranjo das letras de uma palavra, formando palavras com ou sem sentido.

Permutação Circular (definição)

Disposição ordenada de n elementos ao redor de um círculo fechado, onde rotações são consideradas idênticas.

Fórmula da Permutação Circular

PCn = (n - 1)!

Permutação com Repetição (definição)

Arranjo ordenado de n elementos em que alguns elementos aparecem repetidos alfa, beta, gama vezes.

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

P(n; a, b, ...) = n! / (a! × b! × ...)

Diferença essencial: Arranjo vs Combinação

No Arranjo, a ordem dos elementos importa (posições distintas). Na Combinação, a ordem dos elementos não importa.

Arranjo Simples (definição)

Agrupamento ordenado de p elementos escolhidos dentre n elementos distintos, onde n é maior ou igual a p.

Fórmula do Arranjo Simples

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

Arranjo com Repetição (definição)

Sequência de p posições onde cada posição pode ser preenchida por qualquer um dos n elementos disponíveis.

Fórmula do Arranjo com Repetição

AR(n, p) = n elevado a p (n^p).

Combinação Simples (definição)

Subconjunto formado por p elementos não ordenados escolhidos a partir de um conjunto com n elementos distintos.

Fórmula da Combinação Simples

C(n, p) = n! / (p! × (n - p)!)

Relação entre Arranjo e Combinação Simples

A(n, p) = p! × C(n, p) ou C(n, p) = A(n, p) / p!

Combinações Complementares

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

Número de subconjuntos de um conjunto com n elementos

2^n, que equivale à soma C(n, 0) + C(n, 1) + ... + C(n, n).

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

Seleção não ordenada de p objetos dentre n tipos disponíveis, podendo haver repetições de tipos.

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

CR(n, p) = C(n + p - 1, p)

Método dos Traços e Bolinhas (Stars and Bars)

Técnica para resolver equações lineares com inteiros não negativos; equivale a CR(n, p).

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

Número de soluções dado por C(k + n - 1, k) ou C(k + n - 1, n - 1).

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

Número de soluções dado por C(k - 1, n - 1), com k maior ou igual a n.

Coeficiente Binomial (notação)

(n sobre p) representa C(n, p), lido como n escolhe p.

Triângulo de Pascal

Disposição triangular de coeficientes binomiais onde a linha n contém (n sobre 0) até (n sobre n).

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.

Teorema das Linhas no Triângulo de Pascal

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

Teorema das Colunas no Triângulo de Pascal

A soma dos elementos de uma coluna p do topo até a linha n é igual a C(n + 1, p + 1).

Teorema das Diagonais no Triângulo de Pascal

A soma dos elementos ao longo de uma diagonal até certo ponto é igual ao elemento logo abaixo na coluna.

Binômio de Newton (fórmula da expansão)

(x + y)^n = somatório de k=0 até n de C(n, k) × x^(n - k) × y^k.

Termo Geral do Binômio de Newton

T(k + 1) = C(n, k) × x^(n - k) × y^k, representando o termo de ordem k + 1 na expansão.

Número de termos na expansão de (x + y)^n

A expansão de (x + y)^n possui exatamente n + 1 termos.

Termo Central do Binômio de Newton

Se n é par, há 1 termo central em k = n/2. Se n é ímpar, há 2 termos centrais médios.

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

Se n pombos forem colocados em m gavetas com n > m, pelo menos uma gaveta conterá 2 ou mais pombos.

Princípio das Casas dos Pombos Generalizado

Se n itens forem postos em k caixas, ao menos uma caixa conterá teto(n / k) itens.

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

|A união B| = |A| + |B| - |A inter B|

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

|A união B união C| = |A| + |B| + |C| - (|AB| + |AC| + |BC|) + |ABC|

Desarranjo ou Permutação Caótica (definição)

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

Notação e aproximação do Desarranjo (!n)

!n é o número de desarranjos de n elementos, aproximado por n! / e para n suficientemente grande.

Fórmula recursiva do Desarranjo (!n)

!n = (n - 1) × (!(n - 1) + !(n - 2)), com !1 = 0 e !2 = 1.

Fórmula explícita do Desarranjo (!n)

!n = n! × somatório de k=0 até n de (-1)^k / k!

Identidade de Euler no Triângulo de Pascal

C(n, 0) - C(n, 1) + C(n, 2) - ... + (-1)^n C(n, n) = 0 para n > 0.

Permutação Caótica de 3 elementos (!3)

!3 = 3! × (1/0! - 1/1! + 1/2! - 1/3!) = 6 × (1/2 - 1/6) = 2.

Permutação Caótica de 4 elementos (!4)

!4 = 9.

Multinômio de Newton (definição)

Expansão de potências de somas com mais de 2 termos, dada por (x1 + x2 + ... + xm)^n.

Coeficiente Multinomial

n! / (k1! × k2! × ... × km!), onde k1 + k2 + ... + km = n.

Número de termos na expansão de (x1 + x2 + ... + xm)^n

Equivale ao número de soluções inteiras não negativas: C(n + m - 1, m - 1).

Combinações com elementos juntos (Técnica do Bloco)

Tratam-se os elementos que devem ficar juntos como um único elemento e multiplica-se pela permutação interna do bloco.

Combinações com elementos separados (Técnica dos Espaços)

Organizam-se primeiro os elementos livres e colocam-se os elementos restritos nos espaços vazios entre eles.

Contagem pelo Complementar

Total de casos favoráveis = Total absoluto de casos possíveis - Casos não favoráveis (proibidos).

Partição de um Conjunto (definição)

Divisão de um conjunto em subconjuntos não vazios e disjuntos cuja união é o conjunto original.

Números de Stirling de Segunda Espécie S(n, k)

Número de maneiras de particionar um conjunto de n elementos distintos em k subconjuntos não vazios.

Relação recursiva dos Números de Stirling S(n, k)

S(n, k) = S(n - 1, k - 1) + k × S(n - 1, k).

Número de Bell B(n)

Total de partições possíveis de um conjunto com n elementos, soma de S(n, k) para k de 1 até n.