Calculadora de partições inteiras

A função de partição inteira p(n) responde a uma pergunta clássica de contagem: de quantas maneiras é possível escrever um inteiro não negativo n como soma de inteiros positivos quando a ordem das parcelas não importa? Por exemplo, 4 é igual a 4, 3+1, 2+2, 2+1+1 e 1+1+1+1, de modo que p(4) vale cinco; 5 tem sete partições e 10 tem quarenta e dois. Partições aparecem em teoria dos números, funções geradoras, mecânica estatística e maratonas de programação sempre que se contam somas de multiconjuntos em vez de composições ordenadas ou partições de conjuntos rotulados. Esta capacidade aceita um inteiro não negativo n e devolve o p(n) exato como string decimal calculada com programação dinâmica em BigInt, para que valores bem além dos limites habituais de inteiros seguros permaneçam corretos dígito a dígito. Um n negativo é rejeitado com erro claro de validação em vez de um zero silencioso ou uma resposta errada.

Como a função de partição p(n) é definida

Uma partição inteira irrestrita de um inteiro não negativo n é uma forma de escrever n como soma de inteiros positivos em que a ordem das parcelas é irrelevante. Por convenção p(0) vale um, contando a partição vazia de zero. Valores clássicos de livro-texto são p(1)=1, p(2)=2 (a saber, 2 e 1+1), p(3)=3, p(4)=5, p(5)=7, p(6)=11 e p(10)=42.

A função geradora ordinária da sequência é o produto infinito, sobre k maior ou igual a um, de um sobre um menos x elevado a k, que codifica que cada inteiro positivo pode aparecer qualquer número de vezes como parte. Uma recorrência prática usada em software é o programa dinâmico clássico no estilo do troco de moedas: inicializa-se um array com uma forma de formar a soma zero e, para cada tamanho de parte de um até n, somam-se as formas de completar o restante.

Essa recorrência preenche p(n) de forma exata e nunca conta ordenações em dobro porque as partes são introduzidas em ordem não decrescente de tamanho apenas uma vez.

Objetos relacionados, porém distintos, incluem composições, em que a ordem importa e há dois elevado a n menos um composições de n; partições de conjuntos contadas por números de Stirling de segunda espécie ou números de Bell, que particionam elementos rotulados em vez de somar inteiros positivos sem rótulo; e partições restritas que exigem partes distintas, apenas partes ímpares ou um número fixo de partes.

Esta implementação nunca usa aproximação em ponto flutuante, amostragem Monte Carlo nem tabelas externas: preenche um array unidimensional de BigInt para que cada dígito seja correto. O caminho é plenamente determinístico —sem sementes aleatórias, sem relógios, sem rede e sem deriva de modelo—, de modo que o mesmo n sempre produz a mesma string.

Onde partições inteiras aparecem no trabalho real

Cursos de teoria dos números e maratonas de programação perguntam constantemente quantas partições irrestritas um dado n tem, como p(n) cresce ou se uma tabela de valores pequenos coincide com as congruências de Ramanujan e outras identidades clássicas. Projetistas de algoritmos usam contagens de partições ao analisar espaços de estado no estilo mochila inteira, ao contar decomposições em multiconjuntos de um orçamento de recursos ou ao dimensionar tabelas de DP cujas dimensões acompanham tamanhos de parte.

Contextos de física e combinatória ligam p(n) a funções de partição bosônicas e coeficientes de funções geradoras; educadores costumam mostrar uma lista curta de partições de um n pequeno e depois pedir apenas a contagem. Preparação para entrevistas e treino olímpico frequentemente precisam de um p(n) confiável sem manter à mão tabelas grandes nem arriscar contagens de composições com erro de um.

Se mais tarde você precisar de composições em que a ordem importa, partições de conjuntos via números de Stirling de segunda espécie, apenas números de Bell, partições restritas com partes distintas ou só ímpares, ou um listagem explícita de cada partição em vez da contagem, trate-os como intenções de busca separadas em vez de sobrecarregar esta página.

Mantenha n dentro do limite documentado para que a latência do nível gratuito permaneça previsível, e prefira consumidores de string para o valor devolvido porque p(n) deixa a faixa de inteiros seguros muito antes de cinco mil.