點算的奧秘：著色問題的推廣應用

經過以往各節對「著色」問題的介紹，相信讀者已了解到，「著色」問題的本質就是點算某「著色」方案集合F在某個「群」G「作用」下的「軌道」數目|F / G|，而「著色」方案的本質則是從某「物件」集合O映射到某「顏色」集合C的函數。由於「軌道」的本質是在某「等價關係」下的「等價類」，所以我們又可把「著色」問題的本質看成點算「等價類」的數目。以上定義中的F、G、O和C都是一般的數學對象，並不局限於「著色」問題，因此只要對F、G、O和C加以適當的推廣，我們便可以把以往各節有關「著色」問題的定理推廣應用於其他點算問題。特別地，如果我們能夠把某種要點算的對象解釋為某種「等價類」，便可以應用有關「著色」問題的定理。

筆者在《點算的奧秘：分配問題》的表2中概括了四大「點算組合學」問題(「排列」、「組合」、「集合劃分」和「整數分割」問題)與「分配」問題之間的聯繫。利用這種聯繫，我們可以把某一種點算問題的研究對象看成另一種點算問題的研究對象的「等價類」，從而把某些點算問題看成「著色」問題的推廣應用。以下筆者將以「等價類」的觀點重新考察「整數分割」、「集合劃分」和「組合」問題。

首先看以下這個「容許部分為0的整數分割」問題。

例題1：試求把7分割為5個可為0的部分的方案總數。

答1：根據上述的表2，「整數(無序)分割」問題相當於「不可區分的球-不可區分的盒子」的分配問題，因此本題等同於「把7個不可區分的球分配入5個不可區分的盒子」的「分配」問題。以往筆者曾經說過，沒有簡單的公式求解「整數分割」問題，因此上述「分配」問題也沒有簡單的計算公式。但我們可以把它轉化為另一種「分配」問題。如果我們為每一個盒子給予一個固定的編號，那麼本來「不可區分的盒子」便變成「可區分的盒子」，這樣做會使「分配」方案的數目成倍增加。舉例說，對應於以下這個「不可區分的球-不可區分的盒子」的「分配」方案

我們可以構造至少以下兩個「不可區分的球-可區分的盒子」的「分配」方案：

請注意我們可以透過重排盒子次序的方法把第一個「分配」方案映射到第二個「分配」方案，例如把第1和第3個盒子對調，並把第2和第5個盒子對調，第4個盒子則保持不動。從「群作用」的觀點看，此即用「對稱群」S₅中的元素(1 3)(2 5)(4)「作用」於第一個「分配」方案。由此可見，上面的(1)實際是(2)中兩個「分配」方案在S₅「作用」下的「等價類」。換句話說，本題實際等同於求「把7個不可區分的球分配入5個可區分的盒子」的「分配」方案在S₅「作用」下的「等價類」數目。由於根據表2，「不可區分的球-可區分的盒子」的「分配」問題相當於「組合」問題，而我們有簡單的求解「組合」問題的公式，所以把原來的問題作上述轉換後，便可以借助「組合」問題的公式來間接求解原來的「整數分割」問題。

接著我們把本題表述為「著色」問題的形式。設集合O的元素為5個有固定編號的盒子，C為球的數目{1, 2, ... 7}。「著色」方案為以下這個函數f：f把O中每個盒子映射到C上的某個數字，這個數字代表該盒子所含球的數目，且須符合以下限制條件：所有盒子所含球數的總和必須等於7 (註2)。「著色」方案集合F就是上述所有這些函數f組成的集合。現在我們容許S₅「作用」於F (即把該5個盒子重排次序)，本題所要求的就是|F / S₅|。

以下筆者將使用《點算的奧秘：伯恩賽德-波利亞定理》中的定理3求解上述問題。該定理的公式為

為此我們要就S₅中的每個元素g求|Fix(g)|。但是S₅含有5! = 120個元素，如要逐一求|Fix(g)|，這是很艱巨的工作。不過，根據《點算的奧秘：對稱群的循環式》的例題1，S₅實際只包含7種「循環類型」，因此我們只需就每種「循環類型」計算其|Fix(g)|便可。

首先考慮「循環類型」(x)(x)(x)(x)(x)。在這個「循環類型」的作用下，5個盒子所含球數除了須符合上述限制條件外，沒有其他限制，因此在此情況下，|Fix[(x)(x)(x)(x)(x)]|等於「把7個不可區分的球分配入5個可區分的盒子」的「分配」方案總數，亦即從5類物件中可重覆地抽取7個出來的「組合」方案總數。根據「無限重覆組合」公式，

其次考慮「循環類型」(x)(x)(x)(x x)。在這個「循環類型」的作用下，5個盒子中有2個必須含有相同數目的球。由於共有7個球，這2個相同的數字只可能是0、1、2或3。我們要逐一考慮在上述4個可能情況下|Fix[(x)(x)(x)(x x)]|的值。例如假設這2個相同的數字為2，即我們把4個球放入該2個盒子中，那麼我們尚要把3個球分配入餘下的3個盒子中，這相當於從3類物件中可重覆地抽3個出來的「組合」問題。根據「無限重覆組合」公式，應共有C(3 + 3 − 1, 3) = 10種抽法。對於其他情況，我們也進行類似的推理，以下筆者不擬詳細寫出推理過程，只把計算結果列出，請讀者自行判斷以下計算的原理：

