文章目录
一、正整数拆分总结二、正整数拆分示例参考博客 :
【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )【组合数学】生成函数 ( 线性性质 | 乘积性质 )【组合数学】生成函数 ( 移位性质 )【组合数学】生成函数 ( 求和性质 )【组合数学】生成函数 ( 换元性质 | 求导性质 | 积分性质 )【组合数学】生成函数 ( 性质总结 | 重要的生成函数 ) ★【组合数学】生成函数 ( 生成函数示例 | 给定通项公式求生成函数 | 给定生成函数求通项公式 )【组合数学】生成函数 ( 生成函数应用场景 | 使用生成函数求解递推方程 )【组合数学】生成函数 ( 使用生成函数求解多重集 r 组合数 )【组合数学】生成函数 ( 使用生成函数求解不定方程解个数 )【组合数学】生成函数 ( 使用生成函数求解不定方程解个数示例 )【组合数学】生成函数 ( 使用生成函数求解不定方程解个数示例 2 | 扩展到整数解 )【组合数学】生成函数 ( 正整数拆分 | 无序 | 有序 | 允许重复 | 不允许重复 | 无序不重复拆分 | 无序重复拆分 )
一、正整数拆分总结
正整数拆分 , 需要先给出 拆分后出的数 ,
每个被拆分出的数 , 都可以有一个对应的 生成函数分项 ,
每个 生成函数的项的 yyy 次幂项个数 , 与该 被拆分的数的取值个数种类 一样 ,
如 : 某个被拆分出来的数 a1a_1a1 , 其 可以取值 0,1,20,1,20,1,2 三个值 , 那么对应的 生成函数的项的 yyy 次幂项个数 有 333 个值 , 为 (ya1)0+(ya1)1+(ya1)2(y^{a_1})^0 + (y^{a_1})^1 + (y^{a_1})^2(ya1)0+(ya1)1+(ya1)2 ,
该生成函数项中的 底是 y被拆分的数y^{被拆分的数}y被拆分的数 , 次幂数就是 该正整数 可能的取值 , 项中的 yyy 次幂分项个数 就是 该 正整数 取值的种类个数 ;
正整数拆分 , 允许重复 与 不允许重复 , 区别是 被拆分的整数 的出现次数不同 ,
如果 不允许重复 , 该被拆分的 正整数 只能出现 0,10,10,1 次 ;如果 允许重复 , 那么该正整数可以 出现 0,1,2,⋯0,1,2, \cdots0,1,2,⋯ 无限次 ;
正整数拆分生成函数 :
生成函数项个数 :就是 拆分后的正整数种类数 ; 可拆分成 2,4,82,4,82,4,8 三个数 , 那么是三个生成函数项相乘 ;生成函数项中的 yyy 次幂个数 :对应 拆分后的正整数 取值种类个数 ; 某个拆分后的整数可能出现 0,10,10,1 次 , 代表取值种类数是 222 ;生成函数项中的 yyy 次幂底 :y拆分后的正整数y^{拆分后的正整数}y拆分后的正整数 , 某个拆分后正整数是 555 , 那么底就是 y5y^5y5 ;生成函数项中的 yyy 次幂 :拆分后的正整数的 取值个数 ; 某个拆分后正整数是 555 , 那么底就是 y5y^5y5 , 出现一次 , 对应的项是 (y5)1(y^5)^1(y5)1
二、正整数拆分示例
证明任何 正整数 二进制表示是唯一的 ;
上述问题可以等价为 , 将 任意正整数 , 都可以 拆解成 222 的次幂之和 , 并且 不允许有重复的元素 ;
222 的次幂情况 : 20,21,22,23,⋯2^0, 2^1, 2^2, 2^3 , \cdots20,21,22,23,⋯
由于不允许有重复 , 因此每个 222 次幂 的个数 , 只能是 0,10,10,1 两种情况 ;
按照正整数拆分的模型 , 写出一个生成函数 :
202^020 对应的生成函数项 : 底是 y20=yy^{2^0} = yy20=y , 取值 0,10, 10,1 , 则对应的 生成函数项是 y0+y1=1+yy^0 + y^1 = 1+ yy0+y1=1+y
212^121 对应的生成函数项 : 底是 y21=y2y^{2^1} = y^2y21=y2 , 取值 0,10, 10,1 , 则对应的生成函数项是 (y2)0+(y2)1=1+y2(y^2)^0 + (y^2)^1 = 1+ y^2(y2)0+(y2)1=1+y2
222^222 对应的生成函数项 : 底是 y22=y4y^{2^2} = y^4y22=y4 , 取值 0,10, 10,1 , 则对应的生成函数项是 (y4)0+(y4)1=1+y4(y^4)^0 + (y^4)^1 = 1+ y^4(y4)0+(y4)1=1+y4
232^323 对应的生成函数项 : 底是 y23=y8y^{2^3} = y^8y23=y8 , 取值 0,10, 10,1 , 则对应的生成函数项是 (y8)0+(y8)1=1+y8(y^8)^0 + (y^8)^1 = 1+ y^8(y8)0+(y8)1=1+y8
⋮\vdots⋮
完整的生成函数是 :
G(x)=(1+y)(1+y2)(1+y4)(1+y8)⋯G(x) = (1+ y)(1+ y^2)(1+ y^4)(1+ y^8)\cdotsG(x)=(1+y)(1+y2)(1+y4)(1+y8)⋯
分解上述每个 生成函数项 :
1+y=1−y21−y1+ y= \cfrac{1-y^2}{1-y}1+y=1−y1−y2
1+y2=1−y41−y21+ y^2= \cfrac{1-y^4}{1-y^2}1+y2=1−y21−y4
1+y4=1−y81−y41+ y^4= \cfrac{1-y^8}{1-y^4}1+y4=1−y41−y8
将上面三个等式代入生成函数 G(x)G(x)G(x) 中 ,
G(x)=1−y21−y⋅1−y41−y2⋅1−y81−y4⋯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−y1−y2⋅1−y21−y4⋅1−y41−y8⋯
=11−y\ \ \ \ \ \ \ \ \ \ = \cfrac{1}{1-y}=1−y1
=1+y+y2+y3+⋯\ \ \ \ \ \ \ \ \ \ = 1 + y + y^2 + y^3 + \cdots=1+y+y2+y3+⋯
上述生成函数是 1n1^n1n 通项公式 对应的数列的 生成函数 ;
上述生成函数展开后 , 每项前的系数都为 111 , 说明只有一种方案 ;
