五边形数 笔记

[博客观赏效果更佳]
github
cnblogs
近日，一国外小哥学习了这个定理，竟然能预处理出整数划分的方案数！快跟小编来看看吧

这个小哥学习的定理，就是小编（我）接下来要讲的五边形数定理

好的，让我们一起来看看这个定理吧

五边形数是啥

百度百科

用图来讲，就是若干个点，排成若干个五边形，需要多少个点。

百度百科上有一个很清楚的图：

它的通项公式为 $a_n=\dfrac{n(3n-1)}{2}$an​=2n(3n−1)​，前面几项是 $0, 1, 5, 12, 22, 35, 51, 70, 92, 117, 145, 176, 210...$0,1,5,12,22,35,51,70,92,117,145,176,210...。你可以在 OEIS 上找到它，是序列 A000326

我们要研究的是 广义五边形数，是这样一个数列：$p=a_0,a_{1},a_{-1},a_{2},a_{-2}...$p=a0​,a1​,a−1​,a2​,a−2​...

其中，如果 $p$p 的下标是负数，照样代入到上面的通项公式里算即可。容易证明，当 $n<0$n<0 时，$p_n$pn​ 也是正的。前面几项是 $0, 1, 2, 5, 7, 12, 15, 22, 26, 35, 40, 51, 57, 70, 77, 92, 100, 117...$0,1,2,5,7,12,15,22,26,35,40,51,57,70,77,92,100,117...，同样可以在 OEIS 上找到它是 A001318

它能干啥

欧拉函数（五边形数）

（为了和欧拉数论函数区别开来，这里给它起名叫欧拉函数-五边形数(*/ω＼*)

是这样一个函数：$\varphi(x)=(1-x)(1-x^2)(1-x^3)(1-x^4)...(1-x^\infin)=\prod\limits_{i=1}^{\infin} (1-x^i)$φ(x)=(1−x)(1−x2)(1−x3)(1−x4)...(1−x∞)=i=1∏∞​(1−xi)

这东西有一个很神奇的性质。如果你闲的没事，可以暴力拆开它，发现它等于

$x^0-x^1-x^2+x^5+x^7-x^{12}-x^{15}+x^{22}+x^{26}...=\sum\limits_{i=1}^{\infin} (-1)^{(i+1)/2} x^{p_i}$x0−x1−x2+x5+x7−x12−x15+x22+x26...=i=1∑∞​(−1)(i+1)/2xpi​

系数：一个正，两个负，两个正，两个负，两个正，两个负…

指数：广义五边形数

与整数划分问题的联系

然后我们可以来解决整数划分问题。设 $P(n)$P(n) 表示将 $n$n 分成若干个整数的无序方案（即，$a+b$a+b 和 $b+a$b+a 只算一次），同一个数可以用很多次。

比如，$P(4)=5$P(4)=5，因为 $4$4

$=1+1+1+1$=1+1+1+1

$=1+1+2$=1+1+2

$=1+3$=1+3

$=2+2$=2+2

$=4$=4

特殊地，$P(0)=1$P(0)=1

我们求出 $P(n)$P(n) 的生成函数 $f(x)=\sum\limits_{n=0}^{\infin} P(n)x^n$f(x)=n=0∑∞​P(n)xn

给它换个定义：我们要选出若干个（可以是 $0$0 个） $1$1，若干个 $2$2，若干个 $3$3…使得选出来的所有数和为 $n$n。

这样就好考虑了。看这个式子：

$(1+x+x^2+x^3...)(1+x^2+(x^2)^2+(x^2)^3...)(1+x^3+(x^3)^2+(x^3)^3...)...$(1+x+x2+x3...)(1+x2+(x2)2+(x2)3...)(1+x3+(x3)2+(x3)3...)...

第一个因式表示我们能随便选择用多少个 $x^1$x1

第二个因式表示我们能随便选择用多少个 $x^2$x2

…

乘起来之后，考虑 $x^n$xn 的系数，你会发现它就是 $P(n)$P(n)！是不是特别巧妙φ(>ω<*)

于是 $f(x)=(1+x+x^2+x^3...)(1+x^2+(x^2)^2+(x^2)^3...)(1+x^3+(x^3)^2+(x^3)^3...)...=\prod\limits_{n=1}^{\infin} \sum\limits_{i=0}^{\infin} (x^n)^i$f(x)=(1+x+x2+x3...)(1+x2+(x2)2+(x2)3...)(1+x3+(x3)2+(x3)3...)...=n=1∏∞​i=0∑∞​(xn)i

然后我们用等比数列求和公式化一下，得到：

$f(x)=\prod\limits_{n=1}^{\infin} \dfrac{1}{1-x^n}$f(x)=n=1∏∞​1−xn1​

我们发现它就是欧拉函数-五边形数的倒数(/≧▽≦/)！

即

$\varphi(x)f(x)=1$φ(x)f(x)=1

也就是

$(1-x-x^2+x^5+x^7-x^{12}-x^{15}...)(\sum\limits_{n=0}^{\infin} P(n)x^n)=1$(1−x−x2+x5+x7−x12−x15...)(n=0∑∞​P(n)xn)=1

观察其中 $x^n$xn 项的系数（分别考虑左边和右边的括号出的是几次项），容易发现这个系数应该是 $P(n)-P(n-1)-P(n-2)+P(n-5)+P(n-7)...$P(n)−P(n−1)−P(n−2)+P(n−5)+P(n−7)...

$n=0$n=0 时，这个式子显然为 $1$1。那么 $n>0$n>0 时， $x^n$xn 乘以它的系数的和就得是 $0$0 了。

然后我们发现等式右边是 $1$1。并且原式为恒等式，所以 $x$x 取任何值都成立。为了让 $x$x 取任何值时等式都成立，对于 $n>0$n>0 时，$P(n)-P(n-1)-P(n-2)$P(n)−P(n−1)−P(n−2) 这个可怜的等式只好取 $0$0 了。

然后就得到了：

$P(n)-P(n-1)-P(n-2)+P(n-5)+P(n-7)-P(n-12)-P(n-15)...=0$P(n)−P(n−1)−P(n−2)+P(n−5)+P(n−7)−P(n−12)−P(n−15)...=0

于是 $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)...

然后 $\le n$≤n 的五边形数是 $\sqrt{n}$n​ 级别的（注意到五边形数的通项公式是二次的）

于是我们可以递推出 $P(n)$P(n)，是 $O(n\sqrt{n})$O(nn​) 的，是不是很厉害呢(✪ω✪)

好了，以上就是这个定理的全部内容了，喜欢记得收藏起来哟