Talk:Integer partition

This page comes from the merger of two previous articles on 16:03, 4 May 2006 (UTC). Their talk pages are Talk:Integer partition and Talk:Partition function (number theory).

Q

Hi, does anybody know an asymptotic formula for the number of partitions of k into AT MOST n parts? Somwhere, it is denoted by par(k,n). Franp9am 21:28, 9 March 2007 (UTC)

Generating partitions

This article, without ever really being clear about it, is mostly about finding out the number of partitions. That can be at most half the article. What about finding the partitions? There's no closed formula according to my lecturers. There are recursive methods, though, and one should at least be given. I have constructed one particularly inelegant approach in Haskell, and I don't really want to quote it here out of embarrassment (it is very verbose, quite stupidly for haskell). I hope someone else will offer up something. 81.23.56.9 (talk) 23:27, 24 November 2008 (UTC)

"Someone else" = Knuth. Donald E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 3: Generating All Combinations and Partitions, section 7.2.1.4, "Generating all partitions". Probably a version of this is available from Knuth's web site. —David Eppstein (talk) 00:05, 25 November 2008 (UTC)

It may be easier to understand your question, if you could explain what you are trying to do in more detail. I'm just a dabbler in mathematics and Wikipedia won't let me post any original material, but one of my reinventions of the wheel was the discovery of partitions. So, I may be able to provide some insights if you want to pose your problem to me directly (johnnleach@att.net). Mathematicians and computer scientists don't always think of solutions in the same perspective. I could easily write an algorithm to generate partitions, but the mathematical perspective would be to write a formula that would crank them out without testing each potential case. This is why computer scientists have little trouble generating prime numbers, but mathematicians are still searching for a prime number function. I'm a mathematician at heart, but I also recognize that sometimes you merely have to change your perspective. The acceptance of fractals was a breakthrough in changing perspectives. Still, I enjoy trying to make everything fit from a mathematician's perspective. Sometimes computer scientists forget that an algorithm may be only approximating the correct answer and has limitations, so there is always room for revisiting old problems. Perspectives are also different for engineers. Engineers tend to be interested in only the final answer, so when they include formulas in their documents, they often omit any terms that cancel. As a math minded person, I like to use formulas that describe what is going on. Therefore, I often include terms, which point out that certain things may be counterbalanced by other responses, but should that counterbalance be broken, don't forget about these other factors. I don't know what you are looking for and I may or may not be able to help you. One discovery that I've made about partitions is that I can calculate the number of partitions that contain no repeated values. If I dig out my old notes, I'm may have a few more properties to share. I find that integer partitions is a beautiful pattern. It is a pattern that could be thought of as an abstract fractal, because you can look at it in so many ways and you keep finding the same pattern within itself no matter how you twist your perspective. Unfortunately, I've found very few applications in the real world. The only one that I could come up with was something like determining the probability of finding eggs on an Easter egg hunt.--JNLII (talk) 21:09, 16 December 2008 (UTC) Another potential application, which I never explored would be the study of explosions. By measuring the size of fragments and the number of them, you are partitioning a mass. It may be possible to compare these observed partitioning results to the randomized case (integer partitioning) to describe certain properties of the mass. How strong is the glue that holds it together or did the force of explosion originate from the center?--JNLII (talk) 17:10, 17 December 2008 (UTC)

I also find it interesting that most of the information that I find on the topic fails to mention the overlap in distribution tables between partitioning integers and partitioning infinity.--208.4.152.131 (talk) 23:06, 16 December 2008 (UTC) Probably because the pattern is fractal in nature, it is also easy to determine the number of partitions with a given number of fragments or the total number of partitions that contain a specific value or set of values. The best way to describe partitions is with simplier partitions. It can not be described in algebraic terms.--JNLII (talk) 17:46, 18 December 2008 (UTC)

