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

第頁共頁構(gòu)造組合模型巧證組合恒等式論文構(gòu)造組合模型巧證組合恒等式論文證明組合恒等式，一般是利用組合數(shù)的性質(zhì)、數(shù)學歸納法、二項式定理等，通過一些適當?shù)挠嬎慊蚧唩硗瓿桑?，很多組合恒等式，也可直接利用組合數(shù)的意義來證明．即構(gòu)造一個組合問題的模型，把等式兩邊看成同一組問題的兩種計算方法，由解的唯一性，即可證明組合恒等式．例１證明Ｃｎｍ＝Ｃｎｍ－１＋Ｃｎ－１ｍ－１．分析^p：原式左端為ｍ個元素中?。顐€的組合數(shù)．原式右端可看成是同一問題的另一種算法：把滿足條件的組合分為兩類，一類為不取某個元素ａ１，有Ｃｎｍ－１種取法．一類為必?。幔庇校茫睿保恚狈N取法．由加法原理可知原式成立．例２證明Ｃｎｍ·Ｃｐｎ＝Ｃｐｍ·Ｃｎ－ｐｍ－ｐ．分析^p：原式左端可看成一個班有ｍ個人，從中選出ｎ個人清掃衛(wèi)生，在選出的ｎ個人中，ｐ人清掃教室，余下的ｎ－ｐ人清掃環(huán)境衛(wèi)生的選法數(shù)．原式右端可看成直接在ｍ人中選出ｐ人清掃教室，在余下的ｍ－ｐ人中再選出ｎ－ｐ人清掃環(huán)境衛(wèi)生．顯然，兩種算法計算的是同一個問題，結(jié)果當然是一致的．以上兩例雖然簡單，但它提醒了用組合數(shù)的意義證明組合恒等式的.一般思路：先由恒等式中意義比較明顯的一邊構(gòu)造一個組合問題的模型，再根據(jù)加法原理或乘法原理對另一邊進展分析^p．假設(shè)是幾個數(shù)〔組合數(shù)〕相加的形式，可以把構(gòu)造的組合問題進展適當分類，如例１，假設(shè)是幾個數(shù)〔組合數(shù)〕相乘的形式，那么應(yīng)進展適當?shù)姆植接嬎?，如例２，當然，很多情況下是兩者結(jié)合使用的．例３證明Ｃｋｍ＋ｎ＝Ｃ０ｍＣｋｎ＋Ｃ１ｍＣｋ－１ｎ＋Ｃ２ｍＣｋ－２ｎ＋…＋ＣｋｍＣ０ｎ，其中當ｐ＞ｑ時Ｃｐｑ＝０．證明：原式左邊為ｍ＋ｎ個元素中選ｋ個元素的組合數(shù)．今將這ｍ＋ｎ個元素分成兩組，第一組為ｍ個元素，剩下的ｎ個元素為第二組，把取出的ｋ個元素，按在第一組取出的元素個數(shù)ｉ〔ｉ＝０，１，２，…，ｋ〕進展分類，這一類的取法數(shù)為ＣｉｍＣｋ－ｉｎ．于是，在ｍ＋ｎ個元素中?。雮€元素的取法數(shù)又可寫成?ｋｉ＝０ＣｉｍＣｋ－ｉｎ．故原式成立．例４證明Ｃｎｎ＋Ｃｎｎ＋１＋Ｃｎｎ＋２＋…＋Ｃｎｎ＋ｍ＝Ｃｎ＋１ｎ＋ｍ＋１．證明：原式右邊為ｍ＋ｎ＋１個元素中?。睿眰€，元素的組合數(shù)，不失一般性，可以認為是在１，２，３，…，ｍ＋ｎ，ｍ＋ｎ＋１，共ｍ＋ｎ＋１個數(shù)中取ｎ＋１個數(shù)．將取出的ｎ＋１個數(shù)ａ１，ａ２…，ａｎ＋１由小到大排列，即設(shè)ａ１＜ａ２＜ａｎ＋１，按取出的最大數(shù)ａｎ＋１＝ｋ＋１分類，顯然ｋ＝ｎ，ｎ＋１，…，ｎ＋ｍ．當ｋ＝ｎ＋ｉ時〔ｉ＝０，１，２，…，ｍ〕，這一類取法數(shù)為Ｃｎｎ＋ｉ，所以取法總數(shù)又等于?ｍｉ＝０Ｃｎｎ＋ｉ．原式成立．對于某些組合恒等式，有時其左右兩邊所表示的意義都不易看出，但是假設(shè)根據(jù)組合數(shù)的特點仔細分析^p，或?qū)υ竭M展一些適當?shù)淖冃?，往往可以巧妙地?gòu)造一個組合問題做為模型，證明就可化難為易．例５證明Ｃ１ｎ＋２Ｃ２ｎ＋３