IDEA激活码
文章目录
- 一、重复有序拆分
- 二、不重复有序拆分
-
- 1、无序拆分基本模型
- 2、全排列
- 三、重复有序拆分方案数证明
参考博客 : 按照顺序看
- 【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )
- 【组合数学】生成函数 ( 线性性质 | 乘积性质 )
- 【组合数学】生成函数 ( 移位性质 )
- 【组合数学】生成函数 ( 求和性质 )
- 【组合数学】生成函数 ( 换元性质 | 求导性质 | 积分性质 )
- 【组合数学】生成函数 ( 性质总结 | 重要的生成函数 ) ★
- 【组合数学】生成函数 ( 生成函数示例 | 给定通项公式求生成函数 | 给定生成函数求通项公式 )
- 【组合数学】生成函数 ( 生成函数应用场景 | 使用生成函数求解递推方程 )
- 【组合数学】生成函数 ( 使用生成函数求解多重集 r 组合数 )
- 【组合数学】生成函数 ( 使用生成函数求解不定方程解个数 )
- 【组合数学】生成函数 ( 使用生成函数求解不定方程解个数示例 )
- 【组合数学】生成函数 ( 使用生成函数求解不定方程解个数示例 2 | 扩展到整数解 )
- 【组合数学】生成函数 ( 正整数拆分 | 无序 | 有序 | 允许重复 | 不允许重复 | 无序不重复拆分 | 无序重复拆分 )
- 【组合数学】生成函数 ( 正整数拆分 | 无序不重复拆分示例 )
- 【组合数学】生成函数 ( 正整数拆分 | 正整数拆分基本模型 | 有限制条件的无序拆分 )
一、重复有序拆分
将 正整数
N
N
N 重复地 , 有序拆分 成
r
r
r 部分 , 方案数为
C
(
N
−
1
,
r
−
1
)
C(N-1, r-1)
C(N−1,r−1) ★
( 三、中有该组合数由来证明 )
如果对 正整数
N
N
N 作 任意重复的有序拆分 , 即可以拆分成
1
1
1 个数 ,
2
2
2 个数 ,
⋯
\cdots
⋯ ,
N
N
N 个数 ,
拆分成
1
1
1 个数方案个数是
(
N
−
1
1
−
1
)
\dbinom{N-1}{1-1}
(1−1N−1)
拆分成
2
2
2 个数方案个数是
(
N
−
1
2
−
1
)
\dbinom{N-1}{2-1}
(2−1N−1)
⋮
\vdots
⋮
拆分成
N
N
N 个数方案个数是
(
N
−
1
N
−
1
)
\dbinom{N-1}{N-1}
(N−1N−1)
上述总的方案个数是 :
∑
r
=
1
N
=
2
N
−
1
\sum\limits_{r=1}^{N}=2^{N-1}
r=1∑N=2N−1
( 根据基本组合恒等式计算出来 )
二、不重复有序拆分
先进行 不重复无序拆分 , 再进行 全排列 ;
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
这种形式可以使用 不定方程非负整数解个数 的生成函数计算 , 是 带系数 , 带限制条件的情况 , 参考 : 组合数学】生成函数 ( 使用生成函数求解不定方程解个数 )
无序拆分的情况下 , 拆分后的正整数 , 允许重复 和 不允许重复 , 是两类组合问题 ;
如果不允许重复 , 那么这些
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
2、全排列
n
n
n 的全排列是
n
!
n!
n!
n
n
n 元集
S
S
S , 从
S
S
S 集合中选取
r
r
r 个元素 ;
根据 元素是否允许重复 , 选取过程是否有序 , 将选取问题分为四个子类型 :
| 元素不重复 | 元素可以重复 | |
|---|---|---|
| 有序选取 | 集合排列
P ( n , r ) P(n,r) P(n,r) |
多重集排列 |
| 无序选取 | 集合组合
C ( n , r ) C(n,r) C(n,r) |
多重集组合 |
选取问题中 :
- 不可重复的元素 , 有序的选取 , 对应 集合的排列 ;
P
(
n
,
r
)
=
n
!
(
n
−
r
)
!
P(n,r) = \dfrac{n!}{(n-r)!}
P(n,r)=(n−r)!n! - 不可重复的元素 , 无序的选取 , 对应 集合的组合 ;
C
(
n
,
r
)
=
P
(
n
,
r
)
r
!
=
n
!
r
!
(
n
−
r
)
!
C(n,r) = \dfrac{P(n,r)}{r!} = \dfrac{n!}{r!(n-r)!}
C(n,r)=r!P(n,r)=r!(n−r)!n! - 可重复的元素 , 有序的选取 , 对应 多重集的排列 ;
全
排
列
=
n
!
n
1
!
n
2
!
⋯
n
k
!
全排列 = \cfrac{n!}{n_1! n_2! \cdots n_k!}
全排列=n1!n2!⋯nk!n! , 非全排列k
r
,
r
≤
n
i
k^r , \ \ r\leq n_i
kr, r≤ni - 可重复的元素 , 无序的选取 , 对应 多重集的组合 ;
N
=
C
(
k
+
r
−
1
,
r
)
N= C(k + r - 1, r)
N=C(k+r−1,r)
三、重复有序拆分方案数证明
使用一一对应的方法证明 : 将 正整数
N
N
N 重复地 , 有序拆分 成
r
r
r 部分 , 方案数为
C
(
N
−
1
,
r
−
1
)
C(N-1, r-1)
C(N−1,r−1) ★
拆分后的正整数 , 如果交换了次序之后 , 排列不同 , 其所代表的方案数也不同 ;
将该拆分转换成组合计数问题 ;
假设
N
=
a
1
+
a
2
+
⋯
+
a
r
N=a_1 + a_2 + \cdots + a_r
N=a1+a2+⋯+ar 是满足条件的拆分 , 该拆分 重复 , 有序 ;
将上述方案 , 做成部分序列 ,
拆分方案 与 拆分序列 :
根据拆分方案写出拆分序列 :
原始方案
6
=
1
+
2
+
3
6=1+2+3
6=1+2+3 , 由原始方案作部分序列 ,
第一个序列
S
1
=
1
S_1 = 1
S1=1 , 取原始方案的第一个成分
1
1
1 出来 ,
第二个序列
S
2
=
1
+
2
=
3
S_2 = 1 + 2 = 3
S2=1+2=3 , 取原始方案的前两个成分
1
+
2
1 + 2
1+2 出来 ,
第三个序列
S
3
=
1
+
2
+
3
=
6
S_3 = 1 + 2 + 3 = 6
S3=1+2+3=6 , 取原始方案的前三个成分
1
+
2
+
3
1 + 2 + 3
1+2+3 出来 ,
第一个序列是第一个数 , 第二个序列是前两个数 , 第
n
n
n 个序列是前
n
n
n 个数 , 最后一个序列包含了所有的拆分的正整数 ;
只要给定一个原始方案 , 就可以作出上述部分序列出来 ;
只要方案相同 , 作出的序列完全相同 , 方案不同 , 作出的序列肯定不相同 ;
根据拆分序列写出拆分方案 :
反之 , 给定一个序列 , 可以 还原出一个拆分方案来 , 如给出序列
S
1
=
1
,
S
2
=
3
,
S
3
=
6
S_1 = 1 , S_2=3, S_3=6
S1=1,S2=3,S3=6 , 对应的拆分方案 :
最后一个序列式所有数之和 , 被拆分的正整数就是最后一个序列的数值
6
6
6
第一个正整数 就是第一个序列
1
1
1
第二个正整数 是第二序列减去第一序列
S
2
−
S
1
=
3
−
1
=
2
S_2 - S_1 = 3-1=2
S2−S1=3−1=2
第三个正整数 是第三序列减去第二序列
S
3
−
S
2
=
6
−
3
=
3
S_3-S_2=6-3=3
S3−S2=6−3=3
拆分方案是
6
=
1
+
2
+
3
6 = 1+2+3
6=1+2+3
N
=
a
1
+
a
2
+
⋯
+
a
r
N=a_1 + a_2 + \cdots + a_r
N=a1+a2+⋯+ar 的拆分序列是
S
1
=
a
1
S_1 = a_1
S1=a1
S
2
=
a
1
+
a
2
S_2= a_1 + a_2
S2=a1+a2
S
3
=
a
1
+
a
2
+
a
3
S_3= a_1 + a_2 + a_3
S3=a1+a2+a3
⋮
\vdots
⋮
S
i
=
a
1
+
a
2
+
a
3
+
⋯
+
a
i
=
∑
k
=
1
t
a
i
,
i
=
1
,
2
,
3
,
⋯
S_i= a_1 + a_2 + a_3 + \cdots + a_i = \sum\limits_{k=1}^ta_i\ , \ \ \ \ \ i=1,2,3, \cdots
Si=a1+a2+a3+⋯+ai=k=1∑tai , i=1,2,3,⋯
上述的拆分序列一定有下面的性质 :
0
<
S
1
<
S
2
<
⋯
<
S
r
=
N
0 < S_1 < S_2 < \cdots < S_r = N
0<S1<S2<⋯<Sr=N
因为
S
2
S_2
S2 肯定是
S
1
S_1
S1 加上一个正整数 ,
S
r
S_r
Sr 肯定是
S
r
−
1
S_{r-1}
Sr−1 加上一个正整数 , 最后一项是所有的
r
r
r 个正整数之和 , 是被拆分的正整数
N
N
N ;
上述拆分序列
S
1
,
S
2
,
⋯
,
S
r
S_1, S_2, \cdots , S_r
S1,S2,⋯,Sr , 最后一个数
S
r
=
N
S_r = N
Sr=N ,
最后一个数不管 , 前面的
r
−
1
r-1
r−1 个数的取值范围是
1
,
2
,
3
,
⋯
,
N
−
1
1, 2, 3, \cdots , N-1
1,2,3,⋯,N−1 , 上述取值范围内 有
n
−
1
n-1
n−1 个正整数 ;
从
n
−
1
n-1
n−1 个正整数中 , 选取
r
−
1
r-1
r−1 个正整数 ,
因此, 将 正整数
N
N
N 重复地 , 有序拆分 成
r
r
r 部分 , 方案数为
C
(
N
−
1
,
r
−
1
)
C(N-1, r-1)
C(N−1,r−1) ★
