遊戲規則:本遊戲為猜密碼的遊戲。密碼為0到100之間的其中1個整數,電腦會提示密碼的所在範圍,玩家必須在6次之內猜到密碼才能過關。
★ 終極密碼為0到100之間 ★
您共有六次機會
Catalan 數 $C_{n}$ (Koshy
Catalan 數不只在在組合學中頻繁出現, 在資訊、 代數、 幾何、 拓樸等領域中也可以發現它的蹤影, 也因此
Catalan 數一直是組合學家研究的課題之一。 目前已經發現的能用 Catalan 數計數的組合結構就有 207 種, 有興趣的讀者能在
Richard Stanley 的個人網站
本文的主要目的是探討 $C_{2,n}$ 的整數論性質。 在第二節中, 我們討論 $C_{m,n}$ 與二項式係數的關係。
在第三節中, 我們考慮 $C_{2,n}$ 的一個整除性, 它推廣了 T. Koshy and Z. Gao
定義1[Sands
性質1.對任意正整數 $m$ 及 $n$, 下列二式與 \eqref{1} 式等價
\begin{eqnarray} C_{m,n} &=&\frac{1}{n}\binom{\left( m+1\right) n}{n-1} \\ C_{m,n} &=&\frac{1}{\left( m+1\right) n+1}\binom{\left( m+1\right) n+1}{n} \end{eqnarray}\begin{align*} \frac{1}{n}\binom{\left( m+1\right) n}{n-1}& =\frac{1}{n}\cdot \frac{\left( mn+n\right) !}{\left( n-1\right) !\left( mn+1\right) !}=\frac{1}{mn+1}\cdot \frac{\left( mn+n\right) !}{\left( n!\right) \left(mn\right) !}\\ &=\frac{1}{mn+1}\binom{\left( m+1\right) n}{n}=C_{m,n} \end{align*} \begin{align*} \frac{1}{\left( m+1\right) n+1}\binom{\left( m+1\right) n+1}{n}& =\frac{1}{% \left( m+1\right) n+1}\cdot \frac{\left( mn+n+1\right) !}{\left( n!\right) \left( mn+1\right) !} \\ & =\frac{1}{mn+1}\cdot \frac{\left( mn+n\right) !}{\left( n!\right) \left( mn\right) !} \\ & =\frac{1}{mn+1}\binom{\left( m+1\right) n}{n}=C_{m,n}\tag*{$\Box$} \end{align*} 下面我們要說明 $C_{m,n}$ 與二項式係數的關係, 由此可得 $C_{m,n}$ 為正整數。
性質2.對任意正整數 $m$ 及 $n$, 有 \begin{align*} C_{m,n}=\binom{\left( m+1\right) n}{n}-m\binom{\left( m+1\right) n}{n-1}% \end{align*}
\begin{align*} \binom{\left( m+1\right) n}{n}-m\binom{\left( m+1\right) n}{n-1}& =\frac{% \left( mn+n\right) !}{\left( n!\right) \left( mn\right) !}-m\cdot \frac{% \left( mn+n\right) !}{\left( n-1\right) !\left( mn+1\right) !} \\ & =\frac{\left( mn+n\right) !}{\left( n!\right) \left( mn+1\right) !}\left[ \left( mn+1\right) -mn\right] \\ & =\frac{1}{mn+1}\binom{\left( m+1\right) n}{n}=C_{m,n}\tag*{$\Box$} \end{align*}
因為 $\binom{\left( m+1\right) n}{n}$ 與 $m\binom{\left( m+1\right) n}{n-1}$ 為正整數, 我們由性質 2 可得 $C_{m,n}$ 為正整數。 又因為 $C_{m,n}$, $\binom{\left( m+1\right) n}{n-1}$ 與 $\binom{\left( m+1\right) n+1}{n}$ 為整數, 我們得到性質 1 中 (2)、(3) 式有整除性 $n\mid \binom{\left( m+1\right) n}{n-1}$ 與 $\left[ \left( m+1\right) n+1\right] \mid \binom{\left( m+1\right) n+1}{n}$。
我們將 $C_{n}$ 的已知性質(見 Koshy
$C_{n}$ | $C_{m,n}$ |
$\frac{1}{n+1}\binom{2n}{n}$ | $\frac{1}{mn+1}\binom{\left( m+1\right) n}{n}$ |
$\frac{1}{n}\binom{2n}{n-1}$ | $\frac{1}{n}\binom{\left( m+1\right) n}{n-1}$ |
$\frac{1}{2n+1}\binom{2n+1}{n}$ | $\frac{1}{\left( m+1\right) n+1}\binom{% \left( m+1\right) n+1}{n}$ |
$\binom{2n}{n}-\binom{2n}{n-1}$ | $\binom{\left( m+1\right) n}{n}-m\binom{% \left( m+1\right) n}{n-1}$ |
$\binom{2n-1}{n-1}-\binom{2n-1}{n-2}$ | $\frac{m+n}{mn+1}\binom{\left( m+1\right) n-1}{n-1}-\binom{\left( m+1\right) n-1}{n-2}$ |
$2\binom{2n}{n}-\binom{2n+1}{n}$ | $\frac{1}{m}\left[ \frac{\left( m+1\right) \left( n+1\right) }{mn+1}\binom{\left( m+1\right) n}{n}-\binom{% \left( m+1\right) n+1}{n}\right] $ |
$\binom{2n+1}{n}-2\binom{2n}{n-1}$ | $\binom{\left( m+1\right) n+1}{n}% -\left( m+1\right) \binom{\left( m+1\right) n}{n-1}$ |
$\binom{2n+1}{n+1}-2\binom{2n}{n+1}$ | $\binom{\left( m+1\right) n+1}{mn+1}% -\left( m+1\right) \binom{\left( m+1\right) n}{mn+1}$ |
定義2[Mersenne數
根據上述定義可以得到下述遞迴關係式 \begin{align*} M_{k+1}=2M_{k}+1 , M_{1}=1 \text{。 } \end{align*}
T. Koshy 和 Z.Gao
(i) $2^{k}\mid C_{2M_{k}}$
(ii) $\left( 2^{k+1}-3\right) \mid C_{M_{k}}$
自然地, 我們想問在 $C_{m,n}$ 上是否有類似結果? 在本文中我們證明了 $C_{2,n}$ 時, 這個問題的答案是肯定的。
性質3. 對任意正整數$m$及$n$, 廣義Catalan數$C_{m,n}$可用$C_{m,n-1}$表示為 \begin{align*} C_{m,n}=\frac{\left( m+1\right) \left( mn+n-1\right) \left( mn+n-2\right) \cdots\left( mn+n-m\right) }{\left( mn+1\right) \left( mn\right) \cdots\left( mn-m+2\right) }C_{m,n-1} \end{align*}
\begin{align*} C_{m,n} =&\frac{1}{mn+1}\binom{\left( m+1\right) n}{n}=\frac{1}{mn+1}\cdot \frac{\left( mn+n\right) !}{n!\left( mn\right) !} \\ =&\frac{1}{mn\!+\!1}\cdot \frac{\left( mn\!+\!n\right) \left( mn\!+\!n\!-\!1\right) \left( mn\!+\!n\!-\!2\right) \cdots \left( mn\!+\!n\!-\!m\right) \left( mn\!+\!n\!-\!m\!-\!1\right) !}{\left( n\right) \left( mn\right) \left( mn\!-\!1\right) \cdots \left( mn\!-\!m\!+\!2\right) \left( mn\!-\!m\!+\!1\right) \left( n\!-\!1\right) !\left( mn\!-\!m\right) !} \\ =&\frac{\left( m+1\right) \left( mn+n-1\right) \left( mn+n-2\right) \cdots \left( mn+n-m\right) }{\left( mn+1\right) \left( mn\right)\cdots\left( mn-m+2\right) }\cdot \frac{1}{mn-m+1}\\ &\cdot \frac{\left( mn+n-m-1\right) !}{% \left( n-1\right) !\left( mn-m\right) !} \\ =&\frac{\left( m+1\right) \left( mn+n-1\right) \left( mn+n-2\right) \cdots\left( mn+n-m\right) }{\left( mn+1\right) \left( mn\right)\cdots\left(mn-m+2\right) }\\ &\cdot \frac{1}{m\left( n-1\right) +1}\binom{\left( m+1\right) \left( n-1\right) }{n-1} \\ =&\frac{\left( m+1\right) \left( mn+n-1\right) \left( mn+n-2\right) \cdots\left( mn+n-m\right) }{\left( mn+1\right) \left( mn\right) \cdots\left( mn-m+2\right) }C_{m,n-1}\tag*{$\Box$} \end{align*}
根據性質3. 當$m=2$時, $C_{2,n}$ 與 $C_{2,n-1}$可以得到下列關係式 \begin{equation} C_{2,n}=\frac{3\left( 3n-1\right) \left( 3n-2\right) }{\left( 2n+1\right) \left( 2n\right) }C_{2,n-1}.\label{4} \end{equation}
推論1. 對任意正整數 $m$ 及 $n$, \begin{align*} \lim_{n\rightarrow \infty }\frac{C_{m,n}}{C_{m,n-1}}=\left( m+1\right) \left( 1+\frac{1}{m}\right) ^{m} \end{align*}
\begin{align*} \lim_{n\rightarrow \infty }\frac{C_{m,n}}{C_{m,n-1}}& =\lim_{n\rightarrow \infty }\frac{\frac{1}{mn+1}\binom{\left( m+1\right) n}{n}}{\frac{1}{m\left( n-1\right) +1}\binom{\left( m+1\right) \left( n-1\right) }{n-1}} \\ & =\lim_{n\rightarrow \infty }\frac{\left( m+1\right) \left( mn+n-1\right) \left( mn+n-2\right)\cdots\left( mn+n-m\right) }{\left( mn+1\right) \left( mn\right) \cdots\left( mn-m+2\right) } \\ & =\lim_{n\rightarrow \infty }\left( m+1\right) \frac{\left[ \left( m+1\right) n-1\right] \left[ \left( m+1\right) n-2\right] \cdots\left[ \left( m+1\right) n-m\right] }{\left( mn+1\right) \left( mn\right) \cdots\left( mn-m+2\right) } \\ & =\left( m+1\right) \frac{\left( m+1\right) ^{m}}{m^{m}}=\left( m+1\right) \left( 1+\frac{1}{m}\right) ^{m}\tag*{$\Box$} \end{align*}
註1.
當 $m=1$ 時, 即得 $\lim\limits_{n\rightarrow\infty}\dfrac{C_{n}}{C_{n-1}}=4$ (Koshy
接下來的定理我們給出了前面提到的問題在$C_{2,n}$時的答案。
定理2. 若 $k$ 為正整數, 且 $k\not\equiv 3\left( \operatorname{mod}4\right) $ 及 $k\not\equiv2\left( \operatorname{mod}3\right) $, 則 \begin{align*} \frac{\left( 3M_{k}-1\right) \left( 3M_{k}-2\right) }{2}\mid C_{2,M_{k}}% \text{ $ $且$ $ } \frac{M_{k+1}M_{k}}{3}\mid C_{2,M_{k}-1} \end{align*}
對於任意正整數$k$, 令$n=M_{k}=2^{k}-1$, 代入(2)式 \begin{align*} C_{2,M_{k}}& =\frac{3\left( 3M_{k}-1\right) \left( 3M_{k}-2\right) }{\left( 2M_{k}+1\right) \left( 2M_{k}\right) }C_{2,M_{k}-1} \\ & =\frac{3\left[ 3\left( 2^{k}-1\right) -1\right] \left[ 3\left( 2^{k}-1\right) -2\right] }{\left[ 2\left( 2^{k}-1\right) +1\right] \left[ 2\left( 2^{k}-1\right) \right] }C_{2,M_{k}-1} \\ & =\frac{3\left( 3\cdot 2^{k}-4\right) \left( 3\cdot 2^{k}-5\right) }{% 2\left( 2\cdot 2^{k}-1\right) \left( 2^{k}-1\right) }C_{2,M_{k}-1} \\ & =\frac{\frac{\left( 3\cdot 2^{k}-4\right) \left( 3\cdot 2^{k}-5\right) }{2}}{\frac{\left( 2^{k+1}-1\right) \left( 2^{k}-1\right) }{3}}% C_{2,M_{k}-1} , \end{align*}
整理可得 \begin{equation} \left( 2^{k+1}-1\right) \left( 2^{k}-1\right) \left( 2C_{2,M_{k}}\right) =\left( 3\cdot 2^{k}-4\right) \left( 3\cdot 2^{k}-5\right) \left( 3C_{2,M_{k}-1}\right).\label{5} \end{equation}
考慮 \eqref{5} 式中$3\cdot2^{k}-4$、 $3\cdot2^{k}-5$、 $2^{k+1}-1$、 及 $2^{k}-1$ 四項之間的因數與倍數關係:
(i) 已知$\gcd \left( 3\cdot 2^{k}-4,2^{k+1}-1\right) =\gcd \left( 2^{k}-3,5\right) $。 由於 $5\mid 2^{k}-3$ 的充要條件為 $k\equiv 3\left( \operatorname{mod}4\right) $, 故當 $k\not\equiv 3\left( \operatorname{mod}4\right) $ 時, $\gcd \left( 3\cdot 2^{k}-4,2^{k+1}-1\right) =\gcd \left( 2^{k}-3,5\right)=1 $。
(ii) $\gcd \left( 3\cdot 2^{k}-4,2^{k}-1\right) =\gcd \left( -1,2^{k}-1\right) =1$。
(iii) 已知 $\gcd\left( 3\cdot2^{k}% -5,2^{k+1}-1\right) =\gcd\left( 2^{k}-4,7\right) $。 由於$7\mid 2^{k}-4$的充要條件為$k\equiv 2\left( \operatorname{mod}3\right) $, 所以當 $k\not\equiv 2\left( \operatorname{mod}3\right) $ 時, $\gcd\left( 3\cdot2^{k}% -5,2^{k+1}-1\right) =\gcd\left( 2^{k}-4,7\right)=1 $。
(iv) 因為 $\gcd\left( 3\cdot2^{k}-5,2^{k}-1\right) =\gcd\left( -2,2^{k}-1\right)$, 又因$2^{k}-1$ 是奇數, 使得 $\gcd\left( 3\cdot2^{k}-5,2^{k}-1\right) =\gcd\left( -2,2^{k}-1\right) =1$。
根據上述討論, 當 $k\not\equiv 3\left( \operatorname{mod}4\right) $ 及 $k\not\equiv2\left( \operatorname{mod}3\right) $ 時, $\left( 3\cdot 2^{k}-4\right) \left( 3\cdot 2^{k}-5\right)$ 和 $\left( 2\cdot 2^{k}-1\right) \left( 2^{k}-1\right)$ 互質, 因此我們可以得到 \begin{equation} \left( 3\cdot 2^{k}-4\right) \left( 3\cdot 2^{k}-5\right) \mid 2C_{2,M_{k}}\label{6} \end{equation} 與 \begin{equation} \left( 2^{k+1}-1\right) \left( 2^{k}-1\right) \mid 3C_{2,M_{k}-1}.\label{7} \end{equation}
對任意正整數 $k$, 因為 $3\cdot 2^{k}-4=2\left( 3\cdot 2^{k-1}-2\right) $, 所以 $2\mid \left( 3\cdot 2^{k}-4\right) $, 因此 $\frac{\left( 3\cdot 2^{k}-4\right) \left( 3\cdot 2^{k}-5\right) }{2}$ 為整數。 又當$k$是偶數時, $2^{k}-1\equiv0\left( \operatorname{mod}% 3\right) $, 當 $k$ 是奇數時, $2^{k+1}-1\equiv0\left( \operatorname{mod}% 3\right) $, 所以 $3\mid \left( 2^{k+1}-1\right) \left( 2^{k}-1\right) $, 因此 $\frac{\left( 2^{k+1}-1\right) \left( 2^{k}-1\right) }{3}$ 為整數。
我們可將 \eqref{6}、 \eqref{7} 式表示成 \begin{align*} \frac{\left( 3\cdot 2^{k}-4\right) \left( 3\cdot 2^{k}-5\right) }{2}\mid C_{2,M_{k}}% \text{ $ $且$ $ }\frac{\left( 2^{k+1}-1\right) \left( 2^{k}-1\right) }{3}\mid C_{2,M_{k}-1} , \end{align*} 亦可表示為 \begin{align*} \frac{\left( 3M_{k}-1\right) \left( 3M_{k}-2\right) }{2}\mid C_{2,M_{k}}% \text{ $ $且$ $ }\frac{M_{k+1}M_{k}}{3}\mid C_{2,M_{k}-1} \text{。 }{\Box} \end{align*}
例1. 令 $k=4$, 則 \begin{eqnarray*} \frac{C_{2,M_{4}}}{\frac{1}{2}\left( 3\cdot 2^{4}-4\right) \left( 3\cdot 2^{4}-5\right) } &=&\frac{11124755664}{946}= 11\,759\,784 &=&\frac{1822766520}{155}=\frac{C_{2,M_{4}-1}}{\frac{1}{3}\left( 2^{5}-1\right) \left( 2^{4}-1\right) } \end{eqnarray*} 由上式可得 $\frac{\left( 3\cdot 2^{4}-4\right) \left( 3\cdot 2^{4}-5\right) }{2}\mid C_{2,M_{4}}$ 且 $\frac{\left( 2\cdot 2^{4}-1\right) \left( 2^{4}-1\right) }{3}\mid C_{2,M_{4}-1}$。
在 2013 年, T. Koshy 和 Z.Gao
對任意正整數 $n$, 令 $A_{n}=F_{n}$、 $L_{n}$ 或 $P_{n}$, 當 $A_{n}\not\equiv 3\left( \operatorname{mod}4\right) $ 及 $A_{n}\not\equiv2\left( \operatorname{mod}3\right) $ 時, 可以得到 $\frac{\left( 3M_{A_{n}}-1\right) \left( 3M_{A_{n}}-2\right) }{2}\mid C_{2,M_{A_{n}}}$ 且 $\frac{M_{A_{n}+1}M_{A_{n}}}{3}\mid C_{2,M_{A_{n}}-1}$。
例2. 令 $n=7$, $F_{7}=13$, 則 \begin{align*}C_{2,M_{F_{7}}}=C_{2,8191}=\frac{1}{16383}\binom{24573}{8191},\qquad C_{2,M_{F_{7}-1}}=C_{2,8190}=\frac{1}{16381}\binom{24570}{8190},\end{align*} \begin{align*}\frac{\left( 3\cdot 2^{13}-4\right) \left( 3\cdot 2^{13}-5\right) }{2}% = 301\,879\,306,\qquad \frac{\left( 2\cdot 2^{13}-1\right) \left( 2^{13}-1\right) }{3}% = 44\,731\,051,\end{align*} \begin{align*}\hbox{所以}\ \frac{\left( 3\cdot 2^{13}-4\right) \left( 3\cdot 2^{13}-5\right) }{2}\mid C_{2,M_{F_{7}}}\ \hbox{且}\ \frac{\left( 2\cdot 2^{13}-1\right) \left( 2^{13}-1\right) }{3}\mid C_{2,M_{F_{7}}-1}\hbox{。}\end{align*}
令 $n=3$, $L_{3}=4$, 則 \begin{align*}C_{2,M_{L_{3}}}\!=\!C_{2,15}\!=\!\frac{1}{31}\binom{45}{15}\!=\! 11\, 124\,755\,664,\ C_{2,M_{L_{3}}-1}\!=\!C_{2,14}\!=\!\frac{1}{29}\binom{42}{14}\!=\! 1822\,766\,520,\end{align*} \begin{align*}\frac{\left( 3\cdot 2^{4}-4\right) \left( 3\cdot 2^{4}-5\right) }{2}% = 946,\qquad \frac{\left( 2\cdot 2^{4}-1\right) \left( 2^{4}-1\right) }{3}= 155,\end{align*} \begin{align*}\hbox{所以}\ \frac{\left( 3\cdot 2^{4}-4\right) \left( 3\cdot 2^{4}-5\right) }{2}\mid C_{2,M_{L_{3}}}\ \hbox{且}\ \frac{\left( 2\cdot 2^{4}-1\right) \left( 2^{4}-1\right) }{3}\mid C_{2,M_{L_{3}}-1}\hbox{。}\end{align*}
令 $n=4$, $P_{4}=12$, 則 \begin{align*}C_{2,M_{P_{4}}}=C_{2,4095}=\frac{1}{8191}\binom{12285}{4095},\qquad C_{2,M_{P_{4}}-1}=C_{2,4094}=\frac{1}{8189}\binom{12282}{4094}, \end{align*} \begin{align*}\frac{\left( 3\cdot 2^{12}-4\right) \left( 3\cdot 2^{12}-5\right) }{2}% = 75\,442\,186,\qquad \frac{\left( 2\cdot 2^{12}-1\right) \left( 2^{12}-1\right) }{3}% = 11\,180\,715,\end{align*} \begin{align*}\hbox{所以}\ \frac{\left( 3\cdot 2^{12}-4\right) \left( 3\cdot 2^{12}-5\right) }{2}\mid C_{2,M_{P_{4}}}\ \hbox{且}\ \frac{\left( 2\cdot 2^{12}-1\right) \left( 2^{12}-1\right) }{3}\mid C_{2,M_{P_{4}}-1}\hbox{。}\end{align*}
定理3.[Koshy, Salmassi
自然地, 我們會好奇對一般的 $C_{m,n}$ 有哪些 $m,n$ 使的 $C_{m,n}$ 為質數, 本節我們的目標在找出 $m=2$ 時, 有哪些 $n$ 使得 $C_{2,n}$ 為質數。
第三節中 \eqref{4} 式可改寫整理為 \begin{equation} \frac{\left( 2n+3\right) \left( 2n+2\right) C_{2,n+1}}{C_{2,n}}=3\left( 3n+2\right) \left( 3n+1\right).\label{8} \end{equation}
首先, 假設 $C_{2,n}$ 為質數, 因為 \eqref{8} 式等號右邊為正整數, 等號左邊可分為三種可能情況 $C_{2,n} \mid \left( 2n+3\right)$、 $C_{2,n} \mid \left( 2n+2\right)$ 或 $C_{2,n} \mid C_{2,n+1}$。
情況 1: $C_{2,n} \mid \left( 2n+3\right)$, 我們考慮 $\frac{2n+3}{C_{2,n}}$, \begin{eqnarray*} \frac{2n+3}{C_{2,n}} &=&\frac{2n+3}{\frac{1}{2n+1}\dbinom{3n}{n}}=\frac{2n+3% }{\frac{1}{2n+1}\cdot \frac{\left( 3n\right) \left( 3n-1\right) \cdots\left( 2n+3\right) \left( 2n+2\right) \left( 2n+1\right) }{n!}} \\ &=&\frac{n\left( n-1\right) \cdots 4\cdot 3\cdot 2\cdot 1}{\left( 3n\right) \left( 3n-1\right) \cdots\left( 2n+4\right) \left( 2n+2\right) } \\ &=&\frac{\left( n-1\right) \cdots4\cdot 2\cdot 1}{\left( 3n-1\right)\cdots\left( 2n+4\right) \left( 2n+2\right) } , \end{eqnarray*} 可以得到 $ \frac{\left( n-1\right) \cdots 4\cdot 2\cdot 1}{\left( 3n-1\right) \cdots \left( 2n+4\right) \left( 2n+2\right) }$ 不為整數, 即 $\frac{2n+3}{C_{2,n}}$ 不為整數, 所以 $C_{2,n} \nmid \left( 2n+3\right)$。
情況 2: $C_{2,n} \mid \left( 2n+2\right)$, 我們考慮 $\frac{2n+2}{C_{2,n}}$, \begin{eqnarray*} \frac{2n+2}{C_{2,n}} &=&\frac{2n+2}{\frac{1}{2n+1}\dbinom{3n}{n}}=\frac{2n+2% }{\frac{1}{2n+1}\cdot \frac{\left( 3n\right) \left( 3n-1\right) \cdots\left( 2n+2\right) \left( 2n+1\right) }{n!}} \\ &=&\frac{n\left( n-1\right) \cdots 4\cdot 3\cdot 2\cdot 1}{\left( 3n\right) \left( 3n-1\right) \cdots\left( 2n+4\right) \left( 2n+3\right) } \\ &=&\frac{\left( n-1\right) \cdots 4\cdot 2\cdot 1}{\left( 3n-1\right) \cdots\left( 2n+4\right) \left( 2n+3\right) } , \end{eqnarray*} 可以得到 $\frac{\left( n-1\right) \cdots 4\cdot 2\cdot 1}{\left( 3n-1\right) \cdots\left( 2n+4\right) \left( 2n+3\right) }$ 不為整數, 即 $\frac{2n+2}{C_{2,n}}$ 不為整數, 所以 $C_{2,n} \nmid \left( 2n+2\right)$。
情況 3: $C_{2,n} \mid C_{2,n+1}$, 我們令 $C_{2,n+1}=kC_{2,n}$, $k$ 為整數, \eqref{8} 式可表示成 \begin{align*} \left( 2n+3\right) \left( 2n+2\right) kC_{2,n}=3\left( 3n+2\right) \left( 3n+1\right) C_{2,n} \end{align*} 整理得 \begin{eqnarray*} k &=&\frac{3\left( 3n+2\right) \left( 3n+1\right) }{\left( 2n+3\right) \left( 2n+2\right) }=\frac{27n^{2}+27n+6}{4n^{2}+10n+6} &=&6+\frac{3n^{2}-33n-30}{4n^{2}+10n+6}=6+\frac{3\left( n-10\right) \left( n+1\right) }{2\left( 2n+3\right) \left( n+1\right) } &=&6+\frac{3\left( n-10\right) }{2\left( 2n+3\right) }=6+\frac{3n-30}{4n+6} , \end{eqnarray*} 因為 $k$ 為整數, 則 $\dfrac{3n-30}{4n+6}$ 為整數, 可以得到 $\left\vert 3n-30\right\vert \geqslant 4n+6$ 或 $3n-30=0$。 因此有下列三種可能
>(i) $3n-30\geqslant 4n+6$, 可得 $n\leqslant -36$。
(ii) $-\left( 3n-30\right) \geqslant 4n+6$, 可得 $7n\leqslant 24$, 則 $n\leqslant \frac{24}{7}$。
(iii) $3n-30=0$, 即 $n=10$。
因為 $n$ 為非負整數, 所以可能 (i) 矛盾。 由 (ii) 和 (iii) 可以得到 $n=0,1,2,3$ 及 $n=10$。 由定義 1 我們知道當 $m=2$時, $C_{2,n}=\frac{1}{2n+1}\dbinom{3n}{n}$, 前幾項為 $\left\{ C_{2,n}\right\} _{n\geqslant 0}=\left\{ 1,1,3,12,55,\ldots\right\} $ 及 $C_{2,10}=1430715$ 並非質數。所以我們推得 $C_{2,2}=3$ 為 $C_{2,n}$ 中的唯一質數。
由上述討論我們可以得到下述定理, 定理4. Catalan 數 $C_{2,n}$ 中只有 $C_{2,2}=3$ 為質數。
註2. 因為 Catalan 數 $C_{m,n}$ 當 $m \geqslant 3$ 時, 推廣為整數論性質過程相當複雜, 所以本文只討論到 $C_{2,n}$ 的情況。
感謝中研院數學所暑期組合數學與圖論專題計畫的資助, 讓筆者有機會在暑假跟隨美國內華達大學數學系薛昭雄教授做暑期研究, 由衷感謝薛昭雄教授的指導、 學長廖信傑的修稿與同學賴冠宇的協助, 因為薛教授、 廖學長與賴同學的鼓勵及鉅細靡遺建議本文才能完稿。 亦感謝數學傳播審稿人給予修改建議及審查校正, 使本文更加精確完整。
---本文作者就讀國立東華大學應用數學系---
聯絡方式: 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.