分拆数
分拆:将自然数
和式中每个正整数称为一个部分。
分拆数:
自
n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|---|
1 | 1 | 2 | 3 | 5 | 7 | 11 | 15 | 22 |
k 部分拆数
将
显然,
如果这个方程里面恰有
相邻两个和式作差,得:
如果列出表格,每个格里的数,等于左上方的数,加上该格向上方数,所在列数个格子中的数。
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 |
例题
计算 k 部分拆数
计算
观察表格与递推式,按列更新对于存储更有利。不难写出程序:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|
生成函数
由等比数列求和公式,有:
对于
Ferrers 图
Ferrers 图:将分拆的每个部分用点组成的行表示。每行点的个数为这个部分的大小。
根据分拆的定义,Ferrers 图中不同的行按照递减的次序排放。最长行在最上面。
例如:分拆
将一个 Ferrers 图沿着对角线翻转,得到的新 Ferrers 图称为原图的共轭,新分拆称为原分拆的共轭。显然,共轭是对称的关系。
例如上述分拆
最大
根据共轭的定义,有显然结论:
最大
互异分拆数
互异分拆数:
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 |
例题
计算互异分拆数
计算互异分拆数
观察表格与递推式,按列更新对于存储更有利。代码中将后一位缩减了空间,仅保留相邻两项。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
|
奇分拆数
奇分拆数:
有一个显然的等式:
最左边是互异分拆数的生成函数,最右边是奇分拆数的生成函数。两者对应系数相同,因此,奇分拆数和互异分拆数相同:
但显然
再引入两个概念:
互异偶分拆数:
互异奇分拆数:
因此有:
同样也有相应的
五边形数定理
单独观察分拆数的生成函数的分母部分:
将这部分展开,可以想到互异分拆,与互异分拆拆出的部分数奇偶性有关。
具体地,互异偶部分拆在展开式中被正向计数,互异奇部分拆在展开式中被负向计数。因此展开式中各项系数为两方法数之差。即:
接下来说明,多数情况下,上述两方法数相等,在展开式中系数为
这里可以借助构造对应的办法。
画出每个互异分拆的 Ferrers 图。最后一行称为这个图的底,底上点的个数记为
要想在互异偶部分拆与互异奇部分拆之间构造对应,就要定义变换,在保证互异条件不变的前提下,使得行数改变
变换 A:当
变换 B:当
这两个变换,对于多数时候的
变换 A 不能进行的条件:底与坡有一个公共点,且
这时,展开式中第
变换 B 不能进行的条件:底与坡有一个公共点,且
这时,展开式中第
至此,我们就证明了:
将这个式子整理,对比两边各项系数,就得到递推式。
这个递推式有无限项,但是如果规定负数的分拆数是
例题
计算分拆数
计算分拆数
采用五边形数定理的方法。有代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
|
本页面最近更新:2023/2/18 07:57:07,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:Early0v0, Great-designer, Ir1d, ksyx, myeeye, YOYO-UIAT
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用