Talk:Integer partition/Archive 1

Archive 1

Untitled

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? Somewhere, 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)

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)

What is the sum of the reciprocals of partition numbers?

Many of Wikipedia's articals on integar sequences have information on the sum of their reciprocals. Robo37 (talk) 16:09, 30 January 2011 (UTC)

I should imagine that no interesting theorems are known about the sum you refer to. Results elsewhere need not apply here, to the sum of the reciprocals of the values of the partition function.

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)

It seems to me that referring to something as a miraculous result is inappropriate in general in Wikipedia but it certainly is for a result that hasn't even appeared yet. Hype has no place in Wikipedia. Since I just stumbled on this, I felt i shouldn't change it but someone more invested in this page should. Bsimonca (talk) 16:16, 26 January 2011 (UTC) Barry Simon

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

Right? —Preceding unsigned comment added by 198.202.70.136 (talk) 03:31, 25 January 2011 (UTC)

Right! The closed form equation for counting the partitions of a number should be posted, as well as any other illuminating discoveries by Ken Ono. Anybody read Ono's article yet? 134.29.231.11 (talk) 18:20, 28 January 2011 (UTC)

The [OEIS website] is pretty good at updating quickly and is a good source for references.Cliff (talk) 17:08, 1 February 2011 (UTC)

Shall we start a new section entitled "Closed Form equation for calculuating p(n)"? "Recent Findings"? the latter might not be great because recent is a subjective term. Any other title suggestions or should Ono's new finding be included in another section?Cliff (talk) 16:56, 1 February 2011 (UTC)

The results have been added to Ramanujan's congruences which is probably where they belong. I'm going to go ahead and remove the "expert needed" tag since it seems to be referring to this issue.--RDBury (talk) 13:17, 25 November 2011 (UTC)

Title, image, organization

Most of this article is about the partition function p(n) that counts the number of partitions of size n. However, some portions of the article (Ferrers diagrams, Young diagrams) actually are about partitions. It seems to me that the present article should be renamed something like "partition function (number theory)" (currently a redirect to this page) or "number of partitions" except for a small number of sections that are actually about partitions. The article here would include one section on counting partitions, but more emphasis would be placed on things like Ferrers diagrams, Young's lattice, etc. Thoughts?

On a not-totally-unrelated note, it seems to me that the content of the article is much more about combinatorics than it is about number theory. This is less egregious than for Composition (number theory) (an article with no number-theoretic content whatsoever, as far as I can tell) -- is there some good reason this is classed as number theory and not combinatorics?

Finally, the first image in the article has pictures of Young diagrams, but its caption says that it has pictures of Ferrers diagrams. Would anyone object to changing this? --Joel B. Lewis (talk) 14:29, 18 July 2011 (UTC)

What is the sum of the reciprocals of the partition numbers?

Is it true that:

• ${1 \over P(1,1)}+{1 \over P(1,2)}+{1 \over P(1,3)}+{1 \over P(1,4)}+{1 \over P(1,5)}+{1 \over P(1,6)}+\cdots ={{\sqrt {5}}\pi \over 2}?$

If not, what is the sum of the reciprocals of the partition numbers? Robo37 (talk) 20:23, 18 August 2011 (UTC)

This is not the right place for questions of this sort; try http://en.wikipedia.org/wiki/Wikipedia:Reference_desk/Mathematics Computing the first 1000 or so terms suggests that $\sum _{n\geq 0}{\frac {1}{P(n)}}<3.511$, while ${\frac {{\sqrt {5}}\pi }{2}}>3.512$. It seems unlikely to me that your sum has a closed-form expression. --Joel B. Lewis (talk) 02:56, 19 August 2011 (UTC)

Okay, thanks. So what is the sum of the first 1000 terms? Robo37 (talk) 08:18, 19 August 2011 (UTC)

It's a rational number approximately equal to 3.5106. http://www.wolframalpha.com/input/?i=Sum[1%2FPartitionsP[n]%2C{n%2C0%2C1000}] --Joel B. Lewis (talk) 13:20, 19 August 2011 (UTC)

