點算的奧秘:分配問題


本網站至今已介紹了「點算組合學」的幾個主要問題:排列、組合和集合劃分問題。現在的問題是,能否把這 些性質不同的問題統統納入一個統一的框架之下?答案是可以的。本節將指出,上述這些問題都可以看成「分 配」問題的特例。「分配」(Distribution)問題是指以下這類問題:現要把r件物件(以下統統以「球 」為例)分配入n個容器(以下統統以「盒子」為例)中,問有多少種不同的分配方法?這類問題中的球和盒子可 以有多種變化形式(例如它們可以是「可區分」(Distinguishable)的或「不可區分」(Indistinguishable)的, 盒子可容許或不容許空置,每個盒子的容量可以有限或無限等等),因而產生多種類型的「分配」問題。本文將 介紹幾種主要的「分配」問題,並討論它們與其他「點算組合學」問題的對應關係。

為方便舉例,以下用不同的數字1、2、3代表「可區分」的球,並用同一種數字(例如1)代表「不可區分」的球 。至於盒子,則用方括號[]代表。對於「可區分」的盒子,我們可以把它們編號,分別命名為1號、2號 ... n 號盒子,而對於「不可區分」的盒子,則無法進行排序。因此「可區分」的盒子實際等同於「有次序」的盒子, 而「不可區分」的盒子則實際等同於「沒有次序」的盒子。本文用「-」表示盒子之間的次序,若盒子之間沒有 次序,則用逗號(,)把盒子隔開。舉例說,設我們要把4個球分配入3個盒子中,那麼[1,1]-[]-[1,1]便表示把4 個「不可區分」的球中的兩個放進1號盒子,把其餘兩個放進3號盒子,並使2號盒子空置;而[],[1,3],[2,4]則 表示把1號和3號球放進3個「不可區分」的盒子中的一個,把2號和4號球放進另一個,並使餘下的一個盒子空置 (註1)。

現在首先考慮「可區分的球」的分配問題。因應盒子是否可區分,這類問題又可分為兩個次類:「可區分 的球-可區分的盒子」的分配問題和「可區分的球-不可區分的盒子」的分配問題。根據註1,這 類問題與「集合劃分」問題有著明顯的對應關係:各個「可區分的球」對應著不同的元素,各個盒子則對應著 子集。根據前段,「可區分」的盒子等同於「有次序」的盒子,因此「可區分的球-可區分的盒子」的分配問題 便對應著「集合有序劃分」問題,而「可區分的球-不可區分的盒子」的分配問題則對應著「集合(無序)劃分」 問題。

《點算的奧秘:集合劃分問題》中,筆者討論了多種「集合劃分」問題 。除了最基本的「集合劃分」問題(即對子集不加任何限制的「集合劃分」問題)外,其他「集合劃分」問題都 可看成是對子集加上各種限制的「集合劃分」問題,而這些限制在分配問題上則反映為對盒子的限制。舉例說, 「空集」對應著空置的盒子,因此「是否容許空集存在」便對應著「是否空許盒子空置」,而「規定各個子集 的元素個數」則對應著「規定各個盒子所載球的數目」。由於這些限制在上述網頁中已作詳細討論,本文不再 重覆,這裡只提供一個例題。

例題1:如要把210這個數分解為若干個大於1的正整數的乘積,其中各個正整數按遞增序排列,問有 多少種不同分解法?試列出所有分解法。

答1:210可被分解為4個質數的連乘積:2 × 3 × 5 × 7。我們可以把這個問題看 成一個「分配」問題。4個質數相當於4個「可區分的球」,各個正整數則相當於盒子,把4個質數組合成正整數 就相當於把4個球放入盒子中。由於題目規定了正整數按遞增序排列,這實際等於說:在確定各種不同分解法時 ,無需考慮各個正整數的次序(註2),因此可以把這些盒子看成沒有次序的盒子,即「不可區分的盒子」。由於 本題沒有規定正整數的數目,而正整數的數目最多可以有4個,最少必須有1個,這相當於共有4個盒子,並容許 某些盒子空置。根據「分配」問題與「集合劃分」問題的對應關係,本題相當於把4個元素劃歸4個(無序)子集 的「容許空集的集合(無序)劃分」問題,因此可以應用《點算的奧秘:集合劃 分問題》中的公式(5)求解。把n = 4,r = 4代入該公式,得

