Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
Thank you very much. Yes that is what I wanted to do. Indeed it seems complicated than i thought. –  danny Jun 7 '13 at 14:46
    
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
    
Luckily for my problem permutations don't matter. –  danny Jun 7 '13 at 14:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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