Hm, I've been wondering, can you enter any of the many Partition number formula's into Wolframalpha, as a way to get non-integer resaults? It's just I'm also looking for what number Partion number 4 should be but entering 'PartionsP(x)=4' into Wolframalpha doesn't work. plus I'm also partially interested in what the ith Partition number is. Robo37 (talk) 14:34, 27 August 2011 (UTC)

Determinant formulas section

The 'Determinant formulas' section seems to be a collection of determinant expressions easily, if not trivially derivable from generating function identities. The section is mostly unreferenced but it seems to be taken from the paper by J. Malenfant cited in the article elsewhere. As far as I can tell this paper has not been subject to peer review and so should not be considered a reliable source. If is it reliable then it is still a primary source and basing the section on it is contrary to WP:PRIMARY. So, if there are no reasonable objections I'm going to remove, or at least drastically trim the section,--RDBury (talk) 13:51, 25 November 2011 (UTC)

No particular interest in endorsing an analysis that implies that wikipedia articles shouldn't cite the mathematical research literature, but I agree that the section seems excessively large and that trimming it would improve the article. --Joel B. Lewis (talk) 03:59, 26 November 2011 (UTC)

To be more specific about the how the determinants can be derived, they are special cases of a general proposition: If

${\frac {b_{0}+b_{1}x+b_{2}x^{2}+b_{3}x^{3}+\dots }{1+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\dots }}=p_{0}+p_{1}x+p_{2}x^{2}+p_{3}x^{3}+\dots$

then

$p_{0}=|b_{0}|,\,p_{1}={\begin{vmatrix}1&b_{0}\\a_{1}&b_{1}\end{vmatrix}},\,p_{2}={\begin{vmatrix}1&&b_{0}\\a_{1}&1&b_{1}\\a_{2}&a_{1}&b_{2}\end{vmatrix}},\,p_{3}={\begin{vmatrix}1&&&b_{0}\\a_{1}&1&&b_{1}\\a_{2}&a_{1}&1&b_{2}\\a_{3}&a_{2}&a_{1}&b_{2}\end{vmatrix}},\,\dots \ .$

This is given (in slightly modified form) in the paper "Expression for Laplace's coefficients, Bernoullian and Eulerian numbers, &c, as Determinants" by J. W. L. Glaisher, appearing in the Messenger of Mathematics, vol VI, pp 49-63 (see [2]). According to Thomas Muir however, this is due to Faure in 1855 (see [3]), but I wasn't able to find more specific information on the internet. To prove the result, for example for n=3, multiply by the denominator on the left hand side to obtain p₀, -p₁, p₂, -p₃ as the solution to the system of equations

$b_{0}=x_{0}\,$

$b_{1}=a_{1}x_{0}+x_{1}\,$

$b_{3}=a_{1}x_{0}+a_{0}x_{1}+x_{2}\,$

$b_{4}=a_{2}x_{0}+a_{1}x_{1}+a_{0}x_{2}+x_{3}\,$

from which

$p_{3}={\begin{vmatrix}1&&&b_{0}\\a_{1}&1&&b_{1}\\a_{2}&a_{1}&1&b_{2}\\a_{3}&a_{2}&a_{1}&b_{2}\end{vmatrix}}$

follows by Cramer's rule.

In the case where the numerator of the left hand side is 1, this result becomes

$-p_{1}=|a_{1}|,\,p_{2}={\begin{vmatrix}a_{1}&1\\a_{2}&a_{1}\end{vmatrix}},\,-p_{3}={\begin{vmatrix}a_{1}&1&\\a_{2}&a_{1}&1\\a_{3}&a_{2}&a_{1}\end{vmatrix}},\,\dots \ .$

From this and the pentagonal number theorem

