數學傳播

1. 引言

Riordan 矩陣是在 1991 年由 Shapiro、 Getu、 Woan 和 Woodson 所提出, Shapiro 為了紀念他的老師 Riordan 而將這類矩陣命名為 Riordan 矩陣。 因為Riordan矩陣的原理很簡單, 但在組合、 計數等問題上有很多的應用, 因此最近在國外是一個很熱門的主題。

Riordan 矩陣的應用方面, Sprugnoli 利用 Riordan 矩陣找出多種組合和式的生成函數, 由生成函數就能得到組合和式的封閉表達式或漸進值; Sprugnoli 和 Merlini 也利用 Riordan 矩陣給出了 Sun 提出的一個組合恆等式證明的另解。 應用之外, 因為 Riordan 矩陣在矩陣乘法的作用下形成群, 稱做 Riordan 群, 也有人研究 Riordan 群的代數結構, He、 Hsu 和 Shiue 證明 Riordan 群和 Sheffer 群同構並將 Riordan 矩陣推廣到更高維度; Jean-Louis 和 Nkwanta 研究了一些代數性質, 並給出 Riordan 群的中心化子 (centralizer) 和穩定化子 (stabilizer) 等等。 (更多關於 Riordan 矩陣的研究可以參閱 Sprugnoli )

本文第二節將介紹 Riordan 矩陣的定義與基本定理, 並驗證Riordan群; 第三節將基本定理做應用, 證明一些恆等式。

2. Riordan 矩陣

定義1.(Shapiro et al. ) 給定兩個冪級數 (power series) $g(x)=1+\sum\limits_{n=1}^\infty g_nx^n$, $f(x)=\sum\limits_{n=1}^\infty f_nx^n$。 考慮一個無限矩陣 $M=\left(m_{ni}\right)_{n, i\geq 0}$, 若 $M$ 之第 $i$ 行 (column) $(m_{0i}, m_{1i}, m_{2i}, \cdots)$ 的生成函數為 $C_i(x)=g(x)[f(x)]^i$ 即 $\sum\limits_{n\geq 0}m_{ni}x^n=g(x)[f(x)]^i$, 則我們稱這種矩陣為 Riondan 矩陣並將其記為 $M=(g(x), f(x))$。}

例1. 令 $g(x)=\frac{1}{1-x}$, $f(x)=\frac{x}{1-x}$, 可以寫出 $P=(g(x), f(x))=\left(\frac{1}{1-x}, \frac{x}{1-x}\right)$。 我們有 $$ C_i(x)=\frac{1}{1-x}\cdot\left(\frac{x}{1-x}\right)^i=\sum_{k\geq 0}\binom{i}{k}x^k\mbox{, } $$ $$ P=\left[\begin{array}{cccccc} 1\\ 1 & 1\\ 1 & 2& 1\\ 1 & 3& 3 & 1\\ 1 & 4& 6 & 4& 1\\ & &\vdots && &\ddots\\ \end{array}\right] =\left[\binom{n}{k}\right]_{n, k\geq 0}\mbox{, 為 Pascal 矩陣。} $$ 相反地, Pascal矩陣可由$(g(x), f(x))=\left(\dfrac{1}{1-x}, \dfrac{x}{1-x}\right)$ 所生成。 設 $$ P=\left[\binom{n}{k}\right]_{n\geq 0} =\left[\begin{array}{cccccc} 1\\ 1 & 1\\ 1 & 2& 1\\ 1 & 3& 3 & 1\\ 1 & 4& 6 & 4& 1\\ & &\vdots && &\ddots\\ \end{array}\right]\mbox{。} $$ 在這邊很明顯的取$g(x)=1+1\cdot x+1\cdot x^2+1\cdot x^3+\cdots =\dfrac{1}{1-x}$, 而我們已經知道如果$A(x)=a_0+a_1x+a_2x^2+\cdots$, 則 $$ A(x)\frac{1}{1-x} =a_0+\left(a_0+a_1\right)x+\left(a_0+a_1+a_2\right)x^2+\cdots =\sum_{n=0}^{\infty}\left(\sum_{i=0}^na_i\right)x^n\mbox{, } $$故 $$ \sum_{n=0}^ka_{ni}=a_{k+1, i+1}\mbox{, } $$ 或可由二項式$\displaystyle\binom{k}{k}+\binom{k+1}{k}+\binom{k+2}{k}+\cdots+\binom{n}{k}=\binom{n+1}{k+1}$得到此結果。 另外, 行向量寫成 $$ C_k(x)\frac{x}{1-x}=C_{k+1}(x),\quad C_i(x)=\frac{1}{1-x}\cdot\left(\frac{x}{1-x}\right)^i\mbox{。}\tag*{$\Box$} $$

