組合恒等式證明的幾種方法(1)

1、1 引言組合恒等式是組合數(shù)學(xué)的一個(gè)重要部分.它在數(shù)學(xué)的各個(gè)分支中都有廣泛應(yīng)用,而且它的證明方法多種多樣,具有很強(qiáng)的靈活性.下面通過(guò)幾個(gè)實(shí)例具體講述一下，幾種證法在組合恒等式中的運(yùn)用2 代數(shù)法通常利用組合恒等式的一些性質(zhì)進(jìn)行計(jì)算或化簡(jiǎn)，使得等式兩邊相等，n或者利用二項(xiàng)式定理(x+ y)n = Cnrxryn r 在展開式中令x和 y為某個(gè)特定的r=0值，也可以先對(duì)二項(xiàng)式定理利用冪級(jí)數(shù)的微商或積分后再代值，得出所需要的恒等式 .例 1Cnm 1 Cnm 1 2Cnm Cnm21， n m .分析：這個(gè)等式兩邊都很簡(jiǎn)單，我們可以利用一些常用的組合恒等式去 求證 .證明: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)淮陰師范學(xué)院畢業(yè)論文(設(shè)計(jì))右邊= 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分析：看到上式，很容易想到二項(xiàng)式的展開式，嘗試?yán)枚?xiàng)式定理去做.證明：由二項(xiàng)式定理建立恒等式，（3 n）n3nC1n3n1xCn23n2x2Cnn13xn1xn令 x 1,即得4n22n3n C1n 3n 1 Cn23n 2Cnn 13 1即證 .例3（ 1）設(shè) n 是大于 2 的整數(shù)，則9C1n 2Cn2 3Cn3( 1)nCnn0.1 (2n1 1). n12) n 為正整數(shù)，則1 12C1n13Cn3 n11Cnn分析：觀察上面兩式的系數(shù)，很容易想到它們和微分積分有關(guān)，我們可.證明： ( 1) (1 x)nCn0Cn1x Cn2x2Cnnxn

4、等式兩邊對(duì)x求導(dǎo)，n( 1 xn)1Cn12Cn2 xnnnCn x1令 x 0得， 0 Cn1 2Cn2 3Cn3( 1)n 1nCnn.2)由二項(xiàng)式定理有，(1x)nCn0 Cn1x Cn2x2Cnnxn上式兩邊對(duì)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此類方法證明組合恒等式的步驟是先對(duì)恒等式(a x)nCnian ixi兩邊i0對(duì)x求一階或二階導(dǎo)數(shù)，或者積分，然后對(duì)x取特殊值代入，得到所需證明的

5、我們也可以利用組合恒等式的性質(zhì)，證明一些恒等式，例如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 組合分析法所謂組合分析法就是通過(guò)構(gòu)造具體的組合計(jì)數(shù)模型或模型實(shí)例，利用不同的方法解得的結(jié)果應(yīng)該相同，從而得到恒等式相等.例 5 證明：Crr Crr 1CnrCnr 11.證明：C

6、nr 11是n 1 元集 Aa1,a2, ,an 1 中 r 1 元子集的個(gè)數(shù)，這些子集可以分為n 1 類 .第 0類 : r 1 元子集中含有a1，則共有Cnr個(gè) .第 1 類 : 不含a1 ，但含a2的r 1 元子集共有Cnr 1 個(gè) ;,第 n類 :不含a1, a2, ,an但含an 1的 r 1 元子集共有C0r個(gè) .由加法原理得C0rC1rCrr Crr 1CnrCnr 11.但是Ckr0,當(dāng)kr時(shí) ,所以有 CrrCrr 1 CnrCnr 11.001122mm m例6 求證: CmCnCmCnCmCnCm Cn Cmn (n m) .證明： 構(gòu)造組合模型，假設(shè)一個(gè)班有m 個(gè)男生，

7、 有 n 個(gè)女生， 現(xiàn)在要選m個(gè)人，組成一組，那么有多少種選法.選法一：不區(qū)分男女生時(shí)，共有m n個(gè)人，選出m 人，共有選法Cmm n ;選法二： 選出的男生人數(shù)為k個(gè)， k 0,1,2, , m,男生的選法共有Cmk， 女生的選法共有Cnn k ，完成事件的選法共Cnn kCmk 種，于是CnnkCmkCmmn，又因?yàn)镃nnkCnk.所以CnkCmkCmmn， k 0,1,2, ,m.001122mm m即 CmCn CmCn CmCnCm CnCm n (n m) .當(dāng) n m時(shí)，即有(Cn1)2 (Cn2)2(Cnn)2C2nn.4 比較系數(shù)法主要是利用二項(xiàng)式定理中兩邊多項(xiàng)式相等的充要條

