组合恒等式证明的几种方法(1)

1、1 引言组合恒等式是组合数学的一个重要部分.它在数学的各个分支中都有广泛应用,而且它的证明方法多种多样,具有很强的灵活性.下面通过几个实例具体讲述一下，几种证法在组合恒等式中的运用2 代数法通常利用组合恒等式的一些性质进行计算或化简，使得等式两边相等，n或者利用二项式定理(x+ y)n = Cnrxryn r 在展开式中令x和 y为某个特定的r=0值，也可以先对二项式定理利用幂级数的微商或积分后再代值，得出所需要的恒等式 .例 1Cnm 1 Cnm 1 2Cnm Cnm21， n m .分析：这个等式两边都很简单，我们可以利用一些常用的组合恒等式去 求证 .证明:Cnm+1 +Cnm 1+2C

2、nm = Cnm+21m+1 n m m m 1Cn= Cn ,Cnm+1左边Cnm (nm+mCmn+1 m nmm+1n+1m+2)=Cnm(nm2 m )m1 n1mCnm(n m 2)(n 1 m)m2(m 1)(n 1 m)m)Cnm(Cnm(n2 3n 2(m 1)(n 1 m)(n 2)(n 1)(m 1)(n 1 m)淮阴师范学院毕业论文(设计)右边= Cnm21(n 2)!(n 2)(n 1)n!(n 1 m)! m 1 ! (m 1)(n 1 m)(n m)! m!Cm (n 1)(n 2)n (n 1 m)(m 1)左边=右边即证.2n例 2 求证:3n Cn13n 1

3、Cn23n 2Cnn 131 Cnn30 2分析：看到上式，很容易想到二项式的展开式，尝试利用二项式定理去做.证明：由二项式定理建立恒等式，（3 n）n3nC1n3n1xCn23n2x2Cnn13xn1xn令 x 1,即得4n22n3n C1n 3n 1 Cn23n 2Cnn 13 1即证 .例3（ 1）设 n 是大于 2 的整数，则9C1n 2Cn2 3Cn3( 1)nCnn0.1 (2n1 1). n12) n 为正整数，则1 12C1n13Cn3 n11Cnn分析：观察上面两式的系数，很容易想到它们和微分积分有关，我们可.证明： ( 1) (1 x)nCn0Cn1x Cn2x2Cnnxn

4、等式两边对x求导，n( 1 xn)1Cn12Cn2 xnnnCn x1令 x 0得， 0 Cn1 2Cn2 3Cn3( 1)n 1nCnn.2)由二项式定理有，(1x)nCn0 Cn1x Cn2x2Cnnxn上式两边对x积分，有110 (1 x)ndx 0 (Cn0 Cn1x Cn2x2Cnnxn)dx1n1(1 x)n 1nCnk k0k11n1(2n 1n1)Cnkk01k111 Cn11 Cn21 Cnn 1 (2n 1 1) .23n1n1n此类方法证明组合恒等式的步骤是先对恒等式(a x)nCnian ixi两边i0对x求一阶或二阶导数，或者积分，然后对x取特殊值代入，得到所需证明的

5、我们也可以利用组合恒等式的性质，证明一些恒等式，例如1利用 m2Cm Cm ,求证：12 n n(n 1)(2n 1)mm6证明：左边2(C22 C32Cn2 ) (C11 C21C1n)2(1C33C32Cn2C33)(1C22C12Cn1C22)2Cn3 1 Cn22(n 1)! n(n 1)n 2 !3!21n(n 1)(2n 1)6m3 6Cm3 6Cm1 C1m，可以证明213 23n3n(n 1)2.3 组合分析法所谓组合分析法就是通过构造具体的组合计数模型或模型实例，利用不同的方法解得的结果应该相同，从而得到恒等式相等.例 5 证明：Crr Crr 1CnrCnr 11.证明：C

6、nr 11是n 1 元集 Aa1,a2, ,an 1 中 r 1 元子集的个数，这些子集可以分为n 1 类 .第 0类 : r 1 元子集中含有a1，则共有Cnr个 .第 1 类 : 不含a1 ，但含a2的r 1 元子集共有Cnr 1 个 ;,第 n类 :不含a1, a2, ,an但含an 1的 r 1 元子集共有C0r个 .由加法原理得C0rC1rCrr Crr 1CnrCnr 11.但是Ckr0,当kr时 ,所以有 CrrCrr 1 CnrCnr 11.001122mm m例6 求证: CmCnCmCnCmCnCm Cn Cmn (n m) .证明： 构造组合模型，假设一个班有m 个男生，

7、 有 n 个女生， 现在要选m个人，组成一组，那么有多少种选法.选法一：不区分男女生时，共有m n个人，选出m 人，共有选法Cmm n ;选法二： 选出的男生人数为k个， k 0,1,2, , m,男生的选法共有Cmk， 女生的选法共有Cnn k ，完成事件的选法共Cnn kCmk 种，于是CnnkCmkCmmn，又因为CnnkCnk.所以CnkCmkCmmn， k 0,1,2, ,m.001122mm m即 CmCn CmCn CmCnCm CnCm n (n m) .当 n m时，即有(Cn1)2 (Cn2)2(Cnn)2C2nn.4 比较系数法主要是利用二项式定理中两边多项式相等的充要条

