组合公式及证明

1、组合恒等式、知识概要数学竞赛中组合数计算和组合恒等式的证明，是以高中排列、组合、二项式定理为基础，并加以推广和补充而形成的一类习题，它往往会具有一定的难度且灵活性较强。解决这类问题常常对学生良好的运算能力和思维的灵活性都有较高的要求。同时，此类问题的解决也有着自身特殊的解题技巧。因此，在各类数学竞赛中经常被采用。1，基本的组合恒等式许多竞赛中出简单的组合恒等式的化简和证明，可以直接运用课本所学的基本组合恒等式。事实上，现的较复杂的组合数记算或恒等式证明，也往往运用这些基本组合恒等式，通过转化，分解为若干个简单的组合恒等式而加以解决。课本中的组合恒等式有：nr CnrCn ；CniCnr 1 C

2、nr； kCnkk1nCn 1 ； CnrCrmCnmCnrmm； Cn0C1nCn2Cnn2n；nn Cn0Cn12nCnn0.Cn2，解题中常用方法运用基本组合恒等式进行变换； 运用二项展开式作为辅助函数，通过比较某项的系数进行计算或证明； 运用数学归纳法； 变换求和指标； 运用赋值法进行证明； 建立递推公式，由初始条件及递推关系进行计算和证明； 构造合理的模型。、运用举例123例1，求证：Cn2Cn3CnLnCnn2n1证明：根据前面提到的基本的组合恒等式第三条可得:左边nC；112nCn1nCn1nCn1,f右边例2,求和式nk2Cnk的值。k1基本思路：将k2C八改写为kkCnk先将

3、kCn用恒等式3提取公因式kn，然后再将kCn1变形成为k1C：1V；k1Cn1又可以继续运用上述恒等变形这样就使得各项系数中均不含有变动指标k了。n解：k2cn；k1Cnk2nCC12004例3，求k2005的值。n2n2n2004解：k200520042004C；004C；004C；004C；00420042003C20042004C2004例4,设m,nN，求证:3mnn21。Cf证明:例5,基本思路：由两个连续自然数mk与mk1的积，联想到可化为2C；k1,进一步运用C；1LCrrkCrr1c；iLC；k,反复运用基本的组合恒等式2即可化简。29m1Cm2CmC22CmC3C;ClC3

4、LCmC3m1n时，求证基本思路：利用基本组合恒等式证明:显然，当m左边Cm3m23mnrmCnCr4化简原式左边各项,n时，原式左边n时，利用基本组合恒等式rCmCm1CnCnmnCnmk使得化简后仅有4可得:Cnm中含有变动指标mCCn1rC；o只要令mm1Cmkk1Vm说明：变换求和指标是解决较复杂的组合记数的一种常见技巧,它可以起到简化计算的目的求和指标的上、下限需要同时变换。原式即可变为：00即原式成立。变换求和指标时，要注意例6,求证:nUn022n12n!2n2n2n!n!2n证明：k0CkC2nCkC2nCkC2n22nCkC2n22nCn1C2nC2nLC2nC2n22nCn

5、1C2nC2nn2LC0C2n22nCkC2n22nnCkCnC2nC2n所以，2C；n22nC2n,C;nk0k02n?2n12n!右边2n!n!o2i22n!例7,求证：CC1Ln!n!基本思路1：此题若考虑用基本组合恒等式来证明是比较困难的，展开式中注意到左端各项恰好是二项各项系数的平方，考虑构造两个二项展开式证明：因为CC：xLC:xn,1nCn0xCn-lxn显然，1的展开式中，常数项即为所求证等式的左端。不妨设变形为:2n将上式展开，其中常数项为C2n,由此可知，原式成立。基本思路2：注意到恒等式CnnrCn,要证的等式的左边可变形为W C ： Cnn1 LC； n,因此可以考虑2

6、n!2nc：cn。；而等式右边即为：一n!n!n!2nn!建立适当的组合记数模型来加以证明证明：设袋子中有n个白球，n个红球，现从这2n个小球中随机抽取n个小球，其方法种数2n!为：C2nno另一方面，可以看成n1次如下的取球活动：从n个白球中取出r个，再n!n!rnrr2从n个红球中取出nr个，其取法种数为：CnCnCn,r0,1,2,L,n，所以符合题意02122的取球方法种数是：c：C：LC：。因此原式成立。说明：本题的两种证明方法均采用了构造思想。构造法是解决竞赛问题的一种常用方法。三、巩固练习1,求证：CmLACm1。m2,求证：当n是偶数时，12CnC：2C：C：L2cn1c：01J121八33,求证：CnCnCnCnL234XCn一Cnn111k1Cn1n（利用Cn1k1n14,求Cn1的值。（22n2）k05,求证:Cn'x。（利用CjCnn6,求证：dcA1.（利用1x2n1xn1xn）k12nk7,求证：1CmCm