摘要: 朱世傑$-$范德蒙公式 (the Chu-Vandermonde formula) 是現代組合計數理論的一個基本公式。 本文闡明了該公式的組合意義, 分別論述了朱世傑 (1303) 和 A. T. Vandermonde (1772) 的歷史貢獻, 追蹤錢寶琮 1923 年首次解讀朱世傑的成果和傳播海外的歷程, 並對朱$-$范公式的現代發展作出概要介紹。

關鍵詞: 組合數學、組合計數、朱世傑$-$范德蒙公式、數學史。

現在國內外組合分析家所發表的一些論文和著作中, 當涉及對兩組合的乘積求和或 "卷積型" 恒等式時, 時常提到 "the Chu-Vandermonde formula" (下文簡稱 "朱---范公式")。 這裡的 "Chu" 即朱世傑 (字漢卿, 號松庭), 我國宋元數學四大家之一, 他在 1303 年出版了 $\langle\!\langle$四元玉鑒$\rangle\!\rangle$, 對中世紀世界數學卓有貢獻。 Vandermonde 就是學高等代數的人熟知的法國數學家范德蒙 (A. T. Vandermonde, 1735$\sim$1796, 或譯為旺德蒙德)。 二百多年來, 朱$-$范公式已有 Rothe (1793), Gauss, Hagen (1891), Gould (1956), Handa 和 Mohanty (1969) 等人的多種擴充, 應用甚廣。 因此, 有必要對朱世傑、 Vandermonde 的工作和後來的進展作一概述。

1. $\langle\!\langle$四元玉鑒$\rangle\!\rangle$ 中的組合恒等式

朱世傑在 $\langle\!\langle$四元玉鑒$\rangle\!\rangle$ (1303) "茭草形段"、 "如象招數" 和 "果垛疊藏" 中用傳統的垛積招差術獲得了一批重要成果, 其中有朱世傑恒等式: \begin{equation} %(1) \sum_{k=1}^n {k+p-1 \choose p} = {n+p \choose p+1} \end{equation} 它是賈憲三角形中每斜行前 $n$ 項和的計數公式, 表明了組合的一項基本性質, 作者認為與帕斯卡恒等式具有同樣的重要性。 式 (1) 右邊的組合數 (在賈憲和朱世傑時僅為計算二項式係數的演算法, 不含從多少元素中取出多少元素不同取法總數的組合意義) 在中國數學史上叫做三角垛系列, 朱世傑給出 $p=2, 3, 4, 5, 6$ 時的名目依次為: 茭草垛、 三角垛、 撒星形垛、 撒星更落一形垛、 三角撒星更落一形垛。 在通常的組合數學書和組合恒等式表中常見的等式是 \begin{equation} %(2) \sum_{k=0}^m {k \choose p} = {m+1 \choose p+1} \end{equation} 及 \begin{equation} %(3) \sum_{k=0}^q {p+k \choose k} = {p+q+1 \choose q} \end{equation} 其實兩者均為朱世傑恒等式的等價公式, 表示賈憲三角形中的同一性質。

證明: 由 (3) 知 $\displaystyle\sum_{k=0}^q{p+k\choose p}={p+q+1\choose p+1}$, 令 $m=p+q$, $q=m-p$, 代入得 $$ \sum\limits_{k=0}^{m-p}{p+k\choose p}={m+1\choose p+1}, \quad \hbox{亦 } \sum\limits_{k=0}^m{k\choose p}={m+1\choose p+1}, \quad \hbox{即式 (3) 變換成 (2)。} $$ 再證 (1) (2) 兩式等價。令 $m=n+p-1$, $$ \sum_{k=1}^n {k+p-1\choose p} = \sum_{k=1}^{m-p+1}{k+p-1\choose p} = \sum_{k=p}^m{k\choose p} = \sum_{k=0}^m{k\choose p} = {m+1\choose p+1} $$ 式 (1) 即變換成 (2) 式; 反之, (2) (3) 式亦可變換成 (1) 式。證完。

據清代學者羅士琳的解釋, 可將 "茭草形段" 第四題給出的關係表示為 \begin{equation} %(4) \sum_{k=1}^n {k+1\choose 2}{n+2-k\choose 2} = \sum_{k=1}^n {k+3\choose 4} = {n+4\choose 5} \end{equation} 在原著中 "撒星更落一形垛" 可用式右的組合表示, 是式 (1) 中 $p=5$ 時的情況。 羅士琳將 $a_k=k(k+1)/2$ 叫做 "三角積", $b_k=(n-k+2)(n-k+1)/2$ 叫做 "逆列三角積"。 顯然 $\Sigma a_kb_k$ 構成卷積。

