數學傳播

1. 引言

Catalan 數 原始定義為符合遞迴關係式$$c_{n+1}=c_0 c_n+c_1 c_{n-1}+\dots +c_n c_0,\enspace c_0=1$$的數列， 可算出其一般式為$c_n=\frac{1}{n+1}{2n \choose n}$。其前幾項為 $$\{c_n\}_{n\geq 0}=1,1,2,5,14,42,132,\dots .$$ Catalan數有許多種組合解釋，其中一種是指利用 $(1,1)$ 和 $(1,-1)$ 兩向量從原點在上半平面中走到 $(2n,0)$ 的方法數；而如果改考慮利用 $(1,s-1)$ 和 $(1,-1)$ 從原點在上半平面中走到 $(sn,0)$ 的方法數 ， 已由 N. I. Fuss 在 1791 年發現其路徑數即為 Fuss-Catalan 數 ，

其一般式為 $c^{(s)}_{n}=\frac{1}{(s-1)n+1}{sn \choose n}$。 雖然 Fuss-Catalan 數為 Catalan 數的推廣，但 Fuss 的研究卻是在 Catalan 數發表前許多年獨立完成。 接著考慮遞迴關係式 \begin{equation} c^{(s)}_{n+1}=\sum_{r_1+r_2+\dots +r_k=n}c^{(s)}_{r_1}\times c^{(s)}_{r_2}\times \dots \times c^{(s)}_{r_3}. \label{eqn:rr} \end{equation} 由於當 $s=2$ 時剛好是Catalan數的遞迴關係式，因此我們希望 Fuss-Catalan 的一般式也能符合推廣後的關係式 (\ref{eqn:rr})。然而用遞迴關係對 {$c^{(s)}_{n}$} 所造的生成函數 $A^{(s)} (x)$ 必須滿足 $s$ 次式 $x(A^{(s)})^s (x)=A^{(s)} (x)-1$ (見系理 5， 第44 頁)， 是一個很難解的多次式； 而即使已知固定 $s$ 時 Fuss-Catalan 數的生成函數 $C^{(s)} (x)$ 應該是 $\sum_{n\geq 0}c^{(s)}_{n}x^n$，但要驗證 $C^{(s)} (x)$ 滿足上述 $s$ 次式須要做 $s$ 次疊合(convolution)， 也不是一件容易的事。所以在第 2 節中列出六個 Fuss-Catalan 數的組合解釋，而其中(A)、(B)、(C)可以解釋一般式， (D)、(E)、(F)可以解釋遞迴關係，並由(C)、(F)等價，因此知道一般式符合遞迴關係。接著在第 3 節中嘗試找到 Fuss-Catalan 數不同於 Catalan 數的組合意義；並在最後於第 4 節利用 Fuss-Catalan 數推廣 Jonah 定理，以說明 Fuss-Catalan 數的必要性。

2. Fuss-Catalan 數的基本性質

2.1. 先備知識

首先先觀察Catalan數和Fuss-Catalan數有什麼類似的特性。

性質. 我們可以用不同方式刻畫Catalan數或Fuss-Catalan數:

1. 以下幾種Catalan數的定義等價：
   • $c_n=\frac{1}{n+1}{2n \choose n}$
   • $c_n=\frac{1}{2n+1}{2n+1 \choose n} =\frac{1}{n}{2n \choose n+1} =\frac{1}{n}{2n \choose n-1}$
   • $c_{n+1}=c_0 c_n+c_1 c_{n-1}+\dots +c_n c_0,\enspace c_0=1$
2. 以下幾種Fuss-Catalan數的定義等價：
   • $c^{(s)}_{n}=\frac{1}{(s-1)n+1}{sn \choose n}$
   • $c^{(s)}_{n}=\frac{1}{sn+1}{sn+1 \choose n} =\frac{1}{n}{sn \choose (s-1)n+1} =\frac{1}{n}{sn \choose n-1}$
   • 符合(\ref{eqn:rr})式，且$c^{(s)}_{0}=1$

