Partições de um número inteiro e formas de formar um valor com moedas
Conte as partições de n (com k partes, em partes distintas) e as formas de compor ou trocar um valor com um conjunto de moedas.
- Roda no seu navegador
Resultado
O resultado aparece aqui.
Contar partições e trocos
Uma partição de n é uma forma de escrever n como soma de inteiros positivos, sem importar a ordem: 4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1 e 4 (cinco partições). A ferramenta conta as partições e as formas de formar um valor com moedas que você informa.
| Cálculo | O que conta | Exemplo |
|---|---|---|
| Partições p(n) | somas de inteiros positivos, sem ordem | p(100) = 190.569.292 |
| Com k partes | exatamente k parcelas | 10 em 3 partes: 8 |
| Partes distintas | sem parcelas repetidas | 10: 10 |
| Troco com moedas | combinações de moedas, sem ordem | 100 com 1, 5, 10, 25 e 50: 292 |
| Composições com moedas | a ordem das moedas importa | 10 com 1 e 2: 89 |
p(n) = Σ (−1)^(k+1) · [p(n − k(3k − 1)/2) + p(n − k(3k + 1)/2)] (teorema do número pentagonal de Euler)
Troco e composições
No troco, a ordem não conta: há 292 maneiras de formar 100 com moedas de 1, 5, 10, 25 e 50. Nas composições, 1 + 2 e 2 + 1 são diferentes: há 89 maneiras de formar 10 com 1 e 2, os números de Fibonacci.
Limites
- p(n) vai até 2.000; com k partes, até 500; partes distintas, até 1.000. Com moedas, o valor vai até 10.000 e a lista tem até 50 moedas de 1 a 10.000 (repetidas contam uma vez).
- A ferramenta conta, não lista as partições. O resultado é exato e completo.
Perguntas frequentes
Quantas partições tem um número inteiro?
Depende do número e cresce depressa: 10 tem 42 e 100 tem 190.569.292 partições.
De quantas maneiras posso dar troco com moedas?
Informe o valor e as moedas. Com moedas de 1, 5, 10, 25 e 50, há 292 maneiras de formar 100.
Qual a diferença entre partição e composição?
Na partição a ordem das parcelas não conta; na composição conta. Para 10 com moedas de 1 e 2 são 89 composições.