P1(4, 4)= Σ1 ≤ i ≤ 4 Σ0 ≤ k ≤ i(−1)k C(i, k) (i − k)4 / i!
 = (1 × 1 − 1 × 0) / 1 + (1 × 16 − 2 × 1 + 1 × 0) / 2 +
   (1 × 81 − 3 × 16 + 3 × 1 − 1 × 0) / 6 + (1 × 256 − 4 × 81 + 6 × 16 − 4 × 1 + 1 × 0) / 24
 = 1 + 7 + 6 + 1
 = 15

不過,上述答案包括了一個我們不想要的情況,那就是把4個元素全部劃歸同一個子集,此一情況相當於把210 「分解」成210。由於這不是一個乘積,我們要從上述答案撇除此一情況,所以本題的正確答案應為14。

這14種分解法是2 × 105、3 × 70、5 × 42、7 × 30、6 × 35、10 × 21、14 × 15、2 × 3 × 35、2 × 5 × 21、2 × 7 × 15、3 × 5 × 14、3 × 7 × 10、5 × 6 × 7、2 × 3 × 5 × 7。□

接著讓我們再從另一角度看「可區分的球-可區分的盒子」的分配問題。在 《點算的奧秘:集合劃分問題》中,筆者曾指出某些「集合有序劃分」問題與某些「排列」問題的對應關 係,由於「集合有序劃分」問題與「可區分的球-可區分的盒子」的分配問題存在明顯的對應關係,因此可以推 斷,「可區分的球-可區分的盒子」的分配問題與「排列」問題也應存在對應關係。事實上,這兩類問題的確存 在以下的對應關係:把r個「可區分的球」分配入n個「可區分的盒子」對應於從n類物件(註3)中抽r個出來排列 ;球的編號1、2 ... r對應於排列的次序;盒子的次序對應於物件類別的編號;盒子的容量對應於各類物件的 數目。舉例說,設n = 3,r = 4,那麼分配[3]-[1,4]-[2]便對應著排列 O2-O3-O1-O2,這是因為根據上述對應關係,3號球放於第1個 盒子應對應著把O1排在第3個位置,餘類推。

我們還可以對上述的對應關係作進一步的推廣,從而把以前介紹過的各類「排列」問題解釋為各類「可區分的 球-可區分的盒子」的分配問題。由於盒子對應著物件類別,對各個盒子容量的各種限制就相當於對各類物件數 目的限制。假如盒子的容量沒有限制,那就相當於「無限重覆排列」問題;假如規定了每個盒子所裝載球的數 目,那就相當於「有限重覆全排列」問題;假如規定了每個盒子容量的上/下限,那就相當於「帶上/下限的 排列」問題;假如規定在進行分配時所有盒子都不能空置,那就相當於在進行排列時各個類別的物件都要至少 抽一個出來,這是「帶下限的排列問題」的一種特例;假如規定每個盒子最多只可包含一個物件,那就相當於 「不可重覆的部分排列問題」;最後,假如n = r,並且規定每個盒子有且只有一個物件,那就相當於「不可重 覆的全排列」問題。

至此我們確立了各類「可區分的球-可區分的盒子」的分配問題與各類「排列」問題的一一對應關係。建立這種 對應關係的好處是,當我們解決了其中一方的問題,便同時解決了另一方的對應問題,因此這兩類問題的公式 可以互相借用。舉例說,在《點算的奧秘:集合劃分 問題》中,筆者曾介紹以下的「不容許空集的集合有序劃分」問題的計算公式(本文重新編號為公式(1)):

Σ0 ≤ k ≤ n(−1)k C(n, k) (n − k)r     (1)

現在根據前述的對應關係,我們知道這條公式也就是以下「排列」問題的公式:現要從n類物件中抽r個出來排 序,若規定每類物件都必須至少抽一個出來,問有多少種排法?

接著再看一個例子。

例題2:現要把4個「可區分的球」分配入3個「可區分的盒子」中。若規定第1個盒子最多只可載3個 球而第2個盒子不能空置,問有多少種分配法?