例2. \begin{align*} 令g(x)=\dfrac{1-\sqrt{1-4x^2}}{2x^2}, f(x)=\dfrac{1-\sqrt{1-4x^2}}{2x}。計算可得\label{preThm} \end{align*} \begin{align*} [x^k]\left(1-4x\right)^{\frac{1}{2}} & =[x^k]\sum_{n\geq 0}\binom{\frac{1}{2}}{n}(-4x)^n\\ & =[x^k]\sum_{n\geq 0}\frac{\frac{1}{2}(-\frac{1}{2})(-\frac{3}{2})\cdots(\frac{1}{2}-n+1)}{n!}(-1)^n2^{2n}x^n\\ & =[x^k]\sum_{n\geq 0}\frac{(-1)\cdot 1\cdot 3\cdots (2n-3)}{n!}2^nx^n\\ & =[x^k]\sum_{n\geq 0}\frac{(-1)(2n-2)!}{2^{n-1}(n-1)!n!}2^nx^n\\ & =[x^k]\sum_{n\geq 0}\frac{(-2)}{n}\cdot\frac{(2n-2)!}{(n-1)!(n-1)!}x^n\\ & =-\frac{2}{k}\binom{2k-2}{k-1}\mbox{。}\\[10pt] g(x)&=\frac{1}{2x^2}\Bigg(1+\sum\limits_{\substack{n\geq 1 \\ n\mbox{是偶數}}} \frac{2}{n}\binom{2n-2}{n-1}x^n\Bigg)=1+x^2+2x^4+5x^6+\cdots\mbox{, } \\[7pt] g(x)f(x)&=\frac{\left(1-\sqrt{1-4x^2}\right)^2}{4x^3}=\frac{1-2x^2-\sqrt{1-4x^2}}{2x^3}=x+2x^3+5x^5+\cdots\mbox{, } \\[7pt] g(x)[f(x)]^i&=\frac{1-\sqrt{1-4x^2}}{2x^2}\cdot\left(\frac{1-\sqrt{1-4x^2}}{2x}\right)^i=\frac{1}{x} \cdot\left(\frac{1-\sqrt{1-4x^2}}{2x}\right)^{i+1}\mbox{。}\\[10pt] & M=(g(x), f(x)) =\left[\begin{array}{ccccccc} 1\\ 0 & 1\\ 1 & 0& 1\\ 0 & 2& 0 & 1\\ 2 & 0& 3 & 0& 1\\ 0 & 5& 0 & 4& 0&1\\ & &\vdots && & &\ddots\\ \end{array}\right]\mbox{。}\tag*{$\Box$} \end{align*}

現在在 Riordan 矩陣 $M=(m_{ni})=(g(x), f(x))$ 右方乘上一行向量 $\left(a_0, a_1, a_2, \cdots\right)^T$, 如下 $$ (g(x), f(x))\left[\begin{array}{c} a_0\\ a_1\\ a_2\\ a_3\\ \vdots\\ \end{array}\right] =\left[\begin{array}{c} b_0\\ b_1\\ b_2\\ b_3\\ \vdots\\ \end{array}\right]\mbox{。} $$ 假設 $\{a_n\}_{n\geq 0}$ 的生成函數為 $A(x)$, 所得行向量形成的數列 $\{b_n\}_{n\geq 0}$ 的生成函數記為 $B(x)$。 注意到 $$ B(x)=\sum_{n\geq 0}b_nx^n =\sum_{n\geq 0}\left(\sum_{i\geq 0}m_{ni}a_i\right)x^n =\sum_{i\geq 0}a_i\sum_{n\geq 0}m_{ni}x^n\mbox{, } $$ 其中 $\{m_{ni}\}_{n\geq 0}$ 為 $M=(g(x), f(x))$ 的第 $i$ 個行向量, 所以 $$ B(x)=\sum_{i\geq 0}a_ig(x)[f(x)]^i =g(x)\sum_{i\geq 0}a_i[f(x)]^i =g(x)A(f(x))\mbox{。} $$ 即$\{b_n\}_{n\geq 0}$ 的生成函數 $B(x)$ 和 $\{a_n\}_{n\geq 0}$ 的生成函數 $A(x)$, 與 $g(x)$、 $f(x)$ 有如下關係 $$ g(x)A(f(x))=B(x)\mbox{。} $$

