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

In summary, the conversation discusses a combinatorial problem of writing a natural number n as a sum of positive integers in different ways, with the largest number to the left and the order not mattering. The formula {2n-1 \choose n} is mentioned but is found to give too many options. The partition numbers, Sloane's A000041, are also mentioned, but it is noted that there is no explicit formula for them. The conversation then delves into the fractal nature of integer partitioning and the potential practical applications of studying integer partitions. A recursive formula is also mentioned as a possible solution to the combinatorial problem of building k towers with n identical cubes or LEGO building blocks.
  • #1
nonequilibrium
1,439
2
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 [tex]{2n-1 \choose n}[/tex], but this would give too much because it counts 19 + 1 as different from 1 + 19.
 
Physics news on Phys.org
  • #3
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?
 
  • #4
These are the partition numbers, Sloane's A000041. Much is known about them.
 
  • #5
Aha, thank you. Sad to know there's no explicit formula, but happy to be aware of it :)
 
  • #6
Oops, I overlooked the part about the order not mattering.
 
  • #7
mr. vodka said:
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.
 
  • #8
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.
 

Attachments

  • Integer Partition Table.png
    Integer Partition Table.png
    62.5 KB · Views: 1,794
  • #9
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.
 
  • #10
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.
 
  • #11
jleach said:
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?
 
  • #12
I remember this as a combinatorial problem:
Given [tex] n [/tex] identical cubes (or LEGO building blocks), in how many ways can we build [tex]k[/tex] towers with it. Example for [tex]n = 4 [/tex] and [tex]k = 2[/tex] (where we can do this in 2 ways)

Code:
                   #
# #                #
# #                # #
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)

[tex]f(n, k) = f(n - 1, k - 1) + f(n - k, k)[/tex]

So the answer to your question would be

[tex]f(n, 1) + f(n, 2) + \dots + f(n, n)[/tex]

( why is there not a button to wrap input in a tex-tag)
 
Last edited:
  • #13
Outlined said:
I remember this as a combinatorial problem:
Given [tex] n [/tex] identical cubes (or LEGO building blocks), in how many ways can we build [tex]k[/tex] towers with it. Example for [tex]n = 4 [/tex] and [tex]k = 2[/tex] (where we can do this in 2 ways)

Code:
                   #
# #                #
# #                # #
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)

[tex]f(n, k) = f(n - 1, k - 1) + f(n - k, k)[/tex]

So the answer to your question would be

[tex]f(n, 1) + f(n, 2) + \dots + f(n, n)[/tex]

This is essentially the same as the partition numbers that I mentioned (though you're subtracting 1).
 
  • #14
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.
 
  • #15
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
 
Last edited by a moderator:

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

1. How do you determine the number of ways to write a given number as a sum of integers?

The number of ways to write a given number, n, as a sum of integers is equal to the number of partitions of n. A partition is a way of breaking down a number into smaller, non-negative integers. For example, the number 4 can be partitioned in 5 different ways: 4, 3+1, 2+2, 2+1+1, and 1+1+1+1.

2. Is there a formula or equation for calculating the number of ways to write n as a sum of integers?

Yes, there is a formula known as the partition function, denoted by p(n), which calculates the number of ways to partition a given number, n. However, this formula can be quite complex and is often calculated using recursive algorithms.

3. Are there any patterns or rules for determining the number of ways to write n as a sum of integers?

Yes, there are some patterns and rules that can help in determining the number of ways to write a given number as a sum of integers. For example, the number of partitions for even numbers is always greater than the number of partitions for odd numbers, and the number of partitions for a number increases as the number itself increases.

4. Can the number of ways to write n as a sum of integers be calculated for very large numbers?

Yes, the partition function can be used to calculate the number of ways to partition very large numbers. However, as the numbers get larger, the calculations can become more complex and time-consuming.

5. How is the concept of writing a number as a sum of integers useful in mathematics?

The concept of partitioning a number as a sum of integers has many applications in mathematics, including in number theory, combinatorics, and statistics. It can also be useful in solving problems involving combinations and permutations, as well as in understanding patterns and relationships between numbers.

Similar threads

  • Linear and Abstract Algebra
Replies
33
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
12
Views
1K
  • Calculus and Beyond Homework Help
Replies
7
Views
2K
Replies
13
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
11
Views
831
Replies
4
Views
385
  • Linear and Abstract Algebra
Replies
15
Views
4K
  • Engineering and Comp Sci Homework Help
Replies
7
Views
2K
Replies
6
Views
1K
  • General Math
Replies
2
Views
1K
Back
Top