建構(gòu)概率模型證明組合恒等式

【摘要】 本文通過(guò)建構(gòu)概率模型證明了一些組合恒等式，使組合恒等式的證明直觀簡(jiǎn)潔.

【關(guān)鍵詞】 組合恒等式；概率

【中圖分類號(hào)】 O211 【文獻(xiàn)標(biāo)志碼】 A

引 言

近年來(lái)，組合恒等式的研究正越來(lái)越受到人們的關(guān)注，它已成為組合數(shù)學(xué)中的一個(gè)新的分支.1972年H.W.Gould教授[1]在《Combinatorial Identities》一書中收集了550個(gè)組合恒等式，而且將證明方法歸為9類，這無(wú)疑是組合恒等式研究上了不起的工作.眾所周知，許多組合恒等式的證明存在一定的困難，有的證明還很繁瑣.概率方法有時(shí)使得組合恒等式的證明簡(jiǎn)便且極易掌握.石煥南，范淑香[2]給出了兩個(gè)組合恒等式的概率證明.黃丹，周學(xué)松[3]則得到了四個(gè)新的組合恒等式.本文利用概率方法證明了一些組合恒等式，值得一提的是利用隨機(jī)變量的獨(dú)立性證明組合恒等式.

1.用古典概型證明組合恒等式

引理 1.1 若{A1，A2，…，An}構(gòu)成一個(gè)完備事件組，即A1，A2，…，An兩兩互斥，∪ n i=1 Ai=Ω，則∑ n i=1 P（Ai）=1.

定理 1.1 ∑ m k=0 CkmCr+kn=Cm+rm+n.

證明 考慮隨機(jī)試驗(yàn)：從m件正品和n件次品中隨機(jī)地取m+r件產(chǎn)品，設(shè)事件Am-k表示“其中恰有m-k件正品”，k=0，1，…，m.Am，Am-1，…，A0兩兩互斥，且∪ m k=0 Am-k=Ω，由概率的有限可加性有

1=P（∪ m k=0 Am-k）= ∑ m k=0 Cm-kmCr+kn Cm+rm+n .

又由對(duì)稱性有Cm-km=Ckm，于是∑ m k=0 CkmCr+kn=Cm+rm+n.

定理 1.2 Cnn+m-1=C1mC0n-1+C2mC1n-1+…CnmCm-1n-1.

證明 建構(gòu)概率模型：把n只沒(méi)有區(qū)別的球放入m（m≤n）個(gè)標(biāo)了號(hào)的盒子中.Ak表示事件“從1到m中選取任意的k個(gè)盒子，n只球放到k個(gè)盒子中，且沒(méi)有盒子空著”，k=1，2，…，m.由古典概率計(jì)算公式得

P（Ak）= CkmCk-1n-1 Cm-1n+m-1 = CkmCk-1n-1 Cnn+m-1 .

A1，A2，…，Am兩兩互斥，∪ m i=1 Ai=Ω，則

1=P（Ω）=P（A1∪A2∪…∪Am）=∑ m k=1 P（Ak）=∑ m k=1 CkmCk-1n-1 Cnn+m-1 .

從而證得Cnn+m-1=C1mC0n-1+C2mC1n-1+…CnmCm-1n-1.

2.用乘法定理證明組合恒等式

引理 2.1 設(shè)A1，A2，…An 為n個(gè)事件，n≥2，且P（A1A2…An-1）>0，則有

P（A1A2…An）=P（An|A1A2…An-1）P（An-1|A1A2…An-2）…P（A2|A1）P（A1）.

定理 2.1 1=（k！）2Ckn∑ 2k-1 i=k Ci-km Cim+ni！（2k-i）！ .

證明 建構(gòu)摸球模型：設(shè)袋中裝有m只白球，n只紅球，自袋中取k（k≤min{m，n}）只球，若取出1只紅球，則計(jì)為1只球；若取出1只白球，則相應(yīng)取出1只紅球，白球不計(jì)數(shù)，只算取出1只球.然后接著再取，直到總共取出k只球?yàn)橹?Bi表示事件“實(shí)際取出i只球”，i=k，k+1，…，2k-1Bk，Bk+1，…，B2k-1兩兩互斥，∪ 2k-1 i=k Bi=Ω，Aj表示事件“實(shí)際第j次取球取得紅球”，則第i次取得紅球，前面i-1次有k-1次取得紅球，其余取得白球.考慮在指定的k-1次取得紅球，不妨設(shè)前2k-i次取得紅球，后面先是取得白球后是取得紅球，其概率為

P（A1A2…A2k-iA2k-i+1 A2k-i+2…Ai-1 Ai）=P（Ai|A1A2…Ai-1 ）…P（A2|A1）P（A1）= n（n-1）…（n-k+1）m（m-1）…（m-（i-k）+1） （m+n）（m+n-1）…（m+n-i+1） .

這種指定的方式有Ci-kk種，則有

P（Bi）=Ci-kk n（n-1）…（n-k+1）m（m-1）…（m-（i-k）+1） （m+n）（m+n-1）…（m+n-i+1） = （k！）2Ckn Ci-km Cim+ni！（2k-i）！ .故有

1=P（Ω）=P（∪ 2k-1 i=k Bi）=（k！）2Ckn∑ 2k-1 i=k Ci-km Cim+ni！（2k-i）！ .

3.用隨機(jī)變量的獨(dú)立性證明組合恒等式

定義3.1[4] 負(fù)二項(xiàng)分布亦稱“帕斯卡（Pascal）分布”，它有如下基本模型：

設(shè)p為伯努利試驗(yàn)中每次試驗(yàn)成功的概率，則伯努利試驗(yàn)列中恰好出現(xiàn)n次成功所需試驗(yàn)次數(shù)服從參數(shù)為n，p的負(fù)二項(xiàng)分布

P{Y=k}=Cn-1k-1pn（1-p）k-n，k=n，n+1，n+2，….

記作Y～NB（n，p），其中0

定理3.1 ∑ i-1 m=r Cr-1m-1Cs-1i-m-1=∑ i-1 n=s Cr-1i-n-1Cs-1n-1.

證明 假設(shè)X～NB（r，p），Y～NB（s，p），故