本文於 2026 年 1 月 6 日刊載於中研院訊漫步科研專欄, 作者及中研院訊同意本刊轉載。

我們首先看看以下這個中學生也能理解的組合問題：

問1：

 

在 $4\times 2$ 的方格(如上圖)中填入 $1\ldots 8$ 的數字, 並且滿足以下遞增條件：

$\bullet$ 若在座標 $(i,j)$ 的格子填入 $a$, 在座標 $(i+1,j)$ 的格子填入 $b$, 則 $b\gt a$；
$\bullet$ 若在座標 $(i,j)$ 的格子填入 $a$, 在座標 $(i,j+1)$ 的格子填入 $b$, 則 $b\gt a$；

試問有幾種方法？

答1： $14$ 種, 可以如下圖依序枚舉

 

上述的問題可以推廣, $4$ 換成任意的正整數 $n \ge 0$。

問2： 在 $n\times 2$ 的方格中填入 $1 \ldots 2n$ 的數字, 並且滿足以下遞增條件：

$\bullet$ 若在座標 $(i,j)$ 的格子填入 $a$, 在座標 $(i+1,j)$ 的格子填入 $b$, 則 $b\gt a$；
$\bullet$ 若在座標 $(i,j)$ 的格子填入 $a$, 在座標 $(i,j+1)$ 的格子填入 $b$, 則 $b\gt a$；

試問有幾種方法？

答2： Catalan 數

$$ C_n = \frac{(2n)!}{n!(n+1)!} $$

這公式可由遞迴方法證明。 現在考慮一個整數 $1 \le m \le n$, 並考慮以下額外條件

$\bullet$ 座標 $(m,2)$ 的格子填入 $2m$；
$\bullet$ 對所有滿足 $1 \le i \lt m$ 的數字 $i$, 座標 $(i, 2)$ 的格子填入的數字 $\gt 2i$；

那麼, 滿足這二個額外條件的填入數字的方法共有 $C_{m-1}C_{n-m}$ 種。 因為每一個填入數字的方法都有一個唯一的 $m$ 滿足以上額外條件, 我們就推得遞迴式

$$ C_0 = \sum_{m=1}^n C_{m-1}C_{n-m} $$

由此遞迴式以及初始值 $C_0 = 1$ 就可由數學歸納法推得上述對一般 $n\ge 0$ 的公式。 例如：

$$ C_5 = \frac{10!}{6!\cdot 5!} = \frac{10\cdot 9\cdot 8\cdot 7}{5\cdot 4\cdot 3\cdot 2\cdot 1} = 42 $$

讀者不妨動手驗證 $5\times 2$ 的格子真的有 $42$ 種填入 $1\ldots 10$ 並且滿足遞增條件的方法。

既然 $n\times 2$ 的方格有一般的公式 (Catalan 數), 那這個公式能不能再推廣呢？ $n\times m$ 的方格如何？ 更不規則的方格圖呢？

問3：

 

在以上方格圖表中填入 $1\ldots 9$ 的數字, 並且滿足以下遞增條件：

$\bullet$ 若在座標$(i,j)$ 的格子填入 $a$, 在座標$(i+1,j)$ 的格子填入 $b$, 則$b\gt a$；
$\bullet$ 若在座標$(i,j)$ 的格子填入 $a$, 在座標$(i,j+1)$ 的格子填入 $b$, 則$b\gt a$；

試問分別有幾種方法？

答3： 分別為 $84, 168, 162$。

這三個數字 $84, 168, 162$ 可由著名的「鉤長公式」算出, 我們現在就來解釋這個公式。 對圖中任一個方格 $(i,j)$ 定義其鉤長 $h(i,j) =\,$正右方與正上方 (含自身) 方格的總數, 例如下圖中

 

方格 $(1,1)$, $(2,2)$, $(4,1)$ 的鉤長分別為 $h(1,1)=6$, $h(2,2)=3$, $h(4,1)=1$。 如果我們將方格圖各橫列的長度由下而上標示為$\lambda = (\lambda_1, \lambda_2, \ldots, \lambda_r)$, 那麼鉤長公式如下：

$$ \frac{(\lambda_1 + \cdots + \lambda_r)!}{\prod_{j=1}^r\prod_{i=1}^{\lambda_j}h(i,j)} $$

上面的第二個方格圖的橫列長為$ \lambda = (4,3,2) $, 所以套用鉤長公式可以算出滿足遞增條件的填表方法數為

$$ \frac{(4 + 3 + 2)!}{7\cdot 5 \cdot 3 \cdot 1 \cdot 4\cdot 3\cdot 1\cdot 2\cdot 1} = 168 $$

同樣的方法, 可以算出 $3\times 3$ 的方格 $\lambda = (3,3,3)$, 填入 $1\ldots 9$ 並且滿足遞增條件的方法共有 $84$ 種。

鉤長公式是 1900 年由普魯士數學家 Ferdinand Georg Frobenius 所發現。 Frobenius 利用排列群 $S_n$ 的線性表現的特徵函數證明了這個公式, 他的方法是現今「對稱函數論」以及「群表現論」二個領域的開端。

「群」是一種數學中用來描述空間對稱性的結構, 其中排列群 $S_n$ 描述的是 $n$ 個點的集合 $\{1, 2, 3, \ldots, n\}$ 的所有排列 (所以 $S_n$ 有$n!$個元素)。 「群表現」則是描述線性空間(歐式空間)對稱性的代數結構。 由於二者的定義脫離了初等數學的範圍, 筆者在此就不更深入介紹。

「對稱函數」是一種空間中有對稱性的函數, 例如： $F(x, y, z) = xy + xz + yz$ 是個對稱函數, 這是因為我們可以將 $x, y, z$ 三個變數任意排列而不影響它的值, 也就是說