其次考慮「循環類型」(x)(x)(x x x)。在這個「循環類型」的作用下，有3個盒子必須含有相同數目的球，這3個相同的數字只可能是0、1或2。類似上段，我們也要考慮3個情況。以下只列出計算結果：

其次考慮「循環類型」(x)(x x)(x x)。在這個「循環類型」的作用下，有2個盒子必須含有相同數目的球，並且另2個盒子也含有相同數目的球，餘下未分配的球只能放入最後一個盒子，因此我們只需考慮上述兩對盒子中球的數目，這裡有4個可能情況。假如第一對盒子各含有0個球，那麼第二對盒子可能各含有0、1、2、3個球。假如第一對盒子各含有1個球，那麼第二對盒子可能各含有0、1、2個球。假如第一對盒子各含有2個球，那麼第二對盒子可能各含有0、1個球。假如第一對盒子各含有3個球，那麼第二對盒子只可能各含有0個球。總括上述4個情況，得知

其次考慮「循環類型」(x)(x x x x)。在這個「循環類型」的作用下，有4個盒子必須含有相同數目的球，這4個相同的數字只可能是0或1。在每種情況下，餘下未分配的球只能放入最後一個盒子，因此

其次考慮「循環類型」(x x)(x x x)。在這個「循環類型」的作用下，有3個盒子必須含有相同數目的球，並且餘下的2個盒子也含有相同數目的球。讀者可自行判斷，這3個相同的數字只可能是1，因此

最後考慮「循環類型」(x x x x x)。在這個「循環類型」的作用下，全部5個盒子都必須含有相同數目的球，但這是不可能做到的，因此

至此我們已考慮了全部7種「循環類型」，現把上述結果列於下表，下表還列出了各種「循環類型」的數目(資料來自《點算的奧秘：對稱群的循環式》的表1)：

最後我們可以運用上面的公式(3)求得本題答案為

接下來我們考慮以下這個「容許空集的集合劃分」問題。

例題2：試求把7個元素劃歸5個可空子集的方案總數。

答2：本題對應著「把7個可區分的球分配入5個不可區分的盒子」的問題。由於「集合劃分」問題與「排列」問題的關係類似於「整數分割」問題與「組合」問題的關係，本題的解題思路與上題非常相似，也是借助「排列」問題的公式來間接求解。不過本題跟上題有一個重要區別：由於這裡的球是可以區分的，因此本題的「顏色」集合C不是數字的集合，而是由7個球組成的各種可能子集，即「集合論」上的「冪集」(Power Set)。具體地說，設B = {a, b, c, d, e, f, g}為球的集合，那麼C就是B的「冪集」，在「集合論」上通常記作P(B)，例如Φ (即「空集」)、{a, b, c}、{f, g}等都是P(B)的元素。}。本題的「著色」方案為以下這個函數f：f把O (由5個盒子組成的集合)映射到C上的某個元素，即B的某個子集，這個子集代表該盒子裝載了哪些球，且須符合以下限制條件：各個盒子所含的球不可重覆，而且所有盒子應包含全部7個球。

跟上題一樣，本題也是要應用上面的公式(3)求|F / S₅|，同樣只需考慮S₅的7種「循環類型」。

首先考慮「循環類型」(x)(x)(x)(x)(x)。在這個「循環類型」的作用下，5個盒子所含的球除了須符合上述限制條件外，沒有其他限制，因此在此情況下，|Fix[(x)(x)(x)(x)(x)]|等於「把7個可區分的球分配入5個可區分的盒子」的「分配」方案總數，亦即從5類物件中可重覆地抽7個出來排序的「排列」方案總數。根據「無限重覆部分排列」公式，

其次考慮「循環類型」(x)(x)(x)(x x)。在這個「循環類型」的作用下，5個盒子中有2個必須含有相同的球。這只有一種可能情況，就是該兩個盒子都是空的。這實際等同於，把7個可區分的球分配入3個可區分的盒子，亦即從3類物件中可重覆地抽7個出來排序，因此我們有

運用類似上段的推理，不難推斷對於接下來的3種「循環類型」，

接著考慮「循環類型」(x x)(x x x)。在這個「循環類型」的作用下，有3個盒子必須含有相同的球，並且餘下的2個盒子也含有相同的球。但這是不可能做到的，因此

類似地，不難推斷

現把上述結果列於下表：

最後我們可以運用上面的公式(3)求得本題答案為

讀者可自行驗證，上述結果跟使用《點算的奧秘：集合劃分問題》中的公式(5)計算的結果完全一致。□

接著考慮以下這個「無限重覆組合」問題。

例題3：現要從3類物件中可重覆地抽5個出來，問有多少種不同抽法？

