五边形数 笔记

近日，一国外小哥学习了这个定理，竟然能预处理出整数划分的方案数！快跟小编来看看吧

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

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

五边形数是啥

百度百科

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

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

它的通项公式为 $a_n=\dfrac{n(3n-1)}{2}$，前面几项是 $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$ 的下标是负数，照样代入到上面的通项公式里算即可。容易证明，当 $n<0$ 时，$p_n$ 也是正的。前面几项是 $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^inf)=\prod\limits_{i=1}^{inf} (1-x^i)$

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

$x^0-x^1-x^2+x^5+x^7-x^{12}-x^{15}+x^{22}+x^{26}…=\sum\limits_{i=1}^{inf} (-1)^{(i+1)/2} x^{p_i}$

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

指数：广义五边形数

与整数划分问题的联系

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

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

$=1+1+1+1$

$=1+1+2$

$=1+3$

$=2+2$

$=4$

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

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

给它换个定义：我们要选出若干个（可以是 $0$ 个） $1$，若干个 $2$，若干个 $3$…使得选出来的所有数和为 $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…)…$

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

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

…

乘起来之后，考虑 $x^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}^{inf} \sum\limits_{i=0}^{inf} (x^n)^i$

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

$f(x)=\prod\limits_{n=1}^{inf} \dfrac{1}{1-x^n}$

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

即

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

也就是

$(1-x-x^2+x^5+x^7-x^{12}-x^{15}…)(\sum\limits_{n=0}^{inf} P(n)x^n)=1$

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

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

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

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

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

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