遊戲規則:本遊戲為猜密碼的遊戲。密碼為0到100之間的其中1個整數,電腦會提示密碼的所在範圍,玩家必須在6次之內猜到密碼才能過關。
★ 終極密碼為0到100之間 ★
您共有六次機會
當 $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
最後, 我們將簡單介紹一些特殊的第一型 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. 當 $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 數如今已被廣泛推廣, 例如 Broder
定義 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 數 (
以下列出我們需要的廣義 Stirling 數的性質:
性質 2.
性質 3.
類似於定理 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 數上。
在
當 $\lambda =-1$、 $-2$ 及 $-3$, Carlitz 分別給出下列的表 1、 表 2, 還有表 3:
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 |
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 |
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$。
類似地, 考慮 $r$-Stirling 數的第一型 $S_r(n,k)$ (請參考
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 |
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$。
備註. 本文之主要定理並不適用於廣義的第二型 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 )。
$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 |
致謝: 感謝中央研究院所舉辦的暑期研習, 讓筆者有機會受到薛昭雄老師的悉心指導, 也謝謝老師常常幫忙看我們所寫的東西, 改正我們的缺點與錯誤。 另外, 特別感謝孫維良同學在本文撰寫期間, 所給予的許多建議及幫助。
---本文作者投稿時就讀國立台東大學數學系---
聯絡方式: 10617 台北市羅斯福路四段1號 天文數學館6樓 中央研究院數學研究所數學傳播編輯部
Tel:02-23685999 轉 382 | Email: media@math.sinica.edu.tw
網路平台: 數學所資訊室 | Tel:02-23685999 轉 743 | Email: ytlin@math.sinica.edu.tw
© 2017 中央研究院數學研究所 All rights reserved.