【组合数学】生成函数 ( 正整数拆分 | 无序不重复拆分示例 )

文章目录

一、正整数拆分总结
二、正整数拆分示例

参考博客 :

【组合数学】生成函数简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )
【组合数学】生成函数 ( 线性性质 | 乘积性质 )
【组合数学】生成函数 ( 移位性质 )
【组合数学】生成函数 ( 求和性质 )
【组合数学】生成函数 ( 换元性质 | 求导性质 | 积分性质 )
【组合数学】生成函数 ( 性质总结 | 重要的生成函数 ) ★
【组合数学】生成函数 ( 生成函数示例 | 给定通项公式求生成函数 | 给定生成函数求通项公式 )
【组合数学】生成函数 ( 生成函数应用场景 | 使用生成函数求解递推方程 )
【组合数学】生成函数 ( 使用生成函数求解多重集 r 组合数 )
【组合数学】生成函数 ( 使用生成函数求解不定方程解个数 )
【组合数学】生成函数 ( 使用生成函数求解不定方程解个数示例 )
【组合数学】生成函数 ( 使用生成函数求解不定方程解个数示例 2 | 扩展到整数解 )
【组合数学】生成函数 ( 正整数拆分 | 无序 | 有序 | 允许重复 | 不允许重复 | 无序不重复拆分 | 无序重复拆分 )

一、正整数拆分总结

正整数拆分 , 需要先给出拆分后出的数 ,

每个被拆分出的数 , 都可以有一个对应的生成函数分项 ,

每个生成函数的项的

次幂项个数 , 与该被拆分的数的取值个数种类一样 ,

如 : 某个被拆分出来的数

a_1

, 其可以取值

0,1,2

三个值 , 那么对应的生成函数的项的

次幂项个数有

个值 , 为

(y^{a_1})^0 (y^{a_1})^1 (y^{a_1})^2

该生成函数项中的底是

y^{被拆分的数}

, 次幂数就是该正整数可能的取值 , 项中的

次幂分项个数就是该正整数取值的种类个数 ;

正整数拆分 , 允许重复与不允许重复 , 区别是被拆分的整数的出现次数不同 ,

如果不允许重复 , 该被拆分的正整数只能出现

0,1

次 ;

如果允许重复 , 那么该正整数可以出现

0,1,2, cdots

无限次 ;

正整数拆分生成函数 :

生成函数项个数 : 就是拆分后的正整数种类数 ; 可拆分成

2,4,8

三个数 , 那么是三个生成函数项相乘 ;

生成函数项中的

次幂个数 : 对应拆分后的正整数取值种类个数 ; 某个拆分后的整数可能出现

0,1

次 , 代表取值种类数是

;

生成函数项中的

次幂底 :

y^{拆分后的正整数}

, 某个拆分后正整数是

, 那么底就是

y^5

;

生成函数项中的

次幂 : 拆分后的正整数的取值个数 ; 某个拆分后正整数是

, 那么底就是

y^5

, 出现一次 , 对应的项是

(y^5)^1

二、正整数拆分示例

证明任何正整数二进制表示是唯一的 ;

上述问题可以等价为 , 将任意正整数 , 都可以拆解成

的次幂之和 , 并且不允许有重复的元素 ;

的次幂情况 :

2^0, 2^1, 2^2, 2^3 , cdots

由于不允许有重复 , 因此每个

次幂的个数 , 只能是

0,1

两种情况 ;

按照正整数拆分的模型 , 写出一个生成函数 :

2^0

对应的生成函数项 : 底是

y^{2^0} = y

, 取值

0, 1

, 则对应的生成函数项是

y^0 y^1 = 1 y

2^1

对应的生成函数项 : 底是

y^{2^1} = y^2

, 取值

0, 1

, 则对应的生成函数项是

(y^2)^0 (y^2)^1 = 1 y^2

2^2

对应的生成函数项 : 底是

y^{2^2} = y^4

, 取值

0, 1

, 则对应的生成函数项是

(y^4)^0 (y^4)^1 = 1 y^4

2^3

对应的生成函数项 : 底是

y^{2^3} = y^8

, 取值

0, 1

, 则对应的生成函数项是

(y^8)^0 (y^8)^1 = 1 y^8

vdots

完整的生成函数是 :

G(x) = (1 y)(1 y^2)(1 y^4)(1 y^8)cdots

分解上述每个生成函数项 :

1 y= cfrac{1-y^2}{1-y}

1 y^2= cfrac{1-y^4}{1-y^2}

1 y^4= cfrac{1-y^8}{1-y^4}

将上面三个等式代入生成函数

G(x)

中 ,

G(x) = cfrac{1-y^2}{1-y} cdot cfrac{1-y^4}{1-y^2} cdot cfrac{1-y^8}{1-y^4} cdots

= cfrac{1}{1-y}

= 1 y y^2 y^3 cdots

上述生成函数是

1^n

通项公式对应的数列的生成函数 ;

上述生成函数展开后 , 每项前的系数都为

, 说明只有一种方案 ;

博客二进制函数模型数学

0 人点赞