提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

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

函数 生成 模型 基本 限制 条件 组合 数学
2023-06-13 09:17:48 时间

文章目录

参考博客 :

一、正整数拆分基本模型

无序拆分基本模型 :

将 正整数

N

无序拆分成正整数 ,

a_1, a_2, \cdots , a_n

是拆分后的

n

个数 ,

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

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}) }

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

将 正整数

N

无序拆分成正整数 ,

a_1, a_2, \cdots , a_n

是拆分后的

n

个数 ,

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

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

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

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

相关文章