答2:根據「可區分的球-可區分的盒子」的分配問題與「排列」問題的對應關係,本題等同於以下排 列問題:現要從3類物件(O1、O2、O3)中抽4個出來排序。若規定其中包含 最多3個O1和最少1個O2,問有多少種排法?可是這實際等於《點算的奧秘:帶上、下限的排列組合問題》中的例題3,因此我們無需重新求解便 可知本題答案為65。□

確定了「排列」問題對應著哪些「分配」問題,下一個問題自然是,「組合」問題又對應著哪些「分配」問題 ?由於「組合」問題與「排列」問題的差別只在於後者要考慮被抽出來的物件的次序,而前者則無需考慮次序 ,所以我們只需對上述「排列」問題與「可區分的球-可區分的盒子」的分配問題的對應關係略作修改,便可找 到「組合」問題的對應問題。根據上述對應關係,物件排列的次序對應著球的編號1、2 ... r。假如現在無需 再考慮物件的次序,那麼相應地我們也無需再考慮球的編號,但這究竟代表甚麼意思?球的編號是用來區分球 的標誌,因此不考慮球的編號就等於不對球作出區分,使我們的球成為「不可區分的球」。不過,「組合」問 題仍然要區分不同類別的物件,根據對應關係,即仍要區分盒子的次序。由此得知,「組合」問題對應著 「不可區分的球-可區分的盒子」的分配問題。

現在我們可以仿照前面的做法,把以前介紹過的各類「組合」問題解釋為各類「不可區分的球-可區分的盒子」 的分配問題。假如盒子的容量沒有限制,那就相當於「無限重覆組合」問題;假如規定了每個盒子容量的上/ 下限,那就相當於「帶上/下限的組合」問題;假如規定在進行分配時所有盒子都不能空置,那就相當於在抽 取物件時各個類別的物件都要至少抽一個出來,這是「帶下限的組合問題」的一種特例;假如規定每個盒子最 多只可包含一個物件,那就相當於「不可重覆的組合問題」。利用上述對應關係,我們可以運用以前學過的知 識來解答某些「不可區分的球-可區分的盒子」的分配問題,試看以下例題。

例題3:現要把r個球分配入n個盒子中(r ≥ n),若規定所有盒子都不能空置,問有多少種不同分 配法?

答3:根據上述對應關係,本題等同於以下「組合」問題:從n類物件中抽取r個出來,其中每類物件 都必須至少抽一個出來,問有多少種不同抽法?本題的限制條件實際等同於規定各類物件的「下限」為1。由於 規定從每類物件中至少抽一個出來,這實際上確定了要抽出來的r個物件中的n個,只剩下r − n個物件尚 待抽出(由於規定了r ≥ n,所以r − n不為負數),所以問題變成了從n類物件中可重覆地抽取r − n個出來的問題。根據「無限重覆組合」公式,所需答案為

 C(n + r − n − 1, r − n)
=C(r − 1, r − n)
=C(r − 1, r − 1 − r + n)
=C(r − 1, n − 1)□    (2)

正如「可區分的球」的分配問題對應著「集合劃分」問題一樣,「不可區分的球」的分配問題也對應著一種「 劃分」問題。在「點算組合學」上,這種「劃分」問題稱為「整數分割」(Partition of Integer)問 題。這種問題可表述如下:給定一個正整數r,現要把它分割成n個非負整數(正整數或零)相加之和,問有多少 種不同的分割方法?舉例說,設r = 5,n = 3,那麼正整數5便有2 + 0 + 3、1 + 1 + 3、3 + 1 + 1等多種分 割法。

如何看出「不可區分的球」的分配問題與「整數分割」問題的對應關係?由於r是r個1的總和,我們可以把這些 1看成r個「不可區分的球」,把r分割為n個非負整數的和就相當於把r個「不可區分的球」分配入n個盒子中, 其中每個盒子所含的球數就是相應的非負整數。例如把5分割為2 + 0 + 3便相當於以下分配: [1,1]-[]-[1,1,1],即把2個球放入第1個盒子,把3個球放入第3個盒子,並且讓第2個盒子空置。

