【组合数学】生成函数 ( 正整数拆分 | 正整数拆分基本模型

文章目录

一、正整数拆分基本模型
二、有限制条件的无序拆分

参考博客 :

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

一、正整数拆分基本模型

无序拆分基本模型 :

将正整数

无序拆分成正整数 ,

a_1, a_2, cdots , a_n

是拆分后的

个数 ,

该拆分是无序的 , 上述拆分的

个数的个数可能是不一样的 ,

假设

a_1

有

x_1

个 ,

a_2

有

x_2

个 ,

cdots

a_n

有

x_n

个 , 那么有如下方程 :

a_1x_1 a_2x_2 cdots a_nx_n = N

这种形式可以使用不定方程非负整数解个数的生成函数计算 , 是带系数 , 带限制条件的情况 , 参考 : 组合数学】生成函数 ( 使用生成函数求解不定方程解个数 )

无序拆分的情况下 , 拆分后的正整数 , 允许重复和不允许重复 , 是两类组合问题 ;

如果不允许重复 , 那么这些

x_i

的取值 , 只能取值

0, 1

; 相当于带限制条件 , 带系数的不定方程非负整数解的情况 ;

对应的生成函数是 :

G(x) = (1 y^{a_1}) (1 y^{a_2}) cdots (1 y^{a_n})

如果允许重复 , 那么这些

x_i

的取值 , 就是自然数 ; 相当于带系数的不定方程非负整数解的情况 ;

对应的生成函数是 :

G(x) = (1 y^{a_1} y^{2a_1}cdots) (1 y^{a_2} y^{2a_2}cdots) cdots (1 y^{a_n} y^{2a_n}cdots )

或

G(x) =cfrac{1}{ (1-y^{a_1}) (1-y^{a_2}) cdots (1-y^{a_n}) }

二、有限制条件的无序拆分

将正整数

无序拆分成正整数 ,

a_1, a_2, cdots , a_n

是拆分后的

个数 ,

该拆分是无序的 , 上述拆分的

个数的个数可能是不一样的 ,

假设

a_1

有

x_1

个 ,

a_2

有

x_2

个 ,

cdots

a_n

有

x_n

个 , 那么有如下方程 :

a_1x_1 a_2x_2 cdots a_nx_n = N

其中存在限制条件 ,

a_i

的取值个数

x_i

取值范围做一下限制 ,

l_i leq x_i leq t_i

上述受限制条件下的无序拆分 , 就是完整的带系数 , 带限制条件的不定方程非负整数解的问题 ;

博客函数模型数学

0 人点赞

【组合数学】生成函数 ( 正整数拆分 | 正整数拆分基本模型 | 有限制条件的无序拆分 )

文章目录

一、正整数拆分基本模型

二、有限制条件的无序拆分