40208 廣義Catalan 數的一些整數論性質

終極密碼

遊戲規則:本遊戲為猜密碼的遊戲。密碼為0到100之間的其中1個整數,電腦會提示密碼的所在範圍,玩家必須在6次之內猜到密碼才能過關。
★ 終極密碼為0到100之間 ★
您共有六次機會

一、引言

Catalan 數 $C_{n}$ (Koshy [4]) 原始定義為對任意非負整數 $n$, 滿足遞迴關係式 \begin{align*} C_{n+1}=C_{0}C_{n}+C_{1}C_{n-1}+\cdots+C_{n}C_{0} , \ C_{0}=1 \end{align*} 的數列。 其一般式為 $C_{n}=\frac{1}{n+1}\binom{2n}{n}$, 其前幾項為 $\left\{ C_{n}\right\} _{n\geqslant 0}=\left\{ 1,1,2,5,14,42,\ldots\right\} $。

Catalan 數不只在在組合學中頻繁出現, 在資訊、 代數、 幾何、 拓樸等領域中也可以發現它的蹤影, 也因此 Catalan 數一直是組合學家研究的課題之一。 目前已經發現的能用 Catalan 數計數的組合結構就有 207 種, 有興趣的讀者能在 Richard Stanley 的個人網站 [7] 上查看資料。 Sands [6] 在 1978 年將 Catalan 數 $C_{n}=\frac{1}{n+1}\binom{2n}{n}$ 推廣為 $C_{m,n}=\frac{1}{mn+1}\binom{\left( m+1\right) n}{n}$。

本文的主要目的是探討 $C_{2,n}$ 的整數論性質。 在第二節中, 我們討論 $C_{m,n}$ 與二項式係數的關係。 在第三節中, 我們考慮 $C_{2,n}$ 的一個整除性, 它推廣了 T. Koshy and Z. Gao [1] 在 $C_{n}$ 的結果。 在第四節中, 我們證明了 $C_{2,n}$ 中只有 $C_{2,2}$ 為質數, 同樣地它推廣了 Koshy 和 Salmassi [[5]p.331] 在 $C_{n}$ 上的結論。

二、廣義 Catalan 數的整數性質

定義1[Sands[6]] 對任意非負整數$m$及$n$, 廣義Catalan數$C_{m,n}$定義為 \begin{equation} C_{m,n}=\frac{1}{mn+1}\binom{\left( m+1\right) n}{n}\label{1} \end{equation} 當 $m=1$ 時, $C_{1,n}$ 即是原本的 Catalan 數 $C_{n}$。

性質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 [5]) 推廣到 $C_{m,n}$ 的性質, $C_{m,n}$ 表為二項式之差有許多種, 列表如下:

$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}$

三、廣義 Catalan 數 $C_{2,n}$ 和 Mersenne 數的關係

定義2[Mersenne數 [4]] 對於任意正整數 $k$, Mersenne 數定義為 \begin{align*} M_{k}=2^{k}-1 \end{align*} 其前幾項為$M_{1}=1$, $M_{2}=3$, $M_{3}=7,\ldots$。

根據上述定義可以得到下述遞迴關係式 \begin{align*} M_{k+1}=2M_{k}+1 , M_{1}=1 \text{。 } \end{align*}

T. Koshy 和 Z.Gao [2] 於 2013 年提出 Catalan 數和 Mersenne 數之關聯, 其主要結果如下: 對於任意正整數 $k$,

(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 [5])。

接下來的定理我們給出了前面提到的問題在$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 [2] 提出用 Fibonacci 數 $F_{n}$、 Lucas 數 $L_{n}$、 Pell 數 $P_{n}$ 表示 $C_{n}$ 與 Mersenne 係數整除性關係, 根據定理 1 我們也推廣到用 $F_{n}$、 $L_{n}$、 $P_{n}$ 表示 $C_{2,n}$ 與 Mersenne 係數的整除性。

對任意正整數 $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*}

四、Catalan 數 $C_{2,n}$ 之質數問題

定理3.[Koshy, Salmassi [5]] Catalan 數 $C_{n}$ 中只有 $C_{2}$ 和 $C_{3}$ 二個質數。

自然地, 我們會好奇對一般的 $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}$ 的情況。

致謝

感謝中研院數學所暑期組合數學與圖論專題計畫的資助, 讓筆者有機會在暑假跟隨美國內華達大學數學系薛昭雄教授做暑期研究, 由衷感謝薛昭雄教授的指導、 學長廖信傑的修稿與同學賴冠宇的協助, 因為薛教授、 廖學長與賴同學的鼓勵及鉅細靡遺建議本文才能完稿。 亦感謝數學傳播審稿人給予修改建議及審查校正, 使本文更加精確完整。

參考資料

1.R. P. Grimaldi, Fibonacci and Catalan Number, An introduction. John Wiley and Sons, Hoboken, New Jersey, 2012.

2.T. Koshy and Z. Gao, Catalan number with Mersenne subscripts. Math. Scintist. 38, 86-91, 2013.

3.T. Koshy and Z. Gao, Some divisibility properties of Catalan numbers. Math. Gazette 95, 96-102, 2011.

4.T. Koshy, Catalan Numbers with Applications. Oxford University Press, 2009.

5.T. Koshy, Elementary Number Theory with Applications, 2nd edn. Academic Press, Boston, MA., 2002.

6.A. D. Sands, On generalized Catalan number, Discrete Math. 21, 219-221, 1978.

7.R. P. Stanley, Catalan addendum. Available at

www-math.mit.edu/~rstan/ec/catadd.pdf, 2013.

---本文作者就讀國立東華大學應用數學系---