上述結果將 Riordan 矩陣與生成函數相乘連繫在一起, Shapiro et al. 將這種連繫記作 $$ (g(x), f(x))*A(x):=g(x)A(f(x))\mbox{。} $$ 並稱其為 Riordan 矩陣基本定理。

定理1. (Riordan 矩陣基本定理) $M=(g(x), f(x))$ 是一個 Riordan 矩陣, $A(x)$ 是一個生成函數, $$ (g(x), f(x))*A(x):=g(x)A(f(x))\mbox{。} $$

我們知道 Riordan 矩陣與一行向量相乘的結果, 那麼兩個 Riordan 矩陣相乘是否仍為一個Riordan矩陣。 利用定理1, 可以證明在矩陣乘法作用下 Riordan 矩陣的集合是一個群, 所以接下來我們逐項檢驗形成群的條件。 矩陣乘法顯然滿足結合律。

(i) 封閉性 讓$(g(x), f(x)), (h(x), l(x))$ 為兩個 Riordan 矩陣, $(h(x),\ l(x))$ 第 $i$ 個行向量為 $h(x)[l(x)]^i$, 代入定理1 中 $A(x)$, 可以得到 $$ (g(x), f(x))*(h(x), l(x))=(g(x)h(f(x)), l(f(x)))\mbox{。} $$

(ii) 單位元存在 單位元即矩陣單位元 $I=(1, x)$。

(iii) 反元素存在 $$ (g(x), f(x))^{-1}=\left(\frac{1}{g(\overline{f}(x))}, \overline{f}(x)\right), $$ 其中$\bar{f}(x)$ 為 $f(x)$ 的反函數, 即 $$ f(\overline{f}(x))=\overline{f}(f(x))=x\mbox{。} $$ 令 $f(x)=x+f_2x^2+f_3x^3+\cdots$, 則保證存在唯一的 $\overline{f}(x)$。 $$ (g(x), f(x))*\left(\frac{1}{g(\overline{f}(x))}, \overline{f}(x)\right) =\left(g(x)\frac{1}{g(\overline{f}(f(x)))}, \overline{f}(f(x)))\right) =(1, x)=I\mbox{, } $$ $$ \left(\frac{1}{g(\overline{f}(x))}, \overline{f}(x)\right)*(g(x), f(x)) =\left(\frac{1}{g(\overline{f}(x))}g(\overline{f}(x)), f(\overline{f}(x))\right) =(1, x)=I\mbox{。} $$

例3. 令$g(x)=\dfrac{1}{1-2x}$, $f(x)=\dfrac{x}{1-2x}$, $A(x)=\dfrac{1}{1-x}$。 \begin{align*} (g(x), f(x))*A(x) & =g(x)A(f(x))\\ & =\frac{1}{1-2x}\cdot\frac{1}{1-\frac{x}{1-2x}}\\ & =\frac{1}{1-3x}\\ & =\sum_{n\geq 0}3^nx^n\mbox{, } \end{align*} $$ \left[\begin{array}{cccccc} 1\\ 2 & 1\\ 4 & 4& 1\\ 8 & 12 & 6& 1\\ 16 & 32 & 24 & 8& 1\\ &&\vdots &&&\ddots\\ \end{array}\right] \left[\begin{array}{c} 1\\ 1\\ 1\\ 1\\ 1\\ \vdots\\ \end{array}\right] =\left[\begin{array}{c} 1\\ 3\\ 9\\ 27\\ 81\\ \vdots\\ \end{array}\right] =\left[\begin{array}{c} 3^0\\ 3^1\\ 3^2\\ 3^3\\ 3^4\\ \vdots\\ \end{array}\right]\mbox{。}\tag*{$\Box$} $$

