構造組合模型巧證組合恒等式

構造組合模型巧證組合恒等式

        證明組合恒等式，一般是利用組合數的性質、數學歸納法、二項式定理等，通過一些適當的計算或化簡來完成。但是，很多組合恒等式，也可直接利用組合數的意義來證明。即構造一個組合問題的模型，把等式兩邊看成同一組問題的兩種計算方法，由解的唯一性，即可證明組合恒等式。
        例１證明Cnm ＝ Cnm － 1m ＋ Cn － 1m －１。分析：原式左端為ｍ個元素中取ｎ個的組合數。原式右端可看成是同一問題的另一種算法：把滿足條件的組合分為兩類，一類為不取某個元素ａ１，有Ｃｎｍ－１種取法。一類為必�。幔庇蠧n － 1m － 1 種取法。由加法原理可知原式成立。
        例２證明Cnm·Cpm ＝ Cpm·Cn － pm －ｐ。
        分析：原式左端可看成一個班有ｍ個人，從中選出ｎ個人打掃衛生，在選出的ｎ個人中，ｐ人打掃教室，余下的n － p 人打掃環境衛生的選法數。原式右端可看成直接在ｍ人中選出ｐ人打掃教室，在余下的m － p 人中再選出n － p 人打掃環境衛生。顯然，兩種算法計算的是同一個問題，結果當然是一致的。
        以上兩例雖然簡單，但它揭示了用組合數的意義證明組合恒等式的一般思路：先由恒等式中意義比較明顯的一邊構造一個組合問題的模型，再根據加法原理或乘法原理對另一邊進行分析。若是幾個數（組合數）相加的形式，可以把構造的組合問題進行適當分類，如例１，若是幾個數（組合數）相乘的形式，則應進行適當的分步計算，如例２，當然，很多情況下是兩者結合使用的。
        例３證明Ckm ＋ n ＝ C0mCkn ＋ C1mCK － 1n ＋ C2mck － 2n ＋…＋ CkmC0m，其中當p ＞ q 時Cpq ＝０。
        證明：原式左邊為m ＋ n 個元素中選ｋ個元素的組合數。今將這m ＋ n 個元素分成兩組，第一組為ｍ個元素，剩下的n 個元素為第二組，把取出的ｋ個元素，按在第一組取出的元素個數ｉ（i ＝ 0，1，2，…，k）進行分類，這一類的取法數為CimCk － in。于是，在ｍ＋ｎ個元素中�。雮�元素的取法數又可寫成ki ＝０CimCk －in。故原式成立。
        例４證明
        Cnn ＋ Cnn ＋ 1 ＋ Cnn ＋ 2 ＋…＋ Cnn ＋ m ＝ Cn ＋ 1n ＋ m ＋ 1。
        證明：原式右邊為m ＋ n ＋ 1 個元素中取n ＋ 1 個，元素的組合數，不失一般性，可以認為是在１，２，３，…，m ＋ n，m ＋ n ＋ 1，共m ＋ n ＋ 1 個數中取n ＋ 1 個數。將取出的n ＋ 1個數al，a2…，an ＋１由小到大排列，即設a1 ＜ a2 ＜ an ＋ 1，按取出的最大數an ＋ 1 ＝ k ＋ 1 分類，顯然k ＝ n，n ＋ 1，…，n ＋ m。當k ＝ n ＋ i 時（i＝ 0，1，2，…，m），這一類取法數為Cnn ＋ i，所以取法總數又等于mi ＝０Cnn ＋ i。原式成立。       對于某些組合恒等式，有時其左右兩邊所表示的意義都不易看出，但是如果根據組合數的特點仔細分析，或對原式進行一些適當的變形，往往可以巧妙地構造一個組合問題做為模型，證明就可化難為易。
        例５證明CIn ＋ 2c2n ＋ 3c3n ＋…＋ nCnn ＝ n2n － 1。
        分析：注意，原式左端等價C11Cin ＋ Ci2C2n ＋…＋ CinCnn，這里CIiCIn 可表示先在n 個元素里選i 個，再在這i 個元素里選一個的組合數，可設一個班有n 個同學，選出若干人（至少1 人）組成一個代表團，并指定一人為團長。把這種選法按取到的人數i 分類（i ＝ 1，2，…，n），則選法總數即為原式左端。今換一種選法，先選團長，有ｎ種選法，再決定剩下的n － 1 人是否參加，每人都有兩種可能，所以團員的選法有2n － 1 種。即選法總數為n2n － 1 種。顯然兩種選法是一致的。這里應注意2n 的意義，并能用組合意義證明ni ＝ 0Cin ＝ 2n。
        例６證明
        Cln ＋ 22C2n ＋ 32C3n ＋…＋ n2Cnn ＝ n（n ＋ 1）2n －２。
        分析：本題左邊與例５左邊類似，不同的是例５左邊為ni ＝ liCin，而本題為ni＝ Li2Cin。只要在例５構造的模型中加上同時還要選一個干事，并且干事和團長可以是同一個人，即可符合原式左邊。對原式右邊我們可分為團長和干事是否是同一個人兩類情況。若團長和干事是同一個人，則有n2n － 1 種選法；若團長和干事不是同一個人，則有n（n － l）2n － l 種選法。所以，共有n2n － l ＋ n（n － l）2n － 2 ＝ n（n ＋ l）2n － 2 種選法。
        若把恒等式中較簡單的一邊去掉，變為化簡組合式，用此法同樣能完成化簡，讀者可自己體會。用組合數的意義證明組合恒等式，除了對提高學生的智力及觀察分析問題的能力有幫助外，還有它獨到的好處，那就是把抽象的組合數還原為實際問題，能提高學生應用數學知識解決實際問題的能力，把枯燥的公式還原為有趣的實例，能提高學生的學習興趣。所以，老師在教學過程中適當介紹一些這方面的內容，將是大有益處的。

【構造組合模型巧證組合恒等式】相關文章：

探析基于VaR模型的證券投資組合風險12-05

試論圖書館信息營銷優化組合模型構建03-10

如何利用小組合作進行教學12-12

論組合打擊樂獨奏《功夫》12-11

淺談小組合作學習的策略03-27

淺談學生小組合作學習01-08

試論電商企業的營銷組合策略11-18

小組合作學習優化思考03-28

淺談營銷組合與服務營銷理論研究12-09