Calcular Combinatoria

O que realmente acontece quando você precisa calcular combinações

A fórmula de combinações simples é C(n,p) = n! / (p! × (n-p)!). A maioria dos livros para por aí. Na prática, o problema não é decorar a fórmula — é lidar com os casos em que ela quebra no seu código ou na sua planilha. Já vi gente perder duas horas tentando entender por que o fatorial de 34 cabia em um número inteiro e o de 35 estourava. O estouro acontece porque 35! 1,03 × 10^40, e o double do IEEE 754 suporta até cerca de 1,8 × 10^308, então o estouro de precisão vem antes do estouro de variável. O que quebra de verdade é a perda de precisão quando você divide dois fatorais enormes para número muito menor. O jeito que eu uso hoje é simplificar antes de multiplicar. Em vez de calcular n! inteiro e depois dividir, você expande apenas o numerador até o ponto em que cancela com o denominador. C(52,5) vira 52×51×50×49×48 dividido por 5×4×3×2×1. Multiplica-se termo a termo, fazendo divisão sempre que o produto atual for divisível pelo próximo fator do denominador. Isso mantém os números intermediários menores e evita overflow em linguagens com tipos inteiros fixos. Se precisar de velocidade e puder usar Python, a função math.comb está disponível desde a versão 3.8 e usa aritmética de inteiros exatos, então o resultado nunca perde precisão. Em JavaScript, não existe função nativa equivalente — você implementa o algoritmo simplificado ou usa BigInt. A diferença entre uma implementação ingênua de fatorial e a versão simplificada costuma ser a diferença entre 0,02ms e 2ms para C(200,100), mas o ganho real aparece quando você chama a função milhões de vezes num loop de simulação.

Permutações e arranjos: a confusão que todo mundo tem

Combinatória, arranjo e permutação são coisas diferentes e a maioria das pessoas trata como sinônimo. Arranjo simples considera ordem: A(n,p) = n! / (n-p)!. Permutação é arranjo onde p = n, ou seja, A(n,n) = n!. Combinação ignora ordem. Essa distinção importa porque trocar um arrangemento por uma combinação no seu código altera o resultado por um fator de p!. EmProbabilidades, errar isso é o erro mais comum que eu vejo em código de simulation. Um caso específico que me deu trabalho foi calcular combinações com repetição para um problema de alocação de recursos. A fórmula é C(n+p-1, p). Eu estava lidando com n=50 e p=30, o que dá C(79,30). O resultado é 8,29 × 10^20. Em C#, tentei armazenar isso em um long e o valor transbordou porque long.MaxValue é 9,22 × 10^18. A solução foi usar BigInteger. Se você trabalha com números desse porte em Cou Java, não brigue com double — use a classe BigInteger nativa do idioma. Isso elimina o problema de overflow e ainda mantém a aritmética exata.

Coisas que ninguém conta sobre calcular combinatoria

O primeiro insight contra-intuitivo é que calcular o logaritmo da combinação é quase sempre mais útil do que calcular a combinação em si. Log(C(n,k)) = log(n!) - log(k!) - log((n-k)!), e você pode pré-computar uma tabela de somas logarítmicas de fatoriais em O(n). Isso transforma um cálculo que envolve números de 300 dígitos em uma subtração de floats. Em modelos de machine learning que precisam comparar probabilidades combinatórias, essa abordagem é padrão. Sem ela, você acaba com underflow em quase qualquer implementação real. O segundo ponto é sobre simetria. C(n,k) = C(n,n-k). Isso parece óbvio, mas em código eu vejo gente calcular C(1000,900) fazendo 100 multiplicações em vez de C(1000,100), que precisa de apenas 100. A diferença entre 1000 iterações e 100 iterações é enorme quando isso está dentro de um loop duplo em R ou em um script Python rodando em dados grandes. Sempre substitua k por min(k, n-k) antes de começar.

Quando a abordagem tradicional falha completamente

Se você precisa de C(n,k) módulo um número primo, a fórmula direta com fatoriais não serve porque a divisão não existe no mesmo sentido. Aí você usa o Teorema de Lucas. Para n grande e k grande, o custo de calcular fatoriais com módulo p ainda é linear em n, mas para múltiplas consultas o preço se paga rapidamente. Se o módulo não for primo, a coisa complica — a inversa multiplicativa nem sempre existe e você precisa fatorar o módulo primeiro. Nesse cenário, eu recomendo usar uma biblioteca específica em vez de implementar do zero. O problema mais chato que eu encontrei foi em um projeto de análise de dados genômicos onde precisei calcular valores-p baseados em hipergeometria acumulada. A função hipergeométrica usa combinações dentro de somas, e os termos podiam variar em ordens de magnitude de 10^60 entre si. Somar esses termos diretamente resultava em catástrofe numérica — os termos pequenos eram completamente perdidos pelo arredondamento. A solução foi trabalhar totalmente no espaço logarítmico, somando usando a técnica log-sum-exp, que traz o maior log-termo para fora da soma antes de converter de volta. Isso transformou um cálculo que dava resultados sem sentido em algo estável.

Implementação prática em Python

Se você quer um código que funcione e seja rápido, aqui está a versão que eu uso: from math import comb
resultado = comb(52, 5)
print(resultado) Isso retorna 2.598.960. Se precisar de controle maior, implemente a versão simplificada com inteiros:

def combinacao(n, k):
k = min(k, n - k)
if k == 0:
return 1
resultado = 1
for i in range(k):
resultado = resultado * (n - i) // (i + 1)
return resultado O operador // garante divisão inteira em Python, e como a combinação de inteiros sempre resulta em inteiro, a divisão sempre será exata a cada passo. Isso é importante: se você usar / no lugar, vai trabalhar com floats e perder precisão.

Limitações reais que você precisa saber

Nenhuma fórmula de combinatoria te ajuda quando o espaço amostral é tão grande que você não consegue enumerar os resultados. C(1000,500) 10^300. Esse número é maior do que a quantidade de átomos no universo observável. Se o seu problema exige você listar todas as combinações possíveis, pare agora e reformule. A melhor estratégia nesses casos é amostragem Monte Carlo ou métodos de importância, não cálculo exato. Outro ponto: calculadoras online que prometem "calcular combinatoria" geralmente usam double e começam a errar a partir de C(67,33). O resultado exibido parece correto porque o double representa 15 dígitos significativos, mas os últimos dígitos já estão poluídos. Se você precisa de exatidão, use aritmética de inteiros. Sempre. Para quem quer uma referência rápida e gratuita, a OEIS (Online Encyclopedia of Integer Sequences) tem a sequência A000984 com os coeficientes binomiais e A008288 com o triângulo de Pascal completo. Não é uma ferramenta de cálculo, mas é útil para verificar se o seu resultado bate com valores conhecidos.