Contents 5 sections
  1. 一个乘积
  2. 系数在数什么
  3. Franklin 的对合
  4. 哪些分拆配不上对
  5. 一个意外的推论:快速计算分拆数

一个乘积

把无穷乘积 (1−x)(1−x2)(1−x3)(1−x4)⋯(1-x)(1-x^2)(1-x^3)(1-x^4)\cdots 乘开,前几项是

1−x−x2+x5+x7−x12−x15+x22+x26−⋯1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + x^{22} + x^{26} - \cdots

有两件事很奇怪。第一,绝大多数系数是 00,按理说乘开后各项应该杂乱地堆积在一起,却几乎全部抵消了。第二,留下的系数只有 ±1\pm1,符号两正两负地交替;指数 1,2,5,7,12,15,22,26,…1, 2, 5, 7, 12, 15, 22, 26, \dots 恰好是广义五边形数。

定理 1(Euler 五边形数定理)

作为形式幂级数,

∏n=1∞(1−xn)=∑k=−∞∞(−1)k xk(3k−1)/2.\prod_{n=1}^{\infty}(1-x^n) = \sum_{k=-\infty}^{\infty} (-1)^k\, x^{k(3k-1)/2}.

k=1,2,3,…k = 1, 2, 3, \dots 时 k(3k−1)/2k(3k-1)/2 给出 1,5,12,22,…1, 5, 12, 22, \dots,即用点摆成的正五边形的点数;k=−1,−2,…k = -1, -2, \dots 给出 2,7,15,26,…2, 7, 15, 26, \dots。Euler 在 1741 年左右通过计算发现了这个规律,直到 1750 年才找到证明。

系数在数什么

先弄清左边的系数意味着什么。乘开 ∏(1−xn)\prod(1 - x^n) 时,从每个因子里要么取 11,要么取 −xn-x^n。取出的 −xn1,−xn2,…,−xnm-x^{n_1}, -x^{n_2}, \dots, -x^{n_m} 相乘得到 (−1)mxn1+⋯+nm(-1)^m x^{n_1+\cdots+n_m},其中 n1,…,nmn_1, \dots, n_m 互不相同。所以

[xN]∏n≥1(1−xn)=e(N)−o(N),[x^N]\prod_{n\ge1}(1-x^n) = e(N) - o(N),

其中 e(N)e(N)、o(N)o(N) 分别是把 NN 写成偶数个、奇数个互不相同的正整数之和的方法数(不计顺序)。

例如 N=6N = 6:分成互异部分的写法有 6, 5+1, 4+2, 3+2+16,\ 5+1,\ 4+2,\ 3+2+1,偶数个的 22 种,奇数个的 22 种,系数为 00。N=5N = 5:5, 4+1, 3+25,\ 4+1,\ 3+2,偶 22 奇 11,系数为 11,与定理一致。

于是定理等价于一个纯组合的命题:除了五边形数,偶分拆与奇分拆一样多。要证明两类一样多,最好的办法是在它们之间建立一一对应。

Franklin 的对合

把一个互异分拆 λ1>λ2>⋯>λm\lambda_1 > \lambda_2 > \cdots > \lambda_m 画成 Ferrers 图:第 ii 行放 λi\lambda_i 个点,左端对齐。定义两个量:

  • ss:底,即最小部分 λm\lambda_m,也就是最后一行的点数;
  • σ\sigma:坡,即从第一行开始、每行恰好比上一行少 11 的最长连续行数,也就是右侧那条 45∘45^\circ 斜边上的点数。

Franklin 定义了两种操作:

  • 操作 A(s≤σs \le \sigma 时):拿走最后一行的 ss 个点,在最上面 ss 行的末尾各加一个点,也就是把底「立起来」贴到坡上。
  • 操作 B(s>σs > \sigma 时):把坡上的 σ\sigma 个点各拿走,作为新的一行放到最下面,也就是把坡「放倒」成新的底。