例4. 將 Pascal 矩陣斜向相加, 如下圖 此操作相當於將包含第一行之後所有行都補上一個$0$項, 再將列(row)加總, 如下 $$ \left[\begin{array}{ccccc} 1\\ 1\\ 1 & 1\\ 1 & 2\\ 1 & 3& 1\\ 1 & 4& 3\\ 1 & 5& 6 & 1\\ &\vdots&& &\ddots\\ \end{array}\right] \left[\begin{array}{c} 1\\ 1\\ 1\\ 1\\ 1\\ 1\\ 1\\ \vdots\\ \end{array}\right] =\left[\begin{array}{c} 1\\ 1\\ 2\\ 3\\ 5\\ 8\\ 13\\ \vdots\\ \end{array}\right]\mbox{, } $$ 這邊將行補上一個 $0$ 項表示對應的數列往後移動一項, 所以可以從原來 Pascal 矩陣的生成 $(\dfrac{1}{1-x}, \dfrac{x}{1-x})$ 中, 第二個函數乘上 $x$ 得出。而 $$ (\frac{1}{1-x}, \frac{x^2}{1-x})*\frac{1}{1-x} =\frac{1}{1-x}\cdot\frac{1}{1-\frac{x^2}{1-x}} =\frac{1}{1-x-x^2}\mbox{, } $$ 所得函數恰好是費波那契數列 (Fibonacci numbers) 的生成函數。 $\tag*{$\Box$}$

例5. Catalan 數 $C_n=\dfrac{1}{n+1}\displaystyle\binom{2n}{n}$ 的生成函數為 $$ C(x)=1+x[C(x)]^2=\frac{1-\sqrt{1-4x}}{2x}\mbox{, } $$ 由例2知 $$ L=\left[\begin{array}{cccccccc} 1\\ 0 & 1\\ 1 & 0& 1\\ 0 & 2& 0& 1\\ 2 & 0& 3& 0 & 1\\ 0 & 5& 0& 4 & 0&1\\ 5 & 0& 9& 0 & 5&0& 1\\ & &&\vdots &&&&\ddots\\ \end{array}\right] =\left(C\left(x^2\right),\ xC\left(x^2\right)\right)\mbox{。} $$

問題是要如何找出構成已知矩陣的生成函數, 那該生成函數又是唯一的嗎? 如果有生成函數, 找出數列是容易的, 反之, 則困難。在這個例子中我們可以觀察到第 $0$ 行為 $\{1, 1, 2, 5, 14$, $42, \ldots\}$ 為 Catalan 數, 並有一個 $0$ 在相鄰兩項之間, 因此可得 $g(x)=\sum\limits_{n=0}^\infty C_nx^{2n}$。 比較 $g(x)$ 與 $g(x)f(x)$ 的係數得到 $f(x)=xC\left(x^2\right)$, 再計算 $g(x)[f(x)]^2$ 以驗證下一行。

接下來要找出$L$的反矩陣, 已知 $C(x)=1+x[C(x)]^2$。 因為 \begin{align*} f(x) & =xC\left(x^2\right)\\ & =x\left[1+x^2\left[C\left(x^2\right)\right]^2\right]\\ & =x+x\cdot \left[xC\left(x^2\right)\right]^2, \end{align*} 又有 $$ f(x)=x+x\cdot (f(x))^2\mbox{。} $$ 將 $x$ 代換為 $\overline{f}(x)$, 得到 \begin{align*} x & =\overline{f}(x)+\overline{f}(x)\cdot x^2\\ & =\overline{f}(x)\left(1+x^2\right)\mbox{, }\ \end{align*} \begin{align*} \overline{f}(x) & =\frac{x}{1+x^2}\mbox{, }\\ g(\overline{f}(x)) & =C\left((\overline{f}(x))^2\right)\\ & =C\left(\frac{x^2}{\left(1+x^2\right)^2}\right)\\ & =1+x^2\mbox{。} \end{align*} 因此可得 $$ L^{-1}=\left(\frac{1}{g(\overline{f}(x))}, \overline{f}(x)\right) \!=\!\left(\frac{1}{1+x^2}, \frac{x}{1+x^2}\right) \!=\!\left[\begin{array}{cccccccc} 1\\ 0& 1\\ -1& 0& 1\\ 0&-2&0& 1\\ 1&0&-3&0& 1\\ 0& 3& 0&-4& 0& 1\\ -1 & 0&6& 0& -5&0&1\\ &&&\vdots&&&&\ddots\\ \end{array}\right]\mbox{。} $$ 如果忽略負號, 可以發現列總和會形成費波那契數。這說明了Catalan數與費式數列特殊的互逆關係。 $\tag*{$\Box$}$

