一. 問題的提出---從細胞繁殖到有序樹

細胞繁殖 (cell-growth problem) 是生物數學中的一個著名問題: 從一個正方形的「細胞」開始, 每次從其中一邊生長出一個新的細胞。 如此繼續, 所形成的「動物」不含空洞。 那麼, $n$ 個細胞 (正方形) 能形成多少個不同的動物?

我們試考察 $n=4$ 的情形。四個細胞所形成的動物如下:

$n=4$

對於一般的 $n$。設 $f(n)$ 表示 $n$ 個細胞的不同動物數。迄今, 只知道如下的結果 $(n\le 24)$ (見)

我們所說的不同的動物, 指的是在旋轉, 反射變換下不同的動物式樣。

如果我們把細胞的生成限制在平面上, 則所述的問題變成平面細胞繁殖問題。

同樣, 對於 $n=4$, 考察平面細胞的不同式樣, 則圖 1 的 (1), (3), (4) 圖無變化, 但圖 (2) 應變成下列兩個圖。

也就是說, 在平面上用旋轉變換, 圖2中的圖 (1) 無論如何是不能變成圖 (2) 的。

處於三維空間的你, 習慣於三維空間中的條件變換, 往往不經意地把三維空間中的反射, 用於限制在二維空間的圖形中, 因而誤認為圖 2 中的圖 (1), (2) 是同一個圖。

正是利用你習慣性思維造成誤判, 電子商炮製出流行的俄羅斯方塊遊戲。 當方塊在平面上翻著"筋斗" 下落時 (圖3), 你能準確地判斷出它能否嵌入下方的凹洞中嗎?

同樣限制在平面上, 我們考慮在計算機演算法中不可或缺的樹圖 (tree)。

所謂 $n$ 階樹, 就是 $n$ 個頂點的無圈連通圖, 而每個頂點所連接的邊數稱為該頂點的度 (degree)。 易知: $n$ 階樹有 $n-1$ 條邊, 且至少有兩個度為 1 的點, 即懸掛點 (pendent vertex), 或稱為葉點。

限制在平面上變換的樹, 稱為平面樹。把樹的某一點作特殊標號, 這樣的樹稱為根樹 (rooted tree)。此特殊的點稱為根點。 根點是懸掛點的根樹稱為植樹(plant tree), 如同上述俄羅斯方塊的原理, 圖 4 中兩棵平面植樹 (1) 和 (2) 是不同的。

因為圖 4 中的樹 (1) 不能通過旋轉變為樹 (2)。於是, 在平面樹中「枝椏」都是有序的。 因此, 平面植樹 (圖 4 中 (1) (2) (3)) 又稱為有序植樹 (ordered plant tree), 平面根樹 (圖 4(4)) (根點不一定是懸掛點) 稱為有序樹 (ordered tree), 而像圖 4 的(1) (2) 那樣僅由 1 度點和 3 度點組成的植樹, 稱為二叉 (有根) 樹 (2-ray tree)。 二叉樹的每個分叉都可以分成左右兩枝。

我們看看以圖 4 中的兩棵二叉樹為模型的演算法框圖, 就可以瞭解它們為什麼應該看作不同。

我們約定左枝表示 Yes, 右枝表示 No。以比較$a$, $b$, $c$ 3個不同的實數的大小為例。

圖 5 中的框圖 (1) 的樹圖模型是圖 4 的根樹 (1) (倒過來), 它判斷是否有 $a=\max\{a$, $b, c\}$ 而圖 5 中的框圖 (2) 的樹圖模型是圖 4 的根樹 (2)。 它判斷是否有 $a=\min\{a ,b, c\}$。

一個自然提出的問題是: $n$ 階有序植樹有多少種不同的式樣?

二. 組合模型---枯燥的排隊激發鮮活的靈感

排隊, 在生活中屢見不鮮, 你曾想過, 排隊與有序樹有什麼聯系嗎?

試看下面的一個排隊買票問題。

