Talk:Integer partition

This is the talk page for discussing improvements to the Integer partition article. This is not a forum for general discussion of the article's subject.

Put new text under old text. Click here to start a new topic. New to Wikipedia? Welcome! Learn to edit; get help. Assume good faith Be polite and avoid personal attacks Be welcoming to newcomers Seek dispute resolution if needed Article policies Neutral point of view No original research Verifiability

Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL

Archives: 1

This  level-5 vital article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Mathematics Mid‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles Mid This article has been rated as Mid-priority on the project's priority scale.

The function ${\displaystyle (x)_{\infty }}$ in this section seems to be Euler's function mentioned a few lines earlier. -Herbmuell (talk) 18:25, 7 August 2016 (UTC)[reply]

Hi, could someone please check the formula ½m(3m − 1) that is given for generalized pentagonal numbers in the section "Generating function" in this article? it seems to me that this is the formula for pentagonal numbers and leaves out the sequence 0, 1, -1, 2, -2, 3, -3, 4 that is needed for generalized pentagonal numbers.

Thanks, Joachim Neumann (talk) 15:25, 8 May 2016 (UTC)[reply]

I don't understand the question. The formula there appears to be a correct recursive formula for the partition function. --JBL (talk) 16:57, 8 May 2016 (UTC)[reply]

The title of this article should really be Partition (Combinatorics). While partitions may have applications in number theory, they are usually thought of as combinatorial objects, and this article certainly treats them this way. 128.138.150.145 (talk) 18:36, 4 October 2013 (UTC)[reply]

But that would be too ambiguous. The disambiguation part of the title is supposed to distinguish the article from other articles with similar titles, but "(combinatorics)" wouldn't distinguish this one from partition of a set. —David Eppstein (talk) 18:49, 4 October 2013 (UTC)[reply]

I have developed a method which enables to find the possible number of partition of any given numerical number. To view my developed method then click on the below link. https://drive.google.com/folderview?id=0B4wrAuhEkQyvMXJuWEVQaHR5MXM&usp=sharing — Preceding unsigned comment added by 59.184.32.163 (talk) 11:44, 29 April 2014 (UTC)[reply]

Then I encourage you to consider submitting it to a peer-reviewed journal for publication. Until then, please see Wikipedia:No original research. Deltahedron (talk) 17:40, 29 April 2014 (UTC)[reply]

Let q(n,m) be the number of partitions of n with parts <= m and at least one part = m. There is a recurrence relation:

q(n,m) = q(n-m,m) + q(n-1,m-1)

Taking q(n,m) = 0 or q(n,m) = 1 in the following base cases:

(where each case assumes the preceding cases do not apply)

n = m then q(n,m)= 1

n = 0 then q(n,m)= 0

m > n then q(n,m)= 0

m = 1 then q(n,m)= 1

m <= 0 then q(n,m)= 0

Is this correct? If so, should it be included in the article?

Best wishes, Jos Koot Jos.koot (talk) 12:52, 29 May 2014 (UTC)[reply]

Up to some possible minor errors, this is correct. But you have more initial values than necessary: it suffices to define q(0, 0) = 1 and q(n, m) = 0 if either n or m is not positive. I am in the middle of a large edit on the article; this recursion will be in it. --JBL (talk) 15:17, 29 May 2014 (UTC)[reply]

Thanks. I took the initial values from a one of my programs that uses (and tests) the relation. The initial cases avoid recurrence where not necessary and avoid a memorizing table to grow more than needed.. But you are right of course. I look forward to your edit. Best wishes, Jos.koot (talk) 16:29, 29 May 2014 (UTC)[reply]