例6. 中央二項式係數$\{\binom{2n}{n}\}_{n\geq 0}=\{1, 2, 6, 20, 70, 252, \cdots\}$的生成函數為 \begin{equation} \sum_{n\geq 0}\binom{2n}{n}x^n=\frac{1}{\sqrt{1-4x}}\mbox{。} \end{equation} 而另一版本的Pascal三角形可記為 $$ B\!=\!\left[\begin{array}{ccccccc} 1\\ 0&1\\ 2&0&1\\ 0&3&0& 1\\ 6&0&4&0&1\\ 0&10&0&5&0&1\\ &&\vdots&&&&\ddots\\ \end{array}\right] \!=\!\left(\frac{1}{\sqrt{1-4x^2}}, \frac{1-\sqrt{1-4x^2}}{2x}\right)\mbox{。} $$ 知道 $B$ 各項元素的關係後, 就可以找出 $f(x)$。 觀察 $$ b_{n+1, j}=b_{n, j-1}+b_{n, j+1} \qquad j\geq 1\mbox{。} $$ 因此得到 $$ C_k(x)=xC_{k-1}(x)+xC_{k+1}(x)\mbox{, } $$ 也就是 $$ g(x)[f(x)]^k=xg(x)[f(x)]^{k-1}+xg(x)[f(x)]^{k+1}\mbox{, } $$ 或寫成 $$ f(x)=x+x[f(x)]^2\mbox{。} $$ 為一 $f(x)$ 的二次多項式, 解得 $$ f(x)=\frac{1-\sqrt{1-4x^2}}{2x}\mbox{。} $$ 經由 $f(x)=x(1+[f(x)]^2)$, 將 $x$ 代換為 $\overline{f}(x)$, 可得 $x=\overline{f}(x)(1+x^2)$, $$ \overline{f}(x)=\frac{x}{1+x^2}\mbox{, } $$ 以及 \begin{align*} \frac{1}{g(\overline{f}(x))} & =\sqrt{1-4\left(\frac{x}{1+x^2}\right)^2}\\ & =\frac{1-x^2}{1+x^2}\\ & =\left(1-x^2\right)\left(1+x^2\right)^{-1}\\ & =1-2x^2+2x^4-\cdots\mbox{。} \end{align*} 可以利用 Riordan 矩陣定義所得的反矩陣求出 \begin{align*} B^{-1}&=\left(\frac{1}{g(\overline{f}(x))}, \overline{f}(x)\right) =\left(\frac{1-x^2}{1+x^2}, \frac{x}{1+x^2}\right)\\ &=\left[\begin{array}{cccccccc} 1\\ 0 & 1\\ -2 & 0& 1\\ 0 & -3& 0& 1\\ 2 & 0& -4&0& 1\\ 0 & 5& 0& -5&0&1\\ -2 & 0& 9&0& -6&0& 1\\ &&&\vdots&&&&\ddots\\ \end{array}\right]\mbox{。} \end{align*}

例7. 先前例子是以普通生成函數 (ordinary generating function) 所形成的數列做為矩陣的行向量, 在此我們也可以用指數生成函數 (exponential generating function) 形成的數列做為 Riordan 矩陣的行向量。

定義第 $i$ 個行向量數列的指數型生成函數為 $$ g(x)\frac{(f(x))^k}{k!} \qquad k=0, 1, 2, 3,\cdots\mbox{。} $$ 例如 Pascal 矩陣 $$ P=\left[\begin{array}{cccccc} 1\\ 1& 1\\ 1& 2& 1\\ 1& 3& 3& 1\\ 1& 4& 6& 4& 1\\ &&\vdots &&&\ddots\\ \end{array}\right] =(e^x, x)\mbox{, } $$ 很容易可以驗證 $$ g(x)=1+1\cdot x+1\cdot \frac{x^2}{2!}+1\cdot \frac{x^3}{3!}+\cdots=e^x\mbox{, } $$ 以及 \begin{align*} e^x\cdot \frac{x^k}{k!}& =\sum_{n\geq 0}\frac{x^{n+k}}{n!k!}=\sum_{n\geq 0}\binom{n+k}{k}\frac{x^{n+k}}{(n+k)!}\\ & =\sum_{n\geq k}\binom{n}{k}\frac{x^n}{n!}\mbox{。}\tag*{$\Box$} \end{align*}

以下我們提供幾個指數型生成函數造出的 Riordan 矩陣的例子。

