Hardy–Ramanujan 分拆渐近公式

形式陈述

不必列出所有分拆，也能知道它们有多快地增长

把 $5$ 写成正整数之和，不计加数顺序，有

5,\quad4+1,\quad3+2,\quad3+1+1,\quad2+2+1,\quad2+1+1+1,\quad1+1+1+1+1

这七种整数分拆，所以 $p(5)=7$ 。随着 $n$ 增大，逐个列举很快变得不现实。Hardy–Ramanujan 公式不负责列举，而是给出分拆总数的精确主导增长规律：

\boxed{\displaystyle p(n)\sim\frac{1}{4n\sqrt3}\exp\!\left(\pi\sqrt{\frac{2n}{3}}\right) }\qquad(n\to\infty).

符号 $\sim$ 表示左右两边的比值趋于 $1$ 。它比只给出指数阶 $\exp(\Theta(\sqrt n))$ 更强，因为连前面的 $1/(4n\sqrt3)$ 也确定了；它又不同于对每个有限 $n$ 都成立的精确等式。[1][4]

直觉

先让生成函数记录“每个大小用了几次”

一个大小为 $k$ 的部件可以出现 $0,1,2,\ldots$ 次，对应

1+q^k+q^{2k}+\cdots=\frac1{1-q^k}.

不同大小的选择相乘，总指数就是分拆之和，因此 Euler 乘积给出

P(q)=\sum_{n\ge0}p(n)q^n =\prod_{k\ge1}\frac1{1-q^k},\qquad |q|<1,

其中 $p(0)=1$ 表示空分拆。这个乘积没有为相同加数的排列额外计数，所以记录的是分拆，而不是有顺序的分拆（composition）。

令 $q=e^{-t}$ ， $t\downarrow0$ 对应从单位圆内部接近 $q=1$ 。取对数可得到

\log P(e^{-t}) =\sum_{k\ge1}-\log(1-e^{-kt}) =\sum_{j\ge1}\frac1{j(e^{jt}-1)}.

把 $e^{jt}-1$ 的小参数行为与 $jt$ 比较，会看到主项中的 $t^{-1}\sum j^{-2}=\pi^2/(6t)$ 。这解释了指数常数从哪里来，但粗略替换还不能恢复多项式前因子。

更精细的乘积变换给出

P(e^{-t})\sim\sqrt{\frac{t}{2\pi}} \exp\!\left(\frac{\pi^2}{6t}-\frac{t}{24}\right).

沿正实轴的这个式子可以帮助理解增长；提取系数时，还需要它在适当复邻域内的一致形式，而不仅是实变量极限。[1][2]

指数中的平方根来自一个平衡点

Cauchy 系数积分会把 $P(q)$ 与 $q^{-n}$ 相乘。代入 $q=e^{-t}$ ，暂时把只影响次阶的 $e^{-t/24}$ 留在振幅中，主指数成为

\Phi(t)=nt+\frac{\pi^2}{6t}.

第一个项随 $t$ 增大，第二个项随 $t$ 减小而增大。鞍点法在两者平衡的位置建立局部近似：

\Phi'(t)=n-\frac{\pi^2}{6t^2}=0 \quad\Longrightarrow\quad t_0=\frac{\pi}{\sqrt{6n}}.

代回得到

\Phi(t_0)=\pi\sqrt{\frac{2n}{3}}.

于是，公式中的 $\sqrt n$ 不是猜测出来的：它来自 $nt$ 与 $1/t$ 两个尺度相平衡。若只做这一步，就只解释了主指数，还没有解释为什么要除以 $n$ 。

前面的常数来自高斯宽度

沿经过 $t_0$ 的局部竖直方向写 $t=t_0+iy$ 。因为一阶导数为零，

\Phi(t_0+iy) =\Phi(t_0)-\frac12\Phi''(t_0)y^2+\cdots,

其中

\Phi''(t_0)=\frac{\pi^2}{3t_0^3} =\frac{2\sqrt6}{\pi}n^{3/2}.

