【正文】 knkknk qpCP ?? 我們可以證明組合公式 k nmmkmnkmknmknm CCCCCCCCC ??? ????? 011110 ? 齊齊哈爾大學(xué)畢業(yè)設(shè)計 (論文 ) 8 運用概率性質(zhì)證明組合恒等式 我們利用概率的性質(zhì)來證明組合恒等式，這是一種方便的證明方法 ，而且簡單易懂，通常用“必然事件的概率等于 1”和“不可能事件的概率等于 0”來證明。利用數(shù)字特征法是證明組合恒等式的一種比較重要的方法，我們在了解了具體概念后就用一系列的例子加以說明并且具體闡述，從而讓我們了解到這種方法是怎 樣的一種方法。 這是求一個隨機變量 X 的期望值： 記事件 { iX? }={取出的前 i1 張卡片全是黑色卡片 }， 令??? ?? )(0 )(1 iX iXXi ?，那么 xXXXxixixi ixi ii i ????? ??????????????? 11100 01 齊齊哈爾大學(xué)畢業(yè)設(shè)計 (論文 ) 13 由于 iX 非負，所以 ? ?? ???? ???? ???? 1!1 110 )()( imi i mnimxi i CCiXPXEEX 但是我們可以將 EX 更簡單的表示形式計算出來，于是我們假設(shè)已經(jīng)把所有的mn? 張卡片從盒子中取出來了，同時令 1X 表示第一張白色卡片之前的黑色卡片張數(shù) ,? 最后 1?nX 表示最末一張白色卡片之后的黑色卡片張數(shù)，根據(jù) 1X 的定義： mExExExmXXX nn ??????? ?? !21121 , ?? 在考慮 121 , ?nxxx ? 的聯(lián)合分布為 P{ 112211 , ?? ??? nn iXiXiX ?}=)!( !!mn mn?，其中 121 , ?niii ? 是非負整數(shù)，它們的和為 m。 于是我們可以得到： 121 , ?mXXX ? 的聯(lián)合分布是 121 , ?niii ? 的對稱函數(shù)，所以對任意 n個變量求和，所得到的結(jié)果是相同的，于是我們知道 ix 的邊緣分布相同。 如果用 1A ， 2A 分別表示甲或 乙瓶中余下 k 根牙簽 . 用 rA 表示一盒用完， 而另一盒中有 k根的事件，則 21 AAAr ?? . 注意到，當(dāng)發(fā)現(xiàn)一盒已空時． 這一盒必定在前面已用過 n次， 另一盒余下 k根， 從而另一盒已用過 n— k 次， 故共用了 2 n — k +1 次 . 每次取到甲 (乙 ) 瓶的概率是 21 . 所以 ? ? ? ? ? ? ? ?2121 APAPAAPAP r ??? ? = rnnnrnrnnnrn CC???? ??????????????????????????? 212121212121 22 = rnnrnC?? ??????22 21 于是我們得出： ? ? ,21 22 knn knCkp ?? ?????????? nk ,2,1,0 ?? . 下面用不同的方法計算隨機變量 ? 的期望值 . 齊齊哈爾大學(xué)畢業(yè)設(shè)計 (論文 ) 17 根據(jù)定義 ： ? ?? ?? ??? ????????????nknkknnknCkkpkE 0 022 21?? = ?? ???nkn knkn CK0 22 221 另一方面，設(shè) uE ?? ，由 ? ??? ??nk kp0 1?知 ： ? ? ? ?? ? ? ? ? ? ? ?? ?? ?? ?? ? ? ?? ? ? ? ? ?? ?? ? 2/012121121121221122121221211010101210112102221020100 0??????????????????????????????????????????????????????????????????????????????????????? ?? ????????????????????????????? ?pnkpkkpnkpknCknCknCknKPknkPknKPKkpnunnknknkknnkknknnkknknknknnkknknnknknknk 移項整理得： ? ? ? ? 12 12101222 ????????? n nn CnpnE ?? 由 ?E 的唯一性知： ?? ? ?????nknnnn knkn CnCk0 2222 121222 1 整理即得： ? ??? ? ??????nknnnn knk CnCk0222 2122 例 7 證明組合恒等式 4112 2))(1( ??? ???? nnk Cknkk 證明 我們構(gòu)造如下概率模型： 設(shè)有 n 張撲克牌，其中只有 3 張是 K,我們將撲克牌洗一遍之后再從中隨機不放回抽取，直到抽取到第二張 K 為止，此時抽出的紙牌數(shù)為 ? ，求它的期望。 例 1 證明組合恒等式 knknknkn CCCC 11111 ????? ??? 證明 首先我們將公式變形為 11111111 ??????????knknknknknknCCCCCC 齊齊哈爾大學(xué)畢業(yè)設(shè)計 (論文 ) 19 接下來 ，我們構(gòu)造這樣的概率模型： 一個盒子里 裝有 1?n 張卡片，其中有 一張紅色卡片，一張黑色卡片 ， 1?n 張白色卡片，現(xiàn)隨機地從盒子 中抽取 k 張卡片 . 設(shè)事件 A 為 k 張卡片中有紅色卡片 的事件，事件 A 的逆事件記為 A . 則 ? ? 。很容易得到 n張白色卡片與 1?r 張黑色卡片的所有排列與方程 )(? 的全體解一一對應(yīng)，由于排列共有 n rnCrn rn 1)!1(! )!1( ?????? 個，即解也有 nrnC 1?? 個，所以得到 ??? ????? ? niin rinn rn CC0 21 或者還可以如下：我們很明顯看出 1x 可取 n,2,1,0 ? 的 1?n 個值， rxx ,2 ? 可以組成一個 1?r 維向量 ),( 2 rxx ? 令 0A ：當(dāng) 1x =0 時， ),( 2 rxx ? 的解的個數(shù)為 nnrnC??? 2 。 例 1 證明 nnnnn CCC 210 ???? ? 證明 這是一個重要的組合恒等式 , 這里用概率的思想證明 . 為此 我們 構(gòu)造 如下 概率模型： “某人 投籃 命中率 21 ，現(xiàn)獨立地重復(fù) 投籃 了 n 次，問投進 的概率是多少？” 記事件 kA 為投籃 n次投進了 k 次（ nk ,2,1 ?? ） , 于是 問題是求 ? ?nAAAP ???? 21 . 由于 nAAAA ?321 , 兩兩互斥，得 齊齊哈爾大學(xué)畢業(yè)設(shè)計 (論文 ) 23 ? ? ? ???? nk kn APAAAP 121 ???? = ????? ????????????? nk nknknknkkn CC11 22121 又因 nAAA ???? 21 的對立事件是 nAAA ?21? ，問題可以轉(zhuǎn)化為求? ?nAAAP ?211 ?? ，而 ? ?nnn CAAAP 2021 ?? ? ? ? nnn CAAAP 211 021 ???? ? 即 nnnnn CCC 210 ???? ? . 例 2 證明組合恒等式 ? ? ? ? ? ? nnnnnn CCCC 222120 ???? ? 證明 根據(jù)組合式的性質(zhì) . rnnrn CC ?? , 原式左邊 可變形 為： nnnnnnnnnnn CCCCCCC 20xx0 ???? ? ? 兩端同除以 nnC2 ，得： 1202120 ???? ?nn nnnnnnnknnnnnnC CCCCCC CC ? 我們來 觀察上面這個式子 式的概率意義， 可以構(gòu)造 下面的模型： “一 盒子里 有 2n張卡片 ，其中 n 張白色卡片 n張紅色卡片 ，今從中任取 n 張卡片 ，求至少有 一張紅色卡片 的概率 .” 記事件 A 為 抽得的 n個球中至少有 一張紅色卡片； 事件 iA 為 抽得的 n個球中恰有 i張紅色卡片 則 ? ?nninnini CCCAP 2?? （ ni ,2,1 ?? ） 而 nAAAA ???? 21? 且 ??ji A? ? ?ji? 根據(jù)有限可加性，得 齊齊哈爾大學(xué)畢業(yè)設(shè)計 (論文 ) 24 ? ? ? ? ? ? ? ?nnnnnnnnnnnnnnnnCCCCCCCCCAPAPAPAP2022221121???????????? 另一方面 ?A { 抽得的 n 張卡片 都是 白色卡片 } 而 ? ?nnnnnCCCAP 20? 于是 ? ? ? ? nnnnnCCCAPAP2011 ???? 所以 n nnnnn n nnnn nnnnn nnnnC CCC CCCCCCCC 2020222211 1 ???? ?? ? nnnnnnnnnn CCCCCCC 20xx00 ???? ? ? 即 ? ? ? ? ? ? nnnnnn CCCC 222120 ???? ? 例 3 證明組合恒等式 ???? ??mimmnim inin CCC0 2 證明 我們 構(gòu)造 以下 概率模型： 設(shè)箱子中有 n 付大小不同的手套，現(xiàn)在我們隨機從 中取出 m 只，計算取出的 手套 全不配對的概率 . 把從 2n 只 手套 中取出 m 只不同 手套 的組合作為樣本點，則樣本點總數(shù)為mnC2 . 記事件 A 為 取出的 m只 手套 全不配對， 接下來 計算 P(A). 方法一 A 發(fā)生要求 m 只 手套 必須取自于不同型號種類的 手套 ，而 手套 的種類有 n 種，因而 m 只 手套 可有 n 種可供選取，共有 mnC 個選取種數(shù) .同時，在每一種類型號的 手套 中又有“左”、“右”兩只 手套 可選擇，有 12C 種取法，這樣，取出 m只 手套 共有 1212 CC ?? （ m個）種取法 .綜合上述， A的 基本事件 數(shù)目為 mmnC 2? ，則 ? ? ./2 2mnmmn CCAP ?? 方法二 令 ?iA 取出的 m 只 手套 中含有 i 個“左”只 手套 ， mi ?,1,0? .顯然齊齊哈爾大學(xué)畢業(yè)設(shè)計 (論文 ) 25 imi AA 0??? 且 ??jiAA （ )ji? 則 ? ? ? ????mi iAPAP 0 .又因 為 iA 中的 i只“左”手套 可有 n種“左” 手套 可供選取，共有 inC 種取法 .其余另外的 im? 只 手套 全是“右” 手套 ，為了使得取出的 m 只 手套 全不配對，那么，這 in? 只“右” 手套只能在剩下的 in? 種型號的 手套 所對應(yīng)的 in? “右” 手套 中選取，共有 iminC?? 種取法 .于是，由乘法原理可得， iA 的 基本事件 數(shù)目為 imininCC ?? （ mi ?2,1,0? ） 那么 ? ? mnim inini CCCAP 2/???