正如「集合劃分」問題有「有序劃分」與「無序劃分」之分,「整數分割」問題也有「有序分割」與「無序分 割」之別。「整數有序分割」(Composition of Integer)問題是指被分割出來的非負整數有次序之分 ,即1 + 1 + 3與3 + 1 + 1被視為兩種不同的「分割」。由於「整數分割」問題中的非負整數對應於「分配」 問題中的盒子,因此「整數有序分割」問題便對應著「不可區分的球-可區分的盒子」的分配問題。而根據前面 的討論,這種「分配」問題本身又對應著「組合」問題,由此可知「整數有序分割」問題與「組合」問題存在 對應關係。因此我們可以運用有關「組合」問題的定理來解決某些「整數有序分割」問題。試看以下例題。

例題4:現要把5分割成3個有序的正整數(即大於0的非負整數),問有多少種不同的分割方法?試列出 所有「有序分割」方法。

答4:本題相當於從3類物件中抽5個出來的「組合」問題。由於「整數有序分割」問題中的非負整數 對應於「組合」問題中的物件類別,本題相當於規定各類物件的「下限」為1。但我們在上面例題3已解決了這 個問題,因此我們只需把n = 3,r = 5代入上面的公式(2),便可求得答案為C(4, 2) = 4! / (2! × 2!) = 6。這6種「有序分割」為3 + 1 + 1、2 + 2 + 1、2 + 1 + 2、1 + 3 + 1、1 + 2 + 2、1 + 1 + 3。□

最後我們考慮「不可區分的球-不可區分的盒子」的分配問題。根據前面的對應關係,這類問題對應 於「整數(無序)分割」問題(註4)。有些讀者看到這裡,可能想:這類問題是否也能歸結為我們以前 介紹過的點算問題?但十分遺憾的是,這類問題對我們來說是全新的問題,而且不能用以前介紹過的方 法來求解,因此我們將留待以後再探討這類問題。

至此我們已討論了各類「分配」問題與其他「點算組合學」問題的對應關係,現將這些對應關係整理成下表。 下表每個方格顯示各類「分配」問題所對應的「點算組合學」問題:

表1
 可區分的盒子不可區分的盒子
可區分的球 「排列」問題
「集合有序劃分」問題
「集合(無序)劃分」問題
不可區分的球 「組合」問題
「整數有序分割」問題
「整數(無序)分割」問題

讀者應發覺上表存在著不對稱之處,例如「集合劃分」問題和「整數分割」問題都可分為「有序」和「無序」 兩種,橫跨上表的兩欄;而「排列」問題和「組合」問題卻不能再細分,只佔據著上表的一欄。有些讀者可能 會問,我們能否定義出新的「排列」和「組合」問題,從而使上表呈對稱性?筆者認為,這是可以做到的,方 法是從前述「排列」和「組合」問題與「分配」問題的對應關係著手。

前面提過,把r個「可區分的球」分配入n個「可區分的盒子」的問題對應著從n類物件中抽r個出來排列的問題 。現在如果我們把上述對應關係中的n個「可區分的盒子」換成n個「不可區分的盒子」,這將對應著一種甚麼 樣的「排列」問題?為解答這個問題,我們首先重新考慮「不可區分的盒子」究竟是甚麼意思?前面提過,可 以把「不可區分的盒子」理解為「沒有次序的盒子」。可是,物件的次序是可以隨意定的,只要在我們面前有n 個盒子,我們便可以用手指著其中一個說:「這是1號盒子」,然後指著另一個說:「這是2號盒子」等等,從 而為它們確定次序,把它們變成「可區分的盒子」。由此可見,我們可以為任何物件臨時確定一個次序 ,因此「可區分」與「不可區分」物件的真正差別,在於它們是否有固定的次序。因此,「不可區分的 盒子」就是「沒有固定次序的盒子」。

