文章目录

一、正整数拆分基本模型

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

参考博客 :

【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )

【组合数学】生成函数 ( 线性性质 | 乘积性质 )

【组合数学】生成函数 ( 移位性质 )

【组合数学】生成函数 ( 求和性质 )

【组合数学】生成函数 ( 换元性质 | 求导性质 | 积分性质 )

【组合数学】生成函数 ( 性质总结 | 重要的生成函数 ) ★

【组合数学】生成函数 ( 生成函数示例 | 给定通项公式求生成函数 | 给定生成函数求通项公式 )

【组合数学】生成函数 ( 生成函数应用场景 | 使用生成函数求解递推方程 )

【组合数学】生成函数 ( 使用生成函数求解多重集 r 组合数 )

【组合数学】生成函数 ( 使用生成函数求解不定方程解个数 )

【组合数学】生成函数 ( 使用生成函数求解不定方程解个数示例 )

【组合数学】生成函数 ( 使用生成函数求解不定方程解个数示例 2 | 扩展到整数解 )

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

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

一、正整数拆分基本模型

无序拆分基本模型 :

将 正整数 N NN 无序拆分成正整数 , a 1 , a 2 , ⋯   , a n a_1, a_2, \cdots , a_na

1

,a

2

,⋯,a

n

 是拆分后的 n nn 个数 ,

该拆分是无序的 , 上述拆分的 n nn 个数的个数可能是不一样的 ,

假设 a 1 a_1a

1

 有 x 1 x_1x

1

 个 , a 2 a_2a

2

 有 x 2 x_2x

2

 个 , ⋯ \cdots⋯ , a n a_na

n

 有 x n x_nx

n

 个 , 那么有如下方程 :

a 1 x 1 + a 2 x 2 + ⋯ + a n x n = N a_1x_1 + a_2x_2 + \cdots + a_nx_n = Na

1

x

1

+a

2

x

2

+⋯+a

n

x

n

=N

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

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

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

i

 的取值 , 只能 取值 0 , 1 0, 10,1 ; 相当于 带限制条件 , 带系数 的 不定方程非负整数解 的情况 ;

对应的生成函数是 : G ( x ) = ( 1 + y a 1 ) ( 1 + y a 2 ) ⋯ ( 1 + y a n ) G(x) = (1+ y^{a_1}) (1+ y^{a_2}) \cdots (1+ y^{a_n})G(x)=(1+y

a

1

)(1+y

a

2

)⋯(1+y

a

n

)

如果 允许重复 , 那么这些 x i x_ix

i

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

对应的生成函数是 : G ( x ) = ( 1 + y a 1 + y 2 a 1 ⋯   ) ( 1 + y a 2 + y 2 a 2 ⋯   ) ⋯ ( 1 + y a n + y 2 a n ⋯   ) 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)=(1+y

a

1

+y

2a

1

⋯)(1+y

a

2

+y

2a

2

⋯)⋯(1+y

a

n

+y

2a

n

⋯)

或 G ( x ) = 1 ( 1 − y a 1 ) ( 1 − y a 2 ) ⋯ ( 1 − y a n ) G(x) =\cfrac{1}{ (1-y^{a_1}) (1-y^{a_2}) \cdots (1-y^{a_n}) }G(x)=

(1−y

a

1

)(1−y

a

2

)⋯(1−y

a

n

)

1

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

将 正整数 N NN 无序拆分成正整数 , a 1 , a 2 , ⋯   , a n a_1, a_2, \cdots , a_na

1

,a

2

,⋯,a

n

 是拆分后的 n nn 个数 ,

该拆分是无序的 , 上述拆分的 n nn 个数的个数可能是不一样的 ,

假设 a 1 a_1a

1

 有 x 1 x_1x

1

 个 , a 2 a_2a

2

 有 x 2 x_2x

2

 个 , ⋯ \cdots⋯ , a n a_na

n

 有 x n x_nx

n

 个 , 那么有如下方程 :

a 1 x 1 + a 2 x 2 + ⋯ + a n x n = N a_1x_1 + a_2x_2 + \cdots + a_nx_n = Na

1

x

1

+a

2

x

2

+⋯+a

n

x

n

=N

其中存在限制条件 , a i a_ia

i

 的取值个数 x i x_ix

i

 取值范围 做一下限制 , l i ≤ x i ≤ t i l_i \leq x_i \leq t_il

i

≤x

i

≤t

i

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

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