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