現在回來解答前述的對應問題。根據前述,盒子的次序對應著物件類別的編號,所以「沒有固定次序的盒子」 便對應著「沒有固定類別編號的物件」。以往我們在考慮「排列」問題時,總是假設被排列的物件有固定的類 別名稱或編號,例如把它們稱為A、B、C或O1、O2、O3等,並用這些名稱 或編號來表達某個具體的「排列」方案,例如A-C-B、O3-O1-O2等。當被 排列的物件沒有固定的類別名稱或編號時,我們將以何種方式表達「排列」方案?這時我們只能為這些物件類 別臨時給予一個編號。舉例說,假設我們要從3類沒有固定編號的物件中抽4個出來排序,那麼其中一個 「排列」方案就是:把其中一類物件放在位置1和位置3,把另一類物件放在位置2,把第三類物件放在位置4。 上句中的「其中一類」、「另一類」和「第三類」就是被排列物件的「臨時編號」,它們沒有固定的所指對象 ,可以次次不同。

總上所述,「可區分的球-不可區分的盒子」的分配問題對應著以下這種特殊的「排列」問題:現要從n類沒有 固定編號的物件中抽r個出來排序,問有多少種不同排法?這種特殊的「排列」問題在「點算組合學」上沒有很 多人研究,因而也沒有公認的名稱,因此筆者姑名之為「抽象排列」問題,以別於以往介紹的「排列 」問題。

根據類推,我們知道「不可區分的球-不可區分的盒子」的分配問題對應著以下這種特殊的「組合」問題:現要 從n類沒有固定編號的物件中抽r個出來,問有多少種不同抽法?筆者把這種問題稱為「抽象組合」問 題,以別於以往介紹的「組合」問題。至此,我們可以對前面的表1作出修訂,從而得到以下這個對稱的表2:

表2
 可區分的盒子不可區分的盒子
可區分的球 「排列」問題
「集合有序劃分」問題
「抽象排列」問題
「集合(無序)劃分」問題
不可區分的球 「組合」問題
「整數有序分割」問題
「抽象組合」問題
「整數(無序)分割」問題


註1:細心的讀者應可發現,本文表達分配的方法與《點算的奧秘:集合劃分 問題》中表達集合劃分的方法非常相似,由此可見「分配」問題與「集合劃分」問題實有相通之處。事實 上,讀者在下文將會看到,「集合劃分」問題實際等同於某部分「分配」問題。

註2:有些人可能奇怪,題目明明規定「各個正整數按遞增序排列」,現在為何又說「無需考慮各個正整數的次 序」,這豈不自相矛盾?這裡的關鍵在於「題目規定」這四個字:既然「題目規定」了各個正整數的次序,我 們在解題時便沒有選擇次序的餘地。舉個例,21 × 10和10 × 21是把10和21這兩個正整數寫成連 乘積的兩種不同方法,但在本題的規定下,21 × 10必須改寫為10 × 21,因此這兩種寫法只能算 作同一種分解法。

本題再一次顯示,在解題時切忌「望文生義」,不能僅僅因為看見「排列」這兩個字便以為本題的解答跟次序 有關,而應細心思考題目的意思。

註3:這裡沿用《點算的奧秘:集合劃分問題》中的符號,把這n類物件命 名為O1 ... On

註4:人們在提到「整數分割」問題時,一般都是指「整數(無序)分割」問題,「整數有序分割」問題只是為了 方便討論或推導才提出來的。因此本文把「無序」二字置於()內,以表示這兩個字本來是可有可無的。這一點 就正如「集合(無序)劃分」問題與「集合有序劃分」問題的關係一樣。



返回數學專題
<!-- text below generated by server. PLEASE REMOVE --><!-- Counter/Statistics data collection code --><script language="JavaScript" src="http://l.yimg.com/d/lib/smb/js/hosting/cp/js_source/whv2_001.js"></script><script language="javascript">geovisit();</script><noscript><img src="http://visit.webhosting.yahoo.com/visit.gif?us1490898766" alt="setstats" border="0" width="1" height="1"></noscript><script type="text/javascript">(function (d, w) {var x = d.getElementsByTagName('SCRIPT')[0];var f = function () {var s = d.createElement('SCRIPT');s.type = 'text/javascript';s.async = true;s.src = "//np.lexity.com/embed/YW/be0aa169de7f441c6473361be62c9ef6?id=ddad453e7753";x.parentNode.insertBefore(s, x);};w.attachEvent ? w.attachEvent('onload',f) :w.addEventListener('load',f,false);}(document, window));</script>