Talk:Partition (number theory)

From Wikipedia, the free encyclopedia

Mathematics Portal This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating:	B Class	Mid Priority	Field: Number theory
Please update this rating as the article progresses, or if the rating is inaccurate. Please also add comments to suggest improvements to the article.

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).

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)

[edit] 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 ", without having looked at this Partition page first, would be led to believe initially that the partition is called d and defined as "" (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 , note that this is what Schur polynomials are indexed by. Marc van Leeuwen (talk) 09:55, 23 April 2008 (UTC)