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

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

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

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

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

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

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

以上兩例雖然簡單，但它揭示了用組合數(shù)的意義證明組合恒等式的一般思路：先由恒等式中意義比較明顯的一邊構(gòu)造一個組合問題的模型，再根據(jù)加法原理或乘法原理對另一邊進(jìn)行分析。若是幾個數(shù)（組合數(shù)）相加的形式，可以把構(gòu)造的組合問題進(jìn)行適當(dāng)分類，如例1,若是幾個數(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時Cpq=0.

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

例4證明

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

證明：原式右邊為m+n+1個元素中取n+1個，元素的組合數(shù)，不失一般性，可以認(rèn)為是在1,2,3,…，m+n,m+n