證明. 由於 Catalan 數為 Fuss-Catalan 數在 $s=2$ 時的特殊狀況，我們僅對 Fuss-Catalan 數的性質做出證明。 \begin{eqnarray*} c^{(s)}_{n}&=&\frac{1}{(s-1)n+1}{sn \choose n} =\frac{(sn)!}{n![(s-1)n+1]!}\\ &=&\frac{1}{sn+1}\frac{(sn+1)!}{n![(s-1)n+1]!} =\frac{1}{sn+1}{sn+1 \choose n}\\ &=&\frac{1}{n}\frac{(sn)!}{(n-1)![(s-1)n+1]!} =\frac{1}{n}{sn \choose (s-1)n+1} =\frac{1}{n}{sn \choose n-1} \end{eqnarray*} 因此知道以上幾種方法都為Fuss-Catalan數的定義，而最後的遞迴關係式，會在接下來的定理中由(C)、(F)等價證明。 $\Box$

為了證明的方便，先引入一個引理：

引理1. 設 $p$, $q$ 為正整數，令集合$$S=\{\vec{x}=(x_1,x_2,\dots ,x_q)\enspace |\enspace 0\leq x_1 \leq x_2 \leq \dots \leq x_q \leq p-1,x_i \in \mathbb{Z}\}.$$ 對於$(x_1,x_2,\dots ,x_q)\in S$以及$0\leq \ell \leq p-1$，令$y_i=(x_i +\ell )\bmod{p}, \enspace 1\leq i \leq q$。定義 $$(x_1,x_2,\dots ,x_q)\oplus \ell :=(z_1,z_2,\dots ,z_q),$$ 其中 $z_1 \leq z_2 \leq \dots \leq z_q $ 為 $y_1,y_2,\dots ,y_q$ 按由小到大的重排 。 在 $S \times S$ 上定義一關係： $\vec{x_1}\sim \vec{x_2}$ 表示存在 $\ell $ 使得 $\vec{x_1}=\vec{x_2}\oplus \ell $。 則：

1. $\sim $為一等價關係
2. 當$(p,q)=1$時，$S/\sim $的每個等價類有$p$個元素
3. $|S/\sim |=\frac{1}{p}{p+q-1\choose q}$

如 $p=5$ 時， $$(1,1,2)\oplus 3=(0,4,4)$$ 而 $(1,1,2)\equiv (0,4,4)$

證明. 考慮 $Z_p$ 作用在集合 $S$ 上，則定理中的一個等價類即群作用中的一個軌跡 (orbit)。 $$Z_p \times S\rightarrow S$$ $$\ell ,\enspace \vec{x} \mapsto \vec{x}\oplus \ell $$ 對任意 $\vec{x}\in S$，令其穩定集 (stabilizer) 個數 $|G_{\vec{x}}|=c$， 我們有 $|Z_p|=c\cdot |O_{\vec{x}}|$， 因此 $c|p$。

令 $G_{\vec{x}}=\lt d\gt ,\enspace cd=p$，則有 $$\vec{x}=d\vec{x}=2d\vec{x}=\dots =(c-1)d\vec{x}$$ 若 $\vec{x} $ 中的第 $1$ 項在 $d$ 作用後跑到第 $i+1$ 項，跑了 $c$ 次回到第 1 項表示 $c\times i =q$， 因此有 $c|q$， 又因 $p$, $q$ 互質，所以 $c=1$， 進而得到對於所有 $S$ 中的 $\vec{x}$ 有 $|O_{\vec{x}}|=p$， 以及 $$|S|={p+q-1\choose q}=\sum_{\vec{x}\in I}{|O_{\vec{x}}|}=p\cdot |I|,$$ 所以 $$|S/\sim |=|I|=\frac{1}{p}{p+q-1\choose q}.$$ $\Box$

由引理 1 及 $|S/\sim |$ 為整數即可得下列系理 2。

系理2. 若 $(p,q)=1$，則 $p\enspace |\enspace {p+q-1\choose q}$.

註. 此結果亦可由數論方法證明： $${p+q-1\choose q}=\frac{(p+q-1)!}{q!(p-1)!}=\frac{p}{q}\frac{(p+q-1)!}{(q-1)!p!}=\frac{p}{q}{p+q-1\choose p},$$ 由於$(p,q)=1$且$\frac{p}{q}{p+q-1\choose p} $為整數，所以 $q\enspace |\enspace \left( \begin{array}{c} p+q-1\\p\end{array}\right).$$\\$ 因此$\frac{1}{q}{p+q-1\choose p}$為整數，得證$p$整除${p+q-1\choose q}$。

由引理1可發現適當地選取 $p$ 和 $q$，則可得到 Fuss-Catalan 數的一般式：