There are so many properties and repeating patterns within Leibniz's distribution table, that I should probably look into publishing a list of these properties. Since I would need help in reseaching those who made these discoveries before me and help in the process for submitting the article to a journal, I would welcome anyone interested in coauthoring the article with me. If this works out, I would be interested in doing the same joint project on more complex partition distributions that I've worked on involving the partitioning of different objects. For example, integer partitioning could be thought of as the number of ways that you can distribute a collection of one type of object into a crowd, say pencils. You don't care who gets a pencil, merely the number of ways that the collection can be broken up. To make the problem more complex, I started looking into the distribution of multiple collections. For example, the number of ways to distribute pencils and magnets into a crowd. Contact me if anyone is interested (johnnleach@att.net).--JNLII (talk) 19:34, 22 December 2008 (UTC)

I've also looked at the partitioning of a collection of unique objects. This has led me to discover a probability distribution that is new to me, so I don't know what to call it. This distribution however is a little flatter than the t-distribution and can be used to tell me the probability of getting a sequence in a correct order, relative to order and not distance. In other words, given a collection (A,B,C,D) to partition, what is the probability of getting a sequence with A before B? I was motivated to investigate this when studying organic chemistry and I wanted to figure out how the instructor should be grading problems that require placing things into a proper sequence. I found that most instructors don't grade these problems correctly, so I recommend keeping to problems comparing only two things at once. I also discovered that if I know the first and last values of the sequence, I have a better chance of getting a higher score if I randomly guess at the rest of the sequence, than if I know two consecutive values and try to guess the rest. The chance of getting the correct sequence remains the same, but the chance of getting a better sequence homology is different. As more and more values are known, the rule for best homology score changes, such that the extremes are not necessarily the best known values to have before guessing. I'm guessing that this will have some application in bioinformatics and understanding how DNA or amino acid sequences may naturally share homologies, even when no selective pressures apply.--JNLII (talk) 16:18, 30 December 2008 (UTC)

A partition is not an expression with plus signs

Looking at this page I am bothered by the fact that partitions are given by expressions involing "+"; for me a partition is just the sequence of its terms, like (3,2,2,1). Normally one considers statements like $1+1=2$ and $4+2+2+1=3+3+3$ to be true, but with the given description they can be construed to be false statements claiming equality of two distinct partitions. Really, the "+" is part of the motivation, but not of the definition of integer partitions. Also I like to think that a sequence is a partition only if it is weakly decreasing, rather than that the nondecreasing case is just "considered to be equal" to a weakly decreasing one. Partitions are used for other things than just for counting; to have to denote say a Schur function as $s_{3+1+1}$ would be disastrous. Marc van Leeuwen (talk) 13:22, 8 April 2008 (UTC)

In an article aimed at a general audience, like this one is, I find the plus-sign notation quite useful for its concreteness. That said, it should certainly be made clear, if it isn't already, that the actual partition is the sequence of terms, not the value of the expression obtained by summing them (which indeed is just the number being partitioned). Since you mention Schur polynomials, I'd like to suggest the "Definition" section in that article as a good example of how the notation ought to be properly used in a manner which is both formally consistent and easy to understand. —Ilmari Karonen (talk) 19:18, 9 April 2008 (UTC)

You are arguing that a partition should be viewed less as a series and more as a sequence? It would make more sense to me that you would call it a multiset rather than either of those two things, but to me the difference between a sequence and a series is that a series emphasizes the idea of adding up the terms, an idea that we should be emphasizing here. Of course, a partition is not the same as the sum of its terms, but neither is a series of any other type the same as the sum of its terms. —David Eppstein (talk) 21:44, 9 April 2008 (UTC)

An interesting point David; I never would have thought of calling something like 1+4+2 a series, but given the text of that article, it is. By the way I note that formal power series, in a sense the simplest kinds of infinite series, are equal to the sum of their terms. But I agree that in general one needs to distinguish between a series and its sum, even though the series is written as a sum. By the way the mentioned article seems to shy away from saying what a series is, saying just that a series is "is often represented as" a sum.

