What are the following types of numbers called?

Sep 2009
177
18
Let n be a natural number, then s is the number of ways to write n as the sum of at least one natural number. What is the number s called?
 

undefined

MHF Hall of Honor
Mar 2010
2,340
821
Chicago
Let n be a natural number, then s is the number of ways to write n as the sum of at least one natural number. What is the number s called?
If the addends are not necessarily distinct and order is not considered, then we have Partition Function P. And here is the Wikipedia article.
 
Sep 2009
177
18
Thanks for replying. I made the conjecture that the number of compositions is \(\displaystyle 2^{n-1}\), but I haven't been able to prove it. I don't understand the proof on wikipedia much either... I shamefully don't know anything about combinatorical proof..
 

undefined

MHF Hall of Honor
Mar 2010
2,340
821
Chicago
Thanks for replying. I made the conjecture that the number of compositions is \(\displaystyle 2^{n-1}\), but I haven't been able to prove it. I don't understand the proof on wikipedia much either... I shamefully don't know anything about combinatorical proof..
The proof is not too hard, let's try an example: n=3.

1+1+1 = (3)
1+1,1 = (2,1)
1,1+1 = (1,2)
1,1,1 = (1,1,1)

You can look at the "+" and "," symbols as 0 and 1.

00
01
10
11

Does it make more sense now?
 
Sep 2009
177
18
yeah, it makes alot more sense. Thanks.