五边形数定理
2026-05-14
前置知识
引入
考虑一个问题,如果有体积为 1,2,⋯,n 的物品,数量无限,求装满容量 n 的方案数。
显然考虑生成函数:
P(x)=(1−x1)(1−x21)(1−x31)⋯=i=1∏∞1−xi1
这样子无法处理,将分母乘到左边:
P(x)⋅i=0∏∞(1−xi)=1
做到这一步,我们需要考虑 ∏i=0∞(1−xi) 能展开出什么,也就跟五边形数定理有关了。
五边形数
考虑一个边长为 n 的五边形,内嵌边长为 n−1,n−2,⋯ 的五边形,容易看出,有 pn=pn−1+3n−2,进而有:pn=23n2−n,这就是五边形数的通项公式。
广义五边形数
我们已经考虑过 n∈N∗ 的情况了,如果将其扩展到整数域,会不会有什么美妙的性质呢?
显然是有的,将 n 按照 0,1,−1,2,−2,⋯ 的顺序带入,便能得到广义五边形数的数列。
五边形数定理
欧拉发现:
i=1∏∞(1−xi)=k=−∞∑∞(−1)kx23k2−k=1−x−x2+x5+x7−x12−x15+⋯
证明笔者也不会,不过有个 visit_world 大佬的链接。
应用
回归到刚才的问题,我们实际要求的是 xn 项的系数,考虑将五边形数定理带入,将 P(x) 乘到右边,得到:
Pn=Pn−1+Pn−2−Pn−5−Pn−7+⋯
由于五边形数是 O(n2) 的级别,所以只需要查表 O(n) 个转移即可。
