IDEA激活码
文章目录
- 一、正整数拆分基本模型
- 二、有限制条件的无序拆分
参考博客 :
- 【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )
- 【组合数学】生成函数 ( 线性性质 | 乘积性质 )
- 【组合数学】生成函数 ( 移位性质 )
- 【组合数学】生成函数 ( 求和性质 )
- 【组合数学】生成函数 ( 换元性质 | 求导性质 | 积分性质 )
- 【组合数学】生成函数 ( 性质总结 | 重要的生成函数 ) ★
- 【组合数学】生成函数 ( 生成函数示例 | 给定通项公式求生成函数 | 给定生成函数求通项公式 )
- 【组合数学】生成函数 ( 生成函数应用场景 | 使用生成函数求解递推方程 )
- 【组合数学】生成函数 ( 使用生成函数求解多重集 r 组合数 )
- 【组合数学】生成函数 ( 使用生成函数求解不定方程解个数 )
- 【组合数学】生成函数 ( 使用生成函数求解不定方程解个数示例 )
- 【组合数学】生成函数 ( 使用生成函数求解不定方程解个数示例 2 | 扩展到整数解 )
- 【组合数学】生成函数 ( 正整数拆分 | 无序 | 有序 | 允许重复 | 不允许重复 | 无序不重复拆分 | 无序重复拆分 )
- 【组合数学】生成函数 ( 正整数拆分 | 无序不重复拆分示例 )
一、正整数拆分基本模型
无序拆分基本模型 :
将 正整数
N
N
N 无序拆分成正整数 ,
a
1
,
a
2
,
⋯
,
a
n
a_1, a_2, \cdots , a_n
a1,a2,⋯,an 是拆分后的
n
n
n 个数 ,
该拆分是无序的 , 上述拆分的
n
n
n 个数的个数可能是不一样的 ,
假设
a
1
a_1
a1 有
x
1
x_1
x1 个 ,
a
2
a_2
a2 有
x
2
x_2
x2 个 ,
⋯
\cdots
⋯ ,
a
n
a_n
an 有
x
n
x_n
xn 个 , 那么有如下方程 :
a
1
x
1
+
a
2
x
2
+
⋯
+
a
n
x
n
=
N
a_1x_1 + a_2x_2 + \cdots + a_nx_n = N
a1x1+a2x2+⋯+anxn=N
这种形式可以使用 不定方程非负整数解个数 的生成函数计算 , 是 带系数 , 带限制条件的情况 , 参考 : 组合数学】生成函数 ( 使用生成函数求解不定方程解个数 )
无序拆分的情况下 , 拆分后的正整数 , 允许重复 和 不允许重复 , 是两类组合问题 ;
如果不允许重复 , 那么这些
x
i
x_i
xi 的取值 , 只能 取值
0
,
1
0, 1
0,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+ya1)(1+ya2)⋯(1+yan)
如果 允许重复 , 那么这些
x
i
x_i
xi 的取值 , 就是 自然数 ; 相当于 带系数 的 不定方程非负整数解 的情况 ;
对应的生成函数是 :
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+ya1+y2a1⋯)(1+ya2+y2a2⋯)⋯(1+yan+y2an⋯)
或
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−ya1)(1−ya2)⋯(1−yan)1
二、有限制条件的无序拆分
将 正整数
N
N
N 无序拆分成正整数 ,
a
1
,
a
2
,
⋯
,
a
n
a_1, a_2, \cdots , a_n
a1,a2,⋯,an 是拆分后的
n
n
n 个数 ,
该拆分是无序的 , 上述拆分的
n
n
n 个数的个数可能是不一样的 ,
假设
a
1
a_1
a1 有
x
1
x_1
x1 个 ,
a
2
a_2
a2 有
x
2
x_2
x2 个 ,
⋯
\cdots
⋯ ,
a
n
a_n
an 有
x
n
x_n
xn 个 , 那么有如下方程 :
a
1
x
1
+
a
2
x
2
+
⋯
+
a
n
x
n
=
N
a_1x_1 + a_2x_2 + \cdots + a_nx_n = N
a1x1+a2x2+⋯+anxn=N
其中存在限制条件 ,
a
i
a_i
ai 的取值个数
x
i
x_i
xi 取值范围 做一下限制 ,
l
i
≤
x
i
≤
t
i
l_i \leq x_i \leq t_i
li≤xi≤ti
这种形式可以使用 不定方程非负整数解个数 的生成函数计算 , 是 带系数 , 带限制条件的情况 , 参考 : 组合数学】生成函数 ( 使用生成函数求解不定方程解个数 )
上述受限制条件下的无序拆分 , 就是完整的 带系数 , 带限制条件 的 不定方程非负整数解 的问题 ;
