構(gòu)造組合模型巧證組合恒等式

時(shí)間:2022-06-04 06:10:00

導(dǎo)語(yǔ):構(gòu)造組合模型巧證組合恒等式一文來(lái)源于網(wǎng)友上傳,不代表本站觀點(diǎn),若需要原創(chuàng)文章可咨詢(xún)客服老師,歡迎參考。

構(gòu)造組合模型巧證組合恒等式

證明組合恒等式,一般是利用組合數(shù)的性質(zhì)、數(shù)學(xué)歸納法、二項(xiàng)式定理等,通過(guò)一些適當(dāng)?shù)挠?jì)算或化簡(jiǎn)來(lái)完成.但是,很多組合恒等式,也可直接利用組合數(shù)的意義來(lái)證明.即構(gòu)造一個(gè)組合問(wèn)題的模型,把等式兩邊看成同一組問(wèn)題的兩種計(jì)算方法,由解的唯一性,即可證明組合恒等式

例1證明Cnm=Cnm-1+Cn-1m-1.

分析:原式左端為m個(gè)元素中取n個(gè)的組合數(shù).原式右端可看成是同一問(wèn)題的另一種算法:把滿(mǎn)足條件的組合分為兩類(lèi),一類(lèi)為不取某個(gè)元素a1,有Cnm-1種取法.一類(lèi)為必取a1有Cn-1m-1種取法.由加法原理可知原式成立.

例2證明Cnm·Cpn=Cpm·Cn-pm-p.

分析:原式左端可看成一個(gè)班有m個(gè)人,從中選出n個(gè)人打掃衛(wèi)生,在選出的n個(gè)人中,p人打掃教室,余下的n-p人打掃環(huán)境衛(wèi)生的選法數(shù).原式右端可看成直接在m人中選出p人打掃教室,在余下的m-p人中再選出n-p人打掃環(huán)境衛(wèi)生.顯然,兩種算法計(jì)算的是同一個(gè)問(wèn)題,結(jié)果當(dāng)然是一致的.

以上兩例雖然簡(jiǎn)單,但它揭示了用組合數(shù)的意義證明組合恒等式的一般思路:先由恒等式中意義比較明顯的一邊構(gòu)造一個(gè)組合問(wèn)題的模型,再根據(jù)加法原理或乘法原理對(duì)另一邊進(jìn)行分析.若是幾個(gè)數(shù)(組合數(shù))相加的形式,可以把構(gòu)造的組合問(wèn)題進(jìn)行適當(dāng)分類(lèi),如例1,若是幾個(gè)數(shù)(組合數(shù))相乘的形式,則應(yīng)進(jìn)行適當(dāng)?shù)姆植接?jì)算,如例2,當(dāng)然,很多情況下是兩者結(jié)合使用的.

例3證明Ckm+n=C0mCkn+C1mCk-1n+C2mCk-2n+…+CkmC0n,其中當(dāng)p>q時(shí)Cpq=0.

證明:原式左邊為m+n個(gè)元素中選k個(gè)元素的組合數(shù).今將這m+n個(gè)元素分成兩組,第一組為m個(gè)元素,剩下的n個(gè)元素為第二組,把取出的k個(gè)元素,按在第一組取出的元素個(gè)數(shù)i(i=0,1,2,…,k)進(jìn)行分類(lèi),這一類(lèi)的取法數(shù)為CimCk-in.于是,在m+n個(gè)元素中取k個(gè)元素的取法數(shù)又可寫(xiě)成ki=0CimCk-in.故原式成立.

例4證明

Cnn+Cnn+1+Cnn+2+…+Cnn+m=Cn+1n+m+1.

證明:原式右邊為m+n+1個(gè)元素中取n+1個(gè),元素的組合數(shù),不失一般性,可以認(rèn)為是在1,2,3,…,m+n,m+n+1,共m+n+1個(gè)數(shù)中取n+1個(gè)數(shù).將取出的n+1個(gè)數(shù)a1,a2…,an+1由小到大排列,即設(shè)a1<a2<an+1,按取出的最大數(shù)an+1=k+1分類(lèi),顯然k=n,n+1,…,n+m.當(dāng)k=n+i時(shí)(i=0,1,2,…,m),這一類(lèi)取法數(shù)為Cnn+i,所以取法總數(shù)又等于mi=0Cnn+i.原式成立.

對(duì)于某些組合恒等式,有時(shí)其左右兩邊所表示的意義都不易看出,但是如果根據(jù)組合數(shù)的特點(diǎn)仔細(xì)分析,或?qū)υ竭M(jìn)行一些適當(dāng)?shù)淖冃危梢郧擅畹貥?gòu)造一個(gè)組合問(wèn)題做為模型,證明就可化難為易.