8、件為同次冪的系數(shù)相等加以證明.一般情況下，用比較系數(shù)法證明所需輔助函數(shù)利用冪的運(yùn)算性質(zhì)：(1 x)m n (1 x)m(1 x)n，其中 m， n為任意實(shí)數(shù)，然后利用二項(xiàng)式定理的展開得到兩個(gè)多項(xiàng)式，再通過(guò)比較同次冪的系數(shù)得到所證的恒等式.上題也可以利用比較系數(shù)法證明： (1 x)m(1 x)n(Cm0 C1mxCmmxm)(Cn0 Cn1xCnnxn )Cm0Cn0(CCm1n0CCm0)x1nC(Cmm0CnCm1mn1 CCmx)mm0nCmmCnmx n m0 m 1 m1m 0i mi所以 x 的系數(shù)為CmCnCmCnCmCn ，又因?yàn)镃mCm .所以C0 m 1 m1m 000112

9、2m mmCnCmCnCmCnCmCnCmCnCmCnCmCn ，又因?yàn)椋?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 的系數(shù)為：Cn0CnnCn1Cnn 1CnnCn0淮陰師范學(xué)院畢業(yè)論文(設(shè)計(jì))Cn0Cn0Cn1Cn1Cn2Cn2CnnC(Cn1)2 (Cn2)2(Cnn)2又 (1 x)n(1 x)n (1 x)2n； (1 x)2n展開式中xn的系數(shù)為C

10、2nn，所以即有（C1n ）2 C（n2 ）2Cn（n ）2C2nn.5 數(shù)學(xué)歸納法我們都知道數(shù)學(xué)歸納法,在證明數(shù)列的題目中,我們就體會(huì)了數(shù)學(xué)歸納法的好處 ,只要按照數(shù)學(xué)歸納法的兩個(gè)步驟進(jìn)行就可以了.組合恒等式是與自然數(shù)有關(guān)的命題,因此,數(shù)學(xué)歸納法也就成為證明組合恒等式的常用方法之一.例 8 求證 ：Cnn Cnn 1Cnn p Cnn p 1，p 為自然數(shù).分析：這里有一個(gè)變量p ,可以利用數(shù)學(xué)歸納法.證明： （ 1）當(dāng)p 1 時(shí)，Cnn Cnn 1 Cnn111顯然成立.（ 2）假設(shè)p k 時(shí)成立，即Cnn Cnn1Cnnk Cnn k1 1p k 1 時(shí)，即上式兩邊同時(shí)加上CnnCnn

11、1Cnn kCnn k 1n1nCn k 1 Cn k 1n1Cn k 2.p k 1 時(shí)也成立.1） （ 2）知命題對(duì)任意自然數(shù)p 皆成立 .例 9 證明 :(-1)0Cn0 (-1)1C1n(-1)mCnm=(-1)mCnm1證明:當(dāng)m 0時(shí) ,上式顯然成立,當(dāng) m 1時(shí) ,有左邊= (-1)0Cn0(-1)1Cn11 Cn Cn 1 =右邊所以原式成立.假設(shè)當(dāng) m k 時(shí)成立,即(-1)0Cn0 (-1)1Cn1(-1)kCnk=(-1)kCnk 1.當(dāng) m k 1時(shí) ,左邊=(-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 時(shí) ,命題也成立.(1),(2)知,命題對(duì)任意自然數(shù)皆成立12淮陰師范學(xué)院畢業(yè)論文（設(shè)計(jì)）結(jié)論關(guān)于組合恒等式證明的方法還有很多，例如，微積分法，二項(xiàng)式反演公式法， 幾何法等.本文介紹的主要是幾種常見的方法，以上的方法是以高中知識(shí)為基礎(chǔ)， 也可以說(shuō)是組合恒等式證明的初等方法.通過(guò)學(xué)習(xí)，我們學(xué)會(huì)用具體問(wèn)題具體分析和解決問(wèn)題多樣化的思想.以上例題的解法大多不是唯一的，本文也

13、有提及 .但各種方法之間也存在一定的聯(lián)系.有時(shí)一道題可以同時(shí)使用幾種方法，思路很活！參考文獻(xiàn)1 孫淑玲 , 許胤龍 . 組合數(shù)學(xué)引論M. 合肥，中國(guó)科學(xué)技術(shù)大學(xué)出版社,1999.2 吳順唐 . 離散數(shù)學(xué)M. 上海，華東師范大學(xué)出版社出版發(fā)行，1997： 79-138.3 孫世新 , 張先迪 . 組合原理及其運(yùn)用M. 北京，國(guó)防工業(yè)出版社,2006.4 陳鎮(zhèn)邃 , 淺談證明組合恒等式的幾種方法J. 數(shù)學(xué)教學(xué)通訊，1986， 02： 15-16.5 張紅兵 , 淺談組合恒等式的證明方法J. 高等函授學(xué)報(bào),2005,19 （ 13） ： 37-42.6 柳麗紅 , 證明組合恒等式的方法與技巧J. 內(nèi)蒙古電大學(xué)刊，2006， 86： 86-87.7 李士榮 , 組合恒等式的幾種證法及應(yīng)用J. 重慶工學(xué)院學(xué)報(bào)（ 自然科學(xué)版）,2007 ， 21（ 5） ： 72-74