$$ F(x, y, z) = F(x, z, y) = F(y, x, z) = F(y, z, x) = F(z, x, y) = F(z, y, x) $$

我們將這個函數 $F(x,y,z)$ 稱為「單項式對稱函數」, 通常記作 $m_{(1,1,0)}(x,y,z)$。 更一般來說, 任意給定一個遞減數列 $\lambda = (\lambda_1, \lambda_2 , \lambda_3)$, 我們都能定義一個對應的單項式對稱函數 $m_\lambda$, 例如

\begin{align*} m_{(3,0,0)}(x,y,z) &= x^3 + y^3 + z^3 \\ m_{(2,1,0)}(x,y,z) &= x^2y + x^2z + y^2x + y^2z + z^2x + z^2y \\ m_{(1,1,1)}(x,y,z) &= xyz \end{align*}

除了這些單項式對稱函數外, 另一組重要的對稱函數稱為 Schur 函數, 記作 $s_\lambda$, 它與對稱群 $S_n$ 的群表現論息息相關, 例如：

\begin{align*} s_{(3,0,0)}(x,y,z) &= x^3 + y^3 + z^3 + x^2y + x^2z + y^2x + y^2z + z^2x + z^2y + xyz \\ s_{(2,1,0)}(x,y,z) &= x^2y + x^2z + y^2x + y^2z + z^2x + z^2y + 2xyz \\ s_{(1,1,1)}(x,y,z) &= xyz \end{align*}

事實上, Schur 函數總是可以寫成單項式對稱函數的倍數的和：

\begin{align*} s_{(3,0,0)} &= m_{(3,0,0)} + m_{(2,1,0)} + m_{(1,1,1)} \\ s_{(2,1,0)} &= m_{(2,1,0)} + 2m_{(1,1,1)} \\ s_{(1,1,1)} &= m_{(1,1,1)} \end{align*}

以上的這些和的各項係數即是著名的 Kostka 數, 它們在「代數組合論」與「群表現論」中有顯著的地位。 仔細觀察 $m_{(1,1,1)}$ 這項的係數, 分別為 $1, 2, 1$, 這正好是以下三方格圖中填入 $1, 2, 3$ 滿足遞增條件的方法數

 

一般來說, 如果方格圖橫列長為遞減數列 $\lambda = (\lambda_1, \lambda_2, \ldots, \lambda_r)$, 且一共有 $n=\lambda_1+\cdots +\lambda_r$ 個格子, 那麼 $s_\lambda$ 這個 Schur 函數中 $m_{(1,1,\ldots,1)}$ 這項的係數即為在方格圖中填入 $1, \ldots, n$ 且滿足遞增條件的方法數。

20 世紀後半以來, 「對稱函數論」以及「群表現論」的發展突飛猛進。 對稱函數論中, 最著名的莫非是英國數學家 Ian Grant Macdonald 所發現的 $(q,t)$-對稱函數以及 $(q,t)$-Kostka 多項式。 前者推廣了 Schur 函數, 後者推廣了 Kostka 數。 這二者仍然是現在「群表現論」以及「對稱函數論」中相當熱門的研究主題。

最後, 為了展示對稱函數論的應用, 我們看看以下問題：

問4： 給定任意一個參數 $q$, 將以下 $x, y, z$ 的對稱函數的乘積展開

\begin{align*} f(x, y, z) = &\left(1 - \frac{x}{y}\right)\left(1 - \frac{x}{y}q\right)\left(1 - \frac{x}{y}q^2\right)\\ &\left(1 - \frac{x}{z}\right)\left(1 - \frac{x}{z}q\right)\left(1 - \frac{x}{z}q^2\right)\\ &\left(1 - \frac{y}{x}\right)\left(1 - \frac{y}{x}q\right)\left(1 - \frac{y}{x}q^2\right)\\ &\left(1 - \frac{y}{z}\right)\left(1 - \frac{y}{z}q\right)\left(1 - \frac{y}{z}q^2\right)\\ &\left(1 - \frac{z}{x}\right)\left(1 - \frac{z}{x}q\right)\left(1 - \frac{z}{x}q^2\right)\\ &\left(1 - \frac{z}{y}\right)\left(1 - \frac{z}{y}q\right)\left(1 - \frac{z}{y}q^2\right) \end{align*}

試問常數項 ($x^0y^0z^0$ 這項)的係數為何？

答4：

$$ \frac{(1 - q^8)(1 - q^7)(1 - q^5)(1 - q^4)}{(1 - q^{2})^2(1 - q)^2} $$

若實際動手計算, 這將曠日廢時, 畢竟 $18$ 個二項式的乘積展開將有 $2^{18} = 262144$ 項。 然而, 這個答案可以不費吹灰之力, 由「Macdonald 常數項公式」輕易算出。 「Macdonald 常數項公式」由俄美數學家 Ivan Cherednik 於 1995 年所證明。 證明的關鍵是 1990 年代所發展的「Dunkl 算子」以及「雙重仿射 Hecke 環」這些代數結構的特質, 這二個代數結構正是在筆者研究領域的範圍內。

作為結語, 現代數學研究中, 代數與幾何方法早已隨處可見, 許多看似簡而易懂的組合問題背後深藏了代數與幾何的結構。 不僅是組合論的研究, 在其他數學領域中 (例如數論) 也是如此。 代數領域中的表現論, 也因為與各種領域互動接觸, 發展出了多采多姿的方法、 技術、 理論來解決各式各樣的問題。 上文所展示的幾個例子不過是窺見一斑。

本文作者任職中央研究院數學研究所研究學者