組合數(shù)學(xué)1-3-組合意義的解釋與應(yīng)用舉例

1、1.3 組合意義的解釋與應(yīng)用舉例,非降路徑問題 組合意義的解釋 應(yīng)用舉例,從(0,0)點出發(fā)沿x軸或y軸的正方向每步走一個單位，最終走到(m,n)點，有多少條路徑？,1. 非降路徑問題,因此若記所求方案數(shù)為 P(m+n; m, n)，則,無論怎樣走法,總有：在x方向上總共走m 步，在y方向上總共走n步。,若用一個x表示x方向上的一步，一個字母y表示y方向上的一步，則(0,0)→(m,n)的每一條路徑可表示為m 個相同的x與n個

2、相同的y的一個排列。,這相當(dāng)于從m+n個位置中選出m個位置放x，剩下的位置自然放置y。,或記為,設(shè)c≥a,d≥b,則由(a,b)到(c,d)的非降路徑數(shù)為：,對每一條接觸x=y 的非降路徑，做(0,1)點到第一個接觸點部分關(guān)于x=y的對稱非降路徑，這樣得到一條從(1,0)到(m,n)的非降路徑。,從(0,1)點到(m,n)點的非降路徑，有的接觸x=y，有的不接觸。,在原模型的基礎(chǔ)上若設(shè)m<n，求(0,1)點到(m,n)點不接

3、觸對角線x=y的非降路徑的數(shù)目 (“接觸”包括“穿過”)?,故所求非降路徑數(shù)為,容易看出從(0,1)到(m,n)接觸x=y的非降路徑與(1,0)到(m,n)的非降路徑(必穿過x=y)一一對應(yīng)。,所求非降路徑數(shù)為,若條件進一步改為可接觸但不可穿過，則限制線要向下或向右移一格，得x-y=1, (0,0)關(guān)于x-y=1的對稱點為(1,-1).,假設(shè)一場音樂會的票價為50元，排隊買票的顧客中有n位只有50元的鈔票，m位只有100元的鈔票。售票處

4、沒有準(zhǔn)備50元的零錢。試問有多少種排隊的方法使得購票能順利進行，即不會出現(xiàn)找不出錢的狀態(tài)。假定每位顧客只買一張票，且n>m。,用一個m+n維的向量來表示一個排隊狀態(tài)，其中每個分量只能取x或y，這里取值y表示這個位置的顧客持有50元的鈔票，取值x表示只有100元的鈔票。,因此這等價于一個從(0,0)到(m,n)點的非降路徑，且滿足y≥x，即可以接觸但不能穿過對角線。,因此所求排隊方法即為上頁討論的答案結(jié)果。,2. 組合意義的解釋,

5、它主要有以下三個重要意義：,(1) 組合意義：n元集中k元子集的個數(shù);,(2) 顯式表示：C(n,k)=n(n-1)…(n-k+1)/k!;,(3) 二項展開式的系數(shù)：即有恒等式,二項式系數(shù) C(n,k) 是組合數(shù)學(xué)中無處不在的一個角色。,1. (對稱性) C(n,r)=C(n,n-r)；,2. (遞推關(guān)系) C(n,r)=C(n-1,r)+C(n-1,r-1)；,從[1,n]去掉一個r子集，剩下一個(n-r)子集。由此建立C(

6、n,r)與C(n,n-r)的一個一一對應(yīng)。,共有C(n-1,r)+C(n-1,r-1)種方案。,a1=1,有C(n-1,r-1)種方案； a1>1,有C(n-1,r)種方案。,解釋1：從[1,n]取a1,a2,…,ar。設(shè)1≤a1＜a2＜…＜ar≤n,對取法分類：,{(0,0)→(m,n)} ={(0,0)→(m,n-1)}∪{(0,0)→(m-1,n)},解釋2：利用非降路徑,C(m+n,m) = C(m+n-1,m)

7、 + C(m+n-1,m-1),也可看做按含1不含1，含2不含2,…,含r不含r的不斷分類。,解釋1：可從上個結(jié)論推論,也可做一下組合證明。從[1,n+r+1]取a1a2…anan+1,設(shè)a1＜a2＜…＜an ＜an+1,可按a1的取值分類：a1=1,2,3,…r,r+1.,若a1=k, 則a2…an+1取自[k+1,n+r+1]，有C(n+r+1-k,n)種取法。這里k從1變到r+1。,故有,解釋2：右邊表示從(0,0)到(n+1

8、,r)的非降路徑數(shù)。,這些路徑一定過且僅過一條帶箭頭的邊。而過這些邊的路徑有(從下到上),按不含1,含1個1,含2個1,…,含r個1分類，,其個數(shù)相應(yīng)為,從[1,…,n+2]中取r個的可重組合模型,,解釋3：利用可重組合.,其個數(shù)為,兩種選法都無遺漏,無重復(fù)地給出可能的方案，應(yīng)該相等。,左邊是從n個元素中取k個組合，再從這k個取r個的組合數(shù)。這相當(dāng)于直接從n個元素中取r個，但是要計算重數(shù)C(n-r,k-r)，因為這相當(dāng)于取定r個后，再