例8. 第一類 Stirling 數 $s(n,k)$ (Stirling numbers of the first kind) 是定義為將對稱群$S_n$ (symmetric group)中的置換做圈分解(cycle decomposition)時, 恰可分成$k$個互斥圈(disjoint cycle)乘積的置換的個數。 \begin{align*} \sum\limits_{n\geq 0}s(n,k)\frac{x^n}{n!}&=\frac{1}{k!}\left(\ln\frac{1}{1-x}\right)^k\mbox{, } \\[5pt] \ln\frac{1}{1-x} & =\int\frac{1}{1-x}dx=\int\left(1+x+x^2+\cdots\right)dx\\ & =x+\frac{x^2}{2}+\frac{x^3}{3}+\cdots +\frac{x^n}{n}+\cdots\\ & =x+\frac{x^2}{2}+\frac{2!x^3}{3!}+\cdots+\frac{(n-1)!x^n}{n!}+\cdots\\ & =\sum\limits_{n\geq 1}(n-1)!\frac{x^n}{n!}\mbox{。} \\[5pt] \left(1, \ln\frac{1}{1-x}\right) &=\left[\begin{array}{ccccccc} 1\\ 0 & 1\\ 0 & 1& 1\\ 0 & 2& 3& 1\\ 0 & 6& 11& 6& 1\\ 0 & 24& 52 & 35& 10& 1\\ &&&\vdots&&&\ddots\\ \end{array}\right] \mbox{。} \end{align*} 第二類 Stirling 數 $S(n,k)$ (Stirling numbers of the second kind) 是定義為將含有 $n$ 個相異元素的集合, 分割成 $k$ 個互不相交的子集合的方法數。 $$ \sum\limits_{n\geq 0}S(n,k)\frac{x^n}{n!}=\frac{1}{k!}\left(e^x-1\right)^k\mbox{, } $$ $$ \left(1, e^x-1\right) =\left[\begin{array}{ccccccc} 1\\ 0 & 1\\ 0 & 1& 1\\ 0 & 1& 3 & 1\\ 0 & 1& 7 & 6& 1\\ 0 & 1& 15& 25&10& 1\\ &&&\vdots&&&\ddots\\ \end{array}\right] \mbox{。} $$ Bell數是計算有多少種方法去分割一個集合, 也就是$B_n=\sum\limits_{k\geq 0}S(n, k)$。 $$ \left[\begin{array}{ccccccc} 1\\ 0 & 1\\ 0 & 1& 1\\ 0 & 1&3& 1\\ 0 & 1&7& 6& 1\\ 0 & 1&15& 25&10&1\\ &&&\vdots&&&\ddots\\ \end{array}\right] \left[\begin{array}{c} 1\\ 1\\ 1\\ 1\\ 1\\ 1\\ \vdots\\ \end{array}\right] =\left[\begin{array}{c} 1\\ 1\\ 2\\ 5\\ 15\\ 52\\ \vdots\\ \end{array}\right]\mbox{, } $$ $$ \left(1, e^x-1\right)*e^x=1\cdot e^{e^x-1}=B(x)\mbox{。} $$ 可以用 Riordan 矩陣基本定理求出 Bell 數的指數生成函數。 $\tag*{$\Box$}$

3. Riordan 矩陣基本定理的應用

在本節中, 我們將利用基本定理來驗證一些組合恆等式。 一般證明組合恆等式常用生成函數方法及 The Snake Oil Method , 而 Riordan 矩陣給了另一種不同的方法。 在這裡我們舉例如下： 例9. $\sum\limits_{k=0}^n\binom{n}{k}2^k=3^n$ \begin{align*} n=0:\ & \binom{0}{0}\cdot 2^0=1\\ n=1:\ & \binom{1}{0}\cdot 2^0+\binom{1}{1}\cdot 2^1=3\\ n=2:\ & \binom{2}{0}\cdot 2^0+\binom{2}{1}\cdot 2^1+\binom{2}{2}\cdot 2^2=9\\ n=3:\ & \binom{3}{0}\cdot 2^0+\binom{3}{1}\cdot 2^1+\binom{3}{2}\cdot 2^2+\binom{3}{3}\cdot 2^3=27\\ \vdots \end{align*} $$ \left[\begin{array}{cccccc} 1\\ 1&1\\ 1&2&1\\ 1&3&3&1\\ 1&4&6&4& 1\\ &&\vdots&&&\ddots\\ \end{array}\right] \left[\begin{array}{c} 2^0\\ 2^1\\ 2^2\\ 2^3\\ 2^4\\ \vdots \end{array}\right] =\left[\begin{array}{c} 3^0\\ 3^1\\ 3^2\\ 3^3\\ 3^4\\ \vdots \end{array}\right] $$ \begin{align*} \left(\frac{1}{1-x}, \frac{x}{1-x}\right)*\frac{1}{1-2x} & =\frac{1}{1-x}\cdot\frac{1}{1-2\frac{x}{1-x}}\\ & =\frac{1}{1-x-2x}\\ & =\frac{1}{1-3x}\\ & =\sum_{n\geq 0}3^nx^n\tag*{$\Box$} \end{align*}