• 如果令 $p=n,\enspace q=n+1$，$\\$ $\Rightarrow |S/\sim |=\frac{1}{n}{2n\choose n+1}=c_n$
• 如果令 $p=n,\enspace q=(s-1)n+1$，$\\$ $\Rightarrow |S/\sim |=\frac{1}{n}{sn\choose (s-1)n+1}=c^{(s)}_{n}$
• 如果令 $p=(s-1)n+1,\enspace q=n$，$\\$ $\Rightarrow |S/\sim |=\frac{1}{(s-1)n+1}{sn\choose n}=c^{(s)}_{n}$

2.2. 六種組合解釋

定理3. 以下三種組合解釋(A)、(B)、(C)可以當做 $c^{(s)}_{n}=\frac{1}{(s-1)n+1}{kn\choose n}$ 的組合意義：

1. 同餘方程式 $$x_1+x_2+\dots +x_{(s-1)n+1}\equiv 0 \mod{n},$$ $$0\leq x_1\leq x_2\leq \dots \leq x_{(s-1)n+1}\leq n-1$$ 其中 $x_i=0,1,\dots ,n-1$, for all $i$，有 $c^{(s)}_{n}$ 組解 。 例： $c^{(3)}_{3}=12.$ $(0,0,0,0,0,0,0),(0,0,0,0,0,1,2),(0,0,0,0,1,1,1),$ $(0,0,0,0,2,2,2),(0,0,0,1,1,2,2),(0,0,1,1,1,1,2),$ $(0,0,1,2,2,2,2),(0,1,1,1,1,1,1),(0,1,1,1,2,2,2),$ $(0,2,2,2,2,2,2),(1,1,1,1,1,2,2),(1,1,2,2,2,2,2).$
2. 在環狀的 $n$ 個洞裡放入 $(s-1)n+1$ 個球，旋轉後可以重合視為同一種，則有 $c^{(s)}_{n}$ 種放法。 例： $c^{(3)}_{3}=12.$
   

   

   
   
3. 從 $(0,0)$ 到 $(n,(s-1)n)$ 不超過 $L:y=(s-1)x$ 的路徑有 $c^{(s)}_{n}$ 種走法 。

例： $c^{(3)}_{3}=12.$

證明. 將三種狀況分開討論

1. 令$p=n,\enspace q=(s-1)n+1,\enspace \vec{1}=(1,1,\dots ,1)$，原式可改寫成$\vec{1}\cdot \vec{x}\equiv 0$。對任一$\vec{x}\in S$，若$\vec{1}\cdot \vec{x}\equiv \ell_0$，則 $$\vec{1}\cdot (\vec{x}\oplus \ell )\equiv \vec{1}\cdot \vec{x}+\vec{1}\cdot \ell\vec{1}\equiv \ell_0+[(s-1)n+1]\ell \equiv \ell_0-\ell \pmod{n},$$ 可知包含$\vec{x}$的分割存在惟一的$\vec{x_0}=\vec{x}\oplus \ell_0$使得$\vec{1}\cdot \vec{x_0}\equiv 0$。由引理1知(A)解的組數$=$ $$|S/\sim |=\frac{1}{n}{n+(s-1)n+1-1\choose (s-1)n+1}=\frac{1}{n}{sn\choose n-1}=c^{(s)}_{n}.$$
2. 令 $p=n,\enspace q=(s-1)n+1$，接著任選一個洞，逆時針依序編號，對任一 $\vec{x}=(x_1,x_2,\dots ,x_n)\in S$， $i$ 在 $\vec{x}$ 中出現的次數可視為在 $i$ 號洞裡放的球數, 運算 $\oplus $ 可視為圖形的旋轉。 由引理 1 可知 (B) 的圖形數 $=$ $$|S/\sim |=\frac{1}{n}{sn\choose n-1}=c^{(s)}_{n}.$$
3. 令 $p=(s-1)n+1,\enspace q=n$，對任一 $\vec{x}\in S$，其第 $j$ 項可視為第 $j$ 行的高度 (如圖)。

   

   證明存在性： $S$ 的每個分割中都存在一個 $\vec{x_0}$，其對應的路徑不超過 $L$。 對任意 $\vec{x}$，取 $m$ 為使 $\vec{x}$ 的對應路徑不超過 $L_m:y=(s-1)x+m$ 的最小的整數，取路徑與 $L_m$ 交點中 $x$-座標最小者之座標為 $(i,y_i)$， 則鉛垂線 $x=i$ 的左邊都和 $L_m$ 沒有交點；又鉛垂線的右邊都沒超過 $L_m$。 因此取 $x_0=x\oplus (-y_i)$，其對應的路徑不會超過 $L$。

   

   證明惟一性： $S$ 的每個分割中都只存在惟一一個 $\vec{x_0}$，其對應的路徑不超過 $L$。 令棋盤的左下角叫 $A$ 點、右上角叫 $C$ 點，對任意路徑 $\vec{x}$， 在原棋盤 $A$ 點往下一格接上另一個棋盤的 $C$，畫上同樣的路徑，對 $0\lt \ell \leq sn$，取 $C_{\ell}$ 為路徑和 $y=\ell $ 交點中最右邊的一點，則以 $C_{\ell }$ 當棋盤 $C$ 點所框出來的路徑即為 $\vec{x}\oplus \ell $，可發覺 $C_{\ell }$ 都不可能在 $L$ 上， 所以任何 $\vec{x}\oplus \ell $ 在 $(0,0)$ 這點都會超過該 (虛線) 棋盤的對角線。

   

   由引理1 知，路徑數 $=|S/\sim |=\frac{1}{(s-1)n+1}{sn\choose n}=c^{(s)}_{n}.$ $\Box$ 引理4. 以下三種組合解釋 (D)、(E)、(F) 可以當做遞迴關係式(1) $, c^{(s)}_{0}=1$ 的組合意義：