$p(n)={\begin{vmatrix}1&-1&&&&&&\\1&1&-1&\\0&1&1&-1&\\0&0&1&1&-1&\\-1&0&0&1&1&-1&\\0&-1&0&0&1&1&-1&\\-1&0&-1&0&0&1&1&-1&\\0&-1&0&-1&0&0&1&1&-1&\\0&0&-1&0&-1&0&0&1&1&\\\vdots &&&&&&&&&\ddots \\\end{vmatrix}}$

follows trivially. Similarly, the formula

$p(5k-1)=5\cdot {\begin{vmatrix}1&&&&&&&1\\-6&1&&&&&&0\\9&-6&1&&&&&0\\10&9&-6&1&&&&0\\-30&10&9&-6&1&&&0\\0&-30&10&9&-6&1&&-5\\11&0&-30&10&9&-6&&0\\\vdots &&&&&&\ddots &\vdots \end{vmatrix}}$

follows directly from the general proposition and Ramanujan's identity

$\sum _{k=0}^{\infty }p(5k+4)x^{k}=5{\frac {(x^{5})_{\infty }^{5}}{(x)_{\infty }^{6}}}=5{\frac {1-5x^{5}\dots }{1-6x+9x^{2}+10x^{3}-30x^{4}\dots }}$

The general proposition seems to have been well known in the 19th century, though perhaps not so much today, and it's really just a corollary to Cramer's rule as shown above. In any case, the determinant expressions given in the section are obtained by plugging in numerical values for the variables used in the proposition.--RDBury (talk) 21:51, 1 December 2011 (UTC)

The arguments that RDBury makes for deleting these partition-function formulas from this article have no merit.

RDBury does not deny that the expressions he deleted are in fact valid formulas for p(n). He claims though, among other things, that they are for the most part unreferenced. This is incorrect; every formula he deleted is derived in the cited article by Malenfant as a special case of a more general expression. This article is available on the archive. True, it has not yet appeared in a peer-reviewed journal, but the same is true for the article by Bruinier and Ono, for which he apparently has no objection.

Whether these expressions were first derived by Malenfant or follow in a direct fashion from earlier work is irrelevant to the issue of whether they should be included in the "Partition Function Formulas" section. Omitting them leaves the reader with the false impression that the partition function can only be calculated using Euler's recurrence relation or by the complicated formulas of Rademacher and of Bruinier and Ono. These determinant formulas are not the most efficient ways to calculate p(n), (that would probably be the Rademacher formula), but they are perhaps the simplest expressions one can have and, unlike the Bruinier-Ono formula, they can actually be used to calculate its values in a direct fashion.

Furthermore: Last January Emory University released a press release on two articles that were co-authored by Ken Ono. The 2nd paper, by Bruinier and Ono, was described as

"another achievement developing an explicit finite formula for the partition function. Previous expressions involved an infinite sum, where each term could only be expressed as an infinite non-repeating decimal number."

And from an Emory University website:

"Mathematician Ken Ono recently presented new breakthroughs in number theory that were centuries in the making. In the above video, you can watch Ono explain the first finite formula to calculate any partition number, and the discovery that partition numbers behave like fractals."

Much was made in these postings of the improvement of the Bruinier-Ono formula over Rademacher's; that it was a finite rather than an infinite sum, and used algebraic numbers instead of transcendental ones. Nowhere in these or in any other of the numerous websites discussing the Bruinier-Ono formula, nor in Ono's lecture, was any mention made of the existence of these simpler, finite determinant formulas. The historical picture drawn by all these postings, without exception, was: Euler's recurrence relation, the Hardy-Ramanujan approximate formula, Rademacher's formula, and finally the Bruinier-Ono formula.

In summary, the expressions deleted by RDBury are some of the very few explicit formulas for p(n), and they deserve to be included in any list of partition function formulas, especially since no one, including an acknowledged expert such as Ken Ono, seemed to be aware of their existence. Archimedes100 (talk) 21:21, 9 December 2011 (UTC)

