Partition function (number theory): Difference between revisions

Revision as of 00:01, 7 August 2024

Latest revision as of 08:03, 10 August 2025

(9 intermediate revisions by 7 users not shown)

Line 9:

==Definition and examples==

For a positive integer {{math|''n''}}, {{math|''p''(''n'')}} is the number of distinct ways of representing {{mvar|n}} as a [[summation|sum]] of positive integers. For the purposes of this definition, the order of the terms in the sum is irrelevant: two sums with the same terms in a different order (e.g., {{math|1 + 1 + 2}} and {{math|1 + 2 + 1}}) are not considered to be distinct.

By convention {{math|1=''p''(0) = 1}}, as there is one way (the [[empty sum]]) of representing zero as a sum of positive integers. Furthermore {{math|1=''p''(''n'') = 0}} when {{mvar|n}} is negative.

Line 29:

<math display="block">\begin{align}

\sum_{n=0}^\infty p(n)x^n &= \prod_{k=1}^\infty \left(\frac {1}{1-x^k} \right)\\

&=\left(1+x+x^2+x^3+\cdots\right) \left(1+x^2+x^4+x^6+\cdots\right)
\left(1+x^3+x^6+x^9+\cdots\right) \cdots \\

&=\frac{1}{1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + x^{22} + x^{26} - \cdots}\\

&=1 \Big/ \sum_{k=-\infty}^{\infty} (-1)^k x^{k(3k-1)/2}.

\end{align}</math>The equality between the products on the first and second lines of this formula is obtained by expanding each factor <math>1/(1-x^k)</math> into the [[geometric series]] <math>(1+x^k+x^{2k}+x^{3k}+\cdots).</math> To see that the expanded product equals the sum on the first line, apply the [[distributive law]] to the product. This expands the product into a sum of [[monomial]]s of the form <math>x^{a_1} x^{2a_2} x^{3a_3} \cdots</math> for some sequence of coefficients <math>a_i</math>, only finitely many of which can be non-zero. The exponent of the term is <math display="inline">n = \sum i a_i</math>, and this sum can be interpreted as a representation of <math>n</math> as a partition into <math>a_i</math> copies of each number <math>i</math>. Therefore, the number of terms of the product that have exponent <math>n</math> is exactly <math>p(n)</math>, the same as the coefficient of <math>x^n</math> in the sum on the left. Therefore, the sum equals the product.

\end{align}</math>

The equality between the products on the first and second lines of this formula

is obtained by expanding each factor <math>1/(1-x^k)</math> into the [[geometric series]] <math>(1+x^k+x^{2k}+x^{3k}+\cdots).</math>

To see that the expanded product equals the sum on the first line,

apply the [[distributive law]] to the product. This expands the product into a sum of [[monomial]]s of the form <math>x^{a_1} x^{2a_2} x^{3a_3} \cdots</math> for some sequence of coefficients

<math>a_i</math>, only finitely many of which can be non-zero.

The exponent of the term is <math display="inline">n = \sum i a_i</math>, and this sum can be interpreted as a representation of <math>n</math> as a partition into <math>a_i</math> copies of each number <math>i</math>. Therefore, the number of terms of the product that have exponent <math>n</math> is exactly <math>p(n)</math>, the same as the coefficient of <math>x^n</math> in the sum on the left.

Therefore, the sum equals the product.

The function that appears in the denominator in the third and fourth lines of the formula is the [[Euler function]]. The equality between the product on the first line and the formulas in the third and fourth lines is Euler's [[pentagonal number theorem]].

The exponents of <math>x</math> in these lines are the [[pentagonal number]]s <math>P_k = k(3k-1)/2</math> for <math>k \in \{ 0, 1,-1,2,-2,\dots\}</math> (generalized somewhat from the usual pentagonal numbers, which come from the same formula for the positive values {{nowrap|of <math>k</math>).}} The pattern of positive and negative signs in the third line comes from the term <math>(-1)^k</math> in the fourth line: even choices of <math>k</math> produce positive terms, and odd choices produce negative terms.

More generally, the generating function for the partitions of <math>n</math> into numbers selected from a set <math>A</math> of positive integers can be found by taking only those terms in the first product for which <math>k\in A</math>. This result is due to [[Leonhard Euler]].{{r|e}} The formulation of Euler's generating function is a special case of a [[q-Pochhammer symbol|<math>q</math>-Pochhammer symbol]] and is similar to the product formulation of many [[modular form]]s, and specifically the [[Dedekind eta function]].

