Published

25/05/2026

Modified

22/04/2026

Matemática: Combinatória e Probabilidade

Metáfora e Motivação

A Análise Combinatória constrói a fundação de algoritmos probabilísticos. Na Programação Competitiva, muitas vezes os números gerados por permutações excedem os limites numéricos básicos (Integer Overflow), forçando você a criar uma tecelagem matemática para recuperar fatias específicas sem precisar gerar o conjunto inteiro.

Introdução Teórica

  1. Permutação (\(P_n\)): Modos de ordenar \(n\) itens distintos de forma exaustiva. \(P_n = n!\).
  2. Arranjo (\(A_{n,k}\)): Selecionar uma equipe de \(k\) pessoas onde o “Cargo/Ordem” importa. \(A_{n,k} = \frac{n!}{(n-k)!}\).
  3. Combinação Numérica (\(\binom{n}{k}\)): Selecionar \(k\) amostras de um tanque de \(n\) onde a ordem genética não importa.
    • \(\binom{n}{k} = \frac{n!}{k!(n-k)!}\)

O Fantástico Triângulo de Pascal

Evite calcular fatoriais diretamente (eles quebram o código a partir do \(20!\)). Se você precisa de muitas combinações seguidas nas maratonas onde \(N \le 2000\), podemos usar Programação Dinâmica simples somando os ombros de trás sem jamais tocar em multiplicações de fatoriais brutais!

Regra do Triângulo: O bloco na linha \(N\) coluna \(K\), é exatamente a soma dos dois blocos imediatamente acima dele: \[\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\]

Algoritmo Pascal via Adição (O Fim do Fatorial)

O código C++ para computar combinações gigantescas baseadas apenas em matrizes aditivas:

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

// Podemos usar modulos em maratonas Ex: 1e9 + 7 se for gigantesco
const int MOD = 1e9 + 7;
long long pascal_DP[2010][2010];

// Popula o triângulo inteiro com Complexidade O(N^2) garantindo acesso a QUALQUER COMBINACAO!
void plota_pascal(int limite) {
    for (int n = 0; n <= limite; ++n) {
        pascal_DP[n][0] = 1; // n Escolhe 0 = Sair de maos vazias (1 forma)
        pascal_DP[n][n] = 1; // n Escolhe N = Pegar todos (1 forma)
        
        for (int k = 1; k < n; ++k) {
            // A magica da Combinatoria vira Programacao Dinâmica!
            pascal_DP[n][k] = (pascal_DP[n-1][k-1] + pascal_DP[n-1][k]) % MOD;
        }
    }
}

void executando_testes() {
    // Calcularemos Pascal ate o número 10
    plota_pascal(10);
    
    // Teste 1: 5 Escolhe 2 deve ser 10 (Ex: 5! / (2! * 3!))
    assert(pascal_DP[5][2] == 10);
    
    // Teste 2: 10 Escolhe 5 deve ser 252. O meio exato da linha 10!
    assert(pascal_DP[10][5] == 252);
    
    // Essa memoria aguenta tranquilamente coisas gigantescas em milissegundos.
    cout << "[✅] Matriz Dinâmica de Pascal operando, livre de Fatoriais mortais!\n";
}

int main() {
    executando_testes();
    return 0;
}

A base probabilística de “Cara ou Coroa” ou “Random Walks” (Passos Aleatórios em X e Y) cai sempre na coluna das Combinações de Pascal se ignorarmos moedas viciadas.

Exercício Prático

Você é capaz de contar os caminhos numa malha \(N \times M\) do topo à base? Em cada quadrado, você só anda para Baixo ou Direita. A fórmula total cai nas nuvens do Triângulo de Pascal! Busque aplicar \(\binom{N+M}{N}\). Experimente no Beecrowd 1585 / 1582.

Problemas de Maratona Sugeridos (Combinatórias Extensivas)

Back to top