Combinatoria E Fatorial

Calculando permutações e combinações sem perder a paciência

A maioria das pessoas trava na hora de decidir se usa P, C ou A. O problema não é a matemática em si, mas a confusão entre arranjo, combinação e permutação simples. Eu fui um deles até tentar resolver um problema prático que envolvia montar listas de execução para um script que processava lotes de arquivos.

O que todo mundo precisa saber sobre combinatoria e fatorial

Fatorial é apenas uma forma compacta de escrever multiplicações encadeadas. N! = n × (n-1) × (n-2) × ... × 1. Pronto. Isso serve de base para tudo que vem depois. O ponto que ninguém explica direito é que fatorial cresce de forma absurda. 10! já é 3.628.800. 20! ultrapassa 2 trilhões e qualquer tipo inteiro comum estoura em 21!. Isso importa porque afeta diretamente como você vai implementar isso no código.

Método prático: quando usar cada fórmula

A primeira pergunta que você deve se fazer é: ordem importa? Se sim, é arranjo ou permutação. Se não, é combinação. Permutação é um caso especial de arranjo onde todos os elementos do grupo são usados. A fórmula de arranjo é A(n,k) = n! / (n-k)!. Combinação é C(n,k) = n! / (k! × (n-k)!). Note que você nunca precisa calcular o fatorial completo de numerais grandes — sempre há cancelamento. Na prática, eu parei de calcular fatoriais inteiros há anos. O que eu faço é simplificar antes de multiplicar. Por exemplo, C(52,5) parece pedir 52!, mas na verdade fica 52×51×50×49×48 dividido por 5×4×3×2×1. O resultado é 2.598.960, e você chega nisso sem jamais precisar lidar com 52!. Isso economiza tempo de processamento e evita estouro de memória em linguagens que não têm aritmética de BigNumber nativa.

Problema real que eu enfrentei

Eu precisava calcular C(1000, 500) mod 10^9+7 para um sistema de geração de chaves. Tentar calcular 1000! diretamente era inviável — o número tem cerca de 2568 dígitos. A solução foi usar o teorema de Lucas combinado com inversos modulares. Basicamente, você decompõe n e k na base do módulo primo e calcula combinações menores. Para um módulo primo p, C(n,k) mod p = produto de C(ni, ki) mod p, onde ni e ki são os dígitos de n e k na base p. Com isso, C(1000,500) mod 10^9+7 foi resolvido em menos de 1ms, enquanto a abordagem ingênua travava o interpretador Python inteiro.

Pegadinhas que custaram horas do meu tempo

Primeiro: C(n,k) = C(n, n-k). Sempre calcule usando o menor k. C(100,90) deve ser resolvido como C(100,10). A diferença no número de operações é gritante. Segundo: muitos frameworks e calculadoras online retornam erro ou Infinity para n maior que 170 porque double flutuante não aguenta. Se você trabalha com valores grandes, esqueça as ferramentas prontas e implemente sua própria função usando simplificação fracionária passo a passo.

Terceiro: permutações com repetição. Se você tem um anagrama de "BANANA", não divide 6! por 3!×2!×1!achando que é combinação. É permutação com repetição, e a fórmula correta é n! / (n1! × n2! × ... × nk!) onde os denominadores são as contagens de cada elemento repetido. Confundir isso com combinação é o erro mais comum que eu vejo em fóruns técnicos.

Quando a abordagem factorial simplesmente não funciona

Se o módulo não for primo, o teorema de Lucas não se aplica diretamente. Você precisa usar a generalização de Granville ou fatorar o módulo e aplicar o teorema chinês do resto. Também não adianta tentar calcular C(n,k) exato para n acima de 10.000 em memória RAM convencional — o número de dígitos excede facilmente o que cabe em variáveis padrão. Nesses casos, trabalhe sempre com representações simbólicas ou bibliotecas como GMP para aritmética de precisão arbitrária. O essencial é entender que fatorial é ferramenta, não resposta. A habilidade real está em reconhecer quando ele pode ser cancelado, simplificado ou substituído por uma técnica modular antes mesmo de abrir uma calculadora.