当前位置:首页 >> 学科竞赛 >>

高二数学竞赛班讲义 第五讲 组合恒等式


高二数学竞赛班二试 第五讲 组合恒等式
班级 姓名

一、知识要点:
数学竞赛中组合数计算和组合恒等式的证明, 是以高中排列、 组合、 二项式定理为基础, 并加以推广和补充而形成的一类习题, 它往往会具有一定的难度且灵活性较强。 解决这类问 题常常对学生良好的运算能力和思维的灵活性都有较高的要求。 同时, 此类问题的解决也有 着自身特殊的解

题技巧。因此,在各类数学竞赛中经常被采用。 1.基本的组合恒等式 简单的组合恒等式的化简和证明,可以直接运用课本所学的基本组合恒等式。事实上, 许多竞赛中出现的较复杂的组合数记算或恒等式证明, 也往往运用这些基本组合恒等式, 通 过转化,分解为若干个简单的组合恒等式而加以解决。课本中的组合恒等式有:
r n ①Cn ? Cn ?r ; r ?1 r r ②Cn?1 ? Cn ?1 ? Cn ;

k k ?1 ③kCn ? nCn?1 ;
r m r ?m ④Cn Crm ? Cn Cn?m ;

0 1 2 n ⑤Cn ? Cn ? Cn ? ?? Cn ? 2n ;
0 1 2 n ⑥Cn ? Cn ? Cn ? ? ? ? ?1? Cn ? 0. n

2.解题中常用方法 ① 运用基本组合恒等式进行变换; ② 运用二项展开式作为辅助函数,通过比较某项的系数进行计算或证明; ③ 运用数学归纳法; ④ 变换求和指标; ⑤ 运用赋值法进行证明; ⑥ 建立递推公式,由初始条件及递推关系进行计算和证明; ⑦ 构造合理的模型。

二、经典例题
1 2 3 n 例 1.求证: Cn ? 2Cn ? 3Cn ? ?? nCn ? n ? 2n?1 .

例 1.证明:根据前面提到的基本的组合恒等式第三条,可得:
0 1 2 n?1 左边 ? nCn?1 ? nCn?1 ? nCn?1 ? ?? nCn?1 ? n ? 2n?1 ? 右边
n

例 2.求和式

?k C
2 k ?1

k n

的值。
k ?1

例 2. 基本思路: k Cn 改写为 k ? kCn , 将 先将 kCn 用恒等式 3 提取公因式 n , 然后再将 kCn ?1
2 k k
k

变形成为 ? k ?1? Cn?1 ? Cn?1 ,而 ? k ? 1? Cn?1 又可以继续运用上述恒等变形,这样就使得各
k ?1 k ?1 k ?1

项系数中均不含有变动指标 k 了。

1

解:

? k 2Cnk ? ? k ? kCnk ? ? k ? nCnk??11 ? n? k ? Cnk??11 ? n? ? k ? 1 ? 1? ? Cnk??11
k ?1 k ?1 k ?1 k ?1 k ?1 k ?1 k ?1 k ?2 k ?1 ? n? ?? k ? 1? ? Cn?1 ? Cn?1 ? ?n? ?? n ? 1? ? Cn?2 ? Cn?1 ? ? ? ? ? k ?1 k ?1 n n

n

n

n

n

n

n n n ? n k ?2 k ?1 ? k ?2 k ?1 ? n ?? ? n ? 1? ? Cn?2 ? ? Cn?1 ? ? n ? n ? 1? ? Cn?2 ? n? Cn?1 k ?1 k ?2 k ?1 ? k ?2 ?

? n ? n ?1? 2n?2 ? n2n?1 ? n ? n ?1? 2n?2
2004

例 3.求

? ? ?1?
k ?0

k

k C2005 的值。

2004

例 3.解:

? ? ?1?
k ?0

k

k 1 2 C2005 ? 1 ? C2005 ? C2005 ? ? ? ? ?1?

2004

2004 C2005

0 1 1 2 ? 1 ? ? C2004 ? C2004 ? ? ? C2004 ? C2004 ? ? ? ? ? ?1?

2004

?C

2003 2004

2004 ? C2004 ?

?1 。
例 4.设 m, n ? N ,求证:
?

? ? m ? k ?? m ? k ? 1? ? 3 ?3m
n
k ?0

n ?1

2

? 3mn ? n 2 ? 1? 。
2