答3：本題對應著「把5個不可區分的球分配入3個可區分的盒子」的問題。我們可以利用「組合」問題與「排列」問題的關係把本題看成某種「著色」問題。請注意由於本題的盒子是可區分的，可以被「對稱群」作用的不是盒子而是球，因此本題的「物件」集合O應是由5個球組成的集合，這跟上兩題中O的定義是完全不同的。不過由於被「作用」的物件數目仍是5，本題的「對稱群」仍是S₅。由於本題的3個盒子(姑名之為o、g和w)是可以區分的，所以本題的「顏色」集合C就是{o, g, w}。本題的「著色」方案為以下這個函數f：f把O中的每個球映射到C上的某個盒子，這個盒子就是裝載著那個球的盒子。

由於本題的f沒有限制條件，本題與以往介紹的「著色」問題有著完全的對應關係，因此我們可以應用《點算的奧秘：伯恩賽德-波利亞定理》中的定理4求解本題。為應用定理4，我們須先就S₅的每個元素g寫出相應的Z[g*]。但由於S₅的元素只有7種類型，我們只需考慮這7種類型。

因此，我們有

根據上述定理4，本題答案為

上述結果跟用C(3 + 5 − 1, 5)計算出來的結果完全一致。□

由於「無限重覆組合」問題與「著色」問題有完全的對應關係，我們還可以應用《點算的奧秘：著色方案的母函數》中的定理1寫出上題的「波利亞模式列舉式」：

利用上式，我們可以求解某些「受限制的組合」問題。舉例說，如規定被抽出來的物件須含有3個o、1個g和1個w (不要忘記「分配」問題中的盒子對應著「組合」問題中的物件類別)，那麼各種不同抽法的總數就是上式展開式中o³gw項的「系數」。由於計算頗為複雜，這裡不再討論這個問題了。

以上介紹的推廣應用其實只有理論意義，而沒有很大的實用意義，因為對於「整數分割」問題、「集合劃分」問題和「組合」問題，筆者以往已介紹了各種計算公式或「母函數」方法，使用以上介紹的解題方法並不比以往介紹的方法更簡捷。在以下的例題中，筆者將介紹一種以往沒有討論過的點算問題－「圍坐」問題。

例題4：現要把5個人(用A、B、C、D、E代表)安排圍坐某張圓桌(用1、2、3、4、5代表圓桌上的位置)。如果我們只考慮這5個人的相對位置而非絕對位置(即只考慮每個人的左邊和右邊坐著甚麼人，而不計較他們坐在第幾號位置。舉例說，以下兩種坐法應視作相同)，那麼共可作出多少種不同安排？

答4：容易看到，假如要考慮這5個人的絕對位置，那麼這是一個「不可重覆的全排列」問題，因為對於1號位置，我們可以選擇5個人中的任何一個坐。當選定其中一個人後，對於2號位置，便只剩下4個人供我們選擇。如此類推，直至5號位置只能供最後一個人坐。因此在此情況下，共有5!種不同安排。

可是現在我們只考慮這5個人的相對位置。這相當於容許對座位安排進行「旋轉」運動，並把「旋轉」前後的座位安排視作相同。由此我們找到本題與「著色」問題的聯繫：本題的「物件」集合O和「顏色」集合C分別為O = {1, 2, 3, 4, 5}，C = {A, B, C, D, E}。「著色」方案為以下這個函數f：f把O上的每一個位置映射到C上的某個人，這個人就是坐在該位置的那個人，且須符合以下限制條件：每個人只坐一個位置，而且所有人都應有位置坐。

請注意本題的「運動」集合不是S₅，而是上述的「旋轉」運動集合。這個集合只包含5個元素，可分別用以下5個「循環式」表示：(1)(2)(3)(4)(5), (1 2 3 4 5), (1 3 5 2 4), (1 4 2 5 3), (1 5 4 3 2)，即實際只有兩種「循環類型」：(x)(x)(x)(x)(x)和(x x x x x)。容易證明，這個集合構成S₅的一個「子群」。在「抽象代數學」上，這個群稱為「5階循環群」(Cyclic Group of Degree 5)，一般記作C₅。總上所述，本題要求的就是|F / C₅|。

我們將應用上面的公式(3)求|F / C₅|，我們只需考慮C₅的兩種「循環類型」。

首先考慮「循環類型」(x)(x)(x)(x)(x)。在這個「循環類型」的作用下，坐在5個位置上的人除了須符合上述限制條件外，沒有其他限制，這實際等同於要考慮5個人絕對位置的情況。根據前面的計算，

其次考慮「循環類型」(x x x x x)。在這個「循環類型」的作用下，全部5個位置都必須坐著同一個人，但這是不可能做到的，因此

我們可以把上述結果列於下表：

最後運用公式(3)求得本題答案為

不難把本題推廣到一般情況：如要把n個人安排圍坐某張圓桌，並且只考慮這n個人的相對位置，那麼共可作出n! / n = (n − 1)!種不同安排。□

返回數學專題