Line 56 ⟶ 50:

coming from the nonzero values of <math>k</math> in the range

<math display="block"> - \frac{\sqrt{24n+1}-1}{6} \leq k \leq \frac{\sqrt{24n+1}+1}{6}.</math>

The recurrence relation can also be written in the equivalent form

<math display="block">

p(n) = \sum_{k = 1}^\infty (-1)^{k+1} \big(p(n-k(3k-1)/2) + p(n-k(3k+1)/2)\big) .

</math>

Another recurrence relation for <math>p(n)</math> can be given in terms of the [[divisor function|sum of divisors function]] {{math|''σ''}}:{{r|wilf}}

Line 245 ⟶ 243:

<ref name=aa>{{citation

| last1 = Al
| first1 = Busra

| last2 = Alkan
| first2 = Mustafa

| contribution = A note on relations among partitions

| pages = 35–39

| title = Proc. Mediterranean Int. Conf. Pure & Applied Math. and Related Areas (MICOPAM 2018)

| url = https://elibrary.matf.bg.ac.rs/handle/123456789/4699

| year = 2018}}</ref>

| access-date = 2018-12-17

| archive-date = 2024-04-27

| archive-url = https://web.archive.org/web/20240427205845/http://elibrary.matf.bg.ac.rs/handle/123456789/4699

| url-status = dead

}}</ref>

<ref name=ab>{{citation

| last1 = Ahlgren
| first1 = Scott

| last2 = Boylan
| first2 = Matthew

| doi = 10.1007/s00222-003-0295-6

| issue = 3

Line 264 ⟶ 271:

| url = https://www.math.sc.edu/~boylan/reprints/nomoreramafinal.pdf

| volume = 153

| year = 2003
| bibcode = 2003InMat.153..487A

| s2cid = 123104639

| access-date = 2018-12-17

| archive-date = 2008-07-19

| archive-url = https://web.archive.org/web/20080719184728/http://www.math.sc.edu/~boylan/reprints/nomoreramafinal.pdf

| url-status = dead

}}</ref>

Line 278 ⟶ 290:

<ref name=ao>{{citation

| last1 = Ahlgren
| first1 = Scott

| last2 = Ono
| first2 = Ken
| author2-link = Ken Ono

| bibcode = 2001PNAS...9812882A

| doi = 10.1073/pnas.191488598

Line 289 ⟶ 304:

| url = https://www.mathcs.emory.edu/~ono/publications-cv/pdfs/061.pdf

| volume = 98

| year = 2001
| pmid = 11606715

| pmc = 60793

| doi-access = free

| access-date = 2018-12-17

| archive-date = 2019-03-04

| archive-url = https://web.archive.org/web/20190304030350/http://www.mathcs.emory.edu/~ono/publications-cv/pdfs/061.pdf

| url-status = dead

}}</ref>

Line 309 ⟶ 329:

<ref name=bo>{{citation

| last1 = Berndt
| first1 = Bruce C.
| author1-link = Bruce C. Berndt

| last2 = Ono
| first2 = Ken
| author2-link = Ken Ono

| contribution = Ramanujan's unpublished manuscript on the partition and tau functions with proofs and commentary

| contribution-url = https://www.mathcs.emory.edu/~ono/publications-cv/pdfs/044.pdf

Line 318 ⟶ 342:

| title = The Andrews Festschrift (Maratea, 1998)

| volume = 42

| year = 1999}}</ref>

| access-date = 2018-12-17

| archive-date = 2019-03-04

| archive-url = https://web.archive.org/web/20190304030309/http://www.mathcs.emory.edu/~ono/publications-cv/pdfs/044.pdf

| url-status = dead

}}</ref>

<ref name=e>{{citation

| last = Euler
| first = Leonhard
| author-link = Leonhard Euler

| journal = Novi Commentarii Academiae Scientiarum Petropolitanae

| language = la

Line 328 ⟶ 359:

| url = https://eulerarchive.maa.org/pages/E191.html

| volume = 3

| year = 1753}}</ref>

| access-date = 2018-12-17

| archive-date = 2023-08-05

| archive-url = https://web.archive.org/web/20230805000145/http://eulerarchive.maa.org//pages/E191.html

| url-status = dead

}}</ref>

<ref name=erdos42>{{citation