Clearly one could define a partition of n either as a weakly decreasing finite sequence of positive integers with sum n, or as an equivalence class (permutation of terms) of finite series of positive numbers with sum n, or as a finite multiset of positive integers with sum n (in each case allowing an empty series/sequence/multiset when n is zero), or as an infinite weakly decreasing sequence of natural numbers, ultimately becoming zero and with sum n, or as a Young/Ferrers diagram (subset of N×N) of size n, or …, and all these definitions would do for the purpose of counting them. But for some purposes they are not equivalent, and I think in the combinatorial literature the weakly decreasing sequence definitions are most frequent, so I think this article should say something about that (currently it does not seem to contain the word "decreasing"). Note that Schur functions are sometimes allowed to be indexed by sequences that are not weakly decreasing, and that the meaning is then not the same as for the decreasingly sorted sequence. —Marc van Leeuwen (talk) 21:38, 22 April 2008 (UTC)

I'm tempted to disagree with your statement that a formal power series "is" the sum of its terms (in order to use that as a definition you have to specify what kind of addition you are using, for what kinds of objects, and you run into trouble with circular reasoning if you make each of the terms itself be a formal power series with one nonzero coefficient) but I think that might take us too far afield. I do agree that, to the extent it can be done without bogging the article down in formality, we should talk about multiple equivalent notions of what a partition is. —David Eppstein (talk) 22:56, 22 April 2008 (UTC)

I said "is", not "is defined as". Maybe you would be easier convinced by the case of polynomials, which are usually considered to be equal to the sum of their terms (though they should not be defined as the sum of their terms either to avoid circularity). And indeed what I meant was viewing the terms of a formal power series S as themselves elements of the ring of formal power series, whose infinite sum is certainly convergent to S in the sense of formal power series. But let us not stray any further.

To get back to partitions, on second thought I think calling the current description of partitions one that views a partition as a series artificial, although formally correct. The interest in series appears to be always as a means to designate their sum (even if the two are distinguished); rearrangements of the series that are guaranteed to preserve convergence and the sum are freely applied, and nobody ever considers enumerating all possible series of some type with a given sum. For partitions on the contrary one starts out with the sum, and the main interest (or so it would seem from this article) is counting the different way to decompose it as sum of positive integers. I think my main difficulty with this article is that it is too much about number theory, and too little about combinatorics. There is only a wee bit about Ferrers diagrams, and even this seems to be only there only to introduce counting of self-conjugate partitions. Partitions themselves, rather than their enumeration, are vastly important in combinatorics related to the symmetric group or symmetric functions (even if those articles currently hardly mention partitions). Macdonald's book (cited in the latter article) has partitions on nearly every page, but does not even bother to write down their generating function even once (I think). Clearly the right reply is to ask me to add what I find missing, and maybe I will if I can find the time. There is a lot to say, and maybe it will cause this page, which appears to be merged from "integer partition" and "partition function" to break up again…

And (unrelated) to reply to Ilmari Karonen, I do not agree that Schur polynomial#Definition is a good example of something that is easy to understand and formally consistent; I think that anybody who reads "given a partition $d=d_{1}+d_{2}+\cdots +d_{n}$", without having looked at this Partition page first, would be led to believe initially that the partition is called d and defined as "$d_{1}+d_{2}+\cdots +d_{n}$" (phrases to be read like that are extremely common). I would say this formulation is neither easy to understand, nor formally consistent. In that article the partition is $(d_{1},d_{2},\cdots ,d_{n})$, note that this is what Schur polynomials are indexed by. Marc van Leeuwen (talk) 09:55, 23 April 2008 (UTC)

Partition Address

I've rambled on and drifted away from the original question presented in the first section, so I'm starting a new section to address it more directly. The question of generating partitions instead of calculating the number of partitions is a problem that I also wondered about. My motivation was for two reasons. One to merely assign an address to the partition, so that everyone would understand which one that I was talking about. Two to use the partition in further calculations, but this would also mean that I would need an algorithm that would tell me about the characteristics of the partition, for example, how many values are in it. The later problem can probably be solved a lot easier by simply utilizing the properties of partitions to classify partitions into groups containing a certain number of values and using the size of the group to perform the calculation. By addressing the partitions, I may also be able to search for repeating properties based on similar addresses. Sort of like the periodic table in chemistry. More details are really needed to help understand your needs. But, an address can easily be assigned to a partition, based on the algorithm used to generate the partition. Most likely, you are going to use a nested loop. The values of the loops can be used as coordinates. With the coordinates and the known method for producing the partition, the address can be understood by anyone. If you don't like having a lot of addresses that refer to rejected partition trials, you can simply renumber the generated partitions in sequencial order. The address can still be understood by everyone, provided that the algorithm is given and the numbering system is explained.--JNLII (talk) 17:07, 31 December 2008 (UTC)

