數學傳播

一、前言

當 $n=1, 2,\ldots$ 時, 我們定義降階乘函數 $\left[ x\right] _n=x\left( x-1\right) \cdots \left( x-n+1\right) $。 特別地, 我們定義 $\left[ x\right] _0=1$。 第一型與第二型的 Stirling 數分別是以冪次函數基底 ${x^k}_{k\ge 0}$ 來表示 $[x]_n$, 與用降階乘函數基底 ${[x]_k}_{k\ge 0}$ 來表示 $x^n$ 所涉及的係數, 是由 James Stirling 在 1780 年定義的。 現在, 我們具體地給出第一型 Stirling 數的定義: $$\left[ x\right] _n=\displaystyle \sum_{k\geq 0}S_1\left( n,k\right) x^k 。 $$ 而第一型 Stirling 數, 還有另一層含義: $|S_1(n,k)|$ 是「將 $n$ 個元素, 先分成 $k$ 個非空組後, 再將每一組做成一個環狀排列」的方法數。 $|S_1(n,k)|$ 也經常被寫成 $\left[ n\atop k \right]$, 因為 $\left[ {n+1}\atop k \right] =n \left[ {n}\atop k \right]+ \left[ {n}\atop {k-1} \right]$ 類似於二項式係數等式。

本文的主要目的是將 Comtet 的同餘關係式 $$S_1\left( p,n\right) \equiv 0 \ \pmod p ,\ 2\leq n\leq p-1,$$ 延伸至模 $p$ 的更高次方 (請參考定理 2 )。 接著再推廣至廣義的第一型 Stirling 數之同餘關係式 (請參考第 3 節)。

最後, 我們將簡單介紹一些特殊的第一型 Stirling 數, 並利用主要定理, 對特殊的第一型 Stirling 數的同餘關係進行探討。

二、第一型 Stirling 數的同餘關係式

從本節開始, 以下的 $p$ 皆為奇質數。我們直接引用下面的遞迴關係式, 因為網路上可以輕易找到證明, 就不浪費篇幅了。

性質 1. $S_1\left( n,k\right) =S_1\left( n-1,k-1\right) -(n-1)S_1\left( n-1,k \right) $。

已知當 $2\leq n\leq p-1$, $S_1\left( p,n\right) \equiv 0 \pmod p$ (請參考 ), 再利用性質 1, 我們有 $$S_1 \left( p+1,n\right) = S_1\left( p,n-1\right) -pS_1\left( p,n\right) \equiv S_1\left( p,n-1\right) \quad\pmod {p^2}\hbox{。}$$ 我們得到一引理如下:

引理 1. 當 $2\leq n\leq p-1$, $$S_1\left( p,n-1\right) \equiv S_1\left( p+1,n\right) \quad\pmod {p^2}。$$

更一般地, 我們可得

