Partições em partes distintas

A função de partição em partes distintas q(n) responde a uma pergunta clássica da teoria dos números: de quantas formas você pode escrever um inteiro não negativo n como soma de inteiros positivos quando cada parcela aparece no máximo uma vez e a ordem não importa? Por exemplo, 5 é igual a 5, 4+1 e 3+2, de modo que q(5) vale três; 6 tem quatro partições em partes distintas e 10 tem dez. Essa contagem difere da função de partição irrestrita p(n), que permite partes repetidas como 2+2 ou 1+1+1. Partições em partes distintas aparecem em identidades de funções geradoras, no teorema de Euler que as equipara às de partes ímpares, em olimpíadas e em exercícios de programação dinâmica. Esta capacidade aceita um inteiro não negativo n e devolve o q(n) exato como string decimal calculada com programação dinâmica 0-1 em BigInt, de modo que valores além dos inteiros seguros permanecem corretos dígito a dígito. Um n negativo é rejeitado com erro de validação claro em vez de um zero silencioso ou uma resposta errada.

Como partições em partes distintas são definidas e contadas

Uma partição de um inteiro não negativo n em partes distintas é uma forma de escrever n como soma de inteiros positivos em que nenhuma parte se repete e a ordem das parcelas é irrelevante. Por convenção q(0) vale um, contando a partição vazia do zero. Valores clássicos de livro são q(1)=1 (a saber, 1), q(2)=1 (a saber, 2), q(3)=2 (3 e 2+1), q(4)=2 (4 e 3+1), q(5)=3 (5, 4+1, 3+2), q(6)=4 e q(10)=10.

A função geradora ordinária da sequência é o produto infinito sobre k maior ou igual a um de um mais x elevado a k, o que codifica que cada inteiro positivo pode aparecer zero vezes ou exatamente uma vez como parte.

Um algoritmo prático em software é o programa dinâmico clássico estilo mochila 0-1: inicialize um arranjo com uma forma de formar a soma zero e, para cada tamanho de parte de um até n, percorra o arranjo de somas restantes de n para baixo até esse tamanho e some as formas que excluem a parte às que a incluem. A ordem descendente garante que cada parte seja usada no máximo uma vez, de modo que o uso múltiplo irrestrito nunca ocorre.

Objetos relacionados mas diferentes incluem partições irrestritas p(n), em que partes podem se repetir; composições, em que a ordem importa; partições de conjuntos contadas por números de Stirling de segunda espécie; e partições só em partes ímpares, que Euler provou equinumeráveis às de partes distintas para todo n. Esta implementação não usa aproximação em ponto flutuante, amostragem Monte Carlo nem tabelas externas: preenche um arranjo unidimensional BigInt para que cada dígito seja correto.

O caminho é totalmente determinístico —sem sementes aleatórias, relógios, rede nem deriva de modelo—, de modo que o mesmo n sempre produz a mesma string.

Onde partições em partes distintas aparecem no trabalho real

Cursos de teoria dos números e competições de programação perguntam com frequência quantas partições de n usam parcelas pairwise distintas, como essa contagem se compara com p(n) irrestrita, ou se uma tabela de valores pequenos coincide com a identidade de Euler com partições em partes ímpares.

Projetistas de algoritmos usam contagens em partes distintas ao analisar espaços de estado estilo subset-sum 0-1, ao contar combinações de tamanhos de recurso únicos que totalizam um orçamento, ou ao dimensionar tabelas de DP cujas dimensões acompanham tamanhos de parte usados no máximo uma vez. Lições de combinatória e funções geradoras conectam q(n) ao produto de um mais x elevado a k e a identidades restritas tipo Rogers–Ramanujan; educadores costumam listar as partições distintas de um n pequeno e depois pedir só a contagem.

Preparação para entrevistas e olimpíadas frequentemente precisa de um q(n) confiável sem manter tabelas à mão nem contar por engano composições ou partições irrestritas. Se mais tarde você precisar de p(n) irrestrita, composições em que a ordem importa, partições de conjuntos via Stirling de segunda espécie, ou uma listagem explícita de cada partição em partes distintas 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 seja previsível, e prefira consumidores de string para o valor devolvido porque q(n) acaba saindo da faixa de inteiros seguros para argumentos grandes.