11403 佔有問題

終極密碼

遊戲規則:本遊戲為猜密碼的遊戲。密碼為0到100之間的其中1個整數,電腦會提示密碼的所在範圍,玩家必須在6次之內猜到密碼才能過關。
★ 終極密碼為0到100之間 ★
您共有六次機會

緒言

在組合學(combinatorics)與機率論的發展歷史中,將$n$個球放在$k$個箱中是個很重要的模式,這個問題稱為佔有問題 (occupa-ncy problem),佔有問題的應用很廣,我們將探討這些問題。首先看看以下的例子:
  1. 車禍:$n$件車禍發生於週一到週日的可能情形,相當於置$n$個球於$k=7$個箱中的分佈狀況。
  2. 抽樣:$n$個人按職業分類,則人相當於球,類別相當於箱子。
  3. 生物放射實驗:眼睛的網膜細胞曝光時,光線的例子相當於球,細胞則相當於箱子。同理,在研究放射對遺傳的影響時,$\alpha$粒子相當於球, 而染色體相當於箱子。
  4. 宇宙射線實驗:射入蓋氏計數器的粒子相當於球,而計數器相當於箱子。
  5. 骰子:擲一個骰子$n$次所出現點數的分配,相當於置$n$個球於$k=6$個箱的分佈。
  6. 隨機亂數:$n$個數字的各種排列,相當於置$n$個球於$k=10$個箱中,10個箱子標示為0,1,2,.........,9。
  7. $n$個人的性別分配:相當於置$n$個人於$k=2$個箱中。
  8. 彩券收集:所收集的彩券相當於球,彩券種類相當於箱子。
  9. 基因分配:每一個體(人、植物或動物)都從上一代遺傳下來某些基因,設某一基因可能有$A_1,A_2,......,A_k k$種型態出現, 則其後代可依基因型態而分類。故後代相當於球而遺傳型態$A_1,A_2,......,A_k$相當於$k$個箱子。
  10. 化學:長鏈聚合體與氧分子發生反映,每一鏈可與0,1,2,......個氧分子發生作用,則反應的氧分子相當於球,而聚合鏈相當於箱子。
  11. 感光乳劑理論:感光版塗上對光量子敏感的藥劑粒子,若一藥劑粒子被$r$個光量子擊中,則發生反應, 我們想知道有幾個粒子可能被$r$個光量子擊中,這裡光量子相當於球,粒子相當於箱子。
  12. 錯印:一本書$k$頁中有$n$個印錯的分配情形,相當於$n$個球置於$k$個箱中的分配情形。

分配型態

將$n$個球放在$k$個箱中,根據球是否可區分,箱子是否可區分,及是否允許有空箱,這個問題的模式共有8種如表1, 稍後我們再一一探討各種不同情況下,分配方法的個數。

球是否可區分箱子是否可區分是否允許有空箱$n$個球放在$k$個箱中的方法數
$1a$$k^n$
$1b$$k!S_{n,k}$
$2a$$C(n+k-1,k-1)$
$2b$$C(n-1,k-1)$
$3a$$S_{n,1}+.........+S_{n,k}$
$3b$$S_{n.k}$
$4a$$n$分割為$k$個或更少正整數和的方法數
$4b$$n$分割為$k$個正整數和的方法數
表1

考慮$n=3,k=2$的例子

(1a)球可區分標識為a、b、c,箱子可區分標識為1、2,允許有空箱,共有8種方法如表2:

分配方法

12345678
箱1
子2
abcabacbcabc
cbabcacababc
表2
  • (1b)同(1a)但不允許有空箱,共有6種方法,即表2的方法2-7。
  • (2a)球不可區分表為a、a、a,箱子可區分標識為1、2,允許有空箱共有4種方法如表3:
分配方法
1234
箱1
子2
aaaaaa
aaaaaa
表3