例 4.基本思路:由两个连续自然数 m ? k 与 m ? k ? 1 的积,联想到可化为 2Cm? k ?1 ,进一 步运用
?1 Crr ? Crr?1 ??? Crr?k ? Crr?1 ? Crr?1 ? ?? Crr?k ,反复运用基本的组合恒等式 2 即可化简。

证明:

? ? m ? k ?? m ? k ? 1? ? 2 ?C
k ?0

n ?1

2 m ?1

2 2 ? Cm? 2 ? ? ? Cm? n ?

2 2 2 2 2 2 ? 2 ?? C2 ? C32 ? ? ? Cm ? Cm?1 ? ? ? Cm? n ? ? ? C2 ? C32 ? ? ? Cm ?? ? ?
3 3 ? 2 ? Cm? n ?1 ? Cm?1 ? ?

n ? 3m2 ? 3mn ? n2 ? 1? 3
n r r n m r

?? ?1?m ? 例 5.当 m ? n 时,求证 ? ? ?1? C C ? ? r ?m ?0 ?

?m ? n? ?m ? n?
r ?m

例 5.基本思路:利用基本组合恒等式 4 化简原式左边各项,使得化简后仅有 Cn?m 中含有 变动指标 r 。
m m 证明:显然,当 m ? n 时,原式左边 ? ? ?1? Cm Cm ? ? ?1? 。 m m

当 m ? n 时,利用基本组合恒等式 4 可得:

2

左边 ?

? ? ?1?
r ?m r

n

r

m r ?m m r ?m Cn Cn?m ? Cn ? ? ?1? Cn ?m 。只要令 r ? m ? k ,原式即可变为: r r ?m

n

m r ?m m Cn ? ? ?1? Cn?m ? Cn ? ? ?1? r ?m k ?0

n

n?m

m?k

k m k Cn?m ? ? ?1? Cn ? ? ?1? Cn?m ? 0 。即原式成立。 m k k ?0

n ?m

说明: 变换求和指标是解决较复杂的组合记数的一种常见技巧, 它可以起到简化计算的目的。 变换求和指标时,要注意求和指标的上、下限需要同时变换。 例 6.求证:

?C
k ?0
n k ?0

n

k 2n

? 22 n?1 ?
2n

? 2n ?!
2 ? n!? n!



例 6.证明:

? C2kn ?? C2kn ?
k ?0

k ? n ?1

?

2n

k C2 n ?22 n ?

k ? n ?1

?C

2n

k 2n

n? n? 2n ?22n ? ? C2 n 1 ? C2 n 2 ? ? ? C2 n ?

n? n? 0 k k n ? 22 n ? ? C2 n 1 ? C2 n 2 ? ? ? C2 n ? ? 22 n ? ? C2 n ? 22 n ? ? C2 n ? C2 n n k ?0 k ?0

n ?1

所以 2

?C
k ?0

n

k 2n

? 2 ? C , ?C ? 2
2n n 2n k ?0 k 2n

n

2 n ?1

n ? 2n ?! ? 右边。 C2n ? ? 22n?1 ? 2 2 ? n!? n!

例 7.求证: Cn

? ? ? ?C ?
0 2

1 2 n

n ? ? ? ? Cn ? ? 2

? 2n ? !
n !? n !

例 7.基本思路 1:此题若考虑用基本组合恒等式来证明是比较困难的,注意到左端各项恰 好是二项展开式中各项系数的平方,考虑构造两个二项展开式。 证明:因为: ?1 ? x ?
n

? 1? 0 1 1 n?1? ? C ? C x ? ? ? C x , ?1 ? ? ? Cn ? Cn ? ? ? Cn ? ? x ? x? ? x?
0 n 1 n n n n
n

n

n

? 1? 显然, ?1 ? x ? ? ?1 ? ? 的展开式中,常数项即为所求证等式的左端。不妨设 x ? 0 ,将原 ? x?
n

式变形为:

1 ? 1 ? 1 1 ? ? ?1 ? x ? ? ?1 ? ? ? ??1 ? x ? ?1 ? ? ? ? ? 2 ? x ? ? ? ? x ? ? 将 上 式 展 ? ? ? ? ? ? x? ? x? ? x? ? ? x ?? ?
n n n

n

2n

开,其中常数项为 C2 n ,由此可知,原式成立。 基本思路 2:注意到恒等式 Cn ? Cn
r n ?r

n

,要证的等式的左边可变形为:

0 n 1 n n 0 Cn Cn ? CnCn ?1 ? ? ? Cn Cn ;而等式右边即为:

