【学习笔记】五边形数

imily's notebook

2021-04-20

小清新生成函数，vp 做到题来学一发

五边形数

$f_1 = 1, f_n = f_{n - 1} + 3n - 2$

$f_n = \frac{n(3n - 1)}{2}$

前几项：$0, 1, 2, 5, 7, 12, 15, 22, 26, 35, 40, 51, 57, 70, 77, 92, 100, 117, 126, 145, 155, \cdots$

$n$ 可以非正。

$\phi(x) = \prod\limits_{i = 1}^{+\infty} (1 - x^i)$

$\phi(x) = 1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} \cdots$

$= 1 + \sum\limits_{i = 1}^{+\infty} (-1)^i ( x^{\frac{i(3i - 1)}{2}} + x^{\frac{-i(-3i - 1)}{2}} )$

定义整数划分为将整数 $n$ 划分为若干正整数之和。

生成函数显然为 $G(x) = \prod \limits_{i = 1}^{+\infty} \frac{1}{1 - x^i}$

$G \times \phi = 1$

就是对 $\phi$ 求逆啦。暴力展开，得：

$G(1) = 1$, $G(n) = G(n - 1) + G(n - 2) - G(n - 5) - G(n - 7) + \cdots$

直接做，枚举五边形数，$O(n \sqrt{n})$