緒言

在組合學(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:

分配方法

	1	2	3	4	5	6	7	8
箱1 子2	abc	ab	ac	bc	a	b	c
		c	b	a	bc	ac	ab	abc

表2

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

分配方法

	1	2	3	4
箱1 子2	aaa	aa	a
		a	aa	aaa

表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為第二型史特林數的一些表值。

應用

最後我們看一些佔有問題應用的例子，其中球與箱子是否可區分，係根據我們解釋來判斷。

例題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)$種。

參考文獻

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