? 2n ?! ?
n!? n!

? 2n ?! ? C n ,因此可以考 2n n!? ? 2n ? n ?!

虑建立适当的组合记数模型来加以证明。 证明:设袋子中有 n 个白球, n 个红球,现从这 2n 个小球中随机抽取 n 个小球,其方法种

3

数为:C2 n ?
n

? 2n ?! 。另一方面,可以看成 n ? 1 次如下的取球活动:从
n !? n !
r n?r 2

n 个白球中取出 r 个,

再从 n 个红球中取出 n ? r 个,其取法种数为: Cn Cn 题意的取球方法种数是: Cn

r ? ? Cn ? , r ? 0,1, 2,?, n ,所以符合

? ? ? ?C ?
0 2

1 2 n

n ? ? ? ? Cn ? 。因此原式成立。 2

说明:本题的两种证明方法均采用了构造思想。构造法是解决竞赛问题的一种常用方法。 例 8.求证:

? (?1)
k ?0

n

k

k ? 2 2 n?2 k C 2 n?k ?1 ? n ? 1.

k k k ?1 例 8. 【分析】考虑到恒等式 C2n?k ?1 ? C2n?k ? C2n?k ,
n

【证明】令 a n ?

? (?1)
k ?0

k

k ? 2 2 n ?2 k ? C 2 n?k ?1 ,

k k k ?1 因为, C2n?k ?1 ? C2n?k ? C2n?k ,
k 所以a n ? 2 2 n ? ? (?1) k ? 2 2 n ? 2 k C 2 n ? k ?1 k ?1 k k 1 ? 2 2 n ? ? (?1) k ? 2 2 n ? 2 k (C 2 n ? k ?C 2 n?? k ) k ?1 k k 1 ? ? (?1) k ? 2 2 n ? 2 k C 2 n ? k ? ? (?1) k ? 2 2 n ? 2 k C 2 n?? k . k ?0 k ?1 n n n n

令r ? k ? 1, 则

? (?1)
k ?1

n

k

k 1 r ? 2 2 n ? 2 k C 2 n?? k ? ? (?1) r ?1 ? 2 2( n ?1) ? 2 r C 2( n ?1) ? r ?1 r ?0 r ? ? ? (?1) r 2 2( n ?1) ? 2 r C 2( n ?1) ? r ?1 ? ?a n ?1 . r ?0 n ?1

n ?1



? (?1)
k ?0

n

k

k ? 2 2 n?2 k C 2 n?k ? bn , 则bn ? a n ? an?1
n ?1



k 又bn ? 2 2 n ? ? (?1) k ? 2 2 n ? 2 k C 2 n ? k ? (?1) n k ?1 k k ?1 ? 2 2 n ? ? (?1) k ? 2 2 n ? 2 k (C 2 n ? k ?1 ?C 2 n ? k ?1 ) ? (?1) n k ?1 n ?1

? 4a n ?1 ? ? (?1) j ? 2 2 ( n ?1) ? 2 j C 2j( n ?1) ? j
j ?0

n ?1

? 4a n ?1 ? bn ?1 .
于是由① 式得 bn?1 ? an?1 ? an?2 , 从而推知an ? an?1 ? 4an?1 ? an?1 ? an?2 ,即an ? an?2 ? 2an?1 . 这说明{an}为等差数列,而 a0=1,a1=2,故公差 d=1,且 an=n+1 .
4

【说明】此题运用变换求和指标的方法,找出了 an,an-1,an-2 之间的线性关系式,再由 初 始条件求得 an.这种利用递推关系求组合数的方法,在解决较复杂的计算或证明组事恒等式 时经常用到.

三、巩固练习 1.求证: Cn ?
m

n ? m ? 1 m ?1 Cn 。 m

1 2 3 4 n n 2.求证:当 n 是偶数时, 1 ? 2Cn ? Cn ? 2Cn ? Cn ? ?? 2Cn ?1 ? Cn ? 3 ? 2n?1 。

3.求证: Cn ?
0