例10. $\sum\limits_{k=0}^n\binom{n}{k}k=n2^{n-1}$ \begin{align*} n=0:\ & \binom{0}{0}\cdot 0=0\\ n=1:\ & \binom{1}{0}\cdot 0+\binom{1}{1}\cdot 1=1\\ n=2:\ & \binom{2}{0}\cdot 0+\binom{2}{1}\cdot 1+\binom{2}{2}\cdot 2=4\\ n=3:\ & \binom{3}{0}\cdot 0+\binom{3}{1}\cdot 1+\binom{3}{2}\cdot 2+\binom{3}{3}\cdot 3=12\\ \vdots \end{align*} $$ \left[\begin{array}{cccccc} 1\\ 1 & 1\\ 1 & 2&1\\ 1 & 3&3&1\\ 1 & 4&6&4& 1\\ &&\vdots&&&\ddots\\ \end{array}\right] \left[\begin{array}{c} 0\\ 1\\ 2\\ 3\\ 4\\ \vdots \end{array}\right] =\left[\begin{array}{c} 0\\ 1\cdot2^0\\ 2\cdot2^1\\ 3\cdot2^2\\ 4\cdot2^3\\ \vdots \end{array}\right] $$ \begin{align*} \left(\frac{1}{1-x}, \frac{x}{1-x}\right)*\frac{x}{(1-x)^2} & =\frac{1}{1-x}\cdot\frac{\frac{x}{1-x}}{(1-\frac{x}{1-x})^2}\\ & =\frac{x}{(1-2x)^2}\\ & =x\sum_{n\geq 0}\binom{2+n-1}{n}(2x)^n\\ & =\sum_{n\geq 0}(n+1)2^nx^{n+1}\\ & =\sum_{n\geq 1}n2^{n-1}x^n\tag*{$\Box$} \end{align*}

例11. $\sum\limits_{k\geq 0}\binom{n-k}{k}6^k=\frac{1}{5}\left(3^{n+1}-(-2)^{n+1}\right)$ $$ \left[\begin{array}{ccccc} 1\\ 1\\ 1& 1\\ 1& 2\\ 1& 3&1\\ 1& 4&3\\ 1& 5&6&1\\ &\vdots&& &\ddots\\ \end{array}\right] \left[\begin{array}{c} 6^0\\ 6^1\\ 6^2\\ 6^3\\ 6^4\\ 6^5\\ 6^6\\ \vdots \end{array}\right] =\left[\begin{array}{c} 1\\ 1\\ 7\\ 13\\ 55\\ 135\\ 463\\ \vdots \end{array}\right] $$ 觀察上方矩陣行向量為 Pascal 矩陣, 但行向量卻相隔兩列, 先前的例子已說明該矩陣可寫成 $(\dfrac{1}{1-x}, \dfrac{x^2}{1-x})$, 而右方行向量形成的數列的生成函數可寫成 $\dfrac{1}{1-6x}$。 經由定理1, \begin{align*} \left(\frac{1}{1-x}, \frac{x^2}{1-x}\right)*\frac{1}{1-6x} & =\frac{1}{1-x}\cdot\frac{1}{1-6\cdot\frac{x^2}{1-x}}\\ & =\frac{1}{1-x-6x^2}\\ & =\frac{1}{(1-3x)(1+2x)}\\ & =\frac{1}{5}\left(\frac{3}{1-3x}+\frac{2}{1+2x}\right)\\ & =\sum\limits_{n\geq 0}\frac{1}{5}(3^{n+1}-(-2)^{n+1})x^n\tag*{$\Box$} \end{align*}

