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