文章目录
一、正整数拆分总结
二、正整数拆分示例
参考博客 :
【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )
【组合数学】生成函数 ( 线性性质 | 乘积性质 )
【组合数学】生成函数 ( 移位性质 )
【组合数学】生成函数 ( 求和性质 )
【组合数学】生成函数 ( 换元性质 | 求导性质 | 积分性质 )
【组合数学】生成函数 ( 性质总结 | 重要的生成函数 ) ★
【组合数学】生成函数 ( 生成函数示例 | 给定通项公式求生成函数 | 给定生成函数求通项公式 )
【组合数学】生成函数 ( 生成函数应用场景 | 使用生成函数求解递推方程 )
【组合数学】生成函数 ( 使用生成函数求解多重集 r 组合数 )
【组合数学】生成函数 ( 使用生成函数求解不定方程解个数 )
【组合数学】生成函数 ( 使用生成函数求解不定方程解个数示例 )
【组合数学】生成函数 ( 使用生成函数求解不定方程解个数示例 2 | 扩展到整数解 )
【组合数学】生成函数 ( 正整数拆分 | 无序 | 有序 | 允许重复 | 不允许重复 | 无序不重复拆分 | 无序重复拆分 )
一、正整数拆分总结
正整数拆分 , 需要先给出 拆分后出的数 ,
每个被拆分出的数 , 都可以有一个对应的 生成函数分项 ,
每个 生成函数的项的 y yy 次幂项个数 , 与该 被拆分的数的取值个数种类 一样 ,
如 : 某个被拆分出来的数 a 1 a_1a
1
, 其 可以取值 0 , 1 , 2 0,1,20,1,2 三个值 , 那么对应的 生成函数的项的 y yy 次幂项个数 有 3 33 个值 , 为 ( y a 1 ) 0 + ( y a 1 ) 1 + ( y a 1 ) 2 (y^{a_1})^0 + (y^{a_1})^1 + (y^{a_1})^2(y
a
1
)
0
+(y
a
1
)
1
+(y
a
1
)
2
,
该生成函数项中的 底是 y 被 拆 分 的 数 y^{被拆分的数}y
被拆分的数
, 次幂数就是 该正整数 可能的取值 , 项中的 y yy 次幂分项个数 就是 该 正整数 取值的种类个数 ;
正整数拆分 , 允许重复 与 不允许重复 , 区别是 被拆分的整数 的出现次数不同 ,
如果 不允许重复 , 该被拆分的 正整数 只能出现 0 , 1 0,10,1 次 ;
如果 允许重复 , 那么该正整数可以 出现 0 , 1 , 2 , ⋯ 0,1,2, \cdots0,1,2,⋯ 无限次 ;
正整数拆分生成函数 :
生成函数项个数 : 就是 拆分后的正整数种类数 ; 可拆分成 2 , 4 , 8 2,4,82,4,8 三个数 , 那么是三个生成函数项相乘 ;
生成函数项中的 y yy 次幂个数 : 对应 拆分后的正整数 取值种类个数 ; 某个拆分后的整数可能出现 0 , 1 0,10,1 次 , 代表取值种类数是 2 22 ;
生成函数项中的 y yy 次幂底 : y 拆 分 后 的 正 整 数 y^{拆分后的正整数}y
拆分后的正整数
, 某个拆分后正整数是 5 55 , 那么底就是 y 5 y^5y
5
;
生成函数项中的 y yy 次幂 : 拆分后的正整数的 取值个数 ; 某个拆分后正整数是 5 55 , 那么底就是 y 5 y^5y
5
, 出现一次 , 对应的项是 ( y 5 ) 1 (y^5)^1(y
5
)
1
二、正整数拆分示例
证明任何 正整数 二进制表示是唯一的 ;
上述问题可以等价为 , 将 任意正整数 , 都可以 拆解成 2 22 的次幂之和 , 并且 不允许有重复的元素 ;
2 22 的次幂情况 : 2 0 , 2 1 , 2 2 , 2 3 , ⋯ 2^0, 2^1, 2^2, 2^3 , \cdots2
0
,2
1
,2
2
,2
3
,⋯
由于不允许有重复 , 因此每个 2 22 次幂 的个数 , 只能是 0 , 1 0,10,1 两种情况 ;
按照正整数拆分的模型 , 写出一个生成函数 :
2 0 2^02
0
对应的生成函数项 : 底是 y 2 0 = y y^{2^0} = yy
2
0
=y , 取值 0 , 1 0, 10,1 , 则对应的 生成函数项是 y 0 + y 1 = 1 + y y^0 + y^1 = 1+ yy
0
+y
1
=1+y
2 1 2^12
1
对应的生成函数项 : 底是 y 2 1 = y 2 y^{2^1} = y^2y
2
1
=y
2
, 取值 0 , 1 0, 10,1 , 则对应的生成函数项是 ( y 2 ) 0 + ( y 2 ) 1 = 1 + y 2 (y^2)^0 + (y^2)^1 = 1+ y^2(y
2
)
0
+(y
2
)
1
=1+y
2
2 2 2^22
2
对应的生成函数项 : 底是 y 2 2 = y 4 y^{2^2} = y^4y
2
2
=y
4
, 取值 0 , 1 0, 10,1 , 则对应的生成函数项是 ( y 4 ) 0 + ( y 4 ) 1 = 1 + y 4 (y^4)^0 + (y^4)^1 = 1+ y^4(y
4
)
0
+(y
4
)
1
=1+y
4
2 3 2^32
3
对应的生成函数项 : 底是 y 2 3 = y 8 y^{2^3} = y^8y
2
3
=y
8
, 取值 0 , 1 0, 10,1 , 则对应的生成函数项是 ( y 8 ) 0 + ( y 8 ) 1 = 1 + y 8 (y^8)^0 + (y^8)^1 = 1+ y^8(y
8
)
0
+(y
8
)
1
=1+y
8
⋮ \vdots⋮
完整的生成函数是 :
G ( x ) = ( 1 + y ) ( 1 + y 2 ) ( 1 + y 4 ) ( 1 + y 8 ) ⋯ G(x) = (1+ y)(1+ y^2)(1+ y^4)(1+ y^8)\cdotsG(x)=(1+y)(1+y
2
)(1+y
4
)(1+y
8
)⋯
分解上述每个 生成函数项 :
1 + y = 1 − y 2 1 − y 1+ y= \cfrac{1-y^2}{1-y}1+y=
1−y
1−y
2
1 + y 2 = 1 − y 4 1 − y 2 1+ y^2= \cfrac{1-y^4}{1-y^2}1+y
2
=
1−y
2
1−y
4
1 + y 4 = 1 − y 8 1 − y 4 1+ y^4= \cfrac{1-y^8}{1-y^4}1+y
4
=
1−y
4
1−y
8
将上面三个等式代入生成函数 G ( x ) G(x)G(x) 中 ,
G ( x ) = 1 − y 2 1 − y ⋅ 1 − y 4 1 − y 2 ⋅ 1 − y 8 1 − y 4 ⋯ G(x) = \cfrac{1-y^2}{1-y} \cdot \cfrac{1-y^4}{1-y^2} \cdot \cfrac{1-y^8}{1-y^4} \cdotsG(x)=
1−y
1−y
2
⋅
1−y
2
1−y
4
⋅
1−y
4
1−y
8
⋯
= 1 1 − y \ \ \ \ \ \ \ \ \ \ = \cfrac{1}{1-y} =
1−y
1
= 1 + y + y 2 + y 3 + ⋯ \ \ \ \ \ \ \ \ \ \ = 1 + y + y^2 + y^3 + \cdots =1+y+y
2
+y
3
+⋯
上述生成函数是 1 n 1^n1
n
通项公式 对应的数列的 生成函数 ;
上述生成函数展开后 , 每项前的系数都为 1 11 , 说明只有一种方案 ;