9、從剩下n-r個元素中取k-r個與之前的r個組合。,5. C(m+n,2)-C(m,2)-C(n,2)=mn;,等式右邊可以看作是m個男生n個女生，一男一女的組合數(shù)，易知為mn。,等式左端是從m+n個人中取2人的組合減去純從男生中取2人的組合和純從女生中取2人的組合，余下的即為一男一女的組合。,在 中令x=y=1即得。,左邊表示可以有

10、0-子集(空集),1-子集,…,m-子集。,解釋1：右邊即m個元素的所有選取方案，每一子集都可取或不取。這樣有 2m 種方案。,解釋2：從(0,0)走m步有2m 種走法，都落在直線x+y=m上。,而到(m,0),(m-1,1),(m-2,2),…,(2,m-2),(1,m-1),(0,m)各點的走法各有C(m,0), C(m,1),C(m,2),…,C(m,m-2), C(m,m-1),C(m,m)種。,7. C(m,0) -C(

11、m,1) + …+(-1)mC(m,m)=0；,在 中令x=-y=1即得。,在任一含1組合及與之對應(yīng)的不含1組合中，必有一奇數(shù)個元的組合與一偶數(shù)個元的組合。將含奇數(shù)個元的組合做成集合，將含偶數(shù)個元的組合做成另一集合。這兩個集合的元素個數(shù)相等。,在所有組合中，含1的組合←→不含1的組合。,解釋1：從m個互異紅球和n個互異藍球中取r個球，

12、按r個球中紅球的個數(shù)分類。,解釋2：(0,0)到(m+n-r,r)點的路徑：,C(m,r-k) C(n,k),(0,0)→(m-r+k,r-k)→(m+n-r,r),例1 從號碼1,2,…N中每次取出一個并登記，然后放回，連取n次，得到一個由n個數(shù)字組成的數(shù)列，問按這種方式能得到(1) 多少個嚴(yán)格遞增數(shù)列(n≤N);(2) 多少個不減數(shù)列？,(2) 可重組合 C(N+n-1,n)。,3. 應(yīng)用舉例,無重組合

13、C(N,n)；,(1) 每３人至少缺１把鑰匙，且每３人所缺鑰匙不同。故至少共有C(7,3)=35把不同的鑰匙。,(2) 任一人對于其他６人中的每３人,都至少有１把鑰匙與之相配才能開鎖.故每人至少持C(6,3)＝20把不同的鑰匙。,例2 某保密裝置須同時使用若干把不同的鑰匙才能打開?，F(xiàn)有７個人，每人持若干把鑰匙。須４人到場，所備鑰匙才能開鎖。問：(1) 至少有多少把不同的鑰匙？(2) 每人至少持幾把鑰匙？,(2) 若能級為kE

14、0的質(zhì)點可有2(k2 +1)種狀態(tài)，而且服從Fermi-Dirac分布，即不允許同能級的兩個質(zhì)點有相同狀態(tài),問系統(tǒng)有幾種不同狀態(tài)?(或圖像),例3 有4個相同質(zhì)點,總能量為4E0，E0是常數(shù)。每個質(zhì)點所具能量為kE0,k=0,1,2,3,4.,(1) 若能級為kE0的質(zhì)點可有k2 +1種狀態(tài)，而且服從Bose-Einstein分布，即同能級的質(zhì)點可以處于相同的狀態(tài)，問系統(tǒng)有幾種不同的狀態(tài)?(或圖像),能級k 0 1 2

15、 3 4 (1) k2+1 1 2 5 10 17(2) 2(k2+1) 2 4 10 20 34 狀態(tài)數(shù),例4 設(shè)n位長能糾r個錯的碼字的個數(shù)為M，則,n位長的0-1字符串共有2n 個。但不能每個串都設(shè)為碼字，否則失去糾錯能力。,設(shè)a=a1a2…an，b=b1b2…bn是n位數(shù)串。則a,b的Hamming距離定義為,即對應(yīng)位不同的位的個數(shù)。,Ha

16、mming距離滿足三角不等式：,右圖表示以a為球心,r為半徑的球體中的串都作為a處理。,由漢明不等式,只要兩個碼字a,b滿足d(a,b)≥2r+1,則不至于產(chǎn)生一個碼字c，使得它與ab的漢明距離都小于r，而無法判定是a還是b的錯。,糾錯處理：能糾正傳輸過程中產(chǎn)生的r個錯是指，若規(guī)定a是碼字，收到a'有d(a,a')≤r則將a'當(dāng)作a處理(發(fā)生最多r個錯誤),每一碼字r鄰域內(nèi)的n位二進制數(shù)串的數(shù)目為：,

17、于是,因此各碼字的r-鄰域必須互不相交。,綜合上兩式，有,另一方面任一串與最近的碼字的距離不大于2r，否則這個串本身可作為一新的碼字。,這表明在以所有碼字為球心以2r為半徑的球中，應(yīng)當(dāng)使任一串落入某球內(nèi)。故,例5 凸n邊形沒有3條對角線交于一點，計算各邊及各對角線所組成的互不重疊的多邊形區(qū)域的個數(shù)。,首先可以如下計算：,另一方面，每兩條對角線決定一個內(nèi)部多邊形的頂點，因此內(nèi)部的各多邊形區(qū)域頂點總數(shù)應(yīng)該是4C(n,4)(每個內(nèi)部頂點在(