Yes, your version avoids (e.g.) using the recurrence to compute a whole bunch of obvious 0s. If you like, feel free to change it -- it now appears in this section of the article. (I have used somewhat different notation, following Stanley's Enumerative Combinatorics.) Best, JBL (talk) 16:58, 29 May 2014 (UTC)[reply]

Thanks. I had to have a good look to recognize my recurrence relation, but it is there! Because the article is about the mathematics rather than about programming I feel no need to change it. Excellent in my view. Very clear. Thanks again, Jos.koot (talk) 19:46, 29 May 2014 (UTC) .[reply]

• Can this be verified by citing an independent reliable source? Or is this original research? If the latter, we cannot include it. Deltahedron (talk) 21:27, 29 May 2014 (UTC)[reply]

Yes, of course it can, it is a widely known elementary property of the objects in question, and appears e.g. in Bona's undergraduate textbook. This question might have been more interesting if there had not already been extended engagement here involving an experienced and subject-expert editor. --JBL (talk) 21:59, 29 May 2014 (UTC)[reply]

If it appears in a textbook, then please add the citation. Just to remind you, Wikipedia:Verifiability policy states "Wikipedia does not publish original research. Its content is determined by previously published information rather than the beliefs or experiences of its editors." Your last statement was possibly badly phrased: it sounded almost as if you were saying that as an experienced and expert editor you were somehow entitled to waive this core policy. Deltahedron (talk) 05:40, 30 May 2014 (UTC)[reply]

Please don't be intentionally dull: the relevance of my expertise and experience is in my ability to recognize OR and it's inappropriateness. In case it's not clear: your intrusion into this discussion was needlessly rude and abrupt, and the point of my comments is to suggest that you find a less irritating way to engage. But, as long as we're dealing in pointless tedium instead of basic politeness and common sense, you'll note that the possibility of citation alone satisfies all relevant policies. (As it happens, I do not possess a copy of the book and so cannot produce a proper citation.) JBL (talk) 13:25, 30 May 2014 (UTC)[reply]

A reminder from Wikipedia:Talk page guidelines: "Talk pages are for improving the encyclopedia, not for expressing personal opinions on a subject or an editor". The claim that "the possibility of citation alone satisfies all relevant policies" is incorrect: Wikipedia:Verifiability is certainly a relevant policy and states "any material whose verifiability has been challenged or is likely to be challenged, must include an inline citation that directly supports the material". I have challenged you to provide a citation and you have admitted that you are currently unable to do so. You might like to look at page 152 of A Course in Combinatorics by J. H. van Lint and R. M. Wilson; or page 34 of Introduction to Combinatorics: Discrete Mathematics and Its Applications by A. B. Slomson; or page 295 of Elementary Number Theory in Nine Chapters by James Joseph Tattersall. Deltahedron (talk) 19:12, 30 May 2014 (UTC)[reply]

In A Course in Combinatorics by J. H. van Lint and R. M. Wilson I find:

Problem 15A. Show that pk(n) = pk−1(n − 1) + pk(n − k) and use this to prove (15.2).

Here we have a reference I think, a very good one, for it is shown as an exercise that a student should be able to solve. If the other sources mentioned by Deltahedron can be regarded as references too, the solution seems to be solved. Just include them. mho. Jos.koot (talk) 21:40, 30 May 2014 (UTC)[reply]

I reverted [1] a good faith edit [2] that changed the sentence "the Young diagram uses boxes" to "the Young diagram uses polyominos", and a third editor has in turn reverted me [3]. My reason is that a Young diagram is not the same thing as a polyomino: a Young diagram satisfies much more stringent conditions; the theory of partitions is not closely connected with the theory of polyominoes; and the word "boxes" is quite apt when studying generalisations of Young diagrams in combinatorics such as Young tableaux, where we are told [a] Young tableau is obtained by filling in the boxes of the Young diagram with symbols taken from some alphabet [my emphasis]. Replacing "boxes" by "polyominoes" here would make nonsense of the description. The third editor's rationale "polyominoes (connected sets of squares) is more precise; they are not made of cardboard" seems irrelevant: as I have said, polynomino is not a precise description, it is less rather than more useful and I certainly did not maintain that Young diagrams are made of cardboard, and cannot see how anyone would imagine that I did. So -- any other opinions? Deltahedron (talk) 07:58, 14 June 2014 (UTC) Additional: it would help the discussion to point to independent reliable sources that refer to Young diagrams as using polyominoes. Deltahedron (talk) 15:35, 14 June 2014 (UTC)[reply]

I know this is a second opinion and you really asked for a third one, but: Google scholar finds multiple hits for the combination of Young diagrams and polyominoes. And obviously, a Young diagram *is* a special kind of polyomino: a polyomino is a connected subset of the boxes, or squares, or cells of the plane, and a Young diagram is defined in the same way but with additional conditions on how the squares are placed. I think the connection is more important in the other direction: one can work happily with partitions and Young diagrams without knowing that they are polyominoes, but if one is working with polyominoes then the theory of Young diagrams is more developed and important as motivation. So I certainly think polyomino should be linked in the Young diagram article, and that Young diagram should be linked in the polyomino article. Whether polyomino should be linked here is less clear, but not unreasonable. But your edit summary "the boxes are not polyominoes" is completely misguided. Of course the boxes are not polyominoes, but the diagrams as a whole are indeed (a special kind of) polyominoes. —David Eppstein (talk) 16:56, 14 June 2014 (UTC)[reply]

The change under discussion is "the Young diagram uses boxes" to "the Young diagram uses polyominos". Is there any support for the phraseology that the cells, boxes, squares, or whatever that the Young diagram uses are ever called polyominoes? There is support for the notion that a Young diagram is a rather special sort of polyomino, although that it not relevant at this precise point in the text. I do not believe there is any support for the notion that a Young diagram uses polyominoes to represent a partition. There is. on the other hand, considerable support for saying that a Young diagram uses boxes (as opposed to dots, as would be used in a Ferrars diagram), to represent a partition. I therefore maintain that in the context of the section "Representation of partitions" and the precise sentence "Rather than representing a partition with dots, as in the Ferrers diagram, the Young diagram uses polyominos", the term polyominoes is misleading, and the original and far more common term "boxes" is appropriate. Deltahedron (talk) 17:19, 14 June 2014 (UTC)[reply]

The things the diagrams are made of are cells, boxes, squares, or whatever. The diagrams themselves are an instance of polyominoes, which are also things made of cells, boxes, squares or whatever but with fewer restrictions on how they're arranged. So of course a Young diagram doesn't *use* polyominoes. It *is* a polyomino. —David Eppstein (talk) 17:37, 14 June 2014 (UTC)[reply]

Then it seems that we are now in agreement that the change to "the Young diagram uses polyominos" can be reverted back to "the Young diagram uses boxes". Deltahedron (talk) 17:59, 14 June 2014 (UTC)[reply]

Ok, I agree. In that precise context, boxes (or squares) would be the right noun to use. I wouldn't mind having polyominoes mentioned somewhere in that section, but as I said above I think it's less important here and more important in the actual Young diagram article. —David Eppstein (talk) 18:09, 14 June 2014 (UTC)[reply]

Thanks for that -- I have restored the status quo. Deltahedron (talk) 20:55, 14 June 2014 (UTC)[reply]

I agree that boxes are more accurate descriptions of the components of Young Diagrams than polyominos. I just want to ask, isn't there an surjective (but not injective) map between partitions (as represented by Young diagrams or Ferrars diagrams or whatever) and polyominos? Because the Young diagram *is* a special kind of polyomino. And wouldn't the relevant articles be better off for mentioning this connection? Matt.mawson (talk) 22:08, 18 June 2014 (UTC)[reply]

Young diagrams can be regarded as a special type of polyomino (so there's an injection from the set of Young diagrams to the set of polyominoes). As David Eppstein mentions above, this fact is mentioned in numerous references, so it seems reasonable to mention it on Wikipedia, suitably attributed. Is there any further significance to the connection beyond that? Deltahedron (talk) 19:56, 19 June 2014 (UTC)[reply]

I'm fine with mentioning polyominos here, but not in a way that requires novice readers to visit that page in order to understand what is said here. I'm not sure that restriction is satisfied by the attempted wordings so far. Instead of saying that it is a polyomino, say that it is a shape formed by adjacent squares (or something like that), and only then note that it is a special type of polyomino. McKay (talk) 03:07, 20 June 2014 (UTC)[reply]

I've tried to add it in a way that meets McKay's criterion. Better this time? —David Eppstein (talk) 05:37, 20 June 2014 (UTC)[reply]

Lovely! McKay (talk) 06:19, 20 June 2014 (UTC)[reply]

Good Matt.mawson (talk) 22:28, 20 June 2014 (UTC)[reply]

The sum of Permutation of all Possible Partition for a given number (n) is equal to 2^(n-1). To have a look then click on the link below. https://drive.google.com/folderview?id=0B4wrAuhEkQyvY0g0QlhfQ3h0UU0&usp=sharing_eid

At the moment the subsection "Representation of partitions" starts of saying that Ferrer diagrams use a row of dots for each part, giving an example. However, all subsequent examples seem to use columns of dots instead. There should be consistency, but I don't know what the standard choice is. — Preceding unsigned comment added by KernelClass (talk • contribs) 10:23, 16 September 2014 (UTC)[reply]

One possible generating function for such partitions, taking k fixed and n variable, is

${\displaystyle \sum _{n\geq 0}p_{k}(n)x^{n}=x^{k}\cdot \prod _{i=1}^{k}{\frac {1}{1-x^{i}}}.}$

More generally, if T is a set of positive integers then the number of partitions of n, all of whose parts belong to T, has generating function

${\displaystyle \prod _{t\in T}(1-x^{t})^{-1}.}$

Isn't there a contradiction between the given example and the general formula ? Why is there a leading ${\displaystyle x^{k}}$ in the example ?

LeCrayonVert (talk) 09:44, 1 February 2015 (UTC)[reply]

No contradiction, just definitions that slightly misalign: p_k requires in its definition that the partitions being counted contain a part of size k; the second formula has no such requirement. --JBL (talk) 16:14, 1 February 2015 (UTC)[reply]

Ok thanks. LeCrayonVert (talk) 19:49, 4 February 2015 (UTC)[reply]

There is something about Leibniz under the heading "See also", but there should be more, as he seems to have introduced partitions. — Preceding unsigned comment added by 79.180.28.37 (talk • contribs) 12:13, 13 January 2016 (UTC)[reply]

In

Using the same conjugation trick as above, one may show that the number pk(n) of partitions of n into exactly k parts is equal to the number of partitions of n in which the largest part has size k.[23] The function pk(n) satisfies the recurrence

pk(n) = pk(n − k) + pk − 1(n − 1)

with initial values p0(0) = 1 and pk(n) = 0 if n ≤ 0 or k ≤ 0.

shouldn't the second addend be p_(k-1)(n)? — Preceding unsigned comment added by 69.12.245.117 (talk • contribs) 00:54, 21 January 2017 (UTC)[reply]

Please, sign your posts in talk pages by four tildes (~~~~).

The formula was correct, but it was not clear that "k-1" was an indice. I have reformatted the formula, hoping that it is now less confusing. D.Lazard (talk) 10:51, 21 January 2017 (UTC)[reply]

Shouldn't the formula for ${\displaystyle a_{k}}$ be "${\displaystyle (-1)^{m}}$ if ${\displaystyle k=3*m^{2}-m}$ or ${\displaystyle k=3*m^{2}+m}$"? At least that is the formula that Abramowitz and Stegun p. 826, 24.2.2 eq. II(A) give. Kdpw (talk) 22:51, 10 April 2017 (UTC)[reply]

Presumably A&S ask that m be positive; the two cases fold into one if we allow m to be any integer, as in that section. --JBL (talk) 01:38, 11 April 2017 (UTC)[reply]

Oh, I see that now. Thanks Kdpw (talk) 14:13, 12 April 2017 (UTC)[reply]

@Joel B. Lewis, that is wrong. It is not the partition that is distinct, it is the parts that are. ImTheIP (talk) 16:20, 28 October 2018 (UTC)[reply]

In this section the recurrence

${\displaystyle p_{k}(n)=p_{k}(n-k)+p_{k-1}(n-1)}$

has been the object of several edits and reverts. It is correct; proof: given a partition of ${\displaystyle p_{k}(n),}$ either all parts are ≥ 2, and one gets a partition of ${\displaystyle p_{k}(n-k)}$ by removing one to each part, or one gets a partition of ${\displaystyle p_{k-1}(n-1)}$ by removing one part equal to 1.

However, another recurrence is also true:

${\displaystyle p_{k}(n)=p_{k}(n-1)+p_{k-1}(n-1)}$

Proof: Substract one to the lowest part.

As this recurrence is simpler (and the initial conditions are much simpler, as there is no need to consider negative integers), this recurrence must appear in this section, and deserve probably to be more emphasized than the one which is presently given. I have no reference under hand, but this is so simple that it must exists, if there is no mistake in my sketched proof. D.Lazard (talk) 14:06, 15 September 2019 (UTC)[reply]

It is obvious that both recurrences cannot be true simultaneously. Your alternative doesn't have a reference because it is wrong: the image of the map "subtract one from the smallest part" does not include all partitions of n - 1 into k parts. Already it is broken for n = 3, k = 2, but it's probably easier to see the problem with n = 5, k = 2. --JBL (talk) 14:09, 15 September 2019 (UTC)[reply]

OK, my mistake, thanks. D.Lazard (talk) 14:14, 15 September 2019 (UTC)[reply]

The Asymptotics section begins like this:

---

The asymptotic expression for p(n) implies that

${\displaystyle \log p(n)\sim C{\sqrt {n}}{\mbox{ as }}n\rightarrow \infty }$

where ${\displaystyle C=\pi {\sqrt {\frac {2}{3}}}}$.

If A is a set of natural numbers, we let p_A(n) denote the number of partitions of n into elements of A. If A possesses positive natural density α then

${\displaystyle \log p_{A}(n)\sim C{\sqrt {\alpha n}}}$

---

No, no, no, no, no. Do not discuss the logarithm of the asymptotic formula when the asymptotic formula has not even been stated yet.

First things first.

This ought to be 100% obvious to anyone writing for an encyclopedia.2600:1700:E1C0:F340:51D:10F4:9B05:6C06 (talk) 05:48, 20 September 2019 (UTC)[reply]

Wikipedia is a collaborative work, and articles can be written by anybody. You should understand that many editors of math. articles know mathematics, but are not specialist of Encyclopedic writing. Here, it is clear that the editor has written "implies that" instead of "can be written". In other words the given formula is a way for stating the asymptotic formula. D.Lazard (talk) 07:37, 20 September 2019 (UTC)[reply]

I agree with D.Lazard that that was a lot of hostile words for a basically trivial infelicity of wording. I have rewritten the sentence to emphasize that this is the place where the asymptotic formula is being introduced. --JBL (talk) 17:55, 20 September 2019 (UTC)[reply]

The function: y=(0.00005)x^9 - (0.00005)x^8 +(0.00005)x^7 -(0.00005)x^6+(0.01)x^5-(0.07)x^4+(0.36)x^3-(0.75)x^2+x+0.85 is a better fit for values of P(n) from 0 to 31. I apologize for my previous typing mistakes. enoraB otreboR 79.42.168.169 (talk) 11:26, 25 April 2023 (UTC)[reply]

The function value is negative for almost all values of x. – I probably won't post any other replies in this section. See WP:NOTFORUM, WP:OR, etc. — Chrisahn (talk) 11:50, 25 April 2023 (UTC)[reply]

Sorry for my mistake, I mean 'this function is a better fit' for values of P(n) from 0 to 31. Of course it has an exponential grow for higher values. 79.42.168.169 (talk) 12:10, 25 April 2023 (UTC)[reply]

I apologize for my previous typing mistakes - enoraB otreboR 79.42.168.169 (talk) 12:57, 25 April 2023 (UTC)[reply]

I apologize for my previous typing mistakes - enoraB otreboR 79.42.168.169 (talk) 13:06, 25 April 2023 (UTC)[reply]