8、件为同次幂的系数相等加以证明.一般情况下，用比较系数法证明所需辅助函数利用幂的运算性质：(1 x)m n (1 x)m(1 x)n，其中 m， n为任意实数，然后利用二项式定理的展开得到两个多项式，再通过比较同次幂的系数得到所证的恒等式.上题也可以利用比较系数法证明： (1 x)m(1 x)n(Cm0 C1mxCmmxm)(Cn0 Cn1xCnnxn )Cm0Cn0(CCm1n0CCm0)x1nC(Cmm0CnCm1mn1 CCmx)mm0nCmmCnmx n m0 m 1 m1m 0i mi所以 x 的系数为CmCnCmCnCmCn ，又因为CmCm .所以C0 m 1 m1m 000112

9、2m mmCnCmCnCmCnCmCnCmCnCmCnCmCn ，又因为，(1x)m(1x)n (1 x)m nCm0nCm1nxCmmnxmCmmnnxnm所以Cm0Cn0 C1mCn1 Cm2Cn2CmmCnm Cmmn(n m).即证 .例 7 求证(Cn1)2 (Cn2)2(Cnn)2 C2nn.证明： (1 x)n (1 x) n展开式中xn 的系数为：Cn0CnnCn1Cnn 1CnnCn0淮阴师范学院毕业论文(设计)Cn0Cn0Cn1Cn1Cn2Cn2CnnC(Cn1)2 (Cn2)2(Cnn)2又 (1 x)n(1 x)n (1 x)2n； (1 x)2n展开式中xn的系数为C

10、2nn，所以即有（C1n ）2 C（n2 ）2Cn（n ）2C2nn.5 数学归纳法我们都知道数学归纳法,在证明数列的题目中,我们就体会了数学归纳法的好处 ,只要按照数学归纳法的两个步骤进行就可以了.组合恒等式是与自然数有关的命题,因此,数学归纳法也就成为证明组合恒等式的常用方法之一.例 8 求证 ：Cnn Cnn 1Cnn p Cnn p 1，p 为自然数.分析：这里有一个变量p ,可以利用数学归纳法.证明： （ 1）当p 1 时，Cnn Cnn 1 Cnn111显然成立.（ 2）假设p k 时成立，即Cnn Cnn1Cnnk Cnn k1 1p k 1 时，即上式两边同时加上CnnCnn

11、1Cnn kCnn k 1n1nCn k 1 Cn k 1n1Cn k 2.p k 1 时也成立.1） （ 2）知命题对任意自然数p 皆成立 .例 9 证明 :(-1)0Cn0 (-1)1C1n(-1)mCnm=(-1)mCnm1证明:当m 0时 ,上式显然成立,当 m 1时 ,有左边= (-1)0Cn0(-1)1Cn11 Cn Cn 1 =右边所以原式成立.假设当 m k 时成立,即(-1)0Cn0 (-1)1Cn1(-1)kCnk=(-1)kCnk 1.当 m k 1时 ,左边=(-1)0Cn0 (-1)1C1n(-1)kCnk (-1)k 1Cnk 1( 1)k (n 1)!( 1)k

12、1n!n k 1 !k!n k 1 !(k 1)!( 1)k(n1)!(1 n)n k 1 !k! k 1k(n1)!(1)(nk1)( 1)n k 1 !k! k 1( 1)k1(n 1)!n k 2 !(k 1)!m k 1 时 ,命题也成立.(1),(2)知,命题对任意自然数皆成立12淮阴师范学院毕业论文（设计）结论关于组合恒等式证明的方法还有很多，例如，微积分法，二项式反演公式法， 几何法等.本文介绍的主要是几种常见的方法，以上的方法是以高中知识为基础， 也可以说是组合恒等式证明的初等方法.通过学习，我们学会用具体问题具体分析和解决问题多样化的思想.以上例题的解法大多不是唯一的，本文也

13、有提及 .但各种方法之间也存在一定的联系.有时一道题可以同时使用几种方法，思路很活！参考文献1 孙淑玲 , 许胤龙 . 组合数学引论M. 合肥，中国科学技术大学出版社,1999.2 吴顺唐 . 离散数学M. 上海，华东师范大学出版社出版发行，1997： 79-138.3 孙世新 , 张先迪 . 组合原理及其运用M. 北京，国防工业出版社,2006.4 陈镇邃 , 浅谈证明组合恒等式的几种方法J. 数学教学通讯，1986， 02： 15-16.5 张红兵 , 浅谈组合恒等式的证明方法J. 高等函授学报,2005,19 （ 13） ： 37-42.6 柳丽红 , 证明组合恒等式的方法与技巧J. 内蒙古电大学刊，2006， 86： 86-87.7 李士荣 , 组合恒等式的几种证法及应用J. 重庆工学院学报（ 自然科学版）,2007 ， 21（ 5） ： 72-74