→7+6+5+3(4 个部分)8+7+6(3 个部分)
图 1操作 A:分拆 7+6+5+3 的底 s = 3(蓝),坡 σ = 3(红)。把底的 3 个点贴到坡上,得到 8+7+6,部分数由偶变奇。

两种操作都使部分的个数恰好改变 11,从而改变奇偶;而且只要能做,结果仍是互异分拆,并且操作 A 与操作 B 互为逆操作。验证要点:操作 A 之后,新的坡至少有 ss 行,新的底大于 ss,所以接下来应做的恰好是操作 B,并且会把刚贴上的 ss 个点原样取下。反之亦然。这样,能做操作的分拆被两两配对,每一对恰好一偶一奇,在 e(N)−o(N)e(N) - o(N) 中相互抵消。

哪些分拆配不上对

问题只出在底和坡共用一个点的时候,也就是坡一直延伸到最后一行(σ=m\sigma = m),右下角那个点既在底上又在坡上。

情形一:s=σ=ms = \sigma = m。按规则该做操作 A,但拿走底的同时也拿走了坡的最后一个点,剩下的 m−1m - 1 行放不下 s=ms = m 个点,操作失败。这时分拆是

m+(m+1)+⋯+(2m−1)=m(3m−1)2.m + (m+1) + \cdots + (2m-1) = \frac{m(3m-1)}{2}.

情形二:s=σ+1s = \sigma + 1 且 σ=m\sigma = m。按规则该做操作 B,但把坡放倒成新的一行(长度 mm)后,原来的底只剩 s−1=ms - 1 = m 个点,与新行一样长,不再是互异分拆,操作失败。这时分拆是

(m+1)+(m+2)+⋯+2m=m(3m+1)2.(m+1) + (m+2) + \cdots + 2m = \frac{m(3m+1)}{2}.

其他情况下操作都能顺利完成。所以对每个 NN:

  • 如果 NN 不是广义五边形数,所有分拆两两配对,e(N)−o(N)=0e(N) - o(N) = 0;
  • 如果 N=m(3m∓1)/2N = m(3m \mp 1)/2,恰好剩下一个配不上对的分拆,它有 mm 个部分,贡献 (−1)m(-1)^m。

而 m(3m−1)/2m(3m-1)/2 与 m(3m+1)/2m(3m+1)/2 正是 k(3k−1)/2k(3k-1)/2 在 k=mk = m 与 k=−mk = -m 时的值,符号都是 (−1)m=(−1)k(-1)^m = (-1)^k。定理 1 得证。

一个意外的推论:快速计算分拆数

把 NN 写成正整数之和(允许重复、不计顺序)的方法数记作 p(N)p(N)。由于

∑N≥0p(N) xN=∏n≥111−xn,\sum_{N\ge0} p(N)\,x^N = \prod_{n\ge1}\frac{1}{1-x^n},

它恰好是五边形数定理左边的倒数。两者相乘等于 11,比较系数就得到:

推论 2(Euler 分拆数递推)

对 N≥1N \ge 1,

p(N)=p(N−1)+p(N−2)−p(N−5)−p(N−7)+p(N−12)+p(N−15)−⋯ ,p(N) = p(N-1) + p(N-2) - p(N-5) - p(N-7) + p(N-12) + p(N-15) - \cdots,

其中约定 p(0)=1p(0) = 1,p(负数)=0p(\text{负数}) = 0。

例如 p(10)=p(9)+p(8)−p(5)−p(3)=30+22−7−3=42p(10) = p(9) + p(8) - p(5) - p(3) = 30 + 22 - 7 - 3 = 42。

这个递推只需要大约 N\sqrt{N} 项,用它计算 p(N)p(N) 远比逐个枚举快。20 世纪初,MacMahon 正是用这个递推手算出了 p(1)p(1) 到 p(200)p(200) 的表格,Hardy 和 Ramanujan 用它来检验他们的渐近公式

p(N)∼14N3 eπ2N/3.p(N) \sim \frac{1}{4N\sqrt3}\,e^{\pi\sqrt{2N/3}}.