组合恒等式参考博客 :
【组合数学】组合恒等式 ( 递推 组合恒等式 | 变下项求和 组合恒等式 简单和 | 变下项求和 组合恒等式 交错和 )【组合数学】组合恒等式 ( 变下项求和 3 组合恒等式 | 变下项求和 4 组合恒等式 | 二项式定理 + 求导 证明组合恒等式 | 使用已知组合恒等式证明组合恒等式 )一、组合恒等式回顾 ( 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}