例5證明C1n+2C2n+3C3n+…+nCnn=n2n-1.

分析:注意,原式左端等價(jià)于C11C1n+C12C2n+…+C1nCnn,這里C1iCin可表示先在n個(gè)元素里選i個(gè),再在這i個(gè)元素里選一個(gè)的組合數(shù),可設(shè)一個(gè)班有n個(gè)同學(xué),選出若干人(至少1人)組成一個(gè)代表團(tuán),并指定一人為團(tuán)長(zhǎng).把這種選法按取到的人數(shù)i分類(lèi)(i=1,2,…,n),則選法總數(shù)即為原式左端.今換一種選法,先選團(tuán)長(zhǎng),有n種選法,再?zèng)Q定剩下的n-1人是否參加,每人都有兩種可能,所以團(tuán)員的選法有2n-1種.即選法總數(shù)為n2n-1種.顯然兩種選法是一致的.

這里應(yīng)注意2n的意義,并能用組合意義證明ni=0Cin=2n.

例6證明

C1n+22C2n+32C3n+…+n2Cnn=n(n+1)2n-2.

分析:本題左邊與例5左邊類(lèi)似,不同的是例5左邊為ni=1iCin,而本題為ni=1i2Cin.只要在例5構(gòu)造的模型中加上同時(shí)還要選一個(gè)干事,并且干事和團(tuán)長(zhǎng)可以是同一個(gè)人,即可符合原式左邊.對(duì)原式右邊我們可分為團(tuán)長(zhǎng)和干事是否是同一個(gè)人兩類(lèi)情況.若團(tuán)長(zhǎng)和干事是同一個(gè)人,則有n2n-1種選法;若團(tuán)長(zhǎng)和干事不是同一個(gè)人,則有n(n-1)2n-1種選法.所以,共有n2n-1+n(n-1)2n-2=n(n+1)2n-2種選法.

例7證明

(C1n)2+2(C2n)2+3(C3n)2+…+n(Cnn)2=nCn-12n-1.

分析:注意到(Cin)2=CinCn-in,可設(shè)一個(gè)班有n個(gè)男生與n個(gè)女生,在這2n個(gè)學(xué)生中選n個(gè)同學(xué)(至少有1名男生)組成一個(gè)代表團(tuán),并指定其中一名男生為團(tuán)長(zhǎng),按選出的男生人數(shù)i(i=1,2,…,n)分類(lèi),這一類(lèi)有iCinCn-in=i(Cin)2種選法,總的選法有ni=1i(Cin)2種.原式右邊的組合意義是明顯的,即直接在n個(gè)男生中選一名團(tuán)長(zhǎng),有n種選法,再?gòu)氖O碌?n-1人中選出n-1人為團(tuán)員,共有nCn-12n-1種選法.

掌握了用組合意義證明組合恒等式這種方法后,還可通過(guò)構(gòu)造一個(gè)組合問(wèn)題的模型,編擬組合恒等式習(xí)題.如在例5中除了要選一名團(tuán)長(zhǎng)外,還要選一名干事和一名聯(lián)絡(luò)員(可以兼職)便可得ni=1i3Cin=n2(n+3)·2n-3.具體證法可參照例5與例6.又如,在例7中除了在2n個(gè)同學(xué)中選出n個(gè)團(tuán)員及指定一名男生為團(tuán)長(zhǎng)外,還要有一名男生擔(dān)任聯(lián)絡(luò)員(可以兼職),則可得組合恒等式:ni=1i2(Cin)2=nCn-12n-1+n(n-1)Cn-22n-2.若在例7中要求,留下的女生中再選一名負(fù)責(zé)人,則有組合恒等式ni=1i2(Cin)2=n2Cn-12n-2.具體證明讀者可自己完成.實(shí)際上習(xí)題的編擬過(guò)程就是用組合意義證明恒等式的過(guò)程.

若把恒等式中較簡(jiǎn)單的一邊去掉,變?yōu)榛?jiǎn)組合式,用此法同樣能完成化簡(jiǎn),讀者可自己體會(huì).

用組合數(shù)的意義證明組合恒等式,除了對(duì)提高學(xué)生的智力及觀察分析問(wèn)題的能力有幫助外,還有它獨(dú)到的好處,那就是把抽象的組合數(shù)還原為實(shí)際問(wèn)題,能提高學(xué)生應(yīng)用數(shù)學(xué)知識(shí)解決實(shí)際問(wèn)題的能力,把枯燥的公式還原為有趣的實(shí)例,能提高學(xué)生的學(xué)習(xí)興趣.所以,老師在教學(xué)過(guò)程中適當(dāng)介紹一些這方面的內(nèi)容,將是大有益處的.