IDEA激活码
文章目录
- 一、组合恒等式回顾 ( 8个 )
- 二、组合恒等式 ( 积 )
- 三、组合恒等式 ( 积 ) 证明
- 四、组合恒等式 ( 积 ) 用途 、求组合数通用方法
组合恒等式参考博客 :
- 【组合数学】组合恒等式 ( 递推 组合恒等式 | 变下项求和 组合恒等式 简单和 | 变下项求和 组合恒等式 交错和 )
- 【组合数学】组合恒等式 ( 变下项求和 3 组合恒等式 | 变下项求和 4 组合恒等式 | 二项式定理 + 求导 证明组合恒等式 | 使用已知组合恒等式证明组合恒等式 )
一、组合恒等式回顾 ( 8个 )
1 . 组合恒等式 ( 递推式 ) :
( 1 ) 递推式 1 :
(
n
k
)
=
(
n
n
−
k
)
\dbinom{n}{k} = \dbinom{n}{n-k}
(kn)=(n−kn)
( 2 ) 递推式 2 :
(
n
k
)
=
n
k
(
n
−
1
k
−
1
)
\dbinom{n}{k} = \dfrac{n}{k} \dbinom{n - 1}{k - 1}
(kn)=kn(k−1n−1)
( 3 ) 递推式 3 ( 帕斯卡 / 杨辉三角公式 ) :
(
n
k
)
=
(
n
−
1
k
)
+
(
n
−
1
k
−
1
)
\dbinom{n}{k} = \dbinom{n - 1}{k} + \dbinom{n - 1}{k - 1}
(kn)=(kn−1)+(k−1n−1)
2 . 回顾四个变下项求和的组合恒等式 : 之前介绍的组合恒等式 中的组合数
(
n
k
)
\dbinom{n}{k}
(kn) , 是下项
k
k
k 一直在累加改变 , 具有
∑
k
=
0
n
\sum\limits_{k=0}^{n}
k=0∑n 累加性质 , 上项
n
n
n 是不变的 ;
( 1 ) 简单和 :
∑
k
=
0
n
(
n
k
)
=
2
n
\sum\limits_{k=0}^{n}\dbinom{n}{k} = 2^n
k=0∑n(kn)=2n
( 2 ) 交错和 :
∑
k
=
0
n
(
−
1
)
k
(
n
k
)
=
0
\sum\limits_{k=0}^{n} (-1)^k \dbinom{n}{k} = 0
k=0∑n(−1)k(kn)=0
( 3 ) 变下项求和 3 :
∑
k
=
0
n
k
(
n
k
)
=
n
2
n
−
1
\sum\limits_{k=0}^{n} k \dbinom{n}{k} = n 2^{n-1}
k=0∑nk(kn)=n2n−1
( 4 ) 变下项求和 4 :
∑
k
=
0
n
k
2
(
n
k
)
=
n
(
n
+
1
)
2
n
−
2
\sum_{k=0}^{n} k^2 \dbinom{n}{k} = n ( n+1 ) 2^{n-2}
∑k=0nk2(kn)=n(n+1)2n−2
3 . 变上项求和 :
∑
l
=
0
n
(
l
k
)
=
(
n
+
1
k
+
1
)
\sum\limits_{l=0}^{n} \dbinom{l}{k} = \dbinom{n + 1}{k + 1}
l=0∑n(kl)=(k+1n+1)
二、组合恒等式 ( 积 )
组合恒等式 ( 积 ) :
(
n
r
)
(
r
k
)
=
(
n
k
)
(
n
−
k
r
−
k
)
\dbinom{n}{r}\dbinom{r}{k} = \dbinom{n }{k}\dbinom{n-k}{r-k}
(rn)(kr)=(kn)(r−kn−k)
三、组合恒等式 ( 积 ) 证明
1 .
(
n
r
)
(
r
k
)
\dbinom{n}{r}\dbinom{r}{k}
(rn)(kr) 组合数解析 : 这是两个组合数的乘法 , 使用的是 分步计数原理 , 对应乘法法则 ;
( 1 ) 第一步 :
(
n
r
)
\dbinom{n}{r}
(rn) 从
n
n
n 个元素中选择
r
r
r 个元素 ;
( 2 ) 第二步 :
(
r
k
)
\dbinom{r}{k}
(kr) 从
r
r
r 个元素中选择
k
k
k 个元素 ;
2 . 上述选择可能会存在重复的情况 , 以下反例可以证明 :
集合
S
=
{
a
,
b
,
c
,
d
,
e
}
S = \{ a, b, c, d, e \}
S={a,b,c,d,e} , 从该集合
S
S
S 中选择
4
4
4 个元素 , 举两个栗子 :
①
{
a
,
b
,
c
,
d
}
\{a, b, c, d\}
{a,b,c,d} , 有子集
{
b
,
c
,
d
}
\{ b,c,d \}
{b,c,d}
②
{
b
,
c
,
d
,
e
}
\{ b,c,d,e \}
{b,c,d,e} , 有子集
{
b
,
c
,
d
}
\{ b,c,d \}
{b,c,d}
这样从
5
5
5 个元素中选择
4
4
4 个 , 然后从
4
4
4 个元素中选择
3
3
3 个 , 最后 出现了选择重复子集的情况 , 有两个重复的
{
b
,
c
,
d
}
\{ b,c,d \}
{b,c,d} ;
3 .
(
n
k
)
(
n
−
k
r
−
k
)
\dbinom{n }{k}\dbinom{n-k}{r-k}
(kn)(r−kn−k) 组合数解析 :
(
n
k
)
\dbinom{n }{k}
(kn) 表示 从
n
n
n 个元素中 , 直接选出
k
k
k 个元素出来 , 查看有多少种方法 ; 栗子 : 上述
5
5
5 元集中直接选择
3
3
3 元素子集的个数 ;
(
n
−
k
r
−
k
)
\dbinom{n-k}{r-k}
(r−kn−k) 是 上述选择方法的重复度 , 每个选择方法会出现多少次 ; 栗子 : 计算上述每个
3
3
3 元素子集选择方案的重复次数 ;
4 . 下面开始研究上述
(
n
−
k
r
−
k
)
\dbinom{n-k}{r-k}
(r−kn−k) 重复度是如何计算出来的
以上面的栗子为例 ,
3
3
3 子集
{
b
,
c
,
d
}
\{ b,c,d \}
{b,c,d} 出现两次的原因是 ,
在
4
4
4 子集
{
a
,
b
,
c
,
d
}
\{a, b, c, d\}
{a,b,c,d} 和
{
b
,
c
,
d
,
e
}
\{ b,c,d,e \}
{b,c,d,e} 都包含同样的
3
3
3 子集
{
b
,
c
,
d
}
\{ b,c,d \}
{b,c,d} ,
在上述
4
4
4 子集中 , 除了
3
3
3 子集之外 , 有其它的添加元素 ,
- 在
{
a
,
b
,
c
,
d
}
\{a, b, c, d\}
{a,b,c,d} 中 , 添加了a
a
a 元素 - 在
{
b
,
c
,
d
,
e
}
\{b,c,d,e\}
{b,c,d,e} 中 , 添加了e
e
e 元素
在
3
3
3 子集中 , 添加不同的元素 , 就可以变成 不同的
4
4
4 子集 , 这里直接求该
3
3
3 子集有多少种添加方法 , 构成
4
4
4 子集的个数 ;
添加的元素是从 原有
S
=
{
a
,
b
,
c
,
d
,
e
}
S = \{ a, b, c, d, e \}
S={a,b,c,d,e} 集合中 , 除掉
{
b
,
c
,
d
}
\{ b,c,d \}
{b,c,d}
3
3
3 子集后的元素中选取的 ,
选取集合有
5
−
3
=
2
5-3 = 2
5−3=2 个元素 ( 相当于公式
n
−
k
n-k
n−k ) ,
选取的个数就是
4
−
3
=
1
4-3=1
4−3=1 个 ( 相当于公式
r
−
k
r-k
r−k ) ;
从
n
−
k
n-k
n−k 个元素中选择
r
−
k
r-k
r−k 个元素 , 方案数为
(
n
−
k
r
−
k
)
\dbinom{n-k}{r-k}
(r−kn−k) ;
5 .
(
n
r
)
(
r
k
)
=
(
n
k
)
(
n
−
k
r
−
k
)
\dbinom{n}{r}\dbinom{r}{k} = \dbinom{n }{k}\dbinom{n-k}{r-k}
(rn)(kr)=(kn)(r−kn−k) 的左右两边都是对同一个组合数的计数结果 , 因此是相等的
四、组合恒等式 ( 积 ) 用途 、求组合数通用方法
组合恒等式 ( 积 ) :
(
n
r
)
(
r
k
)
=
(
n
k
)
(
n
−
k
r
−
k
)
\dbinom{n}{r}\dbinom{r}{k} = \dbinom{n }{k}\dbinom{n-k}{r-k}
(rn)(kr)=(kn)(r−kn−k)
遇到
(
n
r
)
(
r
k
)
\dbinom{n}{r}\dbinom{r}{k}
(rn)(kr) 先乘积 , 再求和的情况 , 如果求和是对
r
r
r 求和的话 , 即
∑
r
=
0
n
\sum\limits_{r=0}^{n}
r=0∑n , 如下 :
对
∑
r
=
k
n
(
n
r
)
(
r
k
)
\sum\limits_{r=k}^{n}\dbinom{n}{r}\dbinom{r}{k}
r=k∑n(rn)(kr) 求和 ;
对
r
r
r 求和 ,
r
r
r 是从
k
k
k 一直到
n
n
n ,
前面的项
(
n
r
)
\dbinom{n}{r}
(rn) 下项是变量 ,
后面的项
(
r
k
)
\dbinom{r}{k}
(kr) 上项是变量 ,
之前的通用方法 : 这就无法使用之前的计算方法了 , 之前的计算方法是 , 常量向
∑
\sum
∑ 符号外面提取 , 剩下的转变成 基本求和式
∑
k
=
0
n
(
n
k
)
=
2
n
\sum\limits_{k=0}^{n}\dbinom{n}{k} = 2^n
k=0∑n(kn)=2n , 或已知的 组合恒等式 , 组合公式 , 进行化简 ;
处理的情况 : 两个组合数 , 一个是下项是累加变量 , 一个是上项是累加变量 , 两个组合数相乘 的情况 ;
上述 积组合恒等式可以将上述情况改变成 下项 是累加变量的情况 ;
这里使用上述 积组合恒等式 , 转变为 :
∑
r
=
k
n
(
n
r
)
(
r
k
)
=
∑
r
=
k
n
(
n
k
)
(
n
−
k
r
−
k
)
\sum\limits_{r=k}^{n}\dbinom{n}{r}\dbinom{r}{k} = \sum\limits_{r=k}^{n} \dbinom{n }{k}\dbinom{n-k}{r-k}
r=k∑n(rn)(kr)=r=k∑n(kn)(r−kn−k)
得到上述公式后 , 分析得到的项
∑
r
=
k
n
(
n
k
)
(
n
−
k
r
−
k
)
\sum\limits_{r=k}^{n} \dbinom{n }{k}\dbinom{n-k}{r-k}
r=k∑n(kn)(r−kn−k) ,
前面的
(
n
k
)
\dbinom{n }{k}
(kn) 项与 求和变量
r
r
r 无关 ,
后面的
(
n
−
k
r
−
k
)
\dbinom{n-k}{r-k}
(r−kn−k) 下项与 求和变量
r
r
r 相关 ;
因此
(
n
k
)
\dbinom{n }{k}
(kn) 项 可以提取到
∑
\sum
∑ 符号外面 ;
=
(
n
k
)
∑
r
=
k
n
(
n
−
k
r
−
k
)
=\dbinom{n }{k} \sum\limits_{r=k}^{n} \dbinom{n-k}{r-k}
=(kn)r=k∑n(r−kn−k)
上述式子就可以进行 变限 , 代换计算了 ; 使用
r
′
=
r
−
k
r' = r-k
r′=r−k 替换
r
r
r ;
原来
r
r
r 的取值范围是
k
k
k ~
n
n
n , 则
r
′
=
r
−
k
r' = r-k
r′=r−k 的取值范围是
0
0
0 ~
n
−
k
n-k
n−k , 代换结果如下 :
=
(
n
k
)
∑
r
′
=
0
n
−
k
(
n
−
k
r
′
)
=\dbinom{n }{k} \sum\limits_{r'=0}^{n - k} \dbinom{n-k}{r'}
=(kn)r′=0∑n−k(r′n−k)
根据 基本求和式
∑
k
=
0
n
(
n
k
)
=
2
n
\sum\limits_{k=0}^{n}\dbinom{n}{k} = 2^n
k=0∑n(kn)=2n , 计算
∑
r
′
=
0
n
−
k
(
n
−
k
r
′
)
\sum\limits_{r'=0}^{n - k} \dbinom{n-k}{r'}
r′=0∑n−k(r′n−k) 的结果为
2
n
−
k
2^{n-k}
2n−k ; 最终的计算结果为 :
=
(
n
k
)
∑
r
′
=
0
n
−
k
(
n
−
k
r
′
)
=
2
n
−
k
(
n
k
)
=\dbinom{n }{k} \sum\limits_{r'=0}^{n - k} \dbinom{n-k}{r'} = 2 ^{n-k}\dbinom{n }{k}
=(kn)r′=0∑n−k(r′n−k)=2n−k(kn)
