IDEA激活码
文章目录
- 一、多重集组合示例
- 二、三个计数模型
排列组合参考博客 :
- 【组合数学】基本计数原则 ( 加法原则 | 乘法原则 )
- 【组合数学】集合的排列组合问题示例 ( 排列 | 组合 | 圆排列 | 二项式定理 )
- 【组合数学】排列组合 ( 排列组合内容概要 | 选取问题 | 集合排列 | 集合组合 )
- 【组合数学】排列组合 ( 排列组合示例 )
- 【组合数学】排列组合 ( 多重集排列 | 多重集全排列 | 多重集非全排列 所有元素重复度大于排列数 | 多重集非全排列 某些元素重复度小于排列数 )
- 【组合数学】排列组合 ( 多重集组合数 | 所有元素重复度大于组合数 | 多重集组合数 推导 1 分割线推导 | 多重集组合数 推导 2 不定方程非负整数解个数推导 )
一、多重集组合示例
将
r
r
r 个相同的球 , 放到
k
k
k 个不同的盒子中 , 每个盒子中球的个数不限 , 求放球的总方法数 ?
球是没有区别的 , 球放到盒子里 , 球没有标号 , 盒子有标号 , 每个盒子放球的个数不同 ;
落入每个盒子中球个数不同 , 就是不同的方案 ;
假设
n
n
n 个盒子 , 每个盒子的球数为
x
1
,
x
2
,
⋯
,
x
k
x_1 , x_2 , \cdots , x_k
x1,x2,⋯,xk ;
存在不定方程 :
x
1
+
x
2
+
⋯
+
x
k
=
r
x_1 + x_2 + \cdots + x_k = r
x1+x2+⋯+xk=r
取值 :
x
1
,
x
2
,
⋯
,
x
k
x_1 , x_2 , \cdots , x_k
x1,x2,⋯,xk 的取值为非负整数 , 可以取值
0
∼
r
0 \sim r
0∼r 之间的值 ;
该问题可以等价于多重集
S
=
{
n
1
⋅
a
1
,
n
2
⋅
a
2
,
⋯
,
n
k
⋅
a
k
}
,
0
≤
r
≤
n
i
≤
+
∞
S = \{ n_1 \cdot a_1 , n_2 \cdot a_2 , \cdots , n_k \cdot a_k \} , \ \ \ 0 \leq r \leq n_i \leq +\infty
S={n1⋅a1,n2⋅a2,⋯,nk⋅ak}, 0≤r≤ni≤+∞ 的
r
r
r 组合数 ;
N
=
C
(
k
+
r
−
1
,
r
)
N= C(k + r - 1, r)
N=C(k+r−1,r)
参考 : 【组合数学】排列组合 ( 多重集组合数 | 所有元素重复度大于组合数 | 多重集组合数 推导 1 分割线推导 | 多重集组合数 推导 2 不定方程非负整数解个数推导 )
上述
r
r
r 个相同的球 , 放在
k
k
k 个不同盒子中 , 放球方法数是
N
=
C
(
k
+
r
−
1
,
r
)
N = C(k + r - 1, r)
N=C(k+r−1,r)
二、三个计数模型
三个计数模型 :
- ① 选取问题 :
- ② 多重集组合问题 :
- ③ 方程非负整数解 :
1. 选取问题 :
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) |
多重集组合 |
选取问题中 :
- 不可重复的元素 , 有序的选取 , 对应 集合的排列
- 不可重复的元素 , 无序的选取 , 对应 集合的组合
- 可重复的元素 , 有序的选取 , 对应 多重集的排列
- 可重复的元素 , 无序的选取 , 对应 多重集的组合
2. 多重集组合问题 :
S
=
{
n
1
⋅
a
1
,
n
2
⋅
a
2
,
⋯
,
n
k
⋅
a
k
}
,
0
≤
n
i
≤
+
∞
S = \{ n_1 \cdot a_1 , n_2 \cdot a_2 , \cdots , n_k \cdot a_k \} , \ \ \ 0 \leq n_i \leq +\infty
S={n1⋅a1,n2⋅a2,⋯,nk⋅ak}, 0≤ni≤+∞
- 元素种类 : 多重集中含有
k
k
k 种不同的元素 , - 元素表示 : 每个元素表示为
a
1
,
a
2
,
⋯
,
a
k
a_1 , a_2 , \cdots , a_k
a1,a2,⋯,ak , - 元素个数 : 每个元素出现的次数是
n
1
,
n
2
,
⋯
,
n
k
n_1, n_2, \cdots , n_k
n1,n2,⋯,nk , - 元素个数取值 :
n
i
n_i
ni 的取值要求是 大于0
0
0 , 小于正无穷+
∞
+ \infty
+∞ ;
上述多重集的组合 , 当 所有元素的重复度
n
i
n_i
ni 组大于组合数
r
r
r 时 ,
r
≤
n
i
r \leq n_i
r≤ni 时 , 多重集的组合数为
N
=
C
(
k
+
r
−
1
,
r
)
N= C(k + r - 1, r)
N=C(k+r−1,r)
3. 不定方程非负整数解问题 :
x
1
+
x
2
+
⋯
+
x
k
=
r
x_1 + x_2 + \cdots + x_k = r
x1+x2+⋯+xk=r
非负整数解个数为 :
N
=
C
(
k
+
r
−
1
,
r
)
N= C(k + r - 1, r)
N=C(k+r−1,r)
