Matemática: Combinatória e Probabilidade

Introdução Teórica

A análise combinatória nos permite contar o número de maneiras de organizar ou selecionar objetos sem listar todos eles. Em computação, isso geralmente envolve calcular coeficientes grandes modulo um número primo.

Estruturas Básicas

  • Permutação (\(P_n\)): Modos de ordenar \(n\) itens distintos. \(P_n = n!\).
  • Arranjo (\(A_{n,k}\)): Escolher e ordenar \(k\) itens de \(n\). \(A_{n,k} = \frac{n!}{(n-k)!}\).
  • Combinação (\(C_{n,k}\) ou \(\binom{n}{k}\)): Escolher \(k\) itens de \(n\) sem importar a ordem.
    • Fórmula: \(\binom{n}{k} = \frac{n!}{k!(n-k)!}\).
    • Triângulo de Pascal: Permite calcular \(\binom{n}{k}\) usando soma: \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\). Isso evita lidar com números gigantes (fatoriais) diretamente quando precisamos apenas do módulo ou quando \(N\) é pequeno (< 2000).

Princípios

  • Aditivo: Se A e B são disjuntos, \(|A \cup B| = |A| + |B|\).
  • Multiplicativo: Se uma tarefa tem etapas independentes, multiplicamos as possibilidades.

Problema Clássico

Problema: Triângulo de Pascal / Coeficientes Binomiais Link: Beecrowd 1582 (Pede Triplas Pitagóricas e MDC, mas o contexto matemático é similar em profundidade).

Problema Mais Direto: Beecrowd 1585 (Fazendo Pandorgas - Geometria simples, mas ilustra matemática).

Melhor Exemplo de Contagem: Link: Beecrowd 1093 (Vampiros) -> Envolve Probabilidade (Gambler’s Ruin), que é extensão da combinatória.

Vamos focar na construção: Para muitos problemas de Programação Dinâmica (como contar caminhos em um grid), usamos a relação de Pascal \(\binom{n}{k}\).

Variações e Exercícios

  1. [Cara ou Coroa]
    • Foco: Probabilidade simples e contagem de vitórias.
    • Link: Beecrowd 1329
  2. [Criptografia / Ataque de Força Bruta]
    • Problemas que pedem para estimar “quantas senhas possíveis” são de combinatória.
  3. [Soma de Fatoriais]
Back to top