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.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.