1 1 1 1 1 2 1 3 1 2 n ?1 ?1 k k? Cn ? Cn ?11 ) Cn ? Cn ? Cn ? ? ? Cnn ? 。 (利用 k ?1 n ?1 2 3 4 n ?1 n ?1
2 n? 2

4.求

?C
k ?0

n ?1

k 2 n ?1

的值。 2 (



5.求证:

k ?m
n

?C C
k n
k ?1 k ?1 n

n

m k

x k ?1 ? x ?

n?k

m k m m k ?m (利用 Cn Ck ? Cn Cn?m ) ? Cn x m 。

6.求证:

?C
2n k ?0

k n? Cn ? C2 n 1. (利用 ?1 ? x ? ? ?1 ? x ? ?1 ? x ? )
2n n n

7.求证:

? ? ?1?

k

k 2 n CmCmn?k ? ? ?1? Cm . (利用 ?1 ? x 2 ? ? ?1 ? x ? ?1 ? x ? ) n
m m m

k 0 k 1 k 2 k k 0 8.求证: Cm?n ? CmCn ? CmCn ?1 ? CmCn ?2 ? ?? CmCn 。
k 9.求证: C2 m?1 是奇数,其中 k ? 1 。
2 n ?1

10.计算:

? ? ?1?
k ?1 n p ?1

k ?1

?

n?k 。 k C2 n
n ?1 ? n ? C2 n?1 。

11.求证:

? p ?C ?

p 2 n

12.求证:

? ?C
k ?0

?n? ?2? ? ?

k n

k ? Cn ?1 ? ? 2

1 n C2 n 。 n ?1

5

? n ?1? ? 2 ? ? ?

13.求证:

? n ? 2k ? 1 ? ? n Cnk ? ? n C2nn??12 。 ? k ?0 ?
2

6


相关文章:
数学奥赛辅导 第九讲 组合恒等式、组合不等式
竞赛数学中的组合恒等式是以高中排列组合,二项式定理...《中学数学信息网》系列资料 信息网》 WWW.ZXSX....数学奥赛辅导 第五讲 高... 数学奥赛辅导 第六讲...
高中数学竞赛讲义(免费)
高中数学竞赛讲义(免费)_高三数学_数学_高中教育_教育...问题 圆排列,有重复元素的排列与组合,组合恒等式。...第五章 数列 一、基础知识 定义 1 数列,按顺序给...
数学竞赛讲义组合1-6
组合恒等式 较为重要和有趣味的组合恒等式 四、抽屉原理与存在性问题 五、容斥...高二数学竞赛班讲义 第四... 8页 免费喜欢此文档的还喜欢 数学竞赛讲义:排列...
数学奥赛辅导_第九讲_组合恒等式、组合不等式
数学奥赛辅导知识、方法、技能Ⅰ.组合恒等式 第九讲 组合恒等式、组合不等式 竞赛数学中的组合恒等式是以高中排列组合、二项式定理为基础,加以推广、补充而形 ① ...
高二竞赛讲义 生成函数方法5
高二数学竞赛班二试讲义 第5讲一、知识点金 生成函数方法班级 姓名 1.生成函数...? 【评注】例 1 体现了生成函数方法证明组合恒等式的基本想法:针对恒等式的...
数学竞赛讲义组合计数
组合恒等式 较为重要和有趣味的组合恒等式 四、抽屉原理与存在性问题 五、容斥...高二数学竞赛班讲义 ... 8页 免费 高中数学竞赛讲义(18)组... 暂无评价 ...
组合数学-第四节:组合恒等式
组合数学-第四节:组合恒等式_数学_自然科学_专业资料。2.4.3 组合恒等式有关...数学竞赛辅导讲座:组合... 4页 免费 高二数学竞赛班讲义 第五... 6页 5...
高中数学奥赛辅导 第九讲 组合恒等式、组合不等式
数学奥赛辅导 第九讲 组合恒等式、组合不等式知识、方法、技能Ⅰ.组合恒等式 竞赛数学中的组合恒等式是以高中排列组合、二项式定理为基础,加以推广、补充而形成的 ...
高中数学竞赛资料收集
高中数学竞赛资料收集_学科竞赛_高中教育_教育专区。...《组合几何》 (单墫) *《几何不等式》(单墫的...现自己拿了 4 个二等奖的时候才不得不回班准备...
高二数学奥赛讲义
高二数学奥赛讲义_数学_高中教育_教育专区。高二数学...对于 n=2 的情形,可以用组合恒等式证明中的“贡献...例 2. 在一个班上,有 n(n ? 4) 名学生,在...
更多相关标签:
高中数学竞赛讲义 | 高中物理竞赛讲义 | 高中生物竞赛讲义 | 学而思物理竞赛讲义 | 蔡子星物理竞赛讲义 | 物理竞赛讲义 | 体育竞赛组织编排讲义 | 高中物理竞赛辅导讲义 |