Contents 5 sections 一个乘积 系数在数什么 Franklin 的对合 哪些分拆配不上对 一个意外的推论:快速计算分拆数 一个乘积
把无穷乘积 ( 1 − x ) ( 1 − x 2 ) ( 1 − x 3 ) ( 1 − x 4 ) ⋯ (1-x)(1-x^2)(1-x^3)(1-x^4)\cdots ( 1 − x ) ( 1 − x 2 ) ( 1 − x 3 ) ( 1 − x 4 ) ⋯ 乘开,前几项是
1 − x − x 2 + x 5 + x 7 − x 12 − x 15 + x 22 + x 26 − ⋯ 1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + x^{22} + x^{26} - \cdots 1 − x − x 2 + x 5 + x 7 − x 12 − x 15 + x 22 + x 26 − ⋯
有两件事很奇怪。第一,绝大多数系数是 0 0 0 ,按理说乘开后各项应该杂乱地堆积在一起,却几乎全部抵消了。第二,留下的系数只有 ± 1 \pm1 ± 1 ,符号两正两负地交替;指数 1 , 2 , 5 , 7 , 12 , 15 , 22 , 26 , … 1, 2, 5, 7, 12, 15, 22, 26, \dots 1 , 2 , 5 , 7 , 12 , 15 , 22 , 26 , … 恰好是广义五边形数 。
定理 1(Euler 五边形数定理) 作为形式幂级数,
∏ n = 1 ∞ ( 1 − x n ) = ∑ k = − ∞ ∞ ( − 1 ) k x k ( 3 k − 1 ) / 2 . \prod_{n=1}^{\infty}(1-x^n) = \sum_{k=-\infty}^{\infty} (-1)^k\, x^{k(3k-1)/2}. n = 1 ∏ ∞ ( 1 − x n ) = k = − ∞ ∑ ∞ ( − 1 ) k x k ( 3 k − 1 ) /2 .
k = 1 , 2 , 3 , … k = 1, 2, 3, \dots k = 1 , 2 , 3 , … 时 k ( 3 k − 1 ) / 2 k(3k-1)/2 k ( 3 k − 1 ) /2 给出 1 , 5 , 12 , 22 , … 1, 5, 12, 22, \dots 1 , 5 , 12 , 22 , … ,即用点摆成的正五边形的点数;k = − 1 , − 2 , … k = -1, -2, \dots k = − 1 , − 2 , … 给出 2 , 7 , 15 , 26 , … 2, 7, 15, 26, \dots 2 , 7 , 15 , 26 , … 。Euler 在 1741 年左右通过计算发现了这个规律,直到 1750 年才找到证明。
系数在数什么
先弄清左边的系数意味着什么。乘开 ∏ ( 1 − x n ) \prod(1 - x^n) ∏ ( 1 − x n ) 时,从每个因子里要么取 1 1 1 ,要么取 − x n -x^n − x n 。取出的 − x n 1 , − x n 2 , … , − x n m -x^{n_1}, -x^{n_2}, \dots, -x^{n_m} − x n 1 , − x n 2 , … , − x n m 相乘得到 ( − 1 ) m x n 1 + ⋯ + n m (-1)^m x^{n_1+\cdots+n_m} ( − 1 ) m x n 1 + ⋯ + n m ,其中 n 1 , … , n m n_1, \dots, n_m n 1 , … , n m 互不相同。所以
[ x N ] ∏ n ≥ 1 ( 1 − x n ) = e ( N ) − o ( N ) , [x^N]\prod_{n\ge1}(1-x^n) = e(N) - o(N), [ x N ] n ≥ 1 ∏ ( 1 − x n ) = e ( N ) − o ( N ) ,
其中 e ( N ) e(N) e ( N ) 、o ( N ) o(N) o ( N ) 分别是把 N N N 写成偶数个 、奇数个 互不相同的正整数之和的方法数(不计顺序)。
例如 N = 6 N = 6 N = 6 :分成互异部分的写法有 6 , 5 + 1 , 4 + 2 , 3 + 2 + 1 6,\ 5+1,\ 4+2,\ 3+2+1 6 , 5 + 1 , 4 + 2 , 3 + 2 + 1 ,偶数个的 2 2 2 种,奇数个的 2 2 2 种,系数为 0 0 0 。N = 5 N = 5 N = 5 :5 , 4 + 1 , 3 + 2 5,\ 4+1,\ 3+2 5 , 4 + 1 , 3 + 2 ,偶 2 2 2 奇 1 1 1 ,系数为 1 1 1 ,与定理一致。
于是定理等价于一个纯组合的命题:除了五边形数,偶分拆与奇分拆一样多 。要证明两类一样多,最好的办法是在它们之间建立一一对应。
Franklin 的对合
把一个互异分拆 λ 1 > λ 2 > ⋯ > λ m \lambda_1 > \lambda_2 > \cdots > \lambda_m λ 1 > λ 2 > ⋯ > λ m 画成 Ferrers 图 :第 i i i 行放 λ i \lambda_i λ i 个点,左端对齐。定义两个量:
s s s :底 ,即最小部分 λ m \lambda_m λ m ,也就是最后一行的点数;
σ \sigma σ :坡 ,即从第一行开始、每行恰好比上一行少 1 1 1 的最长连续行数,也就是右侧那条 45 ∘ 45^\circ 4 5 ∘ 斜边上的点数。
Franklin 定义了两种操作:
操作 A (s ≤ σ s \le \sigma s ≤ σ 时):拿走最后一行的 s s s 个点,在最上面 s s s 行的末尾各加一个点,也就是把底「立起来」贴到坡上。
操作 B (s > σ s > \sigma s > σ 时):把坡上的 σ \sigma σ 个点各拿走,作为新的一行放到最下面,也就是把坡「放倒」成新的底。
→ 7+6+5+3(4 个部分) 8+7+6(3 个部分)
图 1 操作 A:分拆 7+6+5+3 的底 s = 3(蓝),坡 σ = 3(红)。把底的 3 个点贴到坡上,得到 8+7+6,部分数由偶变奇。
两种操作都使部分的个数恰好改变 1 1 1 ,从而改变奇偶;而且只要能做,结果仍是互异分拆,并且操作 A 与操作 B 互为逆操作。验证要点:操作 A 之后,新的坡至少有 s s s 行,新的底大于 s s s ,所以接下来应做的恰好是操作 B,并且会把刚贴上的 s s s 个点原样取下。反之亦然。 这样,能做操作的分拆被两两配对,每一对恰好一偶一奇,在 e ( N ) − o ( N ) e(N) - o(N) e ( N ) − o ( N ) 中相互抵消。
哪些分拆配不上对
问题只出在底和坡共用一个点 的时候,也就是坡一直延伸到最后一行(σ = m \sigma = m σ = m ),右下角那个点既在底上又在坡上。
情形一 :s = σ = m s = \sigma = m s = σ = m 。按规则该做操作 A,但拿走底的同时也拿走了坡的最后一个点,剩下的 m − 1 m - 1 m − 1 行放不下 s = m s = m s = m 个点,操作失败。这时分拆是
m + ( m + 1 ) + ⋯ + ( 2 m − 1 ) = m ( 3 m − 1 ) 2 . m + (m+1) + \cdots + (2m-1) = \frac{m(3m-1)}{2}. m + ( m + 1 ) + ⋯ + ( 2 m − 1 ) = 2 m ( 3 m − 1 ) .
情形二 :s = σ + 1 s = \sigma + 1 s = σ + 1 且 σ = m \sigma = m σ = m 。按规则该做操作 B,但把坡放倒成新的一行(长度 m m m )后,原来的底只剩 s − 1 = m s - 1 = m s − 1 = m 个点,与新行一样长,不再是互异分拆,操作失败。这时分拆是
( m + 1 ) + ( m + 2 ) + ⋯ + 2 m = m ( 3 m + 1 ) 2 . (m+1) + (m+2) + \cdots + 2m = \frac{m(3m+1)}{2}. ( m + 1 ) + ( m + 2 ) + ⋯ + 2 m = 2 m ( 3 m + 1 ) .
其他情况下操作都能顺利完成。所以对每个 N N N :
如果 N N N 不是广义五边形数,所有分拆两两配对,e ( N ) − o ( N ) = 0 e(N) - o(N) = 0 e ( N ) − o ( N ) = 0 ;
如果 N = m ( 3 m ∓ 1 ) / 2 N = m(3m \mp 1)/2 N = m ( 3 m ∓ 1 ) /2 ,恰好剩下一个配不上对的分拆,它有 m m m 个部分,贡献 ( − 1 ) m (-1)^m ( − 1 ) m 。
而 m ( 3 m − 1 ) / 2 m(3m-1)/2 m ( 3 m − 1 ) /2 与 m ( 3 m + 1 ) / 2 m(3m+1)/2 m ( 3 m + 1 ) /2 正是 k ( 3 k − 1 ) / 2 k(3k-1)/2 k ( 3 k − 1 ) /2 在 k = m k = m k = m 与 k = − m k = -m k = − m 时的值,符号都是 ( − 1 ) m = ( − 1 ) k (-1)^m = (-1)^k ( − 1 ) m = ( − 1 ) k 。定理 1 得证。
一个意外的推论:快速计算分拆数
把 N N N 写成正整数之和(允许重复、不计顺序)的方法数记作 p ( N ) p(N) p ( N ) 。由于
∑ N ≥ 0 p ( N ) x N = ∏ n ≥ 1 1 1 − x n , \sum_{N\ge0} p(N)\,x^N = \prod_{n\ge1}\frac{1}{1-x^n}, N ≥ 0 ∑ p ( N ) x N = n ≥ 1 ∏ 1 − x n 1 ,
它恰好是五边形数定理左边的倒数。两者相乘等于 1 1 1 ,比较系数就得到:
推论 2(Euler 分拆数递推) 对 N ≥ 1 N \ge 1 N ≥ 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 ( N ) = p ( N − 1 ) + p ( N − 2 ) − p ( N − 5 ) − p ( N − 7 ) + p ( N − 12 ) + p ( N − 15 ) − ⋯ , 其中约定 p ( 0 ) = 1 p(0) = 1 p ( 0 ) = 1 ,p ( 负数 ) = 0 p(\text{负数}) = 0 p ( 负数 ) = 0 。
例如 p ( 10 ) = p ( 9 ) + p ( 8 ) − p ( 5 ) − p ( 3 ) = 30 + 22 − 7 − 3 = 42 p(10) = p(9) + p(8) - p(5) - p(3) = 30 + 22 - 7 - 3 = 42 p ( 10 ) = p ( 9 ) + p ( 8 ) − p ( 5 ) − p ( 3 ) = 30 + 22 − 7 − 3 = 42 。
1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, …
这个递推只需要大约 N \sqrt{N} N 项,用它计算 p ( N ) p(N) p ( N ) 远比逐个枚举快。20 世纪初,MacMahon 正是用这个递推手算出了 p ( 1 ) p(1) p ( 1 ) 到 p ( 200 ) p(200) p ( 200 ) 的表格,Hardy 和 Ramanujan 用它来检验他们的渐近公式
p ( N ) ∼ 1 4 N 3 e π 2 N / 3 . p(N) \sim \frac{1}{4N\sqrt3}\,e^{\pi\sqrt{2N/3}}. p ( N ) ∼ 4 N 3 1 e π 2 N /3 .
0, 1, 2, 5, 7, 12, 15, 22, 26, 35, 40, 51, 57, 70, 77, …