Science Technology Engineering Mathematics History Thought Belief The Modern World
As remarked on the main Partitions page, there is no simple closed formula for \(p(n)\), the number of unrestricted partitions of \(n\). As described on the Recurrence Formulae for Partition Functions page, to calculate the value of \(p(n\) exactly, it is necessary to use a recurrence formula, which necessitates essentially computing \(p(k)\) for all positive integers \(k\leq n\).
This is extremely slow for large values of \(n\), whether for \(p(n)\) or some restricted partition counting function, and an alternative is to use a Hardy–Ramanujan-Rademacher-type Series . computing \(p(k)\) for all positive integers \(k\leq n\).
However, if one is not interested in an exact value for \(p(n)\) for a particular large \(n\), but instead is just interested in an approximation for how fast the particular partition function under consideration grows, an asymptotic formula suffices. computing \(p(k)\) for all positive integers \(k\leq n\).
Such an approximation formula for \(p(n)\) was give by Hardy and Ramanujan, who showed that $$ p(n)\sim \frac{1}{4n\sqrt{3}}\exp \left( \pi \sqrt{\frac{2n}{3}} \right) \text{ as } n \to \infty. $$ alternatively, $$ \lim_{n \to \infty} \frac{p(n)}{\frac{1}{4n\sqrt{3}}\exp \left( \pi \sqrt{\frac{2n}{3}} \right)}=1. $$ To examine how well this asymptotic formula approximates \(p(n)\), let $$ pp(n):=\frac{1}{4n\sqrt{3}}\exp \left( \pi \sqrt{\frac{2n}{3}} \right) $$ denote the approximation to \(p(n)\) above. computing \(p(k)\) for all positive integers \(k\leq n\).
The following table shows that while the ratio of \(p(n)\) and \(pp(n)\) tends to 1, the difference between the two functions becomes arbitrarily large:
$$
\begin{array}{c|c|c|c}
n &p(n)/pp(n)&p(n)&p(n)-pp(n)\\
\hline
10 & 0.873103 & 42. & -6.10431 \\
100 & 0.956285 & 1.90569\times 10^8 & -8.7116\times 10^6 \\
1000 & 0.986045 & 2.40615\times 10^{31} & -3.40528\times
10^{29} \\
10000 & 0.995573 & 3.61673\times 10^{106} & -1.60807\times
10^{104} \\
100000 & 0.998598838736 & 2.749351056977570\times 10^{346} &
-3.857689446807\times 10^{343} \\
1000000 & 0.999556775923 & 1.471684986358223\times 10^{1107}
& -6.52575456347\times 10^{1103} \\
10000000 & 0.999859826425 & 9.20271755026045\times 10^{3514}
& -1.29015866096\times 10^{3511} \\
100000000 & 0.99995567184 & 1.760517045946249\times
10^{11131} & -7.8043940224\times 10^{11126} \\
1000000000 & 0.99998598207 & 1.604535084280967\times
10^{35218} & -2.2492577894\times 10^{35213} \\
10000000000 & 0.9999955671 & 1.052394346110649\times
10^{111390} & -4.665149022\times 10^{111384} \\
\end{array}
$$
This formula has been extended by Ram Murty [M1] to an asymptotic formula for \(p_k(n)\), the counting function for the number of \(k\)-coloured partitions of \(n\), whose generating function is defined by
\[
\sum_{n=0}^{\infty}p_k(n) q^n = \left(\frac{1}{\prod_{j=1}^{\infty}(1-q^j)}\right)^k.
\]
Note that when \(k=1\), \(p_1(n)=p(n)\).
Murty [M1] show that
$$
p_k(n)\sim \frac{1}{\sqrt{2}n^{(k+3)/4}}
\left( \frac{k}{24} \right)^{(k+1)/4}
\exp \left( \pi \sqrt{\frac{2kn}{3}} \right) \text{ as } n \to \infty.
$$
[M1] R. Murty, The Partition Function Revisited, The Legacy of Srinivasa Ramanujan, RMS-Lecture Notes Series No. 20, 2013, pp. 261–279.
Back to the main Partitions page