组合恒等式参考博客 :
回顾四个变下项求和的组合恒等式 : 之前介绍的组合恒等式 中的组合数
, 是下项
一直在累加改变 , 具有
累加性质 , 上项
是不变的 ;
( 1 ) 简单和 :
( 2 ) 交错和 :
( 3 ) 变下项求和 3 :
( 4 ) 变下项求和 4 :
变上项求和 1 :
上述公式中 , 组合数
中 , 下项
是不变的 , 上项
一直是改变的 , 其取值范围是
~
;
该表达式中有若干项都是
:
时 ,
, 从
个元素中选取
个元素 , 没有方案 ;
时 ,
;
时 ,
才为大于
的值 ;
1 . 证明方法 : 之前使用过两种证明方法 , ① 二项式定理 + 求导 , ② 使用现有组合恒等式推导 ;
在这里使用第三类证明方法 , ③ 组合分析 , 组合分析方法是要构造一个组合计数问题 , 左边和右边都是同一个计数问题的解 ;
2 . 组合分析方法使用 : 使用组合分析方法证明组合数时 , 先指定集合 , 指定元素 , 指定两个计数问题 , 公式两边是对同一个问题的计数 ;
指定计数问题 : 下面两个计数问题都是同一个问题的计数 ;
3 . 组合分析方法使用总结 : 使用组合分析方法证明组合数时 , 先指定集合 , 指定元素 , 指定两个计数问题 , 公式两边是对同一个问题的计数 ;
现在开始构造选取问题 :
1 . 指定集合 : 假定有
个元素的集合 , 记作
,
2 . 指定等号右侧的计数问题 : 从上述集合
中 , 选取
个元素的子集 , 选择方法的个数是
个 ;
3 . 指定等号左侧的计数问题 : 等号左侧是
;
计数问题类型确定 ( 分类选取 ) : 组合式中存在 和号
, 说明该计数问题采用了 分类计数原理 , 对应加法法则 ; 该计数问题肯定是分类选取 ;
集合 , 从
个元素中选取
个元素 ;
( 1 ) 第
类 , 指定某个特定元素
, 在子集中必须含有
, 则只能从剩余的
个元素中选取
个 , 方案数是
;
( 2 ) 第
类 , 与 第
类不重叠 ,
不含
, 但是必须含有
,
不含
那就要从
个元素中选取 ( 从
个元素中去掉一个 ) ,
必须含有
( 从
个元素中再去掉一个, 即
个 ) , 那么就要从
个元素中选取
个元素 ,
最终结果是
( 3 ) 第
类 , 与 第
类不重叠 ,
不含
, 但是必须含有
,
不含
那就要从
个元素中选取 ( 从
个元素中去掉
个 , 即
) ,
必须含有
( 从
个元素中再去掉一个, 即
个 ) , 那么就要从
个元素中选取
个元素 ,
最终结果是
( 4 ) 第
类 , 与 第
类不重叠 ,
不含
, 但是必须含有
,
不含
那就要从
个元素中选取 ( 从
个元素中去掉
个 , 即
) ,
必须含有
( 从
个元素中再去掉一个, 即
个 ) , 那么就要从
个元素中选取
个元素 ,
最终结果是
5 . 在上述两个计数问题都是同一个计数问题 , 都是从
个元素中选取
个元素 ;