组合公式及证明
别妄想泡我
684次浏览
2021年01月29日 15:58
最佳经验
本文由作者推荐
调研报告的格式-与天气有关的谚语
第十讲组合恒等式
一、知识概要
数学竞赛中组合数计算和组合恒等式的证明，是以高中排列、组合、二项式定理为基础
, 并加以推广
和补充而形成的一类习题，它往往会具有一定的难度且灵活性较强。解决这类问
题常常对学生良好的运算
能力和思维的灵活性都有较高的要求。同时，此类问题的解决也有
着自身特殊的解题技巧。因此，在各类
数学竞赛中经常被采用。
1
,
基本的组合恒等式
简单的组合恒等式的化简和证明，可以直接运用课本所学的基本组合恒等式。事实上，
许多竞赛中出
现的较复杂的组合数记算或恒等式证明，也往往运用这些基本组合恒等式，通
过转化，分解为若干个简单
的组合恒等式而加以解决。课本中的组合恒等式有：
①
c
n
c
；
r
；
②
c
n;
c
n
1
c
n
；
k
k 1
③
kC
n
nC
n 1
；
r m
④
C
nG
C
C
m_ r
n
n
⑤
C
0
c
n
C
；
L
C
n
n
2
n
；
⑥
C
0
c
n
C
n
2
L 1
n
C
n
n
0.
2
,
解题中常用方法
①
运用基本组合恒等式进行变换；
②
运用二项展开式作为辅助函数，通过比较某项的系数进行计算或证明
;
③
运用数学归纳法；
④
变换求和指标；
⑤
运用赋值法进行证明；
⑥
建立递推公式，由初始条件及递推关系进行计算和证明；
⑦构造合理的模型。
二、运用举例
12
3
n
例
1
，求证：
C
n
2C
n
3C
n
L nC
n
n
2
n1
证明：根据前面提到的基本的组合恒等式第三条
,
可得
:
0
1 2
n 1
左边
nC
n 1
nC
n 1
nC
n 1
nC
；
；
n 2
右边
n
例
2
,
求和式
k
2
C
n
k
的值。
k 1
基本思路：将
k
2
C
；
改写为
k
kCn
k
先将
kC
n
用恒等式
3
提取公因式
成为
k 1 Cn
k 1
1
1
C
；
1
1
，而
C
n 1
又可以继续运用上述恒等变形
,
中均不含有变动指标
k
了。
n
n
解：
k
2
C
：
kC
k nC
：
1
C
k 1
：
k 1
：
Cn 1
1
C
：
n
C
k 2
n 2
C
：
1
Cn
k 2
n2
n
2
n
2004
例
3
，求
k
2005
的
值。
2004
解：
k
2004
2005
C
2004
2005
C
；
004
C
；
004
C
；
C
；
I
1
2004
004
004
C
c
2003
2004
1
k
n
，然后再将
kC
n 1
变形
这样就使得各项系数
1 C
n
k
1
C
：
n
k 1
C
n 1
k 1
C
2004
2004
n 1
例
4
,
设
m,n N
，求证：
m k m k 1
k 0
-3m 3mn n 1
。
3
2
2 2
基本思路
由两个连续自然数
m k
与
m k 1
的积，联想到可化为
2C
m k 1
，进一步运用
C
：
C
；
1
n 1
证明：
k
0
C
：
：
k
C
：
1
C
r 1
L
C
：
k
，反复运用基本的组合恒等式
2
即可化简。
m
k m k
1
2 c
m1
C
m 2
L
c
2
m n
；
C
；
C
；
C
；
L C
；
2
C
；
2
C
L
C
C
m 1
L
c
m
c
c
m n
2
3
3
c
n
3m
2
3mn
n
2
1
2
c
mn
1
m 1
3
m
n
m n
1
例
5
,
当
m n
时，求证
r
1
c
n
c
r
m
0
m n
4
化简原式左边各项，使得化简后仅有
基本思路：利用基本组合恒等式
；
c
m
；
c
；
m
中含有变动指标
n
时，原式左边
证明
:
显然，当
m
n
时，利用基本组合恒等式
1
r
m r m
c
n
c
n m
左边
c
m
r
n
n
r
C
：
m
m
1
m
c
m
c
m
4
可得
:
。只要令
原式即可变为
:
c
m
r m
C
n m
C
n
C
k
k
n m
1 c
n
m m
m
1 C
；
m
k k
0
。即原式成立。
说明：变换求和指标是解决较复杂的组合记数的一种常见技巧，它可以起到简化计算的目的。
变换求和指标时，要注意
求和指标的上、下限需要同时变换。
n
例
6
,
求证：
C
；
n
2
2n 1
2n !
2 n! n!
。
k 0
k 0
k n 1
k n 1