局部贡献因此集中在宽度约 $n^{-3/4}$ 的区段中。结合乘积的振幅 $\sqrt{t_0/(2\pi)}$ 与系数积分中的 $1/(2\pi)$ ，高斯积分给出主项

\begin{aligned} p(n) &\sim\frac1{2\pi}\sqrt{\frac{t_0}{2\pi}} e^{\Phi(t_0)} \int_{-\infty}^{\infty} e^{-\Phi''(t_0)y^2/2}\,dy\\ &=\frac{\sqrt{t_0/(2\pi)}}{\sqrt{2\pi\Phi''(t_0)}} e^{\Phi(t_0)}\\ &=\frac1{4n\sqrt3} e^{\pi\sqrt{2n/3}}. \end{aligned}

分母的 $n$ 由两个尺度合成：振幅贡献 $n^{-1/4}$ ，有效积分宽度贡献 $n^{-3/4}$ 。这也说明，只保留 $\exp(\pi^2/(6t))$ 而丢掉平方根振幅，会算错前因子。

上面是主项的推导，不是省略误差控制后的完整圆法证明。要把推导提升为定理，还需证明主弧上的近似足够一致，并控制其余弧段；单位圆上其他单位根附近也会产生贡献。Hardy–Ramanujan 的分析处理了这些部分，使它们不会改变这里的首项。[1][2]

例子与边界

怎样使用这个近似

精确值 $p(100)=190\,569\,292$ ，主项公式给出约 $199\,280\,893$ ，相对误差约 $4.57\%$ 。这个例子同时说明了两点：主项已经能把数量级和主要尺度抓住，但“四舍五入渐近式”并不是一个普遍正确的精确计数算法。

推论与应用

增长尺度与受限分拆

对公式取对数，有

\log p(n) =\pi\sqrt{\frac{2n}{3}}-\log n-\log(4\sqrt3)+o(1).

因此，对每个固定 $A>0$ ， $p(n)/n^A\to\infty$ ；对每个固定 $c>1$ ， $p(n)/c^n\to0$ 。分拆数增长快于任意固定多项式，却慢于每一种底数大于 $1$ 的固定指数函数，这就是常说的亚指数增长。

限制条件会改变生成函数，也可能改变增长尺度。固定最多 $k$ 个部件时，可将分拆图转置，转为每个部件大小至多 $k$ 的分拆，生成函数变成有限乘积 $\prod_{j=1}^{k}(1-q^j)^{-1}$ 。约束改变了奇点结构，不能把无约束分拆公式直接照搬。若需要精确整数值，可以使用分拆递推；若需要更强的解析表达，Rademacher 对这一方向的发展给出了精确收敛级数。首项渐近、带误差的近似和精确级数是三个不同层次的结论。[3]

上述系数积分使用Cauchy 积分公式，把生成函数的解析行为转化为系数估计。

参考资料

[1] G. H. Hardy、S. Ramanujan，Asymptotic Formulae in Combinatory Analysis，Proceedings of the London Mathematical Society 17，1918，75–115：原始分拆渐近与圆法分析。

[2] Philippe Flajolet、Robert Sedgewick，Analytic Combinatorics，第 VIII 章：鞍点尺度、Euler 乘积与系数渐近。

[3] George E. Andrews，The Theory of Partitions，1976，第 5 章：Hardy–Ramanujan–Rademacher 理论。受限分拆的对照可参阅 NIST DLMF §26.9(iv)。

[4] Yong-Gao Chen、Ya-Li Li，Asymptotic Formulas for General Colored Partition Functions，引言公式 (1.1)–(1.3)：Euler 乘积、经典分拆渐近式及相对误差阶。

形式陈述 ​

不必列出所有分拆，也能知道它们有多快地增长 ​

先让生成函数记录“每个大小用了几次” ​

指数中的平方根来自一个平衡点 ​

前面的常数来自高斯宽度 ​

怎样使用这个近似 ​

增长尺度与受限分拆 ​