(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$個可區分的箱中,允許有空箱:
$n$個不可區分的球表為aa......a,我們在這$n$個$a$中插入$k-1$條橫線,例如$n=5,k=3$,則a|aaa|a為一種分配方法,即1號箱1個球, 2號箱3個球,3號箱1個球。又如|aaaa|a亦為一種分配方法,即1號箱0個球,2號箱4個球,3號箱1個球。 故$n$個$a$與$k-1$條橫線排列的方法共有$$\frac {(n+k-1)!}{n!(k-1)!} =C(n+k-1,k-1)$$

(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)但不允許有空箱:
同理,分配方法正如將$n$分割成$k$個正整數和的方法,例如$n=5,k=3$, 則共有1+2+2=1+1+3,這2種方法。

(3b)$n$個可區分的球放在$k$個不可區分的箱中,不允許有空箱:
定義這種情況下分配方法的個數為$S_{n,k}$,這個樹稱為第二型史特林數(Striling number of the second kind), 我們將利用包含排除原理(Principle of inclusion and exclusion)證明下式: $$S_{n,k}=\frac 1{k!} \sum_{i=0}^{k} (-1)^i(^k_i)(k-i)^n$$ 例如 ,$n=4,k=2$,則 $$S_{4,2}=\frac 1{2!}\sum_{i=0}^{2}(-1)^i(^2_i)(2-i)^4$$ $$=\frac 1{2}(16-2+0)=7$$ 若4個球表為a、b、c、d,分成兩堆(放入兩個不可區分的箱中),則有以下7種方法: $$\{a,b\},\{c,d\}$$ $$\{a,c\},\{b,d\}$$ $$\{a,d\},\{b,c\}$$ $$\{a\},\{b,c,d\}$$ $$\{b\},\{a,c,d\}$$ $$\{c\},\{a,b,d\}$$ $$\{d\},\{a,b,c\}$$ 現在介紹包含排除原理,由圖(1a),我們可以輕易看出 $$|A_1∪A_2|=|A_1|+|A_2|-|A_1∩A_2|$$ 其中A為集合,|A|表示集合元素之個數。 $$|A^\prime_1∩A^\prime_2|=|S|-(|A_1|+|A_2|)$$ $$+|A_1∩A_2|$$ 由圖(1b)亦不難得知 $$|A_1∪A_2∪A_3|=|A_1|+|A_2|+|A_3|$$ $$-|A_1∩A_2|-|A_1∩A_3|-|A_2∩A_3|$$ $$+|A_1∩A_2∩A_3|$$ $$|A^\prime_1∩A^\prime_2∩A^\prime_3|=|S|-(|A_1|+|A_2|+|A_3|)$$$$ +(|A_1∩A_2|+|A_1∩A_3|)$$$$+(|A_1∩A_2|+|A_1∩A_3|+|A_2∩A_3|)-|A_1∩A_2∩A_3|$$

圖一

將上式推廣,以數學歸納法可證得以下定理:

定理1:包含排除原理
設$A_1,......,A_n$為集合S的子集,則 $$|A_1∪A_2∪......∪A_n|$$ $$\sum_{1\le i\le n} |A_i|-\sum_{1\le i\lt j\le n} |A_i∩A_j|$$ $$+\sum_{1\le i\lt j\lt k\le n}|A_i∩A_j∩A_k|-...$$ $$+(-1)^{n-1}|A_1∩A_2∩...∩A_n|$$ $$|A^\prime_1∩A^\prime_2∩......∩A^\prime_n|$$ $$=|S|-\sum_{1\le i\le n} |A_i|+\sum_{1\le i\lt j\le n}|A_i∩A_j|$$ $$-\sum_{1\le i\lt j\lt k\le n}|A_i∩A_j∩A_k|$$ $$+...+(-1)^n|A_1∩A_2∩...∩A_n|$$ 定理2:$S_{n,k}=\frac{1}{k!}\sum _{i=0}^k(-1)^i(^k_i)(k-i)^n$

證明:考慮將$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$個可區分的箱中,且不允許有空箱:
根據$S_{n.k}$的定義,顯然共有$k!S_{n,k}$種方法。

(3a)$n$個可區分的球,放在$k$個不可區分的箱中,允許有空箱:
情況如同(3b)但允許有空箱,在(3b)中不允許有空箱,共有$S_{n,k}$種方法,現在允許有空箱,可有以下不同情況: 沒有空箱,恰有1個空箱,恰有2個空箱,......,恰有$k-1$個空箱。因此分配方法共有 $$S_{n,k}+S_{n,k-1}+......+S_{n,1}$$

第二型史特林數

我們亦可利用生成函數(generating function)的技巧求得定理2中第二型史特林數的公式,參閱 。我們現在將利用組合推理求得第二型史特林數$S_{n,k}$的遞廻關係 (recurrence relation)。

定理3:$S_{n,k}=S_{n-1,k-1}+kS_{n-1,k}$
$S_{n,1}=1,S_{n,n}=1$

證明根據$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)$
故得,$x^n=\sum^n_{k=0}S_{n,k}[x]_k$
因$S_{n,0}=0$,故 $$x^n=\sum^n_{k=1}S_{n,k}[x]_k=S_{n,1}x+S_{n,2}x(x-1)$$ $$+......+S_{n,n}x(x-1)...(x-n+1)$$ 上式及第二型史特林數的原始定義,例如, $$x^4=x+7x(x-1)+6x(x-1)$$ $$‧(x-2)+x(x-1)(x-2)$$ $$‧(x-3)$$ 故$S_{4,1}=1,S_{4,2}=7,S_{4,3}=6,S_{4,4}=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_{3,3}=1,s_{3,2}=-3,_{3,1}=2$
第二型史特林數,亦可表示如下,證明參閱。 $$S_{n,k}=\frac{k^n}{k!}\frac{Γ(n+1)}{Γ(n+1-k)}\int^{\frac{1}{k}}_0...\int^{\frac{1}{k}}_0(1-\sum^k_{i=1}x_i)^{n-k} \prod^k_{i=1}dx_i$$ 例如,$n=4,k=2,S_{4,2}$ $$=\frac{16}{2}\frac{Γ(5)}{Γ(3)}\int^{\frac{1}{2}}_0\int^{\frac{1}{2}}_0(1-x_1-x_2)^2dx_1dx_2=7$$

最後,我們在考慮第二型史特林數的一般化,定義$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為第二型史特林數的一些表值。

表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$種。
(ii)此為$2a$的情況,共有$C(n+k-1,k-1)$種。
(iii)共有$C(k,n)$種。

參考文獻

Feller,W.(1950)."An Introduc-tion to Probability Theory and its Applications,"2d.ed.,John Wiley & Sons. Olkin,I. & Sobel,M.(1965)."Integral expressions for tail prob-abilities of the multinomial and negative multinomial distributions,"Biometrika,52,p.167-179. Roberts,F.(1984)."Applied Co-mbinatorics,"Prentice-Hall. 劉涵初(1987)."離散與組合數學",華泰書局。

---本文作者任教於逢甲大學統計系---