【正文】 雜的需要我們演算一兩步達(dá)到欲求的結(jié)果，但是并不是所有的組合恒等式都是那么的簡單，有的組合恒等式很復(fù)雜，我們要深入了解，就必須通過一步步的證明、深究，證明組合恒等式的方法有很多，譬如有分類法、概率法、求導(dǎo)法等一系列方法證明組合恒等式 .本文，我們選用利 用概率方法來證明組合恒等式，我主要介紹這幾種方法：構(gòu)造模型法、概率性質(zhì)法、數(shù)字特征法，這些都是前人通過比較發(fā)現(xiàn)的較為好的方法，我們加以更好的應(yīng)用，我們應(yīng)當(dāng)看到組合恒等式與概率二者的結(jié)合，只要把握了這一點(diǎn)，相信就能夠從中受益匪淺，感觸頗多 .含有組合數(shù)的恒等式叫做組合恒等式 .簡單的組合恒等式的化簡和證明，可以直接運(yùn)用課本所學(xué)的基本組合恒等式 .事實上，許多試題中出現(xiàn)的較復(fù)雜的組合數(shù)計算或恒等式證明，也往往運(yùn)用這些基本組合恒等式，通過轉(zhuǎn)化，分解為若干個簡單的組合恒等式而加以解決 .我們簡單的介紹四種組合恒等式：二項式 組合恒等式、關(guān)于Catalan 三角數(shù)的組合恒等式、基于格路模型的組合恒等式、由概率引起的組合恒等式 .通過對一些組合恒等式的了解，我們就選用各種概率的方法加以證明它們，達(dá)到一個比較完善的效果 . 課題背景 組合數(shù)學(xué)是以離散結(jié)構(gòu)為主要研究對象的一門學(xué)科，它主要研究滿足一定條 件的組態(tài) (一種安排 )的存在性、計數(shù)及構(gòu)造等方面的問題 .近幾年，隨著計算 機(jī)科學(xué)的產(chǎn)生與發(fā)展，組合數(shù)學(xué)得到了迅速的發(fā)展 。 齊 齊 哈 爾 大 學(xué) 畢業(yè)設(shè)計（論文） 題 目 用概率 論的 方法證明組合恒等式 學(xué) 院 理 學(xué) 院 專業(yè)班級 信息與計算科學(xué) 082 齊齊哈爾大學(xué)畢業(yè)設(shè)計 (論文 ) I 用概率論的方法證明組合恒等式 摘 要 組合恒等式是組合數(shù)學(xué)中的一個組成部分，也是組合數(shù)學(xué)研究的一個重要內(nèi)容 . 本文主要探討如何利用概率方法研究組合恒等式，主要從不同的角度解答同一概率問題，得到同一事件的概率兩種不同的表達(dá)形式 ，由其相等導(dǎo)出組合恒等式 . 通過構(gòu)造概率模型，利用“必然事件的概率等于 1”和“不可能事件的概率等于0” 證明組合恒等式，或者利用古典概率方法證明組合恒等式，也就是在實際問題中將需要證明的組合恒等式引證出來。 概率起源于歐洲國家的一種賭博方式 —— 擲骰子。 組合數(shù)學(xué)和概率論的產(chǎn)生都可以追溯到十七世紀(jì)，從 17 世紀(jì)到 20 世紀(jì) 30年代，組合數(shù)學(xué)受到娛樂及數(shù)論、概率論、化學(xué)等學(xué)科的推動而迅速發(fā)展，得到了一般的存在定理和計數(shù)原理，如抽屜原理、容斥原理、波利亞計數(shù)定理等，還解決了一系列著名而有趣的組合學(xué)問題，如更列問題、家政問題、 36 軍官問題等，自 20 世紀(jì)以來，許多理 論學(xué)科和應(yīng)用學(xué)科給組合數(shù)學(xué)提出了大量的具有理論和實際意義的課題，促使了許多新理論的產(chǎn)生，如區(qū)組設(shè)計、組合算法等，從而解決了一系列理論上的以及與經(jīng)濟(jì)發(fā)展密切相關(guān)的課題。 在學(xué)習(xí)概率論 中，我們首先接觸到得的是古典概型，這些概率模型的特點(diǎn)是所研究的樣本容量中樣本的個數(shù)是有限的，常利用排列組合方法去解決古典概型中的問題，如分配問題，伯努利概型等。對于如何使用概率論的方法證明組合恒等式，經(jīng)過本人得仔細(xì)思考，大致總結(jié)了以下幾個方法： （ 1）運(yùn)用完備事件組證明組合恒等式 （ 2）運(yùn)用全概率公式證明組合恒等式 （ 3）運(yùn)用隨機(jī)變量的數(shù)字特征證明組合恒等式 （ 4）運(yùn)用構(gòu)造概率模型證 明組合恒等式 （ 5）運(yùn)用等概率法證明組合恒等式 （ 6）運(yùn)用概率性質(zhì)證明組合恒等式 齊齊哈爾大學(xué)畢業(yè)設(shè)計 (論文 ) 4 第 2 章 用概率論的 基本理論 證明組合恒等式 運(yùn)用完備事件組證明組合恒等式 這種方法的基本思想是：我們對于一些組合恒等式，可以構(gòu)造出適當(dāng)?shù)哪Ｐ?，并且選擇出與組合恒等式相關(guān)的隨機(jī)變量，并求出它的分布列 ),2,1(}{ niPiP i ????? 接著我們再利用完備事件組的性質(zhì) 11 ????i iP，于是我們便達(dá)到了證明組合和恒等式的目的。 例 1 證明 組合 恒等式 nnk kk knC 22110 ????? ? 證明 我們構(gòu)造如下 概率模型： 設(shè) 一個人有兩瓶牙簽 ，每 瓶 n根，每次用牙簽時，他在兩瓶中任取一 瓶 ．然后抽出一根，使用若干次后，發(fā)現(xiàn)一瓶牙簽 已經(jīng)用完，求另 一盒中還有 r 根 牙簽的概率 . 如果用 1A ， 2A 分別表示甲瓶或者乙瓶 中余下 r 根 牙簽 . 用 rA 表示一瓶 用完， 而另一 瓶 中有 r 根的事件，則 21 AAAr ?? . 注意到，當(dāng)發(fā)現(xiàn)一 瓶 已空時．這一 瓶 必定在前面已用過 n 次， 另一 瓶 余下r 根， 從而另一 瓶 已用過 rn? 次 ， 故共用了 12 ??rn 次 .每次取到甲 (乙 ) 瓶 的概率是 21 .所以 ? ? ? ? ? ? ? ?2121 APAPAAPAP r ??? ? = rnnnrnrnnnrn CC???? ??????????????????????????? 212121212121 22 = rnnrnC?? ??????22 21 由于 r 的取值必定是 n,2,1 ? 之一，故rnr A1??為必然事件，即 11 ??????? ? rnr AP ? ， 也就是 12121 2 ??????? ?? ??rnnrn rnC 令 rnk ?? , 則 ,1,1,0 ?? nk ? 所以 12110 ??????? ??? ??knnkk knC 或 .22110??? ? ?nknkk knC 例 2 證明組合恒等式當(dāng) nk? 時， 齊齊哈爾大學(xué)畢業(yè)設(shè)計 (論文 ) 9 ? ? 11112111 121 ??????? ??????????? ???????? ? ? knnnknkn nnCnCnC ? 證明 我們 建立 如下概率模型： 設(shè)有 k 張卡片 ，等可能地投入 n個箱子，求每一個箱子中至少有一張卡片 的概率 . 記事件 B 為 每一 箱子中至少有一張卡片 事件 iA 為第 i個箱子中沒有卡片 （ ni ,2,1 ?? ） 則 nAAAAB ????? 321? 根據(jù)容斥原理，得 ? ? ? ?1 2 3 nP B P A A A A? ? ? ? ? ????? ? ?? ?ni nii ii AAPAP1 1121 21 ? ? ? ? ? ? ? ?nnniii iiiiiin AAAPAAAPnnn ????2111 11121 121121??? ???? ???? 因為 ? ? ? ? kkki nnnAP ?????? ???? 111 （ ni ,2,1 ?? ） ? ? ? ? kk kii nnnAAP ?????? ???? 21221 (對任意的 21 ii? ) 依次類推，對任意的 niii ??? ?21 ，我們有 ? ?? ?? ?knkiiikiiinnAAAPnnAAAPnAAAPn?????????????? ????????????1113121121321???? 于是 齊齊哈爾大學(xué)畢業(yè)設(shè)計 (論文 ) 10 ? ?? ?????????????? ???????? ??niiiikniiknininCAAPnCAP21212112112111 所以 ? ? ? ? knnnknkn nnCnCnCBP ?????? ??????????? ???????? ?? ? 1112111 121 ? 從而 ? ? ? ?BPBP ??1 即 ? ? ? ????????? ?????? ??????????? ???????? ??? ?knnnknkn nnCnCnCBP 11121111 121 ? 但是由于 nk? ,事件 B 每 一箱子中至少有一張卡片 為一不可能事件，故 0)( ?BP ,從而當(dāng) nk? 時 . .111)1(2111 121 ??????? ??????????? ???????? ? ?knnnknkn nnCnCnC ? 例 3 證明組合恒等式 nnCCCC nnnnn 12321 232 ?????? ? 證明 我們構(gòu)造如下概率模型： 有一枚均勻的硬幣，我們重復(fù)投擲 n次，求它正面向上的 次數(shù)的期望 。 這是因為從盒中取出的 mn? 張卡片一共有 )!( mn? 種可能方法。 首先我們先需要計算出 ? 的分布列，按照古典概率的計算： 齊齊哈爾大學(xué)畢業(yè)設(shè)計 (論文 ) 18 1,3,2,)2)(1( ))(1(6! ))(1()!3(!3)( ???? ???????? nknnn knkn knknkP ?? 然后根據(jù)數(shù)學(xué)期望的定義我們可以得出： ? ??? ?? ???????? 12 12 ))(1()2)(1( 6)(nk nk knkknnnkkpE ?? 另外，我們假設(shè)從最低下開始一張一張地翻牌，直到抽取到第二張 K 出現(xiàn)為止，此時抽出的紙牌數(shù)目為 ?，由對稱性可知， ? 與 ? 有相同的分布列，于是也有相同的數(shù)學(xué)期望，即 ?? EE ? ,而且它們有關(guān)系： 1??? n?? 對這個式子兩邊求期望： 1??? nEE ?? 所以 21??nE? 然后將其帶入 ? 式可得 4 112 2))(1( ??? ???? nnk Cknkk 運(yùn)用構(gòu)造概率模型證明組合恒等式 運(yùn)用構(gòu)造概率模型證明組合和恒等式大體上分為兩步： 第一步， 將待證明的組合恒等式改寫為 11 ???ni iP的形式； 第二步，通過構(gòu)造出合適的概率模型，使得完備事件組 ),2,1( niAi ?? 互斥，并且 ????ni iA1，同時 ),2,1()( nipAP ii ??? 。? nA ：當(dāng) 1x =n 時， ),( 2 rxx ? 的解的個數(shù)為 nrnC 2?? 由于 1)(10 20?????? ??????n rnniin rinni i CCAP 齊齊哈爾大學(xué)畢業(yè)設(shè)計 (論文 ) 22 所以得到 ??? ????? ? niin rinn rn CC0 21 例 5 證明組合恒等式 ?? ??? ?rjj jmr mr CC0 1 證明 之前的例子我們證明過這樣一個組合恒等式： rnrnrn CCC 111 ??? ?? 這個需要被證明的組合恒等式實際就是該組合恒等式的推廣，于是我們建立如下古典概率模型： 現(xiàn)在將 rm? 張卡片從 1 進(jìn)行編號，并從中抽取 r 張卡片作為一組，用 n 來表示 n,2,1 ? 號都被選出而 1?n 號未被選出的最大值，如 1 號未被選出那么 0?n .若 1 號選上了而 2 號未被選上，則 1?n ，如此等等，令 in? ，不同組的卡片數(shù)顯然等于從編號為 miii ??? ,3,2 ? 的卡片中抽出 ir? 張卡片的選法總數(shù)。 考慮 n 張白色卡片與 1?r 張黑色卡片組成的排列，將每一個這樣的排列與)(? 式按照下面的方式對應(yīng)起來：使 1x 等于排列中第一張黑色卡片左邊的白色卡片的張數(shù)， 2x 等于第二張黑色卡片間白色卡片的張數(shù)，如此繼續(xù)到 rx ，它等于最后一張黑色卡片右邊的白色卡片的張數(shù)。111 ?? ?????? ??? nm rXPXEnm rXP kkk , 1,2,1 ?? mk ? . 齊齊哈爾大學(xué)畢業(yè)設(shè)計 (論文 ) 15 ? 121 ????? mXXXX ? ? ? ? ? ? ? ? ? ?? ?? ????? ???????? 1111 1111mkmk kk nmmrXPXEXE 例 5 證明組合恒等式 ?? ???? ???nkk nmkn mm nmCC1 111 )1(/ 證明 一個盒子中裝有 m 張白色卡片 n 張黑色卡片 ， 我們進(jìn)行連續(xù)不放回地抽