分拆数

分拆：将自然数 写成递降正整数和的表示。

和式中每个正整数称为一个部分。

分拆数：。自然数 的分拆方法数。

自 开始的分拆数：

n	0	1	2	3	4	5	6	7	8
	1	1	2	3	5	7	11	15	22

k 部分拆数

将 分成恰有 个部分的分拆，称为 部分拆数，记作 。

显然， 部分拆数 同时也是下面方程的解数：

如果这个方程里面恰有 个部分非 0，则恰有 个解。因此有和式：

相邻两个和式作差，得：

如果列出表格，每个格里的数，等于左上方的数，加上该格向上方数，所在列数个格子中的数。

k	0	1	2	3	4	5	6	7	8
	1	0	0	0	0	0	0	0	0
	0	1	0	0	0	0	0	0	0
	0	1	1	0	0	0	0	0	0
	0	1	1	1	0	0	0	0	0
	0	1	2	1	1	0	0	0	0
	0	1	2	2	1	1	0	0	0
	0	1	3	3	2	1	1	0	0
	0	1	3	4	3	2	1	1	0
	0	1	4	5	5	3	2	1	1

例题

生成函数

由等比数列求和公式，有：

对于 部分拆数，生成函数稍微复杂。具体写出如下：

Ferrers 图

Ferrers 图：将分拆的每个部分用点组成的行表示。每行点的个数为这个部分的大小。

根据分拆的定义，Ferrers 图中不同的行按照递减的次序排放。最长行在最上面。

例如：分拆 的 Ferrers 图。

将一个 Ferrers 图沿着对角线翻转，得到的新 Ferrers 图称为原图的共轭，新分拆称为原分拆的共轭。显然，共轭是对称的关系。

例如上述分拆 的共轭是分拆 。

最大 分拆数：自然数 的最大部分为 的分拆个数。

根据共轭的定义，有显然结论：

最大 分拆数与 部分拆数相同，均为 。

互异分拆数

互异分拆数：。自然数 的各部分互不相同的分拆方法数。（Different）

n	0	1	2	3	4	5	6	7	8
	1	1	1	2	2	3	4	5	6

同样地，定义互异 部分拆数 ，表示最大拆出 个部分的互异分拆，是这个方程的解数：

完全同上，也是这个方程的解数：

这里与上面不同的是，由于互异，新方程中至多只有一个部分为零。有不变的结论：恰有 个部分非 ，则恰有 个解，这里 只取 或 。因此直接得到递推：

同样像组合数一样列出表格，每个格里的数，等于该格前一列上数，所在列数个格子中的数，加上该格向上方数，所在列数个格子中的数。

k	0	1	2	3	4	5	6	7	8
	1	0	0	0	0	0	0	0	0
	0	1	0	0	0	0	0	0	0
	0	1	0	0	0	0	0	0	0
	0	1	1	0	0	0	0	0	0
	0	1	1	0	0	0	0	0	0
	0	1	2	0	0	0	0	0	0
	0	1	2	1	0	0	0	0	0
	0	1	3	1	0	0	0	0	0
	0	1	3	2	0	0	0	0	0

例题

奇分拆数

奇分拆数：。自然数 的各部分都是奇数的分拆方法数。（Odd）

有一个显然的等式：

最左边是互异分拆数的生成函数，最右边是奇分拆数的生成函数。两者对应系数相同，因此，奇分拆数和互异分拆数相同：

但显然 部奇分拆数和互异 部分拆数不是一个概念，这里就不列出了。

再引入两个概念：

互异偶分拆数：。自然数 的部分数为偶数的互异分拆方法数。（Even）

互异奇分拆数：。自然数 的部分数为奇数的互异分拆方法数。（Odd）

因此有：

同样也有相应的 部概念。由于过于复杂，不再列出。

五边形数定理

单独观察分拆数的生成函数的分母部分：

将这部分展开，可以想到互异分拆，与互异分拆拆出的部分数奇偶性有关。

具体地，互异偶部分拆在展开式中被正向计数，互异奇部分拆在展开式中被负向计数。因此展开式中各项系数为两方法数之差。即：

接下来说明，多数情况下，上述两方法数相等，在展开式中系数为 ；仅在少数位置，两方法数相差 或 。

这里可以借助构造对应的办法。

画出每个互异分拆的 Ferrers 图。最后一行称为这个图的底，底上点的个数记为 （Bottom）；连接最上面一行的最后一个点与图中某点的最长 度角线段，称为这个图的坡，坡上点的个数记为 （Slide）。

要想在互异偶部分拆与互异奇部分拆之间构造对应，就要定义变换，在保证互异条件不变的前提下，使得行数改变 ：

变换 A：当 小于等于 的时候，就将底移到右边，成为一个新坡。

变换 B：当 大于 的时候，就将坡移到下边，成为一个新底。

这两个变换，对于多数时候的 ，恰有一个变换可以进行，就在互异偶部分拆与互异奇部分拆之间构造了一个一一对应。已经构造了一一对应的两部分分拆个数相等，因此这时展开式中第 项系数为 。

变换 A 不能进行的条件：底与坡有一个公共点，且 。这种情形只发生于：

这时，展开式中第 项为：

变换 B 不能进行的条件：底与坡有一个公共点，且 。这种情形只发生于：

这时，展开式中第 项为：

至此，我们就证明了：

将这个式子整理，对比两边各项系数，就得到递推式。

这个递推式有无限项，但是如果规定负数的分拆数是 （ 的分拆数已经定义为 ），那么就简化为了有限项。

例题