4. 圓周上有 $sn$ 個點，用割線連接形成 $n$ 個 $s$ 邊形，其中任兩個 $s$ 邊形不論在圓周上或圓內都沒相交，有 $c^{(s)}_{n}$ 種連接法 例： $c^{(3)}_{3}=12.$

   

5. 有 $n$ 個頂點的 $s$-元樹，有 $c^{(s)}_{n}$ 種。 例： $c^{(3)}_{3}=12.$

   

6. 從 $(0,0)$ 到 $(n,(s-1)n)$ 不超過 $L:y=(s-1)x$ 的路徑有 $c^{(s)}_{n}$ 種走法 。

例： $c^{(3)}_{3}=12.$

證明.

同樣將三種情況分開討論：

• (D) 對於圓周上的 ($s(n+1)$( 個點，固定一個點為 ($v_1$(， 再順時針選取 ($v_2,v_3,\dots ,v_k$(， 可形成一個 $s$ 邊形，若要形成一個 (D) 中敘述的圖形，任兩個頂點間的點數(不包含兩頂點)應該要是 $s$ 的倍數，否則不能再塞入整數個 $s$ 邊形。
  令 $sr_i$ 表示 $v_i$ 和 $v_{i+1}$ 之間的點數， $i=1,2,\dots ,s-1$， $sr_s$ 表示 $v_s$ 和 $v_1$ 之間的點數。因為 $sr_i$ 個點可以形成 $c^{(s)}_{r_i}$ 種圖形，又其彼此互相獨立，對於一組給定的頂點，可以有 $c^{(s)}_{r_1}\times c^{(s)}_{r_2}\times \dots \times c^{(s)}_{r_s}$ 種圖形。但頂點必須符合 $$sr_1+sr_2+\dots +sr_s=s(n+1)-s\Rightarrow r_1+r_2+\dots +r_s=n,$$ 所以可得 $c^{(s)}_{n}$ 符合 (\ref{eqn:rr}) 式且 $c^{(s)}_{0}=1$。

  

• (E) 對於有 $n+1$ 個頂點的 $s$-元樹，其根部可長出 $s$ 個枝幹，若第 $i$ 個枝幹有 $r_i$ 個頂點，則 $r_i$ 個點可形成 $c^{(s)}_{r_i}$ 種樹，每個枝幹的長法互相獨立，所以固定枝幹的頂點數可以有 ($c^{(s)}_{r_i}\times c^{(s)}_{r_2}\times \dots \times c^{(s)}_{r_s}$ (種長法。又因為 ($r_1+r_2+\dots +r_s=n$(，可知 $c^{(s)}_{n}$ 符合 (1) 式且 ($c^{(s)}_{0}=1$(。
• (F) 令 $c^{(s)}_{n+1}$ 表示要從 $(0,0)$ 走到 $(n+1,s(n+1))$ 且不超過 $L:y=(s-1)x$ 的路徑數，在圖上畫 $s$ 條輔助線，第 $i$ 條為 ($y-1=(s-1)(x-1)+i$(。 可知 $(0,0)$ 一定要先走到 $(1,0)$，而必然超過 $s$ 條輔助線各至少一次。 令( $(x_0,y_0)=(1,0),\enspace (x_s,y_s)=(n+1,s(n+1))$( 且 $(x_i,y_i)$表示第一次超過第 $i$ 條輔助線時的交點，訂 ($r_i=x_{i+1}-x_i$(。 可發覺在 $r_i$ 區間中路徑不能超過第 $i$ 條輔助線，因此有 $c^{(s)}_{r_i}$ 種走法，而從 $(0,0)$ 到 $(n+1,s(n+1))$ 則有 ($c^{(s)}_{r_1}\times c^{(s)}_{r_2}\times \dots \times c^{(s)}_{r_s}$ (種走法。又因 ($r_1+r_2+\dots +r_s=n$(，可知 $c^{(s)}_{n}$ 符合 (1) 式且( $c^{(s)}_{0}=1$(。

2.3. 推論

系理5. 生成函數$C^{(s)} (x)=\sum_{n\geq 0}c^{(s)}_{n}x^n$滿足函數方程$x(A^{(s)})^s (x)=A^{(s)} (x)-1$。

證明. 若一數列 $\{c^{(s)}_{n}\}$ 符合 (\ref{eqn:rr}) 式且 $c^{(s)}_{0}=1$，則可知其生成函數 $A^{(s)}(x)$ 的係數關係滿足 $$[x^n]x(A^{(s)})^s(x)=[x^n]A^{(s)} (x),n=1,2,\ldots .$$ 但 $[x^0]x(A^{(s)})^s(x)=0$，所以有 $x(A^{(s)})^s (x)=A^{(s)} (x)-1$。

由定理 3 和定理 4 中的 (C) 和 (F) 知 Fuss-Catalan 數 $c^{(s)}_{n}=\frac{1}{(s-1)n+1}{sn\choose n}$ 會符合 (\ref{eqn:rr}) 式且 $c^{(s)}_{0}=1$， 得知固定 $ s $ 時 $\{c^{(s)}_{n}\}$ 的生成函數 $C^{(s)} (x)=\sum_{n\geq 0}c^{(s)}_{n}x^n$ 會符合 $x(A^{(s)})^s (x)=A^{(s)} (x)-1$。 $ \Box $

3. 其它相關的組合意義

已知 Catalan 數即為 Fuss-Catalan 數在 $ s=2 $ 的情況，特別地在定理 3 中的 (C) 若 $ s=2 $ 時， 我們可以看出 Catalan 數有一種組合意義是關於 $ n\times n $ 「方陣」的路徑數。

也許 Fuss-Catalan 數和 $ n\times n\times n $ 「立方體」也會有某些關係?

考慮從 $ (0,0,0) $ 到 $ (n,n,n) $ 的最短路徑，有 $ \frac{(3n)!}{n!n!n!} $ 種走法。值得注意的是 $ \frac{(3n)!}{n!n!n!} $ 又可以被寫成 $${3n \choose n}{2n \choose n}{n \choose n}=(2n+1)c^{(3)}_{n}\times (n+1)c^{(2)}_{n},$$ 也許試著在這個立方體做一些限制，路徑數剛好就會是 $ c^{(3)}_{n}\times c^{(2)}_{n} $。

引理6. 從 $ (0,0,0) $ 到 $ (n,n,n) $, 在下列限制條件內 $$\left\{ \begin{array}{l} y-z\geq 0\\ x-\frac{1}{2}y-\frac{1}{2}z\geq 0 \end{array}\right. $$ 的最短路徑有 $ c^{(3)}_{n}\times c^{(2)}_{n} $ 種走法。

證明. 此為定理 7 的特殊情形。 $ \Box $

如果推廣成 $ n\times n\times (s-1)n $ 的長方體，則有以下的定理。

引理7. 從 $ (0,0,0) $ 到 $ (n,n,(s-1)n) $, 在下列限制條件內 $$\left\{ \begin{array}{l} (s-1)y-z\geq 0\\ x-\frac{1}{s}y-\frac{1}{s}z\geq 0 \end{array}\right. $$ 的最短路徑有 $ c^{(s+1)}_{n}\times c^{(s)}_{n} $ 種走法。

證明. 任一條路徑投影到 $ yz $ 平面時，可視為是之前所講 (F) 的一種 (參見第43頁)，為一 $ n\times (s-1)n $ 的直角三角形，所以有 $ c^{(s)}_{n} $ 種走法。 又每種走法確定後，用該路徑向 $ x $ 方向切割，其階梯狀的圖形拉直後可以再視為一 $ n\times sn $ 的三角形，所以有 $ c^{(s+1)}_{n} $ 種走法。 由於兩者獨立，所以共有 $ c^{(s+1)}_{n}\times c^{(s)}_{n} $ 種走法。 $ \Box $

如果再把定理7中「底部必須是正方形」的條件放寬，還可以得到以下更一般的結果，而此系理的證明同定理 7。

系理8. 令 $ m $ , $ n $ , $ s $ , $ t $ 為整數且 $ sn=(t-1)m $。則從 $ (0,0,0) $ 到 $ (m,n,(s-1)n) $, 在下列限制條件內 $$\left\{ \begin{array}{l} (s-1)y-z\geq 0\\ x-\frac{m}{sn}y-\frac{m}{sn}z\geq 0 \end{array}\right. $$ 的最短路徑有 $ c^{(t)}_{m}\times c^{(s)}_{n} $ 種走法。

註. 如果考慮更高維度的空間，並經過適當的限制，也許可以得到更一般的結果，這將是以後研究的一個方向。

4. 用 $ c^{(s)}_{n} $ 推廣 Jonah 定理

在 Hilton 的研究中 ， 有一恆等式(Jonah定理)如下： \begin{equation} {n+1 \choose m}=\sum_{i\geq 0}{c_i{n-2i \choose m-i}}, n\in \mathbb{R}, m\in \mathbb{N}_0 , \label{eqn:Hilton} \end{equation} 其中 $ \mathbb{R} $ 為實數、 $ \mathbb{N}_0 $ 為非負整數，而其證明是利用Lattice path的方法。在此試著用 $ c^{(s)}_{n} $ 推廣成 \begin{equation} {n+1 \choose m}=\sum_{i\geq 0}{c^{(s)}_{i}{n-si \choose m-i}}, n\in \mathbb{R}, m\in \mathbb{N}_0 , \label{eqn:gHilton} \end{equation} 要證明這個結果我們須要一些引理：

引理9. 對於符合 $ f(0)=0 $ 的生成函數 $ f(x) $ \begin{equation} f(x)B^s(x)=B(x)-1 \label{eqn:fxBs} \end{equation} 至多只有一個生成函數解。也就是說，如果 $ f(x) $ 是一生成函數且 $ f(0)=0 $, 則至多只有一個生成函數 $ g(x) $ 滿足 $$f(x)g^s(x)=g(x)-1 $$

證明. 若 $ g $ 為(\ref{eqn:fxBs})的一生成函數解，則我們可以用$B-g$除$fB^s-B+1$。而得 $$fB^s-B+1=(B-g)(fB^{s-1}+fgB^{s-2}+\dots +fg^{s-2}B+fg^{s-1}-1)$$ 若 $ B $ 是生成函數，則有 $ B(0)\lt +\infty \Rightarrow f(0)B^i (0)=0,\enspace i\in \mathbb{Z} $, 因為右式的第二個括號在 $ x=0 $ 時等於 $ -1 $ 不等於 $ 0 $, 所以 $ B-g $ 是 $ 0 $ 函數，即 $ B $ 只能等於 $ g $。 $ \Box $

引理10. 若 $$p(x)=1+x,$$ $$q(x)=C^{(s)}(x(1+x)^{-s})=\sum_{i\geq 0}{c^{(s)}_{i}x^i(1+x)^{-is}},$$ 其中 $ C^{(s)} $ 是固定 $ s $ 時$c^{(s)}_{n}$的生成函數。那麼當$f(x)=x(1+x)^{-s}$時， $ p,q $ 都是(\ref{eqn:fxBs})的生成函數解。因此有 $ p $ 恆等於 $ q $, 即 \begin{equation} 1+x=\sum_{i\geq 0}{c^{(s)}_{i}x^i(1+x)^{-is}}. \label{eqn:HIgf} \end{equation}

證明. 自然地 $ p $ 是一生成函數；而 $ q $ 也是一生成函數，因為它是生成函數 $ f(x) $ 的線性組合。$\\$ 我們可以發現：

1. $(x(1+x)^{-s}p^s=x(1+x)^{-s}(1+x)^s=x=p-1)$
2. $(x(1+x)^{-s}q^s=x(1+x)^{-s}(C^{(s)}(x(1+x)^{-s}))^s=C^{(s)}(x(1+x)^{-s})-1=q-1)$

所以 $ p,q $ 都是該方程式的生成函數解。最後由引理9知道至多只有一生成函數解，因此得知 $ p=q $。 $ \Box $

定理11. 對任意的實數 $ n $ 及整數 $ m $, 下列恆等式 \begin{equation} {n+1 \choose m}=\sum_{i\geq 0}{c^{(s)}_{i}{n-si \choose m-i}}, n\in \mathbb{R}, m\in \mathbb{N}_0 \end{equation} 成立。

證明. 將 (\ref{eqn:HIgf}) 兩邊同乘 $ (1+x)^n $, 我們可以得到 $$(1+x)^{n+1}=c^{(s)}_{0} (1+x)^n+c^{(s)}_{1} x(1+x)^{n-s}+\dots +c^{(s)}_{m} x^m(1+x)^{n-ms}+\dots $$ 比較兩邊的 $ x^m $ 項係數就能得到 (\ref{eqn:gHilton})。 $ \Box $

值得注意的是：

• $ s=0 $ $ \Rightarrow $ Pascal定理 $${n+1 \choose m}={n \choose m}+{n \choose m-1}$$
• $ s=1 $ $ \Rightarrow $ 朱世傑定理 $${n+1 \choose m}={n \choose m}+{n-1 \choose m-1}+\dots +{n-m \choose 0}$$
• $ s=2 $ $ \Rightarrow $ Jonah定理

另外一點則是若 $ m\geq n+1 $ 時，該等式依然成立。$\\$ 例：$\\$ $ s=3 $ , $ n=4 $ , $ m=5 $ \begin{eqnarray*} 1&=&{5 \choose 5}=1{4 \choose 5}+1{1 \choose 4}+3{-2 \choose 3}+12{-5 \choose 2}+55{-8 \choose 1}+273{-11 \choose 0}\\ &=&0+0-12+180-440+273=1 \end{eqnarray*} $ s=3 $ , $ n=3 $ , $ m=5 $ \begin{eqnarray*} 0&=&{4 \choose 5}=1{3 \choose 5}+1{0 \choose 4}+3{-3 \choose 3}+12{-6 \choose 2}+55{-9 \choose 1}+273{-12 \choose 0}\\ &=&0+0-30+252-495+273=0 \end{eqnarray*} 註. 推廣的結果(即定理11)當 $ n $ 為非負整數且 $ n-m+1\geq (s-1)m $ 時也可以由Lattice path的方法證明如下：

考慮從 $ (0,0) $ 到 $ (m,n-m+1) $ 的最短路徑數為 $ {n+1 \choose m} $。同時考慮輔助線 $ L:y=(s-1)x $, 則每條路徑都必須通過 $ L $, 所以可以將各路徑利用「第一次」通過 $ L $ 的點來做分割，而第一次是經由 $ (i,(s-1)i) $ 通過 $ L $ 的路徑數有 $ c^{(s)}_{i}{n-si \choose m-i} $, 因為在 $ (i,(s-1)i) $ 之前該路徑不能通過 $ L $ 因而有 $ c^{(s)}_{i} $ 種；在 $ (i,(s-1)i) $ 必須往上走到 $ (i,(s-1)i+1) $ 接著就無任何限制地走到 $ (m,n-m+1) $ 因而有 $ {n-si \choose m-i} $ 種。 而總路徑數等於通過 $ L $ 上各點的路徑數和即得證。

特別感謝

這篇文章是參加中央研究院數學研究所暑期的組合數學專題課程時所撰寫的， 指導老師薛昭雄教授不厭其煩地幫我們修正文章錯誤的地方以及提出各種建議， 往往在百思不解的時候老師拿來的文獻資料都能解開想了好幾天的疑惑， 老師也常常撥出時間和我們討論。因此，在此特別感謝薛老師的教導與指正， 也謝謝中央研究院數學研究所提供學習組合知識以及文章撰寫的機會， 同時也感謝審稿人細心之審查及提供建議，使得本文更加完整。

參考文獻

---本文作者就讀台灣大學數學研究所---