朱世傑在 "果垛疊藏" 第六題中依據同樣的關係和方法求得 \begin{equation} %(5) \sum_{k=1}^n {k+2\choose 3}{n+2-k\choose 2} = \sum_{k=1}^n {k+4\choose 5} = {n+5\choose 6} \end{equation} 朱世傑命名的 "撒星更落一形果子積", 其組合形式應如式 (5)右邊所示, 是式 (1) 中 $p=6$ 時的情況。 羅士琳將 $a_k=(k+2)(k+1)k/6$ 叫做 "三角積積數", $b_k(n+2-k)(n+1-k)/2$ 叫做 "逆列三角積", 顯然 $\Sigma a_kb_k$ 構成卷積。不難看出, (4)、 (5) 兩式屬於更廣泛一類公式的兩個特例, 本文將其推廣, 獲得 \begin{equation} %(6) \sum_{k=1}^n {k+p-1\choose p}{n+q-k\choose q} = \sum_{k=1}^n {k+p+q-1\choose p+q} = {n+p+q\choose p+q+1} \end{equation}

當 $p=2$, $q=2$ 時便是式 (4), 當 $p=3$, $q=2$ 時便是式 (5), 思路較為清晰。 有理由認為朱世傑已掌握這類公式, 推廣它是題中應有之義。 我們將式 (4)、 (5)、 (6) 稱為朱世傑組合卷積公式。 推測它的立術之原, 不大可能是從代數變換而得, 朱世傑一定是從大量操演垛積實物獲得了其間的數量關係, 因此可以說, 垛積成為中國傳統數學早期一種有效的數學模型。

2. Vandermonde 公式的組合意義

A. T. Vandermonde 是法國科學院院士 (1771), 對高等代數的發展有重要貢獻。 Vandermonde 公式在三種中譯本的 $\langle\!\langle$范氏大代數$\rangle\!\rangle$ 中皆有介紹, 並出現於近年出版的組合數學專著、 教材的例題和習題中, 。 然而, 大概是缺乏歷史感之故, 有的書卻未注明范德蒙公式。

在研究怎樣對兩組合的乘積求和、 同時考慮遊動變數可能出現的各種位置時, 范德蒙 1772 年向法國科學院提交了一篇論文, 其中的一個組合公式具有一般性, 在同類公式中最為重要, 通常被稱為 "Vandermonde 綜合式", 原式為: \begin{equation} %(7a) \sum_k {r\choose k}{s\choose n-k} = {r+s\choose n}\tag*{(7a)} \end{equation}

可以這樣來理解這個公式: 式右是從 $r$ 個男人和 $s$ 個女人中來選擇 $n$ 個人的方法數, 而式左中的每一項是從男人中選出 $k$ 個同時從女人中選出 $n-k$ 個人的方法數。 設 $\alpha$, $\beta$ 為任意實數, 則 Vandermonde 公式的一般形式為 \begin{equation} %(7b) \sum_{k=0}^n {\alpha\choose k}{\beta\choose n-k} = {\alpha+\beta\choose n}\tag*{(7b)} \end{equation}

特別當 $\alpha$, $\beta$ 為正整數時, 它的組合意義是: 從 $\alpha$ 中取 $k$ ($k=0, 1, \ldots, n$)個, 同時從 $\beta$ 中取 $n-k$ ($n-k=n, n-1, \ldots, 1, 0$) 個, 其不同取法的總數, 與從 $\alpha+\beta$ 中取 $n$ 個不同取法的總數相等。

這是一個組合卷積 (convolution, 以前曾譯為 "摺積") 公式。設兩函數 $f$ 與 $g$ 構成卷積, 記作 $f*g$, 則其意思即指 $$ f(0)g(n) + f(1)g(n-1) + \cdots + f(n)g(0) = (f*g)(n) $$ \begin{equation} %(8) \hskip -1.3cm \hbox{亦即 } \hskip 3cm (f*g)(n) = \sum_{k=0}^n f(k) g(n-k) \hskip 4.5cm\tag*{(8)} \end{equation} 此處展開式中共含 $n+1$ 項。

可以看出, 上述垛積術中正列 "三角積" 與 "逆列三角積" 逐項對應相乘求和, 恰是卷積的形式, 朱世傑的垛積公式 (4)、 (5)、 (6) 即屬於卷積型的。

演算法和程式設計技術的先驅者、 美國斯坦福大學教授 Donald E. Knuth (克努特, 中文名高德納) 對中國數學感興趣, 他曾關注賈憲、 楊輝、 朱世傑以及明安圖的計數成就。 在他的名著 The Art of Computer Programming $\langle\!\langle$電腦程式設計藝術$\rangle\!\rangle$ (1998) 中, 講到 (6)、 (7) 兩式之間的關係, 指明朱世傑的組合公式在先, 材料出處是李約瑟博士的 $\langle\!\langle$中國的科學與文明$\rangle\!\rangle$ 第 3 卷數學。

3. 朱世傑卷積公式的解讀與傳播

錢寶琮 1923 年在 $\langle\!\langle$學藝$\rangle\!\rangle$ 上發表 "朱世傑垛積術廣義", 首次將上文所稱的朱世傑卷積公式推廣, 得到 (6) 式 (但不包括 (6) 式第二個等號右邊): $$ \sum \frac{r^{|p|}}{1^{|p|}} \cdot \frac{(n+1-r)^{|q|}}{1^{|q|}} = \sum \frac{r^{|p+q|}}{1^{|p+q|}} $$

