2
$\begingroup$

Using natural numbers 1,2,...n, in how many ways can the number n be formed from the sum of one or more smaller natural numbers? I thought it would be an easy problem but i couldn't figure it out. Example: For n = 4, we have 4,1 + 3, 2 + 2, 1 + 1 + 2, 1 + 1 + 1 + 1 for a total of 5.

$\endgroup$
  • $\begingroup$ What prevents you from writing $4=1+1+1+1$? $\endgroup$ – Peter Košinár Jun 7 '13 at 14:38
  • $\begingroup$ Thanks, i corrected that. I guess i can also add 4 if i changed the question to 1 or more sums. $\endgroup$ – danny Jun 7 '13 at 14:40
4
$\begingroup$

The answer is complicated and you've missed $4=1+1+1+1$ in your question. You are looking for partitions - the link has a good bibliography. The exact formula is surprisingly complicated. Your question involves subtracting 1 from the number of partitions as conventionally calculated.

$\endgroup$
  • $\begingroup$ Thank you very much. Yes that is what I wanted to do. Indeed it seems complicated than i thought. $\endgroup$ – danny Jun 7 '13 at 14:46
  • $\begingroup$ The problem gets a lot easier if one treats different orders of the same numbers as different (e.g. $1+3$ being different from $3+1$)... but that's a completely different beast to tackle :-) $\endgroup$ – Peter Košinár Jun 7 '13 at 14:47
  • $\begingroup$ Luckily for my problem permutations don't matter. $\endgroup$ – danny Jun 7 '13 at 14:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.