# What are the following types of numbers called?

#### Chris11

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
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.

#### Chris11

What about when order is considered?

#### undefined

MHF Hall of Honor

#### Chris11

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
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?

#### Chris11

yeah, it makes alot more sense. Thanks.