- #1

nonequilibrium

- 1,439

- 2

I was wondering about the following combinatorial problem:

given a natural number n, for example 20, in how many ways can I write it as the sum of positive integers?

For example:

20 = 20

20 = 19 + 1

20 = 8 + 4 + 4 + 2 + 1 + 1

etc

Please note that I ignore the order of the numbers, i.e. 19 + 1 or 1 + 19 is

*one*way, which makes that you can always write the largest number to the left, 2nd largest right of that one, etc.

Does there exist an explicit formula for this? I first thought of "the number of ways I can partition n non-distinguishable 1s in groups" which would be given (I think) by [tex]{2n-1 \choose n}[/tex], but this would give too much because it counts 19 + 1 as different from 1 + 19.