Thread: What are the following types of numbers called?

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?

Originally Posted by 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?

If the addends are not necessarily distinct and order is not considered, then we have Partition Function P. And here is the Wikipedia article.

What about when order is considered?

Originally Posted by Chris11

What about when order is considered?

This is the number of compositions of n.

Thanks for replying. I made the conjecture that the number of compositions is , 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..

Originally Posted by Chris11

Thanks for replying. I made the conjecture that the number of compositions is , 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?

yeah, it makes alot more sense. Thanks.