IDEA激活码
文章目录
- 一、正整数拆分
- 二、无序拆分
-
- 1、无序拆分 不允许重复
- 2、无序拆分 允许重复
参考博客 :
- 【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )
- 【组合数学】生成函数 ( 线性性质 | 乘积性质 )
- 【组合数学】生成函数 ( 移位性质 )
- 【组合数学】生成函数 ( 求和性质 )
- 【组合数学】生成函数 ( 换元性质 | 求导性质 | 积分性质 )
- 【组合数学】生成函数 ( 性质总结 | 重要的生成函数 ) ★
- 【组合数学】生成函数 ( 生成函数示例 | 给定通项公式求生成函数 | 给定生成函数求通项公式 )
- 【组合数学】生成函数 ( 生成函数应用场景 | 使用生成函数求解递推方程 )
- 【组合数学】生成函数 ( 使用生成函数求解多重集 r 组合数 )
- 【组合数学】生成函数 ( 使用生成函数求解不定方程解个数 )
- 【组合数学】生成函数 ( 使用生成函数求解不定方程解个数示例 )
- 【组合数学】生成函数 ( 使用生成函数求解不定方程解个数示例 2 | 扩展到整数解 )
一、正整数拆分
正整数拆分 涉及内容 :
- 拆分定义与分类
- 无序拆分
- 有序拆分
一个正整数可以 拆分成若干正整数 的和 , 每种不同的拆分方法 , 就可以 看做一个方案 ;
按照拆分顺序进行分类 :
4
4
4 拆分成
1
1
1 和
3
3
3 ,
4
4
4 拆分成
3
3
3 和
1
1
1 ;
- 有序拆分 : 上述
2
2
2 个 正整数拆分 , 是 两种不同的拆分方法 ; - 无序拆分 : 上述
2
2
2 个 正整数拆分 , 是 同一种拆分方法 ;
按照是否重复进行分类 :
- 允许重复 : 拆分时 , 允许拆分成若干个重复的正整数 , 如
3
3
3 拆分成3
3
3 个1
1
1 ; - 不允许重复 : 拆分时 , 拆分的正整数 不允许重复 , 如
3
3
3 拆分成3
3
3 个1
1
1 是错误的 , 只能拆分成1
,
2
1,2
1,2 ;
正整数拆分可以按照性质 , 分为
4
4
4 类 ;
- 有序重复
- 有序不重复
- 无序重复
- 无序不重复
二、无序拆分
无序拆分基本模型 :
将 正整数
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 ; 相当于 带限制条件 , 带系数 的 不定方程非负整数解 的情况 ;
如果 允许重复 , 那么这些
x
i
x_i
xi 的取值 , 就是 自然数 ; 相当于 带系数 的 不定方程非负整数解 的情况 ;
1、无序拆分 不允许重复
讨论 无序拆分 , 不允许重复的情况 , 该方式 等价于 带限制条件 , 带系数 的 不定方程非负整数解 的情况 ;
a
1
a_1
a1 项对应的生成函数项 ,
x
1
x_1
x1 取值
0
,
1
0,1
0,1 , 则对应的生成函数项是
(
y
a
1
)
0
+
(
y
a
1
)
1
=
1
+
y
a
1
(y^{a_1})^{0} + (y^{a_1})^{1}= 1+ y^{a_1}
(ya1)0+(ya1)1=1+ya1
a
2
a_2
a2 项对应的生成函数项 ,
x
2
x_2
x2 取值
0
,
1
0,1
0,1 , 则对应的生成函数项是
(
y
a
2
)
0
+
(
y
a
2
)
1
=
1
+
y
a
2
(y^{a_2})^{0} + (y^{a_2})^{1}= 1+ y^{a_2}
(ya2)0+(ya2)1=1+ya2
⋮
\vdots
⋮
a
n
a_n
an 项对应的生成函数项 ,
x
n
x_n
xn 取值
0
,
1
0,1
0,1 , 则对应的生成函数项是
(
y
a
n
)
0
+
(
y
a
n
)
1
=
1
+
y
a
n
(y^{a_n})^{0} + (y^{a_n})^{1}= 1+ y^{a_n}
(yan)0+(yan)1=1+yan
将上述生成函数项相乘 , 则可得到完整生成函数 :
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)
将上述生成函数写好之后 , 计算 展开 ,
y
y
y 的
N
N
N 次幂的系数 , 就是 正整数
N
N
N 的拆分方案数 ;
2、无序拆分 允许重复
讨论 无序拆分 , 允许重复的情况 , 该方式 等价于 不带限制条件 , 带系数 的 不定方程非负整数解 的情况 ;
a
1
a_1
a1 项对应的生成函数项 ,
x
1
x_1
x1 取值
0
,
1
,
⋯
0,1, \cdots
0,1,⋯ , 则对应的生成函数项是
(
y
a
1
)
0
+
(
y
a
1
)
1
+
(
y
a
1
)
2
=
1
+
y
a
1
+
y
2
a
1
⋯
(y^{a_1})^{0} + (y^{a_1})^{1} + (y^{a_1})^{2}= 1+ y^{a_1} + y^{2a_1}\cdots
(ya1)0+(ya1)1+(ya1)2=1+ya1+y2a1⋯
a
2
a_2
a2 项对应的生成函数项 ,
x
2
x_2
x2 取值
0
,
1
,
⋯
0,1, \cdots
0,1,⋯ , 则对应的生成函数项是
(
y
a
2
)
0
+
(
y
a
2
)
1
+
(
y
a
2
)
2
=
1
+
y
a
2
+
y
2
a
2
⋯
(y^{a_2})^{0} + (y^{a_2})^{1} + (y^{a_2})^{2}= 1+ y^{a_2} + y^{2a_2}\cdots
(ya2)0+(ya2)1+(ya2)2=1+ya2+y2a2⋯
⋮
\vdots
⋮
a
n
a_n
an 项对应的生成函数项 ,
x
n
x_n
xn 取值
0
,
1
,
⋯
0,1, \cdots
0,1,⋯ , 则对应的生成函数项是
(
y
a
n
)
0
+
(
y
a
n
)
1
+
(
y
a
n
)
2
=
1
+
y
a
n
+
y
2
a
n
⋯
(y^{a_n})^{0} + (y^{a_n})^{1} + (y^{a_n})^{2}= 1+ y^{a_n} + y^{2a_n}\cdots
(yan)0+(yan)1+(yan)2=1+yan+y2an⋯
将上述生成函数项相乘 , 则可得到完整生成函数 :
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⋯)
上述生成函数可以根据 如下生成函数的常用取值 :
{
a
n
}
\{a_n\}
{an} ,
a
n
=
1
n
a_n = 1^n
an=1n ;
A
(
x
)
=
∑
n
=
0
∞
x
n
=
1
1
−
x
\begin{aligned} A(x) & = \sum_{n=0}^{\infty} x^n = \frac{1}{1-x} \end{aligned}
A(x)=n=0∑∞xn=1−x1
将
1
+
y
a
1
+
y
2
a
1
⋯
1+ y^{a_1}+ y^{2a_1}\cdots
1+ya1+y2a1⋯ 中的
y
a
1
y^{a_1}
ya1 换元成
x
x
x , 则可得到
1
+
x
+
x
2
+
x
3
+
⋯
1 + x + x^2 + x^3 + \cdots
1+x+x2+x3+⋯
对应的数列是
1
n
1^n
1n
则上述
1
+
y
a
1
+
y
2
a
1
⋯
=
1
1
−
y
a
1
1+ y^{a_1}+ y^{2a_1}\cdots =\cfrac{1}{1-y^{a_1}}
1+ya1+y2a1⋯=1−ya11
最终化简结果 :
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⋯)
=
1
(
1
−
y
a
1
)
(
1
−
y
a
2
)
⋯
(
1
−
y
a
n
)
\ \ \ \ \ \ \ \ \ \ =\cfrac{1}{ (1-y^{a_1}) (1-y^{a_2}) \cdots (1-y^{a_n}) }
=(1−ya1)(1−ya2)⋯(1−yan)1
将上述生成函数写好之后 , 计算 展开 ,
y
y
y 的
N
N
N 次幂的系数 , 就是 正整数
N
N
N 的拆分方案数 ;
