Contagem de composições inteiras

Uma composição ordenada de um inteiro positivo n é uma tupla de inteiros positivos que somam n, em que a ordem das partes faz parte da identidade: 1+3 e 3+1 são duas composições distintas de quatro. A combinatória clássica prova que o número dessas somas ordenadas é sempre dois elevado a n menos um. Esta capacidade aceita um único inteiro positivo n e devolve essa contagem exata, junto com a fórmula fechada 2^(n-1), para que você não precise enumerar cada tupla, percorrer uma árvore binária de separadores nem arriscar um erro de um ao conferir lições, casos de competição ou identidades de funções geradoras.

Por que o número de composições ordenadas é dois elevado a n menos um

Escreva n uns em uma fileira. Entre esses uns existem exatamente n menos um vãos. Em cada vão você pode inserir uma barra que parte a sequência em uma nova parte, ou deixar o vão vazio para que os uns adjacentes fiquem colados como uma parte maior.

Cada padrão de barras e vãos vazios produz uma composição ordenada de n, e toda composição nasce de exatamente um padrão desses. Como cada um dos n menos um vãos tem duas escolhas independentes, o número total de padrões é dois elevado a n menos um. Essa identidade é todo o algoritmo que esta capacidade avalia: ela não percorre ramos de primeira parte, não aloca um array de tuplas e não amostra.

Uma checagem de uma linha para n igual a quatro dá oito, coincidindo com as oito composições (4), (1,3), (3,1), (2,2), (1,1,2), (1,2,1), (2,1,1) e (1,1,1,1). Para n igual a um há um único padrão sem barras e a contagem é um, a própria composição (1). A forma fechada é exata para todo inteiro positivo, de modo que um trabalho que afirme nove composições de quatro está simplesmente errado, e um gerador que precise do tamanho da família de composições pode dimensionar buffers com esta contagem sem nunca listá-las.

A ordem é essencial: se você identifica 1+3 com 3+1, saiu das composições e entrou no mundo das partições, cuja contagem p(n) não tem essa fórmula de potência de dois e é uma intenção de busca diferente.

O que você envia, o que recebe de volta e quando a requisição falha

A regra de produto é rígida: n abaixo de um é inválido, inclusive zero e todo negativo, porque a definição usual de composição exige um inteiro positivo a compor. Em caso de sucesso, a resposta ecoa o n normalizado, devolve count como string decimal do valor exato 2^(n-1) e inclui formula como a string de identidade 2^(n-1) para que os clientes mostrem o teorema sem codificá-lo à mão.

A contagem é uma string de propósito: dois elevado a cinquenta e três já deixa o intervalo de inteiros seguros do JavaScript, e esta página é útil justamente quando n é grande o bastante para que listar cada composição seja inviável. Validação falha não é cobrada.

Onde uma contagem de composições se encaixa e como é cobrada

Use esta contagem quando a pergunta for quantas somas ordenadas existem, não quais são as tuplas. Programadores de competição confrontam soluções candidatas de problemas de contagem de composições com um oráculo determinístico em vez de reimplementar uma potência BigInt em cada harness de linguagem. Professores passam a prova dos vãos e barras e precisam de uma checagem automática de que 2^(n-1) é de fato o tamanho da família antes de os alunos tentarem listá-la.

Sandboxes de entrevista e demos de funções geradoras precisam do mesmo número sempre que perguntam. Trabalho de dados e de compiladores às vezes dimensiona um espaço de busca de divisões por etapas ordenadas de um orçamento n e precisa conhecer a cardinalidade antes de alocar.

Se você realmente precisa de cada tupla, pare aqui e use uma ferramenta de listagem com um n pequeno; se precisa de composições em exatamente k partes, isso é o binomial C(n-1, k-1) e outra página; se a ordem não importa, você quer a função de partição p(n). Mantenha n dentro dos limites documentados, trate a string count como o inteiro exato e você obtém uma contagem de composições reproduzível sem instalar um sistema de álgebra computacional.