Content deleted Content added
m tweak intro |
Rescuing 5 sources and tagging 0 as dead.) #IABot (v2.0.9.5 |
||
| (163 intermediate revisions by 86 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 [[Integer partition|partitions]] of a non-negative integer {{mvar|n}}. For instance, {{math|1=''p''(4) = 5}} because the integer 4 has the five partitions {{math|1 + 1 + 1 + 1}}, {{math|1 + 1 + 2}}, {{math|1 + 3}}, {{math|2 + 2}}, and {{math|4}}.
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.
[[Srinivasa Ramanujan]] first discovered that the partition function has nontrivial patterns in [[modular arithmetic]], now known as [[Ramanujan's congruences]]. For instance, whenever the decimal representation of {{mvar|n}} ends in the digit 4 or 9, the number of partitions of {{mvar|n}} will be divisible by 5.
==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 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.
The first few values of the partition function, starting with {{math|1=''p''(0) = 1}}, are:
{{block indent | em = 1.5 | text = 1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, ... {{OEIS|id=A000041}}.}}
Some exact values of {{math|''p''(''n'')}} for larger values of {{mvar|n}} include:{{r|oeis}}
<math display="block">\begin{align}
p(100) &= 190,\!569,\!292\\
p(1000) &= 24,\!061,\!467,\!864,\!032,\!622,\!473,\!692,\!149,\!727,\!991 \approx 2.40615\times 10^{31}\\
p(10000) &= 36,\!167,\!251,\!325,\!\dots,\!906,\!916,\!435,\!144 \approx 3.61673\times 10^{106}
\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}}
The [[generating function]] for ''p''(''n'') is given by{{r|as}}
<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+\cdots\right)\left(1+x^2+x^4+\cdots\right)
\left(1+x^3+x^6+\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.
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]].
==Recurrence relations==
The same sequence of pentagonal numbers appears in a [[recurrence relation]] for the partition function:{{r|ew}}
<!-- Note: The following is the same formula as in the source, but in a more compact form. See [[Talk:Partition function (number theory)#Recurrence relations]]. -->
<math display="block">\begin{align}
p(n) &= \sum_{k \in \Z\setminus\{0\}} (-1)^{k+1} p(n-k(3k-1)/2) \\
&= p(n-1) + p(n-2)-p(n-5)-p(n-7) +p(n-12) +p(n-15) - p(n-22) -\cdots
\end{align}</math>
As base cases, <math>p(0)</math> is taken to equal <math>1</math>, and <math>p(k)</math> is taken to be zero for negative <math>k</math>. Although the sum on the right side appears infinite, it has only finitely many nonzero terms,
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}}
<math display="block"> p(n) = \frac{1}{n} \sum_{k=0}^{n-1} \sigma(n-k) p(k).</math>
If <math>q(n)</math> denotes the number of partitions of <math>n</math> with no repeated parts then it follows by splitting each partition into its even parts and odd parts, and dividing the even parts by two, that{{r|aa}}
<math display="block">p(n) = \sum_{k=0}^{\left\lfloor n/2 \right\rfloor} q(n-2k) p(k). </math>
== Congruences ==
{{Main|Ramanujan's congruences}}
[[Srinivasa Ramanujan]] is credited with discovering that the partition function has nontrivial patterns in [[modular arithmetic]].
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>
also by Ramanujan,{{r|bo|ono}} where the notation <math>(x)_\infty</math> denotes the product defined by
<math display="block">(x)_\infty = \prod_{m=1}^\infty (1-x^m).</math>
[[generating function#Congruences for the partition function|A short proof of this result]] can be obtained from the partition function generating function.
Ramanujan also discovered congruences modulo 7 and 11:{{r|hw}}
<math display="block">\begin{align}
p(7k + 5) &\equiv 0 \pmod 7,\\
p(11k + 6) &\equiv 0 \pmod {11}.
\end{align}</math>
The first one comes from Ramanujan's identity{{r|ono}}
<math display="block"> \sum_{k=0}^\infty p(7k+5)x^k =
7~ \frac{ (x^7)^3_\infty} {(x)^4_\infty}
+49x ~ \frac{ (x^7)^7_\infty } {(x)^8_\infty}.</math>
Since 5, 7, and 11 are consecutive [[prime number|primes]], one might think that there would be an analogous congruence for the next prime 13, <math>p(13k + a) \equiv 0 \pmod{13}</math> for some {{mvar|a}}. However, there is no congruence of the form <math>p(bk + a) \equiv 0 \pmod{b}</math> for any prime ''b'' other than 5, 7, or 11.{{r|ab}} Instead, to obtain a congruence, the argument of <math>p</math> should take the form <math>cbk+a</math> for some <math>c>1</math>. In the 1960s, [[A. O. L. Atkin]] of the [[University of Illinois at Chicago]] discovered additional congruences of this form for small prime moduli. For example:
<math display="block">p(11^3 \cdot 13 \cdot k + 237)\equiv 0 \pmod {13}.</math>
{{harvs|first=Ken|last=Ono|authorlink=Ken Ono|year=2000|txt}} proved that there are such congruences for every prime modulus greater than 3. Later, {{harvtxt|Ahlgren|Ono|2001}} showed there are partition congruences modulo every integer [[coprime integers|coprime]] to 6.{{r|o2k|ao}}
==Approximation formulas==
Approximation formulas exist that are faster to calculate than the exact formula given above.
An [[asymptotic analysis|asymptotic]] expression for ''p''(''n'') is given by
:<math>p(n) \sim \frac {1} {4n\sqrt3} \exp\left({\pi \sqrt {\frac{2n}{3}}}\right)</math> as <math>n \to \infty</math>.
This [[asymptotic formula]] was first obtained by [[G. H. Hardy]] and [[Ramanujan]] in 1918 and independently by [[J. V. Uspensky]] in 1920. Considering <math>p(1000)</math>, the asymptotic formula gives about <math>2.4402 \times 10^{31}</math>, reasonably close to the exact answer given above (1.415% larger than the true value).
Hardy and Ramanujan obtained an [[asymptotic expansion]] with this approximation as the first term:{{r|hr}}
<math display="block">p(n) \sim \frac{1}{2\pi \sqrt{2}} \sum_{k=1}^v A_k(n)\sqrt{k} \cdot
\frac{d}{dn} \left({\frac {1} {\sqrt{n-\frac{1}{24}}} \exp \left[ {\frac{\pi}{k}
\sqrt{\frac{2}{3}\left(n-\frac{1}{24}\right)}}\,\,\,\right]}\right) ,</math>
where
<math display="block">A_k(n) = \sum_{0 \le m < k, \; (m, k) = 1}
e^{ \pi i \left( s(m, k) - 2 nm/k \right) }.</math>
Here, the notation <math>(m,k)=1</math> means that the sum is taken only over the values of <math>m</math> that are [[relatively prime]] to <math>k</math>. The function <math>s(m,k)</math> is a [[Dedekind sum]].
The error after <math>v</math> terms is of the order of the next term, and <math>v</math> may be taken to be of the order of <math>\sqrt n</math>. As an example, Hardy and Ramanujan showed that <math>p(200)</math> is the nearest integer to the sum of the first <math>v = 5</math> terms of the series.{{r|hr}}
In 1937, [[Hans Rademacher]] was able to improve on Hardy and Ramanujan's results by providing a [[convergent series]] expression for <math>p(n)</math>. It is{{r|andrews|rad}}
<math display="block">p(n) = \frac{1}{\pi \sqrt{2}} \sum_{k=1}^\infty A_k(n)\sqrt{k} \cdot
\frac{d}{dn} \left({
\frac {1} {\sqrt{n-\frac{1}{24}}}
\sinh \left[ {\frac{\pi}{k}
\sqrt{\frac{2}{3}\left(n-\frac{1}{24}\right)}}\,\,\,\right]
}\right) .</math>
The proof of Rademacher's formula involves [[Ford circle]]s, [[Farey sequence]]s, [[modular group|modular symmetry]] and the [[Dedekind eta function]].
It may be shown that the <math>k</math>th term of Rademacher's series is of the order
<math display="block">\exp\left(\frac{\pi}{k} \sqrt\frac{2n}{3} \right) , </math>
so that the first term gives the Hardy–Ramanujan asymptotic approximation.
{{harvs|first=Paul|last=Erdős|authorlink=Paul Erdős|year=1942|txt}} published an elementary proof of the asymptotic formula for <math>p(n)</math>.{{r|erdos42|nathanson}}
Techniques for implementing the Hardy–Ramanujan–Rademacher formula efficiently on a computer are discussed by {{harvtxt|Johansson|2012}}, who shows that <math>p(n)</math> can be computed in time <math>O(n^{1/2+\varepsilon})</math> for any <math>\varepsilon>0</math>. This is near-optimal in that it matches the number of digits of the result.{{r|johansson}} The largest value of the partition function computed exactly is <math>p(10^{20})</math>, which has slightly more than 11 billion digits.{{r|fredrikj}}
== Strict partition function ==
=== 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'') || Strict partitions
!Partitions with only odd parts
|-
| 0 || 1 || () empty partition
|() empty partition
|-
| 1 || 1 || 1
|1
|-
| 2 || 1 || 2
|1+1
|-
| 3 || 2 || 1+2, 3
|1+1+1, 3
|-
| 4 || 2 || 1+3, 4
|1+1+1+1, 1+3
|-
| 5 || 3 || 2+3, 1+4, 5
|1+1+1+1+1, 1+1+3, 5
|-
| 6 || 4|| 1+2+3, 2+4, 1+5, 6
|1+1+1+1+1+1, 1+1+1+3, 3+3, 1+5
|-
|7
|5
|1+2+4, 3+4, 2+5, 1+6, 7
|1+1+1+1+1+1+1, 1+1+1+1+3, 1+3+3, 1+1+5, 7
|-
|8
|6
|1+3+4, 1+2+5, 3+5, 2+6, 1+7, 8
|1+1+1+1+1+1+1+1, 1+1+1+1+1+3, 1+1+3+3, 1+1+1+5, 3+5, 1+7
|-
|9
|8
|2+3+4, 1+3+5, 4+5, 1+2+6, 3+6, 2+7, 1+8, 9
|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 ===
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>
<math display="block">\sum_{n=0}^{\infty} q(n)x^n = \prod_{k = 1}^\infty (1 + x^k) = (x;x^2)_{\infty}^{-1},</math>
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}}:
<math display="block">\sum_{n=0}^{\infty} q(n)x^n = 1+1x+1x^2+2x^3+2x^4+3x^5+4x^6+5x^7+6x^8+8x^9+10x^{10}+\ldots.</math>
This series may also be written in terms of [[theta function]]s as
<math display="block">\sum_{n=0}^{\infty} q(n)x^n = \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>
where
and
<math display="block">\vartheta_{01}(x) = 1 + 2\sum_{n = 1}^{\infty} (-1)^{n} x^{n^2}.</math>
In comparison, the generating function of the regular partition numbers ''p''(''n'') has this identity with respect to the theta function:
<math display="block">\sum_{n=0}^{\infty} p(n)x^n = (x;x)_{\infty}^{-1} = \vartheta_{00}(x)^{-1/6}\vartheta_{01}(x)^{-2/3}\biggl\{\frac{1}{16\,x}\bigl[\vartheta_{00}(x)^4 - \vartheta_{01}(x)^4\bigr]\biggr\}^{-1/24}.</math>
=== Identities about strict partition numbers ===
Following identity is valid for the Pochhammer products:
: <math>(x;x)_{\infty}^{-1} = (x^2;x^2)_{\infty}^{-1}(x;x^2)_{\infty}^{-1}</math>
From this identity follows that formula:
: <math>\biggl[\sum_{n=0}^\infty p(n)x^n\biggr] = \biggl[\sum_{n=0}^\infty p(n)x^{2n}\biggr]\biggl[\sum_{n=0}^\infty q(n)x^n\biggr]</math>
Therefore those two formulas are valid for the synthesis of the number sequence p(n):
: <math>p(2n) = \sum_{k=0}^{n} p(n - k)q(2k)</math>
: <math>p(2n+1) = \sum_{k=0}^{n} p(n - k)q(2k + 1)</math>
In the following, two examples are accurately executed:
: <math>p(8) = \sum_{k=0}^{4} p(4 - k)q(2k) =</math>
: <math>= p(4)q(0) + p(3)q(2) + p(2)q(4) + p(1)q(6) + p(0)q(8) = </math>
: <math>= 5\times 1 + 3\times 1 + 2\times 2 + 1\times 4 + 1\times 6 = 22 </math>
: <math>p(9) = \sum_{k=0}^{4} p(4 - k)q(2k + 1) =</math>
: <math>= p(4)q(1) + p(3)q(3) + p(2)q(5) + p(1)q(7) + p(0)q(9) = </math>
: <math>= 5\times 1 + 3\times 2 + 2\times 3 + 1\times 5 + 1\times 8 = 30 </math>
== Restricted partition function ==
More generally, it is possible to consider partitions restricted to only elements of a subset ''A'' of the natural numbers (for example a restriction on the maximum value of the parts), or with a restriction on the number of parts or the maximum difference between parts. Each particular restriction gives rise to an associated partition function with specific properties. Some common examples are given below.
=== Euler and Glaisher's theorem ===
Two important examples are the partitions restricted to only odd integer parts or only even integer parts, with the corresponding partition functions often denoted <math>p_o(n)</math> and <math>p_e(n)</math>.
A theorem from Euler shows that the number of strict partitions is equal to the number of partitions with only odd parts: for all ''n'', <math>q(n) = p_o(n)</math>. This is generalized as [[Glaisher's theorem]], which states that the number of partitions with no more than ''d-1'' repetitions of any part is equal to the number of partitions with no part divisible by ''d''.
=== 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 [[Gaussian binomial coefficient]]:
:<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>
=== Asymptotics ===
Some general results on the asymptotic properties of restricted partition functions are known. If ''p''<sub>''A''</sub>(''n'') is the partition function of partitions restricted to only elements of a subset ''A'' of the natural numbers, then:
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=475–85}} This result was stated, with a sketch of proof, by Erdős in 1942.<ref name=erdos42></ref>{{sfn|Nathanson|2000|p=495}}
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=458–64}}
:<math> p_A(n) = \left(\prod_{a \in A} a^{-1}\right) \cdot \frac{n^{k-1}}{(k-1)!} + O(n^{k-2}) . </math>
==References==
{{reflist|refs=
<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>
<ref name=ab>{{citation
| last1 = Ahlgren
| first1 = Scott
| last2 = Boylan
| first2 = Matthew
| doi = 10.1007/s00222-003-0295-6
| issue = 3
| journal = [[Inventiones Mathematicae]]
| mr = 2000466
| pages = 487–502
| title = Arithmetic properties of the partition function
| 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>
<ref name=andrews>{{citation
| last = Andrews | first = George E. | author-link = George E. Andrews
| isbn = 0-521-63766-X
| mr = 0557013
| page = 69
| publisher = Cambridge University Press
| title = The Theory of Partitions
| year = 1976}}</ref>
<ref name=ao>{{citation
| last1 = Ahlgren
| first1 = Scott
| last2 = Ono
| first2 = Ken
| author2-link = Ken Ono
| bibcode = 2001PNAS...9812882A
| doi = 10.1073/pnas.191488598
| issue = 23
| journal = [[Proceedings of the National Academy of Sciences]]
| mr = 1862931
| pages = 12882–12884
| title = Congruence properties for the partition function
| 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>
<ref name=as>{{citation
| last1 = Abramowitz
| first1 = Milton
| author1-link = Milton Abramowitz
| last2 = Stegun
| first2 = Irene
| author2-link = Irene Stegun
| isbn = 0-486-61272-4
| page = [https://archive.org/details/handbookofmathe000abra/page/825 825]
| publisher = United States Department of Commerce, National Bureau of Standards
| title = [[Abramowitz and Stegun|Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables]]
| year = 1964
}}</ref>
<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
| mr = 1701582
| at = Art. B42c, 63
| series = [[Séminaire Lotharingien de Combinatoire]]
| 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>
<ref name=e>{{citation
| last = Euler
| first = Leonhard
| author-link = Leonhard Euler
| journal = Novi Commentarii Academiae Scientiarum Petropolitanae
| language = la
| pages = 125–169
| title = De partitione numerorum
| 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
| last = Erdős | first = P. | author-link = Paul Erdős
| doi = 10.2307/1968802
| journal = [[Annals of Mathematics]]
| mr = 0006749
| pages = 437–450
| series = Second Series
| title = On an elementary proof of some asymptotic formulas in the theory of partitions
| url = https://users.renyi.hu/~p_erdos/1942-02.pdf
| volume = 43
| year = 1942
| issue = 3 | jstor = 1968802 | zbl = 0061.07905}}</ref>
<ref name=ew>{{citation
| last = Ewell | first = John A.
| doi = 10.1216/rmjm/1181069871
| issue = 2
| journal = The Rocky Mountain Journal of Mathematics
| jstor = 44238988
| mr = 2072798
| pages = 619–627
| title = Recurrences for the partition function and its relatives
| volume = 34
| year = 2004| doi-access = free
}}</ref>
<ref name=fredrikj>{{citation
| last = Johansson | first = Fredrik
| date = March 2, 2014
| title = New partition function record: p(10<sup>20</sup>) computed
| url = https://fredrikj.net/blog/2014/03/new-partition-function-record/}}</ref>
<ref name=hw>{{citation
| last1 = Hardy | first1 = G. H. | author1-link = G. H. Hardy
| last2 = Wright | first2 = E. M. | author2-link = E. M. Wright
| edition = 6th
| isbn = 978-0-19-921986-5
| mr = 2445243
| page = 380
| publisher = [[Oxford University Press]]
| title = An Introduction to the Theory of Numbers
| year = 2008
| orig-year = 1938
| zbl = 1159.11001}}</ref>
<ref name=hr>{{citation
| last1 = Hardy | first1 = G. H. | author1-link = G. H. Hardy
| last2 = Ramanujan | first2 = S. | author2-link = Srinivasa Ramanujan
| issue = 75–115
| journal = [[Proceedings of the London Mathematical Society]]
| series = Second Series
| title = Asymptotic formulae in combinatory analysis
| volume = 17
| year = 1918}}. Reprinted in ''Collected papers of Srinivasa Ramanujan'', Amer. Math. Soc. (2000), pp. 276–309.</ref>
<ref name=johansson>{{citation
| last = Johansson | first = Fredrik
| doi = 10.1112/S1461157012001088
| journal = LMS Journal of Computation and Mathematics
| mr = 2988821
| pages = 341–59
| title = Efficient implementation of the Hardy–Ramanujan–Rademacher formula
| volume = 15
| year = 2012| arxiv = 1205.5991
| s2cid = 16580723
}}</ref>
<ref name=nathanson>{{citation
| last = Nathanson | first = M. B. | author-link = Melvyn B. Nathanson
| isbn = 0-387-98912-9
| page = 456
| publisher = [[Springer-Verlag]]
| series = [[Graduate Texts in Mathematics]]
| title = Elementary Methods in Number Theory
| volume = 195
| year = 2000
| zbl = 0953.11002}}</ref>
<ref name=oeis>{{Cite OEIS| sequencenumber=A070177| mode=cs2}}</ref>
<ref name=o2k>{{citation
| last = Ono | first = Ken | author-link = Ken Ono
| arxiv = math/0008140
| doi = 10.2307/121118
| issue = 1
| journal = [[Annals of Mathematics]]
| mr = 1745012
| pages = 293–307
| title = Distribution of the partition function modulo <math>m</math>
| volume = 151
| year = 2000
| jstor = 121118 | bibcode = 2000math......8140O | zbl = 0984.11050| s2cid = 119750203 }}</ref>
<ref name=ono>{{citation
| last = Ono | first = Ken | author-link = Ken Ono
| isbn = 0-8218-3368-5
| ___location = Providence, Rhode Island
| page = 87
| publisher = [[American Mathematical Society]]
| series = CBMS Regional Conference Series in Mathematics
| title = The web of modularity: arithmetic of the coefficients of modular forms and <math>q</math>-series
| volume = 102
| year = 2004
| zbl = 1119.11026}}</ref>
<ref name=rad>{{citation
| last = Rademacher | first = Hans | author-link = Hans Rademacher
| doi = 10.1112/plms/s2-43.4.241
| issue = 4
| journal = [[Proceedings of the London Mathematical Society]]
| mr = 1575213
| pages = 241–254
| series = Second Series
| title = On the partition function <math>p(n)</math>
| volume = 43
| year = 1937}}</ref>
<ref name=wilf>{{citation
| last = Wilf | first = Herbert S. | author-link = Herbert Wilf
| doi = 10.2307/2321713
| issue = 5
| journal = [[American Mathematical Monthly]]
| mr = 653502
| pages = 289–292
| title = What is an answer?
| volume = 89
| year = 1982| jstor = 2321713 }}</ref>
}}
==External links==
* [http://www.numericana.com/data/partition.htm First 4096 values of the partition function ]
[[Category:Arithmetic functions]]
[[Category:Integer sequences]]
[[Category:Integer partitions]]
| |||