戲院票房前有 $2n$ 個人買票, 其中 $n$ 個人只有 5 角一張的紙幣, 其餘的 $n$ 個人只有 1 元一張的紙幣。 在開始賣票時, 票房裏無任何零錢, 而每個人只能買一張 5 角的票, 問買票的人有多少種不同的排隊方法, 能使每個人都能買到一張 5 角的票?

我們分析一下, 這種排隊方法, 它必須具有下列特徵: $$ \hbox{(A)} \left \{ \begin{array}{ll} \hbox{(A}_1) & \quad 2n \hbox{ 個人排隊, 每個人手裡不是拿著 5 角就是拿著 1 元} \\ \hbox{(A}_2) & \quad \hbox{恰有 } n \hbox{ 個人拿 5 角, 另外 } n \hbox{ 個人拿 1 元} \\ \hbox{(A}_3) & \quad \hbox{為了保證:　「每個人都能買到一張 5 角的票」, 第一個人必須拿 5 角, 第 2 個人} \\ & \quad \hbox{可拿 5 角或 1 元。若第 2 個人拿 1 元, 則第 3 個人必須拿 5 角, 否則票就賣} \\ & \quad \hbox{不出去; 若第 2 個人拿 5 角, 則第 3 個人 (甚至第 4 個人) 都可拿 5 角或 1} \\ & \quad \hbox{元 $\cdots$。}\\ \end{array} \right. $$

為了使上述特徵變得清晰, 我們把上述組合模型數字化。 把拿 5 角的人表為 0, 拿 1 元的人表為 1, 於是符合要求的排隊, 可表示為如下特徵: $$ \hbox{(B)} \left \{ \begin{array}{ll} \hbox{(B}_1) & \quad \hbox{長為 } 2n \hbox{ 的 0, 1 序列} \\ \hbox{(B}_2) & \quad \hbox{序列中恰有 } n \hbox{ 個 0 和 } n \hbox{ 個1, 且第 1, 2 個數為 0, 1} \\ \hbox{(B}_3) & \quad \hbox{序列的第 1 項為 0, 且由首項到任一項所形成的子序列, 0 的個數不少於 1 的} \\ & \quad \hbox{個數} \end{array} \right. $$ 我們稱滿足 (B$_1$), (B$_2$), (B$_3$) 特徵的 (0, 1) 序列為 B 序列。

現在, 回過頭來, 看看我們的有序植樹。(圖6)

有序植樹的任一個頂點 $v$ 到根點都有唯一的一條路, 路所含的邊數稱為點 $v$ 的水平。 因此, 任一有序樹都可以分成若干水平的頂點。

我們把一個有序植樹的邊表為 0, 頂點 (除了根點) 表為 1, 從根點相連的邊開始, 依次從低水平到高水平, 先點再邊, 同一水平的點從左到右, 兩水平之間的邊亦從左到右, 我們便可讀出一個 0, 1 序列。 例如, 圖 6 中所示的樹的 (0, 1) 序列為 $$ 0~~1~~0~~0~~1~~1~~0~~0~~0~~0~~0~~1~~1~~1~~1~~1~~0~~0~~0~~0~~0~~1~~1~~1~~1~~1 $$

因為任一 $(n+1)$ 階有序植樹, 除了根點外, 恰有 $n$ 個頂點, $n$ 條邊。 因此它的 (0, 1) 序列滿足特徵 (B$_1$), (B$_2$), 而對於有序樹, 除了根點, 第一項必從邊開始, 即 (0, 1) 序列第 1 項必為 0 第 2 項必為 1, 且由於每一水平的頂點都讀在邊之後, 故序列滿足 (B$_3$)。

容易驗證, 任一個 B 序列, 都可對應畫出唯一一個有序植樹。 於是一個 $(n+1)$ 階有序植樹一一對應於一個數字化的組合模型, 即 B 序列。

因此, 求 $(n+1)$ 階有序植樹的個數, 即求 B 序列的個數。

三. 代數模型---此時無聲勝有聲

0 和 1 是世界上最簡單的兩個數, B 序列就是用一個 0, 1 的數組給出了有序植樹的一個組合模型。

可是, 組合模型並沒有直接給出數學性質, 經過分析, 我們給出了 (B$_1$), (B$_2$), (B$_3$) 的描述性的特徵。

下面, 我們把組合模型進一步代數化。

由 B 序列的特徵 (B$_1$), (B$_2$), (B$_3$), 可設數組為 $0, 1, x_1, \ldots x_{2n-2}$。 於是, B 序列的特徵表述為下列代數化條件 $$ \hbox{(C)} \left \{ \begin{array}{lll} x_i = 0 ~\hbox{ 或 }~ 1, & \quad i = 1, 2, \ldots, 2n-2 & \hskip 3.8cm (C_1) \\ x_1 + x_2 + \cdots + x_{2n-2} = n - 1, & \quad n ~\hbox{ 為正整數} & \hskip 3.8cm (C_2) \\ x_1 + x_2 + \cdots + x_j \le \displaystyle\frac{1}{2}j, & \quad j = 1, 2, \ldots, 2n-3 & \hskip 3.8cm (C_3) \end{array} \right. $$ 條件 (C) 沒有任何描述性的語句, 但卻簡明地刻畫了 B 序列的數學本質, 特別是 $(C_3)$。 也許, 從性質 (B) 寫出式子 (C) 並非難事。 然而, 在閱讀數學書籍時, 能夠把式子 (C) 描述成性質 (B), 卻需要一定的數學修養。

於是, 要求出 $(n+1)$ 階有序植樹的個數。只須求出滿足條件 (C) 的所有數組 $(x_1 ~~ x_2$ $\cdots ~~ x_{2n-2})$ 的個數。

代數模型 (C) 提供了我們解決類似問題的思路。試看下列選舉問題。

某次選舉中有侯選人 $P$ 和 $Q$, $P$ 得票 $p$ 張, $Q$ 得票 $q$ 張, $p\gt q$。 要使開票過程中, $P$ 的得票數恒領先於 $Q$ 的可能情況有多少種?

類似前面的分析, 我們不難得出這一問題的代數模型。

我們把 $p+q$ 張選票按開票先後順序記作 $x_1, x_2, \ldots, x_{p+q}$, 其中選 $P$ 的票記作 $x_j=0$, 選 $Q$ 的票, $x_j=1$, 因 $P$ 得票數恒領先於 $Q$; 顯見, 選舉的代數模型為: $$ \left \{ \begin{array}{ll} x_i = 0 ~\hbox{ 或 }~ 1, & \quad i = 1, 2, \ldots, p+q \\ x_1 + x_2 + \cdots + x_{p+q} = q, & \\ x_1 + x_2 + \cdots + x_j \lt \displaystyle\frac{1}{2}j, & \quad j = 1, 2, \ldots, p+q-1 \end{array} \right. $$

本文前面提到的二叉 (有根) 樹是研究計算機資訊存儲的一類重要結構。 例如, 與二叉樹的計數直接聯繫的一個問題是: 按一定順序排列的 9 個字母 $a$, $b$, $c$, $d$, $e$, $f$, $g$, $h$, $i$, $j$, 能構

成多少個不同的不可結合積。 圖 7二叉樹 (省掉了一個根點及邊) 展示的, 就是其中對二元運算 $*$ 的一個不可結合積。 我們注意到 9 個字母按規定次序排在葉點上。邊連字母表示運算 $*$ 。

有序樹與二叉樹的區別在於: 前者的每個頂點不限於 1 度點與 3 度點。 可是, 運用代數模型, 我們卻能知道: $n$ 個葉點的二叉樹與 $(n+1)$ 個頂點 (包括根點) 的有序樹之間是1$-$1對應的。

容易證明: 若二叉樹的 3 度頂點個數為 $n$, 則葉點的個數必為 $n+1$

證: (對 $n$ 用數學歸納法) $n=1$, 顯然 (如圖8) 設二叉樹有 $n$ 個 3 度頂點時, 葉點的個數為 $n+1$。 現增加一個 3 度頂點即把一個葉點改為一個 3 度點, 就必增加兩邊, 於是葉點共有 $(n+1)-1+2=n+2$ 個, 證畢。

因此, 有 $n$ 個葉點的二叉樹, 它的 3 度點有 $n-1$ 個, 連同根點二叉樹共有 $2n$ 個頂點, 把這些頂點用 $1, 2, \ldots, 2n$ 編號。 編號的規則是: 從根點開始由低水平到高水平, 同一水平的頂點從左到右。如圖 9 就是一個編了號的 4 葉點的二叉樹。 令每一點 $i$ 對應於 0 或 1, 規定 3 度點及根點對應於 0, 葉點對應於 1。 於是每一個編號的二叉樹一一對應於一個長為 $2n$ 的 $(0, 1)$ 數組, 其性質是

1. 有 $n$ 個 0, $n$ 個 1
2. 對任一個 $j\lt 2n$, 由 1 到 $j$ 的 $j$ 個點中 3 度點 必多於 1 度點。

於是, 有 $n$ 個葉點的二叉樹的代數模型是 $$ \hbox{(D)} \left \{ \begin{array}{ll} x_i = 0 ~\hbox{ 或 }~ 1, & \quad i = 1, 2, \ldots, 2n \\ x_1 + x_2 + \cdots + x_{2n} = n, & \quad n ~\hbox{ 為正整數} \\ x_1 + x_2 + \cdots + x_j \lt \displaystyle\frac{1}{2}j, & \quad j \lt 2n \end{array} \right. $$ 　

一個有趣的事實是, 代數模型 (C) 和 (D) 是等價的。 因為如果我們把一個 B 序列的後 $2n-2$ 項, 前面加一個 0, 後面加一個 1。 即 $0 ~~ x_1 ~~ x_2 ~~ \cdots ~~ x_{2n-2} ~~ 1$ 就是一個滿足 (D) 的數列, 而任一個滿足 (D) 的數列 $x_1 ~~ x_2 ~~ \cdots ~~ x_{2n}$ 必須有 $x_1=0$, 且 $x_{2n}=1$, 去掉此 0, 1 後把數列由 $x_2$ 開始重新按自然數序編號, 便得到一個長為 $2n-2$ 的滿足 (C) 的數列。 由此, 對代數模型的討論, 我們知道:

$(n+1)$ 階有序植樹的個數等於 $n$ 個葉點的二叉樹的個數。 作為一個練習, 讀者可寫出 $n$ 階有序樹的代數模型, 由此可證明 $n$ 階有序樹的個數等於 $(n+1)$ 階有序植樹的個數。

四. 幾何模型---照鏡子的啟示.

你每天都照鏡子嗎?

在鏡子前,你看到了另一個世界,它和你生活中的世界是一樣的, 這叫做反射。因為反射, 產生了對稱, 這在數學中稱為「反射原理」。 我們就用這個反射原理, 構造出有序樹的一個幾何模型, 從而達到求解的目的。

在構造幾何模型之前, 先看一個眾所周知的郵遞員問題:

在一個 $p$ 段直路, $q$ 段橫路組成的方格幹道網中 (圖10), 郵遞員從郵局 $A$ 到達客戶 $B$, 可以走多少條不同的最短路?

易知, 由 $A$ 到 $B$ 走最短路 (簡稱為 $L$ 路徑) 至少要走 $p$ 段直路, $q$ 段橫路。 不同的 $L$ 路徑 , 相當於 $p$ 段直路和 $q$ 段橫路不同組合數, 其方法數是: $$ \frac{(p+q)!}{p!q!} $$ 的確, 代數模型 (C) 能簡明地刻畫有序數的特徵。 然而利用它卻不易算出滿足 (C) 的解的個數, 下面我們構造出 B 序列的幾何模型, 幫助我們直接求出問題的解。

建立平面坐標系 $XOY$。對任一個 B 序列的後 $2n-2$ 項 $(x_1 ~~ x_2 ~~ \cdots ~~ x_{2n-2})$。 對應於平面的一條從 $(0, 0)$ 到 $(2n-2, 0)$ 的由點對角線組成的折線。 由 $x_1$ 開始, 若 $x_i=0$, 則對應於一段 的線段; 若 $x_i=1$, 對應於一段 的線段。 由這兩類線段組成的路徑, 我們稱為 $T$ 路徑。 例如圖 4 中圖 (1) 的有序樹的 B 序列是 $0 ~ 1 ~ 0 ~ 0 ~ 1 ~ 1 ~ 0 ~ 0 ~ 1 ~ 1$ 其後面 8 項對應的 $T$ 路徑如圖 11

由 B 序列的代數模型 (C) 我們知道:

$T$ 路徑給出了有序樹的一個幾何模型。求出所有滿足性質 (T) 的 $T$ 路徑就能求得 $n+1$ 階有序樹的個數。

我們先計算從 $(0, 0)$ 到 $(2(n-1), 0)$ 的所有 $T$ 路徑。 考察由直線 $y=x$, $y=x-2(n-1)$, $y=-x$, $y=-x+2(n-1)$, 組成的正方形 $Q$。 整點把 $Q$ 分成 $(n-1)\times (n-1)$ 個小正方形 (如圖12)。

於是從 $(0, 0)$ 到 $(2(n-1), 0)$ 的 $T$ 路徑等價於正方形 $Q$ 由 $(0, 0)$到 $(2(n-1), 0)$ 的 $L$ 路徑, 總數是 $$ \frac{(2n-2)!}{(n-1)!(n-1)!} $$ 可是, 算出來的結果並非是滿足性質 (T) 的 $T$ 路徑總數。 它摻雜了很多不滿足性質 (T) 的 $T$ 路徑, 即從 $(0, 0)$ 到 $(2(n-1),0)$ 越過了 $x$ 軸的 $T$ 路徑, 或者說從 $(0, 0) $ $(2(n-1), 0)$ 接觸到直線 $y=-1$ 的 $T$ 路徑。 我們簡稱這些 $T$ 路徑為「壞 $T$ 路徑」。 如果我們把壞 $T$ 路徑的總數算出來, 則我們的問題就告解決。 下面, 我們就用所謂反射原理的方法求出所有壞 $T$ 路徑的總數。

試看任一條壞 $T$ 路徑 $T_1$, 我們把它以直線 $y=-1$ 為對稱軸反射成一條以 $(-2, 0)$ 為起點, $(2(n-1), 0)$ 為終點的 $T'_1$ 路徑 (如圖13), $T'_1$ 路徑落在是一個由直線 $y=x-2$, $y=x-2(n-1)$, $y=-x-2$, $y=-x+2(n-1)$ 組成的正方形 $Q'$ 內, 是一條 $Q'$ 中由 $(-2, 0)$ 到 $(2(n-1), 0)$ 的 $L$ 路。 注意到 $Q'$ 是一個 $n\times(n-2)$ 的矩形。　　　　　　　　　

$Q'$ 所有從 $(-2, 0)$ 到 $(2(n-1), 0)$ 的 $L$ 路總數為 $$ \frac{(n+n-2)!}{n!(n-2)!} = \frac{(2n-2)!}{n!(n-2)!} $$ 於是, 滿足性質 (T) 的 $T$ 路徑總數為 \begin{eqnarray} %(1) && \hskip -25pt \frac{(2n-2)!}{(n-1)!(n-1)!} - \frac{(2n-2)!}{n!(n-2)!} \nonumber \\ &=& \frac{1}{n} \frac{(2n-2)!}{(n-1)!(n-1)!} = \frac{1}{n} {2n-2\choose n-1} \end{eqnarray}

在組合數學裏, $\displaystyle\frac{1}{n+1}{2n\choose n}=C_n$ 稱為卡塔蘭 (Catalan) 數, 這是 19 世紀比利時數學家 Catalan 在研究 $n$ 個因數的不可結合積的個數問題時提出來的。 在計算數學、計算機科學、通訊理論的很多組合問題都歸結為卡塔蘭數。 由 (1) 式知: $n+1$ 階有序植樹的個數是卡塔蘭數 $C_{n-1}$。 而因為 $n$ 個因數的不可結合積等價於 $n$ 個葉點的二叉樹。 由第三節的結論, $n$ 個因數的不可結合積的個數也就是卡塔蘭數 $C_{n-1}$。

五. 生成函數---又回到代數

幾何模型給我們提供了一條直觀解決問題的途徑。然而, 我們更希望用「數學味」更濃的代數方法。

生成函數, 又給我們打開一個回到代數的新天地。

設 $n$ 階的有序植樹的個數為 $p_n$。作序列 $\{p_n\}$ 的生成函數 $P(x)=\sum\limits_{n=1}^\infty p_nx^n$, 這裏約定 $p_1=0$。

以圖 4(3) 的有序植樹為例。 把一個有序植樹的根點及與根相鄰的點去掉, 就得到若干支, 不妨設 $r$ 支 (無根) 的有序植樹。 反之, 把 $r$ 支有序植樹的根「粘」在一起, 再添上一個新的懸掛根點, 可得一棵新的有序植樹。 這個過程, 用生成函數來表達就是 \begin{equation} %(2) P(x) = x^2 \sum_{r=0}^\infty \Big (\frac{P(x)}{x}\Big )^r \end{equation} 這裏 $\displaystyle\frac{P(x)}{x}$ 表示每一有序植樹去掉根點, $\Big (\displaystyle\frac{P(x)}{x}\Big )^r$ 表示把 $r$ 支這種 (無根) 植樹粘起來 (其中 $r$ 可以是 $0, 1, 2, \ldots$), 而乘 $x^2$, 就是最後添上粘在一起的一個點, 及另一個新懸掛根點。

把 (2) 式右邊整理 (注意, 生成函數只著眼於它的展開級數各項的系數。級數的求和無須顧及它的收斂性。 見《數學傳播》 22 卷 2 期拙作「別瞧不起它, 這個中學教材中的公式」) 得 $$ P(x) = x^2 \cdot \frac{1}{1-\displaystyle\frac{P(x)}{x}} $$ 於是得 $P^2(x)-xP(x)+x^3=0$ 解關於 $P(x)$ 的二次方程得 $$ P(x) = \frac{x}{2} (1\pm\sqrt{1-4x}) $$ 　

　　　 因 $P(x)$ 中 $x$ 的一次項係數為 0, 故上式的括號中必須取「$-$」號。於是 \begin{equation} %(3) P(x) = \frac{x}{2} (1-\sqrt{1-4x}). \end{equation} 在中學數學裏, 我們學過二項式定理 $$ (1-x)^m = 1 - mx + \frac{m(m-1)}{2!}x^2 - \frac{m(m-1)(m-2)}{3!}x^3 + \cdots + (-1)^m \frac{m!}{m!}x^m $$ 事實上, 上式的 $m$ 不限於正整數, 可以推廣到任意實數。推廣的二項式定理是 \begin{eqnarray*} (1-x)^m &=& 1 - mx + \frac{m(m-1)}{2!}x^2 - \frac{m(m-1)(m-2)}{3!}x^3 + \cdots \\ && + (-1)^k \frac{m(m-1) \cdots (m-k+1)}{k!} x^k + \cdots \end{eqnarray*} 運用推廣的二項式定理, 我們把式 (3) 展開, 得 \begin{eqnarray*} P(x) &=& \frac{x}{2} \bigg (2x+\frac{2}{2}{2\choose 1}x^2 + \frac{2}{3}{4\choose 2}x^3 + \cdots + \frac{2}{n}{2n-2\choose n-1}x^n + \cdots \bigg ) \\ &=& \sum_{n=1}^\infty \frac{1}{n}{2n-2\choose n-1} x^{n+1} \end{eqnarray*} 對照兩邊 $x^{n+1}$ 的係數, 便得 $$ p_{n+1} = \frac{1}{n}{2n-2\choose n-1}. $$

生成函數是十九世紀著名數學家拉普拉斯 (Laplace) 為解決概率問題而首先引進的方法, 它顯然有點難度, 不如其他模型那樣巧妙, 但卻是組合計數中的典型方法。

它是一支帶刺的玫瑰, 棘手, 但很迷人。

參考文獻

---------本文作者任教中國廣州華南師範大學數學系---------