有关整数拆分

如果看到了下面的数列，就要保持警惕了！！！

1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, 6842, 8349, 10143, 12310, 14883, 17977, 21637, 26015, 31185, 37338, 44583, 53174, 63261, 75175, 89134, 105558, 124754, 147273, 173525

首先，是整数拆分的定义。

定义1 给定 $n$，求不同数组 $\displaystyle (a_{1},a_{2},…,a_{k})$ 的数目，符合下面的条件：

${\displaystyle a_{1}+a_{2}+…+a_{k}=n}$ （${\displaystyle k}$ 的大小不定）
${\displaystyle a_{1}\geq a_{2}\geq …\geq a_{k}>0}$
其他附加条件（例如限定“k是偶数”，或“${\displaystyle a_{i}}$ 不是 1 就是 2 ”等）

分割函数 $p(n)$ 是求符合以上第一、二个条件的数组数目。为了方便起见，我们首先讨论的是忽略条件 3 的情况。

引理1：
$$
\varphi(x) = \prod_{i=1}^\infty (1-x^i)
$$
引理2：设 $f(x) = \text{(将}x\text{分成偶数个不同正整数的方法数)} - \text{(将}x\text{分成奇数个不同正整数的方法数)}$ ，则 $f$ 的生成函数 $F(x)$ 就是：
$$
F(x) = \prod_{i=1}^\infty (1-x^i)
$$
定理1：
$$
\varphi(x) = \prod {i=1}^\infty (1-x^i) = \sum{k=-\infty}^\infty (-1)^k x^{\frac{k(3k-1)}{2}}
$$
证明：根据引理2 的组合意义进行证明。考虑划分的 Ferrers 图，我们构造一种配对方案，将大部分 Ferrers 图两两配对（数学上又称这种方法为构造一个 involution，即满足 $f(f(x)) = x$ 的函数）。详见 wiki (https://en.wikipedia.org/wiki/Pentagonal_number_theorem)。

一些性质：

分拆成若干奇数的方案数 = 分拆成若干互不相同的数的方案数
Ferrers 图的转置通常可以构造出新的分拆，成为分拆的共轭。共轭为自身的分拆如何计数呢？沿着主对角线看去，一层层拆开，那么共轭为自身的分拆个数就是拆分成互不相同的奇数的方案数，两者一一对应。

另一个有趣发现：因数和函数 $\sigma(n)$ 也可以和拆分数一样递推，只是规定考虑 $\sigma(n)$ 时，如果后面的项里有 $\sigma(0)$ ，就视为 $n$ ，而不是 1 。