這裡 $r^{|p|}=r(r+1)\cdots(r+p-1)$, $1^{|p|}=p!$ 這是當時所用的記號。

湯天棟 1926 年在 $\langle\!\langle$科學$\rangle\!\rangle$ 上發表 "茭草形段羅草補注", 用圖形和代數式表示 "茭草形段" 部分的內容 (不涉及用組合符號表示的朱世傑卷積公式)。

錢先生 1929 年在 $\langle\!\langle$中國算學史$\rangle\!\rangle$ 上編中再次引述, 1932 年再版。

方淑姝 1939 年在 $\langle\!\langle$數學雜誌$\rangle\!\rangle$ 上發表 "朱世傑垛積術廣義", 她使用的符號更接近現代常用的組合符號, 提到了錢寶琮和湯天棟的成果。

現代科學史學科的奠基人、 著名科學史家喬治 $\cdot$ 薩頓 G. Sarton較早將此公式介紹到西方; 李約瑟的 $\langle\!\langle$中國的科學與文明$\rangle\!\rangle$ (1953, 譯名 $\langle\!\langle$中國科學技術史$\rangle\!\rangle$) 第 3 卷數學 (王玲參與) 中也引用了這一結果。

需要明確, 正是錢寶琮先生 1923 年首次將朱世傑的式 (6) 表述成現代組合形式發表在 $\langle\!\langle$學藝$\rangle\!\rangle$ 上, 經喬治 $\cdot$ 薩頓、 李約瑟的介紹, 西方學者才對它有所瞭解。至今在現代數學界流傳開來, 錢先生發軔於先, 功不可沒。

但同時也須指出, 我國數學史界對此問題亦有不同的看法, 認為 "實際上這種類型的求和問題已經超出了朱世傑著作中所有問題的範圍", "這一不正確的論斷可能是受到了羅士琳的影響。" 換言之, 朱世傑並無此式。 這涉及到羅士琳對 $\langle\!\langle$四元玉鑒$\rangle\!\rangle$ 此題的解讀是否不著邊際或無中生有, 是需要針對朱、 羅原著逐行、 逐句、 逐詞查證的。 本文的推證已見於前, 限於篇幅, 這裡不能詳細說明; 如果感興趣, 這個問題是可以展開討論的。

4. Chu-Vandermonde 卷積公式的發展

Gauss 研究超比例級數時曾將類似的卷積關係推廣到複數的情形, 被稱為 Gauss-Vandermonde 公式。

Rothe(1793)-Hagen(1891)-Gould(1956) 的卷積型恒等式可寫成, \begin{equation} %(9) \sum_{k=0}^n \frac{x}{x\!+\!kz} {x\!+\!kz\choose k} \frac{y}{y\!+\!(n\!-\!k)z} {y\!+\!(n\!-\!k)z\choose n-k} = \frac{x+y}{x\!+\!y\!+\!nz} {x\!+\!y\!+\!nz\choose n}\tag*{(9)} \end{equation}

其中, Hagen 的恒等式為 \begin{equation} %(10) \sum_{k=0}^n {x+kz\choose k} {y-kz\choose n-k} \frac{x}{x+kz} = {x+y\choose n}\tag*{(10)} \end{equation}

顯然 (10) 式中令 $k=0$ 便得出 (7) 式。Mohanty-Handa (1969)曾將 (9) 推廣成多重和形式。 又, Hagen 還將 (9) 發展成如下形式 \begin{equation} %(11) \sum_{k=0}^n {x\!+\!kz\choose k} {y\!-\!kz\choose n-k} \frac{p+qk}{(x\!+\!kz)(y\!-\!kz)} = \frac{p(x\!+\!y\!-\!nz)\!+\!nxq}{x(x+y)(y-nz)} {x\!+\!y\choose n}\tag*{(11)} \end{equation}

特別當 $p=y$, $q=-z$ 時, 便有 \begin{equation} %(12) \sum_{k=0}^n {x+kz\choose k} {y-kz\choose n-k} \frac{1}{x+kz} = \frac{1}{x} {x+y\choose n}\tag*{(12)} \end{equation}

事實上可以證明, (9) 與 (11) 是等價的, 即兩者可互推。當然它們均為朱$-$范公式的推廣。

注意到組合數學界同感興趣的事實------歷來公認為 Rothe-Hagen-Gould 卷積型恒等式是朱$-$范公式的 "非平凡推廣" (non-trivial extension), 這裡卻有必要說明, 只須利用 Hsu-Gould 反演公式, 即可證明 (11) 與 (9) 都可由朱$-$范公式推證。 這說明 (9) 與 (11) 實質上仍與原始的朱$-$范公式等價 (詳見文獻, )。

謹以此文紀念 $\langle\!\langle$四元玉鑒$\rangle\!\rangle$ 成書 705 周年。

致謝: 徐利治 (Leetsch C. Hsu) 教授和羅伊德 (Keith Lloyd) 教授為本文提供了參考文獻, 特致謝忱。

參考文獻

---本文作者現任教浙江大學科學技術與文化研究所---