IDEA激活码
文章目录
- 一、组合恒等式 ( 积之和 ) 1
- 二、组合恒等式 ( 积之和 ) 1 证明
- 三、组合恒等式 ( 积之和 ) 2
- 四、组合恒等式 ( 积之和 ) 2 证明
组合恒等式参考博客 :
- 【组合数学】组合恒等式 ( 递推 组合恒等式 | 变下项求和 组合恒等式 简单和 | 变下项求和 组合恒等式 交错和 )
- 【组合数学】组合恒等式 ( 变下项求和 3 组合恒等式 | 变下项求和 4 组合恒等式 | 二项式定理 + 求导 证明组合恒等式 | 使用已知组合恒等式证明组合恒等式 )
- 【组合数学】组合恒等式 ( 八个组合恒等式回顾 | 组合恒等式 积 1 | 证明 | 使用场景 )
一、组合恒等式 ( 积之和 ) 1
组合恒等式 ( 积之和 ) 1 :
∑
k
=
0
r
(
m
k
)
(
n
r
−
k
)
=
(
m
+
n
r
)
,
r
=
min
{
m
,
n
}
\sum\limits_{k=0}^{r}\dbinom{m}{k}\dbinom{n}{r-k} = \dbinom{m + n }{r} , \ \ \ \ \ \ r= \min \{ m, n \}
k=0∑r(km)(r−kn)=(rm+n), r=min{m,n}
二、组合恒等式 ( 积之和 ) 1 证明
1 . 组合分析方法使用 : 使用组合分析方法证明组合数时 , 先指定集合 , 指定元素 , 指定两个计数问题 , 公式两边是对同一个问题的计数 ;
( 1 ) 指定集合 : 指定计数是在什么样的集合中产生的 ;
( 2 ) 指定计数问题 : 下面两个计数问题都是同一个问题的计数 ;
- ① 问题 1 : 等号左侧代表的计数问题 ;
- ② 问题 2 : 等号右侧代表的计数问题 ;
( 3 ) 等价说明 : 说明两个计数问题是同一个问题 ;
2 . 使用 组合分析 的方法进行证明 :
( 1 ) 指定集合 : 定义两个集合 ,
A
=
{
a
1
,
a
2
,
⋯
,
a
m
}
A = \{ a_1, a_2 , \cdots , a_m \}
A={a1,a2,⋯,am}
B
=
{
b
1
,
b
2
,
⋯
,
b
n
}
B = \{ b_1, b_2 , \cdots , b_n \}
B={b1,b2,⋯,bn}
( 2 ) 指定等号右边的计数 :
(
m
+
n
r
)
\dbinom{m + n }{r}
(rm+n) 代表 如下计数 :
从这 两个集合的
m
+
n
m + n
m+n 个元素中 , 选取
r
r
r 个元素 , 这样就构造了一个选取问题 ;
( 3 ) 指定等号左边的计数 :
等号左边的 组合数
∑
k
=
0
r
(
m
k
)
(
n
r
−
k
)
\sum\limits_{k=0}^{r}\dbinom{m}{k}\dbinom{n}{r-k}
k=0∑r(km)(r−kn) 计数分析 :
先分类 后 分步 : 上述式子中 , 有乘积 , 有求和 , 说明这是 先分类 ( 加法法则 ) , 每个分类中使用 分步 ( 乘法法则 ) 计算 ;
按照 从两个集合中 选出的
r
r
r 个子集中 , 含有多少个
A
=
{
a
1
,
a
2
,
⋯
,
a
m
}
A = \{ a_1, a_2 , \cdots , a_m \}
A={a1,a2,⋯,am} 集合中的元素进行分类 ,
含有
A
A
A 中的元素
k
k
k 个 ,
剩下的
r
−
k
r-k
r−k 元素取自
B
=
{
b
1
,
b
2
,
⋯
,
b
n
}
B = \{ b_1, b_2 , \cdots , b_n \}
B={b1,b2,⋯,bn} 集合 ;
分步处理的逻辑是 : 先在
A
A
A 集合中选择
k
k
k 个元素 , 然后在
B
B
B 集合中选择
r
−
k
r-k
r−k 个元素 ;
因此
k
k
k 最多取
r
r
r 个 ( 全部从
A
A
A 集合中取 ) , 最少取
0
0
0 个 ( 全部从
B
B
B 集合中取 ) ;
( 4 ) 上述等式左右两边的计数是同一个计数 , 都是在 两个集合中取
r
r
r 个元素的方案数 ;
三、组合恒等式 ( 积之和 ) 2
组合恒等式 ( 积之和 ) 2 :
∑
k
=
0
r
(
m
k
)
(
n
k
)
=
(
m
+
n
m
)
\sum\limits_{k=0}^{r}\dbinom{m}{k}\dbinom{n}{k} = \dbinom{m + n }{m}
k=0∑r(km)(kn)=(mm+n)
四、组合恒等式 ( 积之和 ) 2 证明
该公式是 “组合恒等式 ( 积之和 ) 1” 的特例情况 ,
证明了上述 “组合恒等式 ( 积之和 ) 1” 公式后 , 本公式是上述公式的推论 ;
在 “组合恒等式 ( 积之和 ) 1” 公式
∑
k
=
0
r
(
m
k
)
(
n
r
−
k
)
=
(
m
+
n
r
)
,
r
=
min
{
m
,
n
}
\sum\limits_{k=0}^{r}\dbinom{m}{k}\dbinom{n}{r-k} = \dbinom{m + n }{r} , \ \ \ \ \ \ r= \min \{ m, n \}
k=0∑r(km)(r−kn)=(rm+n), r=min{m,n}
中 , 令
r
=
n
r=n
r=n , 就变成公式
∑
k
=
0
n
(
m
k
)
(
n
n
−
k
)
=
(
m
+
n
n
)
\sum\limits_{k=0}^{n}\dbinom{m}{k}\dbinom{n}{n-k} = \dbinom{m + n }{n}
k=0∑n(km)(n−kn)=(nm+n)
(
n
n
−
k
)
\dbinom{n}{n-k}
(n−kn) 与
(
n
k
)
\dbinom{n}{k}
(kn) 是等价的 , 因此公式可以变成 :
∑
k
=
0
n
(
m
k
)
(
n
k
)
=
(
m
+
n
n
)
=
(
m
+
n
n
)
\sum\limits_{k=0}^{n}\dbinom{m}{k}\dbinom{n}{k} = \dbinom{m + n }{n} =\dbinom{m + n }{n}
k=0∑n(km)(kn)=(nm+n)=(nm+n)
因此 “组合恒等式 ( 积之和 ) 2” 是 “组合恒等式 ( 积之和 ) 1” 的一个特例情况 ;
