参考博客 :

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

一、正整数拆分总结

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

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

每个 生成函数的项的 $y$ 次幂项个数 , 与该 被拆分的数的取值个数种类 一样 ,

如 : 某个被拆分出来的数 $a_1$ , 其 可以取值 $0,1,2$ 三个值 , 那么对应的 生成函数的项的 $y$ 次幂项个数 有 $3$ 个值 , 为 $(y^{a_1}{)}^0+(y^{a_1}{)}^1+(y^{a_1}{)}^2$ ,

该生成函数项中的 底是 $y^{被拆分的数}$ , 次幂数就是 该正整数 可能的取值 , 项中的 $y$ 次幂分项个数 就是 该 正整数 取值的种类个数 ;

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

• 如果 不允许重复 , 该被拆分的 正整数 只能出现 $0,1$ 次 ;
• 如果 允许重复 , 那么该正整数可以 出现 $0,1,2,\cdots$ 无限次 ;

正整数拆分生成函数 :

• 生成函数项个数 : 就是 拆分后的正整数种类数 ; 可拆分成 $2,4,8$ 三个数 , 那么是三个生成函数项相乘 ;
• 生成函数项中的 $y$ 次幂个数 : 对应 拆分后的正整数 取值种类个数 ; 某个拆分后的整数可能出现 $0,1$ 次 , 代表取值种类数是 $2$ ;
• 生成函数项中的 $y$ 次幂底 : $y^{拆分后的正整数}$ , 某个拆分后正整数是 $5$ , 那么底就是 $y^5$ ;
• 生成函数项中的 $y$ 次幂 : 拆分后的正整数的 取值个数 ; 某个拆分后正整数是 $5$ , 那么底就是 $y^5$ , 出现一次 , 对应的项是 $(y^5{)}^1$

二、正整数拆分示例

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

上述问题可以等价为 , 将 任意正整数 , 都可以 拆解成 $2$ 的次幂之和 , 并且 不允许有重复的元素 ;

$2$ 的次幂情况 : $2^0,2^1,2^2,2^3,\cdots$

由于不允许有重复 , 因此每个 $2$ 次幂 的个数 , 只能是 $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$

$⋮$

完整的生成函数是 :

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

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

$1+y=\frac{1-y^2}{1-y}$

$1+y^2=\frac{1-y^4}{1-y^2}$

$1+y^4=\frac{1-y^8}{1-y^4}$

将上面三个等式代入生成函数 $G(x)$ 中 ,

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

$=\frac{1}{1-y}$

$=1+y+y^2+y^3+\cdots$

上述生成函数是 $1^n$ 通项公式 对应的数列的 生成函数 ;

上述生成函数展开后 , 每项前的系数都为 $1$ , 说明只有一种方案 ;

文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。

原文链接：hanshuliang.blog.csdn.net/article/details/109369274