当前位置：首页 > 编程资源 > 编程问答 >内容正文

编程问答

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

发布时间：2025/6/17 编程问答 40 豆豆

生活随笔收集整理的这篇文章主要介绍了【组合数学】生成函数 ( 正整数拆分 | 无序不重复拆分示例 ) 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

参考博客 :

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

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

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

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

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

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

正整数拆分生成函数 :

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

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

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

$2$ 的次幂情况 : $20,21,22,23,⋯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$

$⋮\vdots$

完整的生成函数是 :

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

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

$\cfrac{1-y^2}{1-y}$

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

$y^4= \cfrac{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$

$=11−y\ \ \ \ \ \ \ \ \ \ = \cfrac{1}{1-y}$

$=1+y+y2+y3+⋯\ \ \ \ \ \ \ \ \ \ = 1 + y + y^2 + y^3 + \cdots$

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

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

以上是生活随笔为你收集整理的【组合数学】生成函数 ( 正整数拆分 | 无序不重复拆分示例 )的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。