例12. $\sum\limits_{k=0}^n(-1)^{n-k}2^{2k}\binom{n+k}{2k}=2n+1$ $$ \sum\limits_{k=0}^n(-1)^{n-k}2^{2k}\binom{n+k}{2k}=\sum\limits_{k=0}^n(-1)^{n-k}\binom{n+k}{2k}(4^k) $$ $$ \left[\begin{array}{cccccc} 1\\ -1 & 1\\ 1 & -3 & 1\\ -1 & 6&-5& 1\\ 1 & -10& 15 & -7 & 1\\ &&\vdots&&&\ddots\\ \end{array}\right] \left[\begin{array}{c} 4^0\\ 4^1\\ 4^2\\ 4^3\\ 4^4\\ \vdots \end{array}\right] =\left[\begin{array}{c} 1\\ 3\\ 5\\ 7\\ 9\\ \vdots \end{array}\right] $$ 觀察上方矩陣若忽略負號, 則行向量為 Pascal 矩陣的第 $0, 2, 4,\ldots$ 行, 該矩陣可寫成
$\left(\dfrac{1}{1+x}, \dfrac{x}{(1+x)^2}\right)$, 而右方行向量形成的數列的生成函數可寫成 $\dfrac{1}{1-4x}$。 經由定理1, \begin{align*} \left(\frac{1}{1+x}, \frac{x}{(1+x)^2}\right)*\frac{1}{1-4x} & =\frac{1}{1+x}\cdot\frac{1}{1-4\cdot\frac{x}{(1+x)^2}} =\frac{1+x}{(1-x)^2}\\ & =(1+x)\sum\limits_{n\geq 0}\binom{2+n-1}{n}x^n=(1+x)\sum\limits_{n\geq 0}(n+1)x^n\\ & =\sum\limits_{n\geq 0}(n+1)x^n+\sum\limits_{n\geq 1}nx^n=\sum\limits_{n\geq 0}(2n+1)x^n\tag*{$\Box$} \end{align*}

例13. Catalan 數 $C_n=\dfrac{1}{n+1}\binom{2n}{n}$ $$ (C^2(x), xC^2(x))=\left[\begin{array}{cccccccc} 1\\ 2 & 1\\ 5 & 4& 1\\ 14 & 14& 6& 1\\ 42 & 48& 27&8& 1\\ 132& 165& 110& 44&10& 1\\ 429& 572& 429& 208&65&12&1\\ &&&\vdots&&&&\ddots\\ \end{array}\right] $$ 經由觀察, 發現在同一列連續三項若各別乘上 $1, 2, 1$ 可以得到中間項下一列的數。 也就是 $$ a_{n+1, i}=1\cdot a_{n, i-1}+2\cdot a_{n, i}+1\cdot a_{n, i+1}\mbox{。} $$ 矩陣乘上一向量 $(\underbrace{0, \cdots, 0}_k, 1, 2, 1, 0, \cdots)^T$ 代表從第 $k$ 行的元素開始各別乘上 $1, 2, 1$, 又此向量形成的數列的生成函數可寫做 $x^k(1+x)^2$, 矩陣與此向量作用表示成 \begin{align*} (C^2(x), xC^2(x))*x^k(1+x)^2 & =C^2(x)\cdot \left(xC^2(x)\right)^k\left(1+xC^2(x)\right)^2\\ & =C^2(x)\left(xC^2(x)\right)^kC^2(x)\\ & =x^kC^{2k+4}(x)\\ & =x^{(k+1)-1}C^{2(k+1)+2}(x)\\ & =\frac{1}{x}\cdot x^{(k+1)}C^{2(k+1)+2}(x) \end{align*} 恰好是第 $k+1$行的生成函數, 但數列卻往前移動了一項, 與原矩陣做對應即是得到中間項下一列的數。 讓我們舉 $n=4$, $k=1$ 為例： 我們知道 $(1, 2, 1)$ 是二次二項式展開係數, 那麼三次 $(1, 3, 3, 1)$、 四次 $(1, 4, 6, 4, 1)$ 及以上呢? 作用在這個矩陣上會不會也有類似結果? 考慮 \begin{align*} (C^2(x), xC^2(x))*(1+x)^m & =C^2(x)\cdot\left(1+xC^2(x)\right)^m\\ & =C^2(x)C^m(x)=C^{m+2}(x)\mbox{, } \end{align*} 其中 $m$ 必須是偶數。 令 $m=2k$, $C^{m+2}(x)=C^{2k+2}(x)$ 恰好是第 $k$ 行 (最中間項) 的生成函數, 但數列往前移動 $k$ 項。 讓我們舉 $n=3$, $m=6$ 為例：

致謝

感謝中研院數學所暑期組合數學及圖論專題計畫的資助, 讓筆者有機會在暑假跟隨美國內華達大學數學系薛昭雄教授做暑期研究, 也由衷感謝薛昭雄教授的指導、 廖信傑學長修稿與李沛宸同學的程式教學, 因為薛教授的鼓勵及鉅細靡遺建議本文才能完稿。

參考文獻

---本文作者就讀國立交通大學---