IDEA激活码
文章目录
- 一、多重集组合 ( 所有元素重复度大于组合数 )
- 二、多重集组合 所有元素重复度大于组合数 推导 1 ( 分割线推导 )
- 二、多重集组合 所有元素重复度大于组合数 推导 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)
二、多重集组合 所有元素重复度大于组合数 推导 1 ( 分割线推导 )
多重集 :
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≤+∞
取
r
r
r 种元素的组合 ,
r
≤
n
i
r \leq n_i
r≤ni , 推导过程如下 :
在
k
k
k 种元素中 , 取
r
r
r 种元素 , 每种元素取
0
∼
r
0 \sim r
0∼r 个不等的元素 ,
使用
k
−
1
k-1
k−1 个分割线分割
k
k
k 种元素的位置 ,
k
−
1
k - 1
k−1 个分割线相当于组成了
k
k
k 个盒子 , 在每个盒子中放
0
∼
r
0 \sim r
0∼r 个不等的元素 ,
放置的总元素的个数是
r
r
r 个 , 分割线个数是
k
−
1
k-1
k−1 个 , 这里就产生了一个组合问题 , 在
k
−
1
k-1
k−1 个分割线 和
r
r
r 个元素之间 , 选取
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)
二、多重集组合 所有元素重复度大于组合数 推导 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≤+∞
取
r
r
r 种元素的组合 ,
r
≤
n
i
r \leq n_i
r≤ni , 推导过程如下 :
多重集
S
S
S 每个元素取值 :
-
第
1
1
1 种元素取值个数 : 元素
a
1
a_1
a1 的取值个数是
x
1
x_1
x1 ,
-
第
2
2
2 种元素取值个数 : 元素
a
2
a_2
a2 的取值个数是
x
2
x_2
x2 ,
⋮
\; \; \, \ \ \ \ \ \ \vdots
⋮
- 第
k
k
k 种元素取值个数 :元素a
k
a_k
ak 的取值个数是x
k
x_k
xk ;
不定方程
x
1
+
x
2
+
⋯
+
x
k
=
r
x_1 + x_2 + \cdots + x_k = r
x1+x2+⋯+xk=r ;
x
i
x_i
xi 可以为
0
0
0 , 即某个元素取值个数可以是
0
0
0 ;
则多重集
S
S
S 的
r
r
r 组合是 :
{
x
1
⋅
a
1
,
x
2
⋅
a
2
,
⋯
,
x
k
⋅
a
k
}
\{ x_1 \cdot a_1 , x_2 \cdot a_2 , \cdots , x_k \cdot a_k \}
{x1⋅a1,x2⋅a2,⋯,xk⋅ak}
x
i
x_i
xi 的取值是非负整数
多重集组合与方程对应 : 只要有一个
r
r
r 组合 , 就可以写出一个对象的 方程
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
=
r
x_1 + x_2 + \cdots + x_k = r
x1+x2+⋯+xk=r 不定方程的一组非负整数解 , 就对应着 一个
S
S
S 多重集的
r
r
r 组合 ;
一一对应关系 : 上述
方程的非负整数解的个数
与
S
S
S 多重集的
r
r
r 组合个数 一一对应 ;
求
S
S
S 多重集的
r
r
r 组合数 , 就可以转化成 求
x
1
+
x
2
+
⋯
+
x
k
=
r
x_1 + x_2 + \cdots + x_k = r
x1+x2+⋯+xk=r 方程非负整数解个数 ;
将上述解写成一个序列 , 序列中使用
k
−
1
k-1
k−1 个
0
0
0 , 分割
k
k
k 组
1
1
1 ;
1
⋯
1
⏟
x
1
个
1
\begin{matrix} \underbrace{ 1 \cdots 1 } \\ x_1个1 \end{matrix}
1⋯1x1个1
0
0
0
1
⋯
1
⏟
x
2
个
1
\begin{matrix} \underbrace{ 1 \cdots 1 } \\ x_2个1 \end{matrix}
1⋯1x2个1
0
0
0
1
⋯
1
⏟
x
3
个
1
\begin{matrix} \underbrace{ 1 \cdots 1 } \\ x_3个1 \end{matrix}
1⋯1x3个1
0
0
0
⋯
\cdots
⋯
0
0
0
1
⋯
1
⏟
x
k
个
1
\begin{matrix} \underbrace{ 1 \cdots 1 } \\ x_k个1 \end{matrix}
1⋯1xk个1
不定方程每个解 都对应着 上述
k
−
1
k-1
k−1 个
0
0
0 和
r
r
r 个
1
1
1 的一个排列 ;
相当于一个多重集
S
′
=
{
r
⋅
1
,
(
k
−
1
)
⋅
0
}
S' = \{ r \cdot 1 , (k-1) \cdot 0 \}
S′={r⋅1,(k−1)⋅0} 的全排列 ;
这里就将 多重集的组合问题 , 转化成了 另外一个多重集的全排列问题 , 多重集全排列是有公式的 ;
多重集全排列的公式是 : ( 回顾知识点 ① )
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≤+∞
★ 全排列 :
r
=
n
1
+
n
2
+
⋯
+
n
k
=
n
r = n_1 + n_2 + \cdots + n_k = n
r=n1+n2+⋯+nk=n
N
=
n
!
n
1
!
n
2
!
⋯
n
k
!
N = \cfrac{n!}{n_1! n_2! \cdots n_k!}
N=n1!n2!⋯nk!n!
★ 多重集的全排列数是 元素总数阶乘 , 除以 所有重复度的阶乘 ;
参考 : 【组合数学】排列组合 ( 多重集排列 | 多重集全排列 | 多重集非全排列 所有元素重复度大于排列数 | 多重集非全排列 某些元素重复度小于排列数 ) 二、多重集全排列
( 回顾知识点完毕 ① )
可以根据上述公式 , 计算 多重集
S
′
=
{
r
⋅
1
,
(
k
−
1
)
⋅
0
}
S' = \{ r \cdot 1 , (k-1) \cdot 0 \}
S′={r⋅1,(k−1)⋅0} 的全排列 , 结果是 :
N
=
(
r
+
k
−
1
)
!
r
!
(
k
−
1
)
!
N = \cfrac{(r + k - 1) !}{ r! (k-1)! }
N=r!(k−1)!(r+k−1)!
★ 排列数与组合数回顾 : ( 回顾知识点 ② )
- 排列数 :
n
n
n 元集S
S
S , 从S
S
S 集合中 有序 , 不重复 选取r
r
r 个元素 ,P
(
n
,
r
)
=
n
!
(
n
−
r
)
!
P(n,r) = \dfrac{n!}{(n-r)!}
P(n,r)=(n−r)!n! - 组合数 :
n
n
n 元集S
S
S , 从S
S
S 集合中 无序 , 不重复 选取r
r
r 个元素 ,C
(
n
,
r
)
=
P
(
n
,
r
)
r
!
n
!
(
n
−
r
)
!
r
!
C(n,r) = \dfrac{P(n,r)}{r!} \dfrac{n!}{(n-r)!r!}
C(n,r)=r!P(n,r)(n−r)!r!n!
参考 : 【组合数学】排列组合 ( 排列组合内容概要 | 选取问题 | 集合排列 | 集合组合 )
( 回顾知识点完毕 ② )
由上述的组合数可以看出 ,
N
=
(
r
+
k
−
1
)
!
r
!
(
k
−
1
)
!
N = \cfrac{(r + k - 1) !}{ r! (k-1)! }
N=r!(k−1)!(r+k−1)!
的值正好是从
r
+
k
−
1
r + k - 1
r+k−1 个元素中取
r
r
r 个元素的组合数 ;
N
=
(
r
+
k
−
1
)
!
r
!
(
k
−
1
)
!
=
C
(
r
+
k
−
1
,
r
)
N = \cfrac{(r + k - 1) !}{ r! (k-1)! } = C(r + k - 1 , r)
N=r!(k−1)!(r+k−1)!=C(r+k−1,r)