Article is incomplete!

What about the partition using only distinct integers? This is usually written as q(n) - as in [1], for example. Perhaps a new section only is needed - or the article might be split into two! 81.102.15.200 (talk) 13:28, 30 January 2009 (UTC)

Interesting that you mentioned this, because I derived a way to calculate the number of partitions that do not contain repeated integers, but I've never viewed it has having any practical application and have never heard anyone talk about it before, so I've never shared it. Thanks for letting me know about a more formal visit to this problem. If my approach appears to be unique, I'll share it with others. In a nutshell from the top of my head, I did something like start out with a value equal to the sum of natural numbers up to a point (sum of 1 to n = z) then if I'm interested in partitioning the number K with only non-repeating integers, the number of partitions (I guess q(n) from your notation above) is equal to the number of partitions for (K - n) or (K - z), I'll have to look at my notes if the moths haven't eaten them yet.--JNLII (talk) 20:23, 12 February 2009 (UTC)

13k+7

Perhaps I'm being insufficiently naive, but the idea that the sequence 5k+4, 7k+5, 11k+6 has got to continue 13k+7 seems a really superficial one -- why in the world would π(p) turn up here? 13k+6 is at least as good a guess, I'd think, 6 being 1/24 mod 13; and other constants might work as well. I've tweaked that sentence accordingly. 4pq1injbok (talk) 07:41, 21 October 2009 (UTC)

Fun in excel

If we define a function p1(n; x) "number of partitions of x having no element smaller than n", then we can express it recursively like so:

• p1(n;x) = 0 {n > x}
• p1(n;x) = 1 {n = x}
• p1(n;x) = p1(n+1; x) + p1(n; x-n)

This is easy to put into a spreadsheet, to have it calculate the values. For fun.

An alternative formulation is to define a function p2(n; x) "number of partitions of x having no element greater than n"

• p2(1, x) = 1
• p2(n; 1) = 1
• p2(n; x) = p2(n-1; x) {n > x}
• p2(n, x) = p2(n-1, x) + p2(n; x-n) —Preceding unsigned comment added by 210.193.179.135 (talk) 01:10, 24 November 2010 (UTC)

Recent work by Bruner, Folsom, Kent and Ono

There is a new (as of January 2011) result, the subject of two papers at www.aimath.org:

• Folsom-Kent-Ono, l-adic properties of the partition function

• Bruner-Ono, An algebraic formula for the partition function

which would appear to be worth noting in this article. There is also a blog article oriented at a general audience: theories reveal the nature of numbers (Emory University eScienceCommons, January 20 2011).

I recommend someone who knows more about the subject try to work this into the appropriate part of the article. Robert Munafo (talk) 20:57, 20 January 2011 (UTC)

This does seem to be a recent advancement worth noting, and I second the request for a knowledgeable editor to add it. Here is an additional Link to the press release for general audiences, as the eScienceCommons link didn't work for me: New math theories reveal the nature of numbers KiruJiwak (talk) 06:43, 21 January 2011 (UTC)

Link has moved, it seems.

http://www.eurekalert.org/pub_releases/2011-01/eu-nmt011911.php worked for me. 94.30.84.71 (talk) 19:46, 22 January 2011 (UTC)

Partition 500 in 4s by optimised enumeration

JavaScript shown and demonstrated at http://www.merlyn.demon.co.uk/js-misc0.htm#JAD can calculate partition counts (as IEEE Doubles) of moderate numbers quite rapidly. It can get the number of partitions of 500 (2.3001650325743243e+21) in 4 seconds on an ordinary PC, with Partition and Cache checked. I don't know whether that is of any interest. 94.30.84.71 (talk) 23:19, 20 January 2011 (UTC)

Time to get cracking!

http://esciencecommons.blogspot.com/2011/01/new-theories-reveal-nature-of-numbers.html

Right?