I don't want to join the discussion whether this is OR or not, but I think it's untypical for an encyclopedia article. To me it looks rather like a section from a textbook. I propose that you create a Wikiversity page that is really like a textbook and link it from the Wikipedia article. Your arguments above may likely be good enough to protect the link from deletion. Lipedia (talk) 16:14, 10 December 2011 (UTC)

I really don't see how this section is like a section from a textbook; a textbook would have more discussion and probably go into the derivation of the formulas. The section on "Intermediate function" does seem to be more of that nature. Granted, this section could be shorter, and probably doesn't need as many examples. Archimedes100 (talk) 22:22, 13 December 2011 (UTC)

In response to Archimedes100, the expressions may appear different but in essence they are equivalent to the generating function expressions already given in the article. You can use the same idea to turn the recursive definition for Fibonacci numbers into determinant expressions, viz.

$F_{n+1}={\begin{vmatrix}1&-1&\\1&1&-1&\\&1&1&-1&\\&&1&1&-1&\\&&&1&1&-1&\\\vdots &&&&&&&&&\ddots \\\end{vmatrix}}_{n\times n}$

But when you actually compute the determinate you end up doing the same recursion as in the definition, so really it just another form for the same recursive formula. We aren't a repository for every possible equivalent statement of a theorem or every possible equivalent form of an equation. As for the Ken Ono papers cited, they very well could be unreliable but I didn't investigate them because they didn't strike my notice as questionable in any way. The determinant material, for whatever reason, did and this led me to investigate further and eventually conclude that the material was not encyclopedic. Finally, you are kind of making my point for me by stating that the formulas are not known even my experts. Wikipedia is not a publisher of original thought, no matter how interesting or important that thought is. If it is interesting or important then the people to do publish original thought should publish it and when they do it will presumably be known by experts in the field.--RDBury (talk) 20:19, 10 December 2011 (UTC)

