sum factors of natural numbers

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.

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

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.
• 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 :-) – Peter Košinár Jun 7 '13 at 14:47