組合公式及證明

1、組合恒等式、知識(shí)概要數(shù)學(xué)競(jìng)賽中組合數(shù)計(jì)算和組合恒等式的證明，是以高中排列、組合、二項(xiàng)式定理為基礎(chǔ)，并加以推廣和補(bǔ)充而形成的一類(lèi)習(xí)題，它往往會(huì)具有一定的難度且靈活性較強(qiáng)。解決這類(lèi)問(wèn)題常常對(duì)學(xué)生良好的運(yùn)算能力和思維的靈活性都有較高的要求。同時(shí)，此類(lèi)問(wèn)題的解決也有著自身特殊的解題技巧。因此，在各類(lèi)數(shù)學(xué)競(jìng)賽中經(jīng)常被采用。1，基本的組合恒等式許多競(jìng)賽中出簡(jiǎn)單的組合恒等式的化簡(jiǎn)和證明，可以直接運(yùn)用課本所學(xué)的基本組合恒等式。事實(shí)上，現(xiàn)的較復(fù)雜的組合數(shù)記算或恒等式證明，也往往運(yùn)用這些基本組合恒等式，通過(guò)轉(zhuǎn)化，分解為若干個(gè)簡(jiǎn)單的組合恒等式而加以解決。課本中的組合恒等式有：nr CnrCn ；CniCnr 1 C

2、nr； kCnkk1nCn 1 ； CnrCrmCnmCnrmm； Cn0C1nCn2Cnn2n；nn Cn0Cn12nCnn0.Cn2，解題中常用方法運(yùn)用基本組合恒等式進(jìn)行變換； 運(yùn)用二項(xiàng)展開(kāi)式作為輔助函數(shù)，通過(guò)比較某項(xiàng)的系數(shù)進(jìn)行計(jì)算或證明； 運(yùn)用數(shù)學(xué)歸納法； 變換求和指標(biāo)； 運(yùn)用賦值法進(jìn)行證明； 建立遞推公式，由初始條件及遞推關(guān)系進(jìn)行計(jì)算和證明； 構(gòu)造合理的模型。、運(yùn)用舉例123例1，求證：Cn2Cn3CnLnCnn2n1證明：根據(jù)前面提到的基本的組合恒等式第三條可得:左邊nC；112nCn1nCn1nCn1,f右邊例2,求和式nk2Cnk的值。k1基本思路：將k2C八改寫(xiě)為kkCnk先將

3、kCn用恒等式3提取公因式kn，然后再將kCn1變形成為k1C：1V；k1Cn1又可以繼續(xù)運(yùn)用上述恒等變形這樣就使得各項(xiàng)系數(shù)中均不含有變動(dòng)指標(biāo)k了。n解：k2cn；k1Cnk2nCC12004例3，求k2005的值。n2n2n2004解：k200520042004C；004C；004C；004C；00420042003C20042004C2004例4,設(shè)m,nN，求證:3mnn21。Cf證明:例5,基本思路：由兩個(gè)連續(xù)自然數(shù)mk與mk1的積，聯(lián)想到可化為2C；k1,進(jìn)一步運(yùn)用C；1LCrrkCrr1c；iLC；k,反復(fù)運(yùn)用基本的組合恒等式2即可化簡(jiǎn)。29m1Cm2CmC22CmC3C;ClC3

4、LCmC3m1n時(shí)，求證基本思路：利用基本組合恒等式證明:顯然，當(dāng)m左邊Cm3m23mnrmCnCr4化簡(jiǎn)原式左邊各項(xiàng),n時(shí)，原式左邊n時(shí)，利用基本組合恒等式rCmCm1CnCnmnCnmk使得化簡(jiǎn)后僅有4可得:Cnm中含有變動(dòng)指標(biāo)mCCn1rC；o只要令mm1Cmkk1Vm說(shuō)明：變換求和指標(biāo)是解決較復(fù)雜的組合記數(shù)的一種常見(jiàn)技巧,它可以起到簡(jiǎn)化計(jì)算的目的求和指標(biāo)的上、下限需要同時(shí)變換。原式即可變?yōu)椋?0即原式成立。變換求和指標(biāo)時(shí)，要注意例6,求證:nUn022n12n!2n2n2n!n!2n證明：k0CkC2nCkC2nCkC2n22nCkC2n22nCn1C2nC2nLC2nC2n22nCn

5、1C2nC2nn2LC0C2n22nCkC2n22nnCkCnC2nC2n所以，2C；n22nC2n,C;nk0k02n?2n12n!右邊2n!n!o2i22n!例7,求證：CC1Ln!n!基本思路1：此題若考慮用基本組合恒等式來(lái)證明是比較困難的，展開(kāi)式中注意到左端各項(xiàng)恰好是二項(xiàng)各項(xiàng)系數(shù)的平方，考慮構(gòu)造兩個(gè)二項(xiàng)展開(kāi)式證明：因?yàn)镃C：xLC:xn,1nCn0xCn-lxn顯然，1的展開(kāi)式中，常數(shù)項(xiàng)即為所求證等式的左端。不妨設(shè)變形為:2n將上式展開(kāi)，其中常數(shù)項(xiàng)為C2n,由此可知，原式成立?；舅悸?：注意到恒等式CnnrCn,要證的等式的左邊可變形為W C ： Cnn1 LC； n,因此可以考慮2

6、n!2nc：cn。；而等式右邊即為：一n!n!n!2nn!建立適當(dāng)?shù)慕M合記數(shù)模型來(lái)加以證明證明：設(shè)袋子中有n個(gè)白球，n個(gè)紅球，現(xiàn)從這2n個(gè)小球中隨機(jī)抽取n個(gè)小球，其方法種數(shù)2n!為：C2nno另一方面，可以看成n1次如下的取球活動(dòng)：從n個(gè)白球中取出r個(gè)，再n!n!rnrr2從n個(gè)紅球中取出nr個(gè)，其取法種數(shù)為：CnCnCn,r0,1,2,L,n，所以符合題意02122的取球方法種數(shù)是：c：C：LC：。因此原式成立。說(shuō)明：本題的兩種證明方法均采用了構(gòu)造思想。構(gòu)造法是解決競(jìng)賽問(wèn)題的一種常用方法。三、鞏固練習(xí)1,求證：CmLACm1。m2,求證：當(dāng)n是偶數(shù)時(shí)，12CnC：2C：C：L2cn1c：01J121八33,求證：CnCnCnCnL234XCn一Cnn111k1Cn1n（利用Cn1k1n14,求Cn1的值。（22n2）k05,求證:Cn'x。（利用CjCnn6,求證：dcA1.（利用1x2n1xn1xn）k12nk7,求證：1CmCm