Content deleted Content added
→Restricted partition function: gaussian binomial coefficient |
Rescuing 5 sources and tagging 0 as dead.) #IABot (v2.0.9.5 |
||
| (38 intermediate revisions by 19 users not shown) | |||
Line 1:
{{Short description|The number of partitions of an integer}}
{{CS1 config|mode=cs2}}
[[File:Ferrer partitioning diagrams.svg|thumb|The values <math>p(1), \dots, p(8)</math> of the partition function (1, 2, 3, 5, 7, 11, 15, and 22) can be determined by counting the [[Young diagram]]s for the partitions of the numbers from 1 to 8.]]
In [[number theory]], the '''partition function''' {{math|''p''(''n'')}} represents the [[number]] of possible [[
No [[closed-form expression]] for the partition function is known, but it has both [[asymptotic analysis|asymptotic expansions]] that accurately approximate it and [[recurrence relation]]s by which it can be calculated exactly. It grows as an [[exponential function]] of the [[square root]] of its argument. The [[multiplicative inverse]] of its [[generating function]] is the [[Euler function]]; by Euler's [[pentagonal number theorem]] this function is an alternating sum of [[pentagonal number]] powers of its argument.
Line 8 ⟶ 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
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 22 ⟶ 23:
\end{align}</math>
▲== Generating function==
[[File:Euler_partition_function.svg|thumb|upright|link={{filepath:Euler_partition_function.svg}}|Using Euler's method to find {{math|''p''(40)}}: A ruler with plus and minus signs (grey box) is slid downwards, the relevant terms added or subtracted. The positions of the signs are given by differences of alternating natural (blue) and odd (orange) numbers. In [{{filepath:Euler_partition_function.svg}} the SVG file,] hover over the image to move the ruler.]]
{{main|Pentagonal number theorem}}
Line 30 ⟶ 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
\left(1+x^3+x^6 &=\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.▼
▲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.
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 57 ⟶ 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 68 ⟶ 65:
For instance the number of partitions is divisible by five whenever the decimal representation of <math>n</math> ends in the digit 4 or 9, as expressed by the congruence{{r|hw}}
<math display="block">p(5k+4) \equiv 0 \pmod 5</math>
For instance, the number of partitions for the integer 4 is 5.
For the integer 9, the number of partitions is 30; for 14 there are 135 partitions. This congruence is implied by the more general identity
<math display="block"> \sum_{k=0}^\infty p(5k+4)x^k = 5~ \frac{ (x^5)^5_\infty } {(x)^6_\infty},</math>
Line 130 ⟶ 127:
=== Definition and properties ===
A partition in which no part occurs more than once is called ''strict'', or is said to be a partition ''into distinct parts''. The function ''q''(''n'') gives the number of these strict partitions of the given sum ''n''. For example, ''q''(3) = 2 because the partitions 3 and 1 + 2 are strict, while the third partition 1 + 1 + 1 of 3 has repeated parts. The number ''q''(''n'') is also equal to the number of partitions of ''n'' in which only odd summands are permitted.<ref>{{cite book|first=Richard P.|last=Stanley|author-link=Richard P. Stanley|title=Enumerative Combinatorics 1 |series=Cambridge Studies in Advanced Mathematics|volume=49|publisher=Cambridge University Press|isbn=0-521-66351-2 |year=1997|at=Proposition 1.8.5}}</ref>
{| class="wikitable"
|+ Example values of ''q''(''n'') and associated partitions
|-
! ''n'' || ''q''(''n'') ||
!Partitions with only odd parts
|-
Line 144 ⟶ 138:
|() empty partition
|-
| 1 || 1 ||
|
|-
| 2 || 1 ||
|
|-
| 3 || 2 ||
|
|-
| 4 || 2 ||
|
|-
| 5 || 3 ||
|
|-
| 6 || 4||
|
|-
|7
|5
|
|
|-
|8
|6
|
|
|-
|9
|8
|
|1+1+1+1+1+1+1+1+1, 1+1+1+1+1+1+3, 1+1+1+3+3, 3+3+3, 1+1+1+1+5, 1+3+5, 1+1+7, 9
|}
=== Generating function ===
: <math>\sum_{k=0}^{\infty} q(k)x^k = (x;x^2)_{\infty}^{-1} = \vartheta_{00}(x)^{1/6}\vartheta_{01}(x)^{-1/3}\biggl\{\frac{1}{16\,x}\bigl[\vartheta_{00}(x)^4 - \vartheta_{01}(x)^4\bigr]\biggr\}^{1/24}</math>▼
The generating function for the numbers ''q''(''n'') is given by a simple infinite product:<ref>{{cite book|first=Richard P.|last=Stanley|author-link=Richard P. Stanley|title=Enumerative Combinatorics 1 |series=Cambridge Studies in Advanced Mathematics|volume=49|publisher=Cambridge University Press|isbn=0-521-66351-2 |year=1997|at=Proof of Proposition 1.8.5}}</ref>
where the notation <math>(a;b)_{\infty}</math> represents the [[Pochhammer symbol]] <math>(a;b)_{\infty} = \prod_{k = 0}^{\infty} (1 - ab^{k}).</math> From this formula, one may easily obtain the first few terms {{OEIS|A000009}}:
This series may also be written in terms of [[theta function]]s as
▲
In comparison, the generating function of the regular partition numbers p(n) has this identity with respect to the theta function:▼
where
and
▲In comparison, the generating function of the regular partition numbers ''p''(''n'') has this identity with respect to the theta function:
▲: <math>\vartheta_{00}(x) = 1 + 2\sum_{n = 1}^{\infty} x^{n^2}</math>
▲: <math>\vartheta_{01}(x) = 1 + 2\sum_{n = 1}^{\infty} (-1)^{n} x^{n^2}</math>
▲: <math>(x;x^2)_{\infty} = \prod_{n = 1}^{\infty} (1 - x^{2n - 1})</math>
=== Identities about strict partition numbers ===
Line 248 ⟶ 221:
=== Gaussian binomial coefficient ===
If we denote <math>p(N, M, n)</math> the number of partitions of ''n'' in at most ''M'' parts, with each part smaller or equal to ''N'', then the generating function of <math>p(N, M, n)</math> is the following [[
:<math>\sum_{n=0}^\infty p(N, M, n)q^n = {N+M \choose M}_q
=
\frac{(1-q^{N+M})(1-q^{N+M-1})\cdots(1-q^{N+1})} {(1-q)(1-q^2)\cdots(1-q^M)}</math>
Line 260 ⟶ 233:
If ''A'' possesses positive [[natural density]] α then <math> \log p_A(n) \sim C \sqrt{\alpha n}</math>, with <math>C = \pi\sqrt\frac23</math>
and conversely if this asymptotic property holds for ''p''<sub>''A''</sub>(''n'') then ''A'' has natural density α.{{sfn|Nathanson|2000|pp=
If ''A'' is a finite set, this analysis does not apply (the density of a finite set is zero). If ''A'' has ''k'' elements whose greatest common divisor is 1, then{{sfn|Nathanson|2000|pp=
:<math> p_A(n) = \left(\prod_{a \in A} a^{-1}\right) \cdot \frac{n^{k-1}}{(k-1)!} + O(n^{k-2}) . </math>
Line 270 ⟶ 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
| 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 name=ab>{{citation
| last1 = Ahlgren
| first1 = Scott | last2 = Boylan
| first2 = Matthew | doi = 10.1007/s00222-003-0295-6
| issue = 3
Line 289 ⟶ 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 303 ⟶ 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 314 ⟶ 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 334 ⟶ 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 343 ⟶ 342:
| title = The Andrews Festschrift (Maratea, 1998)
| volume = 42
| year = 1999
| 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>
▲ | year = 2017}}</ref>
<ref name=e>{{citation
| last = Euler
| first = Leonhard | author-link = Leonhard Euler | journal = Novi Commentarii Academiae Scientiarum Petropolitanae
| language = la
Line 359:
| url = https://eulerarchive.maa.org/pages/E191.html
| volume = 3
| year = 1753
| 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
| |||