發刊日期 |
1987年12月
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
標題 | 佔有問題 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
作者 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
關鍵字 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
檔案下載 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
全文 |
緒言在組合學(combinatorics)與機率論的發展歷史中,將$n$個球放在$k$個箱中是個很重要的模式,這個問題稱為佔有問題 (occupa-ncy problem),佔有問題的應用很廣,我們將探討這些問題。首先看看以下的例子:
分配型態將$n$個球放在$k$個箱中,根據球是否可區分,箱子是否可區分,及是否允許有空箱,這個問題的模式共有8種如表1, 稍後我們再一一探討各種不同情況下,分配方法的個數。
考慮$n=3,k=2$的例子 (1a)球可區分標識為a、b、c,箱子可區分標識為1、2,允許有空箱,共有8種方法如表2: 分配方法
(2b)同(2a)但不允許有空箱,共有2種方法,即表3的方法2-3。 (3a)球可區分表為a、b、c,但箱子不可區分,允許有空箱,共有4種方法,即表2的方法1-4(因箱子不可區分,故表2中,方法1與8同, 2與7同,3與6同,4與5同)。 (3b)同(3a)但不允許有空箱,共有3種方法,即表2的方法2-4。 (4a)球不可區分表為a、a、a,箱子亦不可區分,允許有空箱,共有2種方法,即表3的方法1-2(因箱子不可區分,故表3中, 方法1與4同,2與3同)。 (4b)同(4a)但不允許有空箱,共有1種方法,即表3的方法2。 現在我們來求表1中各種不同情況下,分配方法的個數: (1a)$n$個可區分的,放在$k$個可區分的箱中,允許有空箱:因每一個球放入箱中有$k$個選擇,根據乘法原理,共有$k^n$種方法
(2a)$n$個不可區分的球,放在$k$個可區分的箱中,允許有空箱: (2b)同(2a)但不允許有空箱:故每箱先放一個球,還剩$n-k$個球,如同(2a)的組合推理,$n-k$與$a$與$k-1$條橫線排列的方法共有 $$\frac {(n-k+k-1)!}{(n-k)!(k+1)!}$$$$=C(n-1,k-1)。$$ (4a)$n$個不可區分的球放在$k$個不可區分的箱中,允許有空箱:定義一個正整數$n$的分割為一群正整數其和為$n$, 例如5的分割共有7種如下:$$1+1+1+1+1$$$$=1+1+1+2$$$$=1+2+2$$$$=1+1+3$$$$=2+3=1+4=5$$ 故將$n$個不可區分的球放入$k$個不可區分的箱中,且允許有空箱的分配方法,整如將$n$分割為$k$個或更少正整數和的方法, 例如,$n=5,k=3$,則共有1+2+2=1+1+3=2+3=1+4=5,這五種方法,如其中1+4即表一個箱子含1個球,1個箱子含4個球, 另一個箱子為空箱的分配方法。
(4b)如同(4a)但不允許有空箱:
(3b)$n$個可區分的球放在$k$個不可區分的箱中,不允許有空箱: 將上式推廣,以數學歸納法可證得以下定理:
定理1:包含排除原理 證明:考慮將$n$個可區分的球放在$k$個可區分的箱中,且不允許有空箱。令$A_i$表集合含$i$號箱為空的方法,故問題為求 $|A^\prime_1∩A^\prime_2∩......A^\prime_k|$,因$|S|=k^n$,若$i$號箱為空,則每一個球放入箱中只有$k-1$種選擇, 故$|A_i|=(k-1)^n$,同理,$|A_i∩A_j|=(k-2)^n,|A_i∩A_j∩A_k|=(k-3)^n,......$,根據定理1可得 $$|A^\prime_1∩A^\prime_2∩......∩A^\prime_k|$$ $$=k^n-(^k_1)(k-1)^n+(^k_2)(k-2)^n$$ $$+......+(-1)^k(^k_k)(k-k)^n$$ $$=\sum^k_{i=0}(-1)^i(^k_i)(k-i)^n$$ 因$S_{n,k}$表$n$個可區分的球放入$k$個不可區分的箱中,且不允許有空箱的方法數,而前面的結果為$k$個可區分的箱子,故除以$k!$ 即得$S_{n,k}$的式子。
(1b)$n$個可區分的球,放在$k$個可區分的箱中,且不允許有空箱:
(3a)$n$個可區分的球,放在$k$個不可區分的箱中,允許有空箱: 第二型史特林數
我們亦可利用生成函數(generating function)的技巧求得定理2中第二型史特林數的公式,參閱
定理3:$S_{n,k}=S_{n-1,k-1}+kS_{n-1,k}$ 證明根據$S_{n,k}$的定義,$S_{n,k}$表$n$個可區分的球,放在$k$個不可區分的箱中,且不允許有空箱的方法數, 顯然$S_{n,1}=1,S_{n,n}=1$,這是遞廻關係的起始條件。 我們先考慮$n-1$個球放在$k$個箱中,有以下兩種情況:(i)有一個空箱:故有$S_{n-1,k-1}$種方法,剩下的一個球必得放入此空箱。 (ii)沒有空箱:有$S_{n-1,k}$種方法,而剩下的一個球可放在任意一個箱中,因此共有$kS_{n-1,k}$種方法。得證。 例如,$n=4,k=2$,則 $$S_{4,2}=S_{3,1}+2S_{3,2}$$ $$S_{3,2}=S_{2,1}+2S_{2,2}$$ $$=1+2=3$$ 故$S_{4,2}=1+2‧3=7$ $S_{n,k}=S_{n-1,k-1}+kS_{n-1,k}$與$C(n,k)=C(n-1,k-1)+C(n-1,k-1)$這個二項關係很相似,正如巴斯卡三角形 (Pascal's triangle),可利用表4的史特林三角形(striling's triangle)求連續的$S_{n,k}值。$ $$S_{1,1}$$ $$S_{2,1}\,\,S_{2,2}$$ $$S_{3,1}\,\,S_{3,2}\,\, S_{3,3}$$ $$S_{4,1}\,\,S_{4,2}\,\, S_{4,3}\,\, S_{4,4}$$ $$S_{5,1}\,\,S_{5,2}\,\, S_{5,3}\,\, S_{5,4}\,\, S_{5,5}$$ $$1$$ $$1\,\,\,1$$ $$1\,\,\,3\,\,\,1$$ $$1\,\,\,\,7\,\,\,6\,\,\,\,\,1$$ $$1\,\,15\,\,25\,\,10\,\,1$$ 表4
將$n$個可區分的球放在$m$個可區分的箱中,共有$m^n$種方法,若限制不能有空箱,則有$m!S_{n,m}$種方法;若限制只能有一個空箱,
則有$(^m_{m-1})(m-1)!S_{n,m-1}$種方法,若限制只能有個空箱,則有$(^m_{m-2})(m-2)!S_{n,m-2}$種方法,........,故
$$m^n=\sum^m_{k=0}(^m_k)k!S_{n,k}(若n\lt m,則S_{n,k}=0,k\gt n)$$
$$=\sum^n_{k=0}(^m_k)k!S_{n,k}(若n\gt m,則(^m_k)=0,k\gt m)$$
$$=\sum^n_{k=0}S_{n,k}[m]_k$$
定義$[m]_k=m(m-1)......(m-k+1)$
而第一型史特林數的定義$S_{n,k}$則為
$$[x]_n=\sum^n_{k=0}s_{n,k}x^k,s_{n,0}=0,n\gt 0$$
例如,$[x]_3=x(x-1)(x-2)=x^3-3x^2+2x$ 最後,我們在考慮第二型史特林數的一般化,定義$S^{(r)}_{n,k}$為$n$個可區分的球,放在$k$個不可區分的箱中, 且每箱至少$r$個球的方法數,所以$S^{(1)}_{n,k}=S_{n,k}$,以下定理4為$S^{(r)}_{n,k}$的遞迴關係。 定理4:$S^{(r)}_{n,k}=kS^{(r)}_{n-1,k}+(^{n-1}_{r-1})S^{(r)}_{n-r,k-1}$ 證明:先考慮$n-1$個球放在$k$個箱中,有以下兩種情況:(i)每箱至少$r$個球:因此另外一個球可放在任意一個箱中, 共有$kS^{(r)}_{n-1,k}$種方法。(ii)$k-1$個箱中至少有$r$個球,另一個箱子恰有$r-1$個球: 因此另外一個球需放在只有$r-1$個球的箱中,故有$(^{n-1}_{r-1})$種方法選這$r-1$個球,剩下$(n-1)-(r-1)=n-r$個球放在$k-1$ 個箱中且每箱至少$r$個球,則有$S^{(r)}_{n-r,k-1}$種方法,共有$(^{n-1}_{r-1})S^{(r)}_{n-r,k-1}$種方法, 顯然可知,若$n\lt kr$,則$S^{(r)}_{n,k}=0$。若$n\ge r$,則$S^{(r)}_{n,1}=1$。例如, $$S^{(2)}_{4,2}=2S^{(2)}_{3,2}+(^3_1)S^{(2)}_{2,1}$$ $$2‧0+3‧1=3$$ 若球表為a、b、c、d,則3種方法如下 $$\{a,b\},\{c,d\}$$ $$\{a,c\},\{b,d\}$$ $$\{a,d\},\{b,c\}$$
又如,$$S^{(2)}_{5,2}=2S^{(2)}_{4,2}+(^4_1)S^{(2)}_{3,1}$$
$$=2‧3+4‧1=10$$
表5為第二型史特林數的一些表值。
應用最後我們看一些佔有問題應用的例子,其中球與箱子是否可區分,係根據我們解釋來判斷。 例題1:某醫院九月份共接生80個嬰兒,記錄下每個嬰兒的出生日期,則這個事件的發生共有幾種方法? 解:嬰兒看成是球,日期看成是箱子。若不區分嬰兒,只區分日期,則為$2a$的情況,$n=80,k=30$,故有$C(80+30-1,30-1) =C(109,29)$種方法。若每天至少接生一個嬰兒,則為$2b$的情況,共有$C(109,29)$種方法。若不區分嬰兒,亦不區分日期, 我們只想知道有幾天接生兩個嬰兒,有幾天接生三個嬰兒,......,則為$4a$的情況,需考慮80分割成30個或更少的正整數和。例題2:某打卡員打卡100張,共有30個錯誤,這事件的發生共有幾種方法? 解:錯誤看成是球,卡片看成是箱子,錯誤的型態不予考慮,則球不可區分。也許我們想知道是否因工作的枯燥而導致錯誤增加的趨勢。 故考慮卡片可區分此為$2a$的情況,有$C(30+100-1,100-1)=C(129,99)$種方法。 例題3:假設我們案畢業先後次序,記錄某校資訊系1000位畢業生的性別,則這事件的發生共有幾種方法? 解:1000人看成1000個球,性別男與女則看成兩個可區分的箱子。若不區分此1000人,亦即只想知道男女分配的情形, 則此為$2a$的情況,共有$$C(1000+2-1,2-1)$$$$=C(1001,1)=1001種$$ 例題4:電梯上有8位乘客,電梯將在6層不同的樓停下這事件的發生共有幾種方法? 解:乘客看成是球,每層樓看成是箱子。若我們想知道那些乘客在同一層樓出去,則球可區分,箱子不可區分,此為$3a$的情況, 共有$S(8,1)+S(8,2)+........+S(8,6)$種方法。 例題5:統計力學(Statistical Mechanics)在統計力學中,我們想知道$n$個粒子(中子、質子、電子、......),在$k$個不同能階 (energy level)上分佈的情形,共有幾種?(i)假設粒子可區分,則為Macwell-Boltzm-ann模式,(ii)假設粒子不可區分,則為Bose-Einstein模式。 (iii)假設粒子不可區分,且服從Pauli排除原理(Pauli exclusion prin-ciple),亦即不能有兩個粒子在同一能階,則為Fremi-Dirac模式。
解:(i)此為$1a$的情況,共有$k^n$種。 參考文獻---本文作者任教於逢甲大學統計系--- |