What are the following types of numbers called?

• Jun 22nd 2010, 03:30 PM
Chris11
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?
• Jun 22nd 2010, 03:36 PM
undefined
Quote:

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.
• Jun 22nd 2010, 03:39 PM
Chris11
What about when order is considered?
• Jun 22nd 2010, 03:41 PM
undefined
Quote:

Originally Posted by Chris11
What about when order is considered?

This is the number of compositions of n.
• Jun 22nd 2010, 03:45 PM
Chris11
Thanks for replying. I made the conjecture that the number of compositions is $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..
• Jun 22nd 2010, 04:03 PM
undefined
Quote:

Originally Posted by Chris11
Thanks for replying. I made the conjecture that the number of compositions is $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?
• Jun 22nd 2010, 06:33 PM
Chris11
yeah, it makes alot more sense. Thanks.