In how many ways can I write n as a sum of integers?

[nonequilibrium]

Hello,

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 $${2n-1 \choose n}$$, but this would give too much because it counts 19 + 1 as different from 1 + 19.

 

[awkward]

See

http://en.wikipedia.org/wiki/Stars_and_bars_(probability)

 

[nonequilibrium]

Isn't that exactly what I mentioned in my post? Noting that that method counts 19 + 1 and 1 + 19 as distinct options? Or am I missing something?

 

[CRGreathouse]

These are the partition numbers, Sloane's A000041. Much is known about them.

 

[nonequilibrium]

Aha, thank you. Sad to know there's no explicit formula, but happy to be aware of it :)

 

[awkward]

Oops, I overlooked the part about the order not mattering.

 

[CRGreathouse]

Aha, thank you. Sad to know there's no explicit formula, but happy to be aware of it :)

Well, no, but they can be computed quickly nonetheless. Pari computes P(1,000,000), an 1108-digit number, in 80 milliseconds.

 

[jleach]

Integer partitioning can not be described algebraically and is often confused for being a combinatorial problem. The fact is that it is a fractal pattern. See the attached table for a breakdown on the frequency of ways that an integer can be divided up into a given number of parts. The stage values run opposite the number of divisions. At stage 1, the integer is broken up into all one's. In a way the fractal is building an integer instead of breaking it apart. Any algorithim used to generate integer partitions or the frequency of partitions that meet a certain criteria, must be based on a fractal principle. Let me know, if you need a method to generate this table or want to learn more about how to use this pattern to set limiting criteria. Such limiting criteria could be, how many partitions contain the value k or a set of values? It is also interesting to see that infinity can be partitioned and each stage has a maximum value. No matter how large your integer, there is only one way to divide it up into only one's.

 

[chaoseverlasting]

Shouldnt the number of ways be infinite? If you have negative numbers in the sum, then there are an infinite number of ways to represent an integer.

 

[jleach]

But, that would be changing the rules. Negative numbers aren't allowed.

I've done a lot of work studying integer partitions, and I've even started looking at a more complex case by making it N distinct objects instead of N parts. This changes the rule slightly. I'm still not interested in who holds which part of N, but now the parts are not only distinguished by size, but also by the contents.

I think that a lot of people are interested in integer partitions, because many people take the prime number challenge and they think that this may give them a clue. Aside from being able to calculate the probability of finding k eggs in an Easter egg hunt with N eggs, I really haven't been able to find a practical application. This is why I haven't devoted much time to looking at the partitioning of N distinct objects. I've been side tracked by something that I think is much more promising.

 

[chaoseverlasting]

Aside from being able to calculate the probability of finding k eggs in an Easter egg hunt with N eggs, I really haven't been able to find a practical application.

Digital Electronics? A better way to split numbers so we can add them more efficiently?

 

[Outlined]

I remember this as a combinatorial problem:
Given $$n$$ identical cubes (or LEGO building blocks), in how many ways can we build $$k$$ towers with it. Example for $$n = 4$$ and $$k = 2$$ (where we can do this in 2 ways)

                   #
# #                #
# #                # #
1st way          2nd way

The answer to this question is the following recursive formula (which does not has an algebraic solution as far as I know)

$$f(n, k) = f(n - 1, k - 1) + f(n - k, k)$$

So the answer to your question would be

$$f(n, 1) + f(n, 2) + \dots + f(n, n)$$

( why is there not a button to wrap input in a tex-tag)

 

[CRGreathouse]

I remember this as a combinatorial problem:
Given $$n$$ identical cubes (or LEGO building blocks), in how many ways can we build $$k$$ towers with it. Example for $$n = 4$$ and $$k = 2$$ (where we can do this in 2 ways)

                   #
# #                #
# #                # #
1st way          2nd way

The answer to this question is the following recursive formula (which does not has an algebraic solution as far as I know)

$$f(n, k) = f(n - 1, k - 1) + f(n - k, k)$$

So the answer to your question would be

$$f(n, 1) + f(n, 2) + \dots + f(n, n)$$

This is essentially the same as the partition numbers that I mentioned (though you're subtracting 1).

 

[jleach]

I have seen this or a similar explanation in number theory or combinatorial texts that touch upon number theory, but I don't find it to be a satisfactory solution. The reason is because the solution is actually a problem. Sort of like counting the number of dogs by counting their legs and dividing by four. If the solution requires the same amount of work as generating every possibility and then counting the sequences, it doesn't do much to help.

 

[alphachapmtl]

Partition (number theory)

The number of partitions of n is given by the partition function p(n).
http://en.wikipedia.org/wiki/Partition_(number_theory )
http://www.numericana.com/answer/numbers.htm#partitions

First 4096 values of the partition function
http://www.numericana.com/data/partition.htm

Lectures on Integer Partitions by Herbert S. Wilf
http://www.math.upenn.edu/~wilf/PIMS/PIMSLectures.pdf

Generating All Partitions: A Comparison Of Two Encodings
http://arxiv.org/PS_cache/arxiv/pdf/0909/0909.2331v1.pdf

Fast Algorithms For Generating Integer Partitions
http://www.site.uottawa.ca/~ivan/F49-int-part.pdf