The partition function is completely determined by the generating function equation, so the Rademacher formula, the Bruiner-Ono formula, and the Malenfant formula are ALL equivalent to the GFE; if they weren't they wouldn't be of any use. But they are not 'merely' equivalent; they are equivalent because they are solutions to the GFE. (And in fact you don't "end up doing the same recursion as in the definition" when you compute the determinant.) I am not proposing that "every possible equivalent form" of the GFE for p(n) be included; I do think though that a section on partition function formulas should include all of the (few) formulas that exist.

This is a link to an article I came upon on partitions by Richard Lawrence:

http://docs.google.com/viewer?a=v&q=cache:CqnkPkvCzE4J:maths.dur.ac.uk/Ug/projects/db/10504/201000/report_Lawrence_RJ.pdf+Malenfant+partition+function&hl=en&gl=us&pid=bl&srcid=ADGEESi814SvGQEFk5GoJlhuDFopyMAGkk6tYtk4AECIRcOZt4EH4-5WdsrE3H3iqYTGfbuWtuffDf2h8ZHfdd0PShNcilb2W3XFsQC1TIWDsVGOhpY7nCm_pqhS5T9l3zPf3weydl8t&sig=AHIEtbSazxMfK0Cs8Kg29K2gmPhZiuiVCw

It appears to be a senior project or thesis by a student at Durham University in the UK, so I'm not presenting it as something authoritative. But the discussion in Chapter 6 about formulas for p(n) does give, in my opinion, a good summary of the current situation, and makes a case as to why the Malenfant solution should be included. Archimedes100 (talk) 22:22, 13 December 2011 (UTC)

First, it shouldn't even be necessary to argue whether the determinant formulas have merit. Wikipedia's requirements are that the material have a reliable source and that it's encyclopedic. The only source is the Malenfant paper which is not peer reviewed so not reliable. I'm also arguing that it's not encyclopedic since it's a trivial (given well-known facts on determinants) restatement of material that's already in the article. Perhaps I made a mistake here in trying to do my own peer review of the Malenfant paper here, but I was trying to indicate that I'm not just blindly following Wikipedia policy. But really the only justification needed to remove material is that it doesn't have a reliable source and you don't seem to be contesting this. You seem to be saying that Malenfant's formulas should be put on the same level as Rademacher's because they both follow from the definition. There is a big difference however between a result that is obtained via a complex derivation and one which is basically just an application of Cramer's rule. I looked over the Lawrence article and it seems to be a cogent summary of the topic, but the material on the Malenfant paper basically repeats the derivations there without critically examining whether they can be simplified.--RDBury (talk) 12:03, 14 December 2011 (UTC)

I came here from the Wikipedia talk:WikiProject Mathematics page. I don't have an opinion about the article, but I do have an opinion about the current state of the argument. Though it is a goal of Wikipedia that all content should ultimately have a reliable source, it makes no sense to me to argue about sources if both sides agree that the information is correct. Indeed, many mathematics articles have lots of unsourced content, which remains because everyone agrees that the content is correct, and belongs in the article. The hope is that the content will eventually be sourced, but unsourced content does not need to be removed unless its veracity is challenged.

As far as I can tell, this argument is really about whether the content of the 'Determinant formulas' section is helpful for the article. If the content is mathematically correct and helpful for the article, then it should remain for now, though in the long run a reliable primary source ought to be found. If the content is not helpful for the article, then it should be deleted or moved to a separate article. Jim.belk (talk) 16:44, 14 December 2011 (UTC)

Strongly agreed on all counts. To repeat what I said before, I think that the determinant section was clearly over-emphasized in the article initially. I don't have any objection to the presence of a short version. --Joel B. Lewis (talk) 18:31, 14 December 2011 (UTC)

Not every true statement belongs in Wikipedia, even if it is sourced. Giving a cite not only ensures that the material is true but it helps ensure that Wikipedia doesn't fill up with trivia that someone who didn't know better though was profound. For example someone could add alternative statements of Apollonius' theorem: (b-d)(b+d)+c²=2m²+d², b²+(c-d)(c+d)=2m²+d², 2m²=(b-d)(b+d)+(c-d)(c+d) and a dozen other variations. These statements are true but most authors of geometry books would assume (as should we) they're readers will be able to mentally do the algebra to convert them to the b² + c² = 2m² + 2d² given in the article. So how should I respond to someone who adds these kinds of variations to an article? I can't say they are false but I can point out that the statements are unsourced and trivially equivalent to the equation that is given in the article. The argument here is that if it's true then leave it in the article because someday someone might publish it and then it will have a reference. The is the opposite of the WP:V policy that is one of the foundations of Wikipedia. --RDBury (talk) 13:27, 15 December 2011 (UTC)

"The argument here is ....." I don't know to whom you're attributing this argument -- neither Jim.belk nor I have made it. Both Jim.belk and I have taken the position that the argument for including something should be done on the merits, i.e., whether it improves the article. As far as I'm concerned, the question of whether it's properly sourced (provided you agree that it's not actually false) is a not-particularly-interesting sideshow. Archimedes100 believes this section improves the article but could be shortened; Jim.belk didn't say anything about what he believes in the case at hand; and I believe that a short mention is certainly preferable to the long section that was there originally, and possibly preferable to eliminating it entirely. So I reiterate: it makes no sense to argue about the sourcing in a mathematics article if everyone agrees that the mathematics is correct, and so discussion should instead focus on the actual merits of the text in question. --Joel B. Lewis (talk) 15:50, 15 December 2011 (UTC)

It is probably unnecessary to go into detail, given the prevailing support for the inclusion of the short version of the above section, but at least some of the arguments against its inclusion appear to be rather weak. First, at this time Ono's paper is in the same 'unreliable' format as Malenfant's. Second, Malenfant's results are easily verifiable; in fact, by the logic of the 'against' argument they are trivially verifiable. I have not found a flaw in the underlying preprint. If anybody else had, they would have pointed it out by now, as the preprint has been open for discussion for months. Moreover, out of curiosity I did also some direct calculations of the Toeplitz determinants involved out to pretty high numbers (Mathematica, for one, has a built-in function for Toeplitz determinants) - the results came out correct. (This is not a proof, but Malenfant has provided it.) I strongly agree that the discussion should focus on the merits of the text. I find that the short version of the Determinant Results section is correct, relevant, and appropriate for inclusion. Descartes21st (talk) —Preceding undated comment added 23:01, 15 December 2011 (UTC).

I'm not buying the "If the paper is incorrect then someone would have commented on it" argument. I've looked for a way to comment on it to say that many of the results that the author is claiming are original actually date from over a hundred years ago; if I had found one I would have. Perhaps I missed it and if I did please point it out. Plus, the fact something has existed somewhere on the internet doesn't mean that someone qualified to review it will do so. Show that the paper has been reviewed to appear in an actual publication.

The statement following "The argument here is ....." is my paraphrase of "If the content is mathematically correct and helpful for the article, then it should remain for now, though in the long run a reliable primary source ought to be found." I'm not sure how else to interpret that statement. The standard for Wikipedia is verifiability and original research should be removed from articles, whether it's true mathematically or not. There are fundamental reasons for this; a Wikipedia where original research is allowed would soon fill up with postings from crackpots claiming to have proved the Riemann hypothesis and instead of writing articles most editors would be spending time trying to find the subtle fallacies in these postings. Eventually Wikipedia would become like Usenet where everyone can have their say but no one bothers to listen. In any case, if I had thought the material was helpful to the article then I probably wouldn't bother with all this. The formulas are, as I have tried to explain above, not helpful since when you compute the determinants you're really just applying the pentagonal number theorem but using up a lot more paper to do it.

I've been trying to think of a shorter version of the material that I can accept but I keep running across the no OR issue. If there is something there that can be sourced reliably then do so and add it back in. But so far all I'm hearing is "We don't like Wikipedia's policies so we're going to ignore them."--RDBury (talk) 10:04, 16 December 2011 (UTC)

I'd like to thank RDBury for inviting other opinions on this topic by putting it up on the Wikipedia talk:WikiProject Mathematics page. He is however making two claims that are contradictory: that the results are trivial and that they are unreliable.

First of all, the article is not just "somewhere on the internet"; it has been posted on the Cornell archive. Many scientific disciplines consider that as "publication"; the archive has filters to keep the crackpots out.

Secondly, I don't know what you mean by the statement "many of the results that the author is claiming are original actually date from over a hundred years ago". In the article by Malenfant, he proves a general theorem and then shows that the partition-function determinant formula follows as a special case. (Another special case in the article is a formula for the Euler numbers that was earlier derived by Vella by a different method, and to which he gives a reference. Rederiving known results by a different method is an accepted practice as long as you acknowledge the earlier result.) But even if the determinant formula does follow from Cramer's rule, if Malenfant is the first to have actually written it down, then it IS original. "Trivial" does not mean "obvious". The two partition-function formulas, (the determinant one and the sum-over-pentagonal-partitions form), could probably have been derived by Euler; they certainly could have been found by Hardy and Ramanujan, by Rademacher, by Bruiner and Ono, or by any of the other workers in this field. But, as far as I can tell, they weren't. The online buzz that accompanied the announcement of the Bruiner-Ono formula would tend to confirm this. I doubt that Ono, for example, when he gave that lecture and wrote down the known formulas for p(n), knew about these two other formulas but just thought they were too trivial to mention. If one or both of these formulas HAVE been derived by someone earlier, then a reference to that article should be given instead, but the formulas should still be listed in this article.

And finally, when I compute the determinant for p(n), I just enter the appropriate matrix into my HP calculator, hit the 'determinant' button, and the answer pops out. My HP doesn't know anything about the pentagonal number theorem but it does know how to calculate a determinant. Archimedes100 (talk) 15:54, 16 December 2011 (UTC)

I went ahead and restored (with some rephrasing) about half of the shortened version of the material, though it's now a bit more scattered around the article. I also added a bunch of material on q(n) without which having a determinant formula formula for it came more or less out of nowhere. I can't see restoring the section on the cumulative partition function since there isn't anything else in the article about it and it seems rather obscure. There are no refs. listed in the OEIS entry which is an indication that it's not covered in the literature much. I'll probably restore the summation formula as well as alternate way of writing the determinant formula. I hope this is an acceptable compromise since the there are more serious issues in the article that need to be addressed.

I don't know how the HP calculator computes determinants but if you compute the determinants with pencil and paper the relationship between that and the recursion formula becomes pretty obvious. For example, using the cofactor expansion (doing columns in reverse order along the last row for the expression for p(7) gives

$p(7)={\begin{vmatrix}1&-1\\1&1&-1\\0&1&1&-1\\0&0&1&1&-1\\-1&0&0&1&1&-1\\0&-1&0&0&1&1&-1\\-1&0&-1&0&0&1&1\end{vmatrix}}$

$={\begin{vmatrix}1&-1\\1&1&-1\\0&1&1&-1\\0&0&1&1&-1\\-1&0&0&1&1&-1\\0&-1&0&0&1&1\end{vmatrix}}-(1){\begin{vmatrix}1&-1\\1&1&-1\\0&1&1&-1\\0&0&1&1&-1\\-1&0&0&1&1\\0&-1&0&0&1&-1\end{vmatrix}}$

$+(-1){\begin{vmatrix}1&-1\\1&1\\0&1&-1\\0&0&1&-1\\-1&0&1&1&-1\\0&-1&0&1&1&-1\end{vmatrix}}+(-1){\begin{vmatrix}-1\\1&-1\\1&1&-1\\0&1&1&-1\\0&0&1&1&-1\\-1&0&0&1&1&-1\end{vmatrix}}$

$={\begin{vmatrix}1&-1\\1&1&-1\\0&1&1&-1\\0&0&1&1&-1\\-1&0&0&1&1&-1\\0&-1&0&0&1&1\end{vmatrix}}+{\begin{vmatrix}1&-1\\1&1&-1\\0&1&1&-1\\0&0&1&1&-1\\-1&0&0&1&1\end{vmatrix}}-{\begin{vmatrix}1&-1\\1&1\end{vmatrix}}-1$

$=p(6)+p(5)-p(2)-p(0)\,$

which is exactly the recursion formula for p(7).

On the Malenfant paper, for the case X=-1, which I believe is the only case that is applied in the rest of the paper, part II appears (with a rearrangement of columns) at the top of p. 213 in Volume 2 Muir's book on determinants, see [4] for an on-line version. (I recently added this as a cite in the article as well.) Muir attributes this is Henri Faure. Part I of the theorem, again for X=-1, appears with allowances for change in notation and scaling at the bottom of p. 208 in Volume 3 of Muir, see [5]. Muir attributes this to Francesco Brioschi. Granted, Malenfant's version is a generalization, but I think failing to mention Faure and Brioschi is an oversight that a reviewer would catch. Malenfant's formula 56b appears in the middle of p. 236 of Volume 3 of Muir, see [6]. I can find 56a in Muir but I'd be surprised if it wasn't known of around the same time since I don't think the derivation is very different.--RDBury (talk) 01:45, 17 December 2011 (UTC)

Computations of the partition function

I have some new results concerning computation of the partition function, which might be relevant to include: http://journals.cambridge.org/action/displayAbstract?aid=8710297

By the way, this page is quite large and somewhat disorganized. It would make more sense to have a separate partition function (number theory) article (right now that's just a redirect). Fredrik Johansson 17:26, 9 October 2012 (UTC)

Asymptotics of restricted partitions

The result mentioned in section 3.4.3 does not hold when the greatest common divisor of the elements of A is not 1. Can this be fixed? — Preceding unsigned comment added by 18.111.103.189 (talk) 18:45, 18 November 2012 (UTC)

Ken Ono's Work

Where is Ken Ono's work? Isee nowhere in the article. http://blogs.plos.org/badphysics/2011/01/20/ono/

http://www.mathcs.emory.edu/~ono/