组合公式及证明

一、 知识概要

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

简单的组合恒等式的化简和证明，可以直接运用课本所学的基本组合恒等式。事实上，许多竞赛中出现的较复杂的组合数记算或恒等式证明，也往往运用这些基本组合恒等式，通过转化，分解为若干个简单的组合恒等式而加以解决。课本中的组合恒等式有：

rnr①CnCn； r1r1r②Cn1CnCn； kk1③kCnnCn1； rmmrm④CnCrCnCnm； 012⑤CnCnCnnCn2n；

⑥CnCnCn2，解题中常用方法

012n1Cn0.

n① 运用基本组合恒等式进行变换；

② 运用二项展开式作为辅助函数，通过比较某项的系数进行计算或证明； ③ 运用数学归纳法； ④ 变换求和指标； ⑤ 运用赋值法进行证明；

⑥ 建立递推公式，由初始条件及递推关系进行计算和证明； ⑦ 构造合理的模型。

85

二、 运用举例

123例1，求证：Cn2Cn3CnnnCnn2n1.

证明：根据前面提到的基本的组合恒等式第三条，可得： 左边nCn1nCn1nCn1例2，求和式

012n1n1nCn右边 1n2kC2k1nkn的值。

2kkk基本思路：将kCn改写为kkCn，先将kCn用恒等式3提取公因式n，然后再将kCn1变形

k1成为k1Cn1Cn1，而k1Cn1又可以继续运用上述恒等变形，这样就使得各项系数

k1k1k1中均不含有变动指标k了。 解：

kC2k1nknkkCknCknk1k1nnk1n1nkCk1nnk1n1k1nk11Cn1

k1nnk1Ck1nk1n1Ck1n1k2k1nn1Cn2Cn1

k1nnnnk2k1k2k1nn1Cn2Cn1nn1Cn2nCn1

k1k2k1k2nn12n2n2n1nn12n2

2004例3，求

1k0kkkC2005的值。

2004解：

1k0k12C20051C2005C2005120042004C2005

1C2004C2004C2004C2004011212004C200320042004C2004

1 。

例4，设m,nN，求证：

mkmk1k0n1n3m23mnn21。 386

基本思路：由两个连续自然数mk与mk1的积，联想到可化为2Cmk1，进一步运用

2CrrCrr1n11rCrrkCrr1Cr1Crrk，反复运用基本的组合恒等式2即可化简。

2Cm22Cmn

证明：

mkmk12Ck02m1222CC3222CmCm1222CmCCn232Cm

332Cmn1Cm1nn3m23mnn21 3rmmn1rm 例5，当mn时，求证1CnCr

mnrm0基本思路：利用基本组合恒等式4化简原式左边各项，使得化简后仅有Cnm中含有变动指标

rmr。

证明：显然，当mn时，原式左边1CmCm1。

mmmm 当mn时，利用基本组合恒等式4可得： 左边n1rmrnrCCmnrmnmCmn1rmmknrrmCnm。只要令rmk，原式即可变为：

Cmn1rmCrmnmCmnnmk01Cknm1Cmmnnmk01kkCnm0。即原式成立。

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

C2kn22n1k0n2n!2n!n!k2n2n。

证明：

Ck0nk2nCk2nk02n2nkn1C2n2kn1C02n2nk2nn1n222nC2nC2n2nC2n

2C

n12nCn22nC22nknC2C2nC2n

k2n2nk0k0n1n87

所以，2Ck0nk2n2C,C22nn2nk2nk0n2n1n2n!C2n22n1右边。 22n!n!例7，求证：Cn021Cn2nCn22n!

n!n!基本思路1：此题若考虑用基本组合恒等式来证明是比较困难的，注意到左端各项恰好是二项展开式中各项系数的平方，考虑构造两个二项展开式。

01证明：因为：1xCnCnxn1nn011Cnx,1CnCnxxnn1Cn

xn1显然，1x1的展开式中，常数项即为所求证等式的左端。不妨设x0，将原式

xnn变形为：

111n1 1x11x12xxxxxx将上式展开，其中常数项为C2n，由此可知，原式成立。

rnr基本思路2：注意到恒等式CnCn，要证的等式的左边可变形为：

n

nnn2nCCCC0nnn1nn1nCCnn0n2n!；而等式右边即为：n!n!2n!Cn，因此可以考虑

2nn!2nn!建立适当的组合记数模型来加以证明。

证明：设袋子中有n个白球，n个红球，现从这2n个小球中随机抽取n个小球，其方法种数

n为：C2n2n!n!n!。另一方面，可以看成n1次如下的取球活动：从n个白球中取出r个，再

rnrrCn,r0,1,2,2从n个红球中取出nr个，其取法种数为：CnCn的取球方法种数是：C,n，所以符合题意

C02n12nCn2n。因此原式成立。

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

88

三、巩固练习 1，求证：Cn

12342，求证：当n是偶数时，12CnCn2CnCnn1n2CnCn32n1。

mnm1m1Cn。 m

1112133，求证：CCnCnCn2340n12n1111nkk1Cn。（利用CnCn1） n1n1k1n1 4，求 5，求证： 6，求证： 7，求证：

Ck0n1k2n1的值。（22n2）

kmCnkCkmxk1xnnkkmmkmmmCnx。（利用CnCkCnCnm）

Cnk1CnkC2nn1.（利用1x1x1x）

k1n2nnn1k02nkk2nknCmCm1Cm.（利用1x21x1x）

nmmm8，求证：Ck0k1Ck12k2mnCmCnCmnCmCnCk0mCn。

9，求证：Ck2m1是奇数，其中k1。

2n110，计算：1k1nkCk。 k12n

n11，求证：pCp2nCn1n2n1。

p1

n212，求证：CknCk11n2n1Cn2n。 k0

n12213，求证：n2kCk1Cn1n2n2。k0nn

90