定理 2. \begin{align*} S_1\left( p,n\!-\!(k\!-\!1)\right) \equiv \left\{\begin{array}{ll}\displaystyle \sum_{i=0}^{k-2}p^{i}S_1\left( p+1,n+i-(k-2)\right) \quad\pmod {p^k} & ,\ 2 \leq k \leq n+1;\\ 0 \quad \pmod {p} & ,\ k=1 \hbox{。} \end{array}\right. \end{align*} 其中 $2 \leq n \leq p-1$。

證明: 令 $2 \leq n \leq p-1$, 我們將對 $k$ 做數學歸納法。當 $k=2$ 時, 由引理 1 可知此命題為真。
假設當 $2\leq k=j\leq n$ , 此命題為真。亦即 \begin{align*} S_1\left( p,n-(j-1)\right) \equiv \sum_{l=0}^{j-2}p^{l}S_1\left( p+1,n+l-(j-2)\right) \quad\pmod {p^j}\hbox{。} \end{align*} 則當 $k=j+1$ 時, \begin{align*} S_1\left( p,n-j\right) & = S_1\left( p+1,n-j+1\right) +pS_1\left( p,n-(j-1)\right) \\ & \equiv S_1\left( p+1,n-j+1\right) +\sum_{l=0}^{j-2}p^{l+1}S_1\left( p+1,n+l-(j-2)\right) \\ & \equiv S_1\left( p+1,n-j+1\right) +\sum_{i=1}^{j-1}p^{i}S_1\left( p+1,n+i-(j-1)\right) \\ & \equiv \displaystyle \sum_{i=0}^{j-1}p^i S_1\left( p+1,n+i-(j-1)\right) \quad\pmod {p^{j+1}} , \end{align*} 其中 $l=i-1$。由數學歸納法得證。$\tag*{$\Box$}$

三、廣義的 Stirling 數與同餘關係式

在上一節中, 我們所討論的第一型 Stirling 數如今已被廣泛推廣, 例如 Broder 的 $r$-Stirling 數, 以及 Carlitz 在 中所提及兩種衰退的 Stirling 數。 廣義的 Stirling 數, 則由 Hsu 及 Shiue 在 中給出了較具體的定義: 當 $n=1,2,\ldots $ 時, 他們定義 $\left[ z\mid \alpha \right] _n=z(z-\alpha )\cdots (z-n\alpha +\alpha )$, 而 $\left[ z\mid \alpha \right] _0=1$, 其中 $\alpha$ 為任意實數。 明顯地, 有 $\left[ z\mid 0\right] _n=z^n$ 以及 $\left[ z\mid 1\right] _n=\left[ z\right] _n$。我們從 引入以下定義:

定義 1. $$\left[ t\mid \alpha \right] _n=\displaystyle \sum_{k=0}^n S\left( n,k;\alpha ,\beta ,\gamma \right) \left[ t-\gamma \mid \beta \right] _k,$$ 其中 $\alpha$、 $\beta$、 $\gamma $ 為任意實數, 而 $S\left( n,k;\alpha ,\beta ,\gamma \right)$ 即為第一型的廣義 ${\rm Stirling}$ 數。

為了方便起見, 我們把 $S\left( n,k;\alpha ,\beta ,\gamma \right)$ 簡記成 $S\left( n,k\right)$, 必要時會將參數表示出來。 下面是本文會提到的一些特殊廣義第一型 Stirling 數 ():

• 當 $\left\langle \alpha, \beta, \gamma \right\rangle=\left\langle 1,0,0 \right\rangle$ 時, $S\left( n,k \right)$ 即為第一型 Stirling 數;
• 當 $\left\langle \alpha, \beta, \gamma \right\rangle=\left \langle-1, -\lambda ,0\right \rangle$ 時, $S( n,k)$ 即為 Carlitz 的第一型衰退 Stirling 數；
• 當 $\left\langle \alpha, \beta, \gamma \right\rangle=\left \langle-1, 0, r\right \rangle$ 時, $S\left( n,k \right)$ 則為 $r$-Stirling 數的第一型。

這些在稍後會有較詳細的介紹及說明。

以下列出我們需要的廣義 Stirling 數的性質:

性質 2.(遞迴關係式) 對任意的 $\alpha $、$\beta $、$\gamma $ 我們有 $$S\left( n+1, k \right) = S\left( n,k-1 \right) +\left( k\beta -n\alpha +\gamma \right) S\left( n,k \right),$$ 其中 $1\leq k\leq n$。

性質 3. 當 $\alpha $、$\beta $、$\gamma $ 是整數, 我們有以下的同餘關係式: $$S\left( p,n;\alpha ,\beta ,\gamma \right) \equiv 0 \quad\pmod {p},$$ 其中 $2\leq n\leq {p-1}$。

類似於定理 2 可得:

主要定理. 當 $2 \leq n \leq p-1$, 且 $\beta \equiv \gamma \equiv 0 \quad \pmod {p}$ \begin{align*} &S\left( p,n-(k-1)\right)\\ \equiv &\left\{\begin{array}{ll}\displaystyle \sum_{i=0}^{k-2}\left[ \phi +(k-2)\beta \mid \beta \right] _i S\left( p+1,n+i-(k-2)\right) \quad\pmod {p^k} & ,\ 2 \leq k \leq n+1;\\ 0 \quad\pmod {p} & ,\ k=1 。 \end{array}\right. \end{align*} 其中 $\phi =p\alpha-n\beta -\gamma $。

證明: 令 $2 \leq n \leq p-1$, 我們將對 $k$ 用數學歸納法證明。當 $k=2$, 由性質 2 及性質 3, 我們有$$S\left( p+1,n\right) =S\left( p,n-1\right) +( n\beta -p\alpha +\gamma) S\left( p, n\right),$$ 且 $S\left( p,n\right) \equiv 0\quad\pmod {p}$。 又, 因為 $\beta \equiv \gamma \equiv 0 \quad\pmod {p}$, 所以我們有 $$S\left( p,n-1\right) \equiv S\left( p+1,n\right) \pmod {p^2},$$本命題在 $k=2$ 時為真。

假設在 $2\leq k=j \leq n$ 時, 此命題為真, 換句話說, $$S\left( p,n-(j-1)\right) \equiv \displaystyle \sum_{i=0}^{j-2}\left[ \phi +(j-2)\beta \mid \beta \right] _i S\left( p+1,n+i-(j-2)\right) \quad\pmod {p^j}。$$ 則當 $k=j+1$ 時, \begin{align*} &~~~~S\left( p,n-j\right) \\ & = S\left( p+1,n-j+1\right) -\left( (n-j+1)\beta -p\alpha +\gamma\right) S\left( p,n-j+1 \right) \\ & \equiv S\left( p+1,n-j+1\right) \\ &~~~-\left( (n-j+1)\beta -p\alpha +\gamma\right) \displaystyle \sum_{i=0}^{j-2}\left[ \phi +(j-2)\beta \mid \beta \right] _i S\left( p+1,n+i-(j-2)\right) \\ & \equiv S\left( p+1,n-j+1\right) \\ &~~~+\left( \phi +(j-1)\beta \right) \displaystyle \sum_{i=0}^{j-2}\left[ \phi +(j-2)\beta \mid \beta \right] _i S\left( p+1,n+i-(j-2)\right) \\ & \equiv S\left( p+1,n-j+1\right) +\displaystyle \sum_{i=1}^{j-1}\left[ \phi +(j-1)\beta \mid \beta \right] _i S\left( p+1,n+i-(j-1)\right) \\ & \equiv \displaystyle \sum_{i=0}^{j-1}\left[ \phi +(j-1)\beta \mid \beta \right] _i S\left( p+1,n+i-(j-1)\right) \quad\pmod {p^{j+1}}\hbox{。}\tag*{$\Box$} \end{align*}

因為 $S(n,k;1,0,0)=S_1\left( n,k\right)$, 再代入主要定理, 即可得定理 2。

接下來, 我們要將以上的主要定理, 應用在兩個特別的 Stirling 數上。

在 中, Carlitz 第一型衰退的 Stirling 數 $S_1\left( n,k\mid \lambda \right)$ 滿足 \begin{align*} [x]_n=\sum_{k=0}^n (-1)^{n+k}S_1\left( n,k\mid \lambda \right) \left[ x\mid \lambda \right]_k, \end{align*} 我們已知 Carlitz 第一型衰退的 Stirling 數為: $S(n,k;-1,-\lambda ,0)$。

當 $\lambda =-1$、 $-2$ 及 $-3$, Carlitz 分別給出下列的表 1、 表 2, 還有表 3:

表 1. $\lambda =-1$.

k n	$0$	$1$	$2$	$3$	$4$	$5$
0	1
1	0	1
2	0	2	1
3	0	6	6	1
4	0	24	36	12	1
5	0	120	240	120	20	1

表 2. $\lambda =-2$.

k n	$0$	$1$	$2$	$3$	$4$	$5$
0	1
1	0	1
2	0	3	1
3	0	12	9	1
4	0	60	75	18	1
5	0	360	660	255	30	1

表 3. $\lambda =-3$.

k n	$0$	$1$	$2$	$3$	$4$	$5$
0	1
1	0	1
2	0	4	1
3	0	20	12	1
4	0	120	128	24	1
5	0	840	405	440	40	1

此時 $\phi =n\lambda -p $, 再利用主要定理, 可得:

系理 3. 當 $\lambda \equiv 0 \pmod p $, 且 $2 \leq k \leq n+1$, $2 \leq n \leq p-1$ 時, \begin{align*} & ~S\left( p,n-(k-1);-1,-\lambda ,0\right) \\ & \equiv \displaystyle \sum_{i=0}^{k-2}\left[ (n-k+2)\lambda -p\mid -\lambda \right] _i S\left( p+1,n+i-(k-2);-1,-\lambda ,0\right) \quad\pmod {p^k}\hbox{。} \end{align*}

例 1. 取 $p=3$、$\lambda =-3$、$n=2$。

• 當 $k=2$ 時, \begin{align*}\mbox{左式}=S\left( 3,1;-1, 3,0\right)&=20; \\ \mbox{右式}=S\left( 4,2;-1, 3,0\right)&=128\hbox{。}\end{align*} 顯然 $S\left( 3,1;-1, 3,0\right)\equiv 20\equiv 128\equiv S\left( 4,2;-1, 3,0\right)\ \pmod 9$。
• 當 $k=3$ 時, \begin{align*}\mbox{左式}&=S\left( 3,0;-1, 3,0\right)=0; \\ \mbox{右式}&=S\left( 4,1;-1, 3,0\right)-6\cdot S\left( 4,2;-1, 3,0\right)=-648=(-24)\cdot 27\hbox{。}\end{align*} 所以有 $S\left( 3,0;-1, 3,0\right)\equiv S\left( 4,1;-1, 3,0\right)-6\cdot S\left( 4,2;-1, 3,0\right)\quad\pmod {27}$。

類似地, 考慮 $r$-Stirling 數的第一型 $S_r(n,k)$ (請參考 ), 滿足以下關係式: \begin{align*} \, [x\mid -1]_n=\displaystyle \sum_{k=0}^n S_r(n,k) (x-r)^k , \end{align*} 所以 $S_r(n,k)=S\left( n,k;-1,0,r \right)$。當 $r =2, 3$ 時, Broder 分別給出表 4 和表 5:

表 4. $r=2$.

k n	$0$	$1$	$2$	$3$	$4$	$5$
0	1
1	2	1
2	6	5	1
3	24	26	9	1
4	120	154	71	14	1
5	720	1044	580	155	20	1

表 5. $r=3$.

k n	$0$	$1$	$2$	$3$	$4$	$5$
0	1
1	3	1
2	12	7	1
3	60	47	12	1
4	360	342	119	18	1
5	2520	2754	1175	245	25	1

在這種情況下, $\phi=-p-r$, 利用主要定理, 可得以下系理:

系理 4. 當 $r \equiv 0\ \pmod p$, 且 $2 \leq k \leq n+1$, $2 \leq n \leq p-1$ 時 \begin{align*} &S\left( p,n-(k-1);-1 ,0 ,r \right) \\ &\equiv \displaystyle \sum_{i=0}^{k-2}(-1)^i \left( p+r \right) ^i S\left( p+1,n+i-(k-2);-1 ,0 ,r \right) \quad\pmod {p^k}\hbox{。} \end{align*}

例 2. 取 $p=r=3$、$n=2$。

• 當 $k=2$ 時, \begin{align*}\mbox{左式}=S\left( 3,1;-1, 0,3\right)&=47; \\ \mbox{右式}=S\left( 4,2;-1, 0,3\right)&=119\hbox{。}\hskip 4cm~\end{align*} 顯然我們有 $S\left( 3,1;-1, 0,3\right) \equiv 47\equiv 119\equiv S\left( 4,2;-1,0,3\right) \ \pmod 9$。
• 當 $k=3$ 時, \begin{align*}\mbox{左式}&=S\left( 3,0;-1, 0,3\right)=60; \\ \mbox{右式}&=S\left( 4,1;-1, 0,3\right)-6\cdot S\left( 4,2;-1, 0,3\right)=-372\hbox{。}\end{align*} 明顯地, $$S\left( 3,0;-1, 0,3\right) \equiv 60\equiv -372\equiv S\left( 4,1;-1,0,3\right) -6\cdot S\left( 4,2;-1, 0,3\right) \quad\pmod {27}\hbox{。}$$

備註. 本文之主要定理並不適用於廣義的第二型 Stirling 數。我們針對第二型 Stirling 數舉一個反例:

當 $p=3$、$n=k=2$ 時, 主要定理中的左式為 $S_2(3,1)=1$, 而右式則為 $S_2(4,2)=7$。但, 明顯地 $S_2(3,1) \not\equiv S_2(4,2) \ \pmod {3^2}$ (請參考表 6 )。

表 6.

	$0$	$1$	$2$	$3$	$4$	$5$
0	1
1	0	1
2	0	1	1
3	0	1	3	1
4	0	1	7	6	1
5	0	1	15	25	10	1

致謝: 感謝中央研究院所舉辦的暑期研習, 讓筆者有機會受到薛昭雄老師的悉心指導, 也謝謝老師常常幫忙看我們所寫的東西, 改正我們的缺點與錯誤。 另外, 特別感謝孫維良同學在本文撰寫期間, 所給予的許多建議及幫助。

參考資料

---本文作者投稿時就讀國立台東大學數學系---