0. はじめに
本記事では組み合わせ論に頻出する重要な対象であるCatalan数の数論的な性質について簡単に解説します.
組み合わせ論的な解釈については他の方が書かれた良記事がたくさんありますので, そちらをご参考いただければと思います.
高度な数学はほとんど出てきませんので, 是非お気軽にご覧下さい.
1. Catalan数の定義
ではまず本記事のテーマであるCatalan数を定義しましょう.
以下の漸化式
\begin{align}
&C_{0} = 1, \\
&C_{n} = \sum_{k = 0}^{n - 1}C_{k}C_{n - 1 - k} \quad (n \geq 1)
\end{align}
で定まる整数列 $C_{n}$ を Catalan数 といいます.
以前三角関数に隠された組み合わせの秘密でご紹介したZig-Zag Number $Alt_{n}$ の漸化式によく似ていますね.1
後程ご紹介する一般項によってCatalan数を定義することもあるのですが, 漸化式として覚えておいた方が組み合わせ論的な解釈の理解をしやすいので, 本記事では漸化式によってCatalan数を定義しています.
組み合わせ論的解釈についてはWikipediaや高校数学の美しい物語様をご覧ください.
また、上記定義によりCatalan数 $C_{n}$ は自然数となることが分かります.
2. 一般項と諸性質
本章ではCatalan数の一般項を求め, いくつかの簡単な公式や不等式を示します.
2.1. Catalan数の一般項
本節ではCatalan数の一般項を求めたいと思います.
しかし, 上記漸化式はそう簡単に解けそうではありませんよね.
こういう場合には母関数による議論に持ち込むと解ける場合があります.
Catalan数 $C_{n}$ の母関数を
F(x) = \sum_{n = 0}^{\infty}C_{n}x^{n}
と定義します.
すると, Catalan数の定義より,
\begin{align}
F(x) &= 1 + \sum_{n = 1}^{\infty}C_{n}x^{n} \\
&= 1 + \sum_{n = 1}^{\infty} \left(\sum_{k = 0}^{n - 1}C_{k}C_{n - 1- k}\right)x^{n} \\
&= 1 + \sum_{n = 0}^{\infty} \left(\sum_{k = 0}^{n}C_{k}C_{n - k}\right)x^{n + 1} \\
&= 1 + x\sum_{n = 0}^{\infty} \left(\sum_{k = 0}^{n}C_{k}C_{n - k}\right)x^{n} \\
&= 1 + xF(x)^{2}
\end{align}
より,
xF(x)^{2} - F(x) + 1 = 0
つまり,
\left\{xF(x)\right\}^{2} - xF(x) + x = 0
となります.
ここで $G(x) = xF(x)$ とおくと上記の等式は,
G(x)^{2} - G(x) + x = 0
であるからこれを $G(x)$ について解けば,
G(x) = \dfrac{1 - \sqrt{1 - 4x}}{2}
となります. ただし, 二次方程式の解は $2$ つ出ますが, $G(0) = 0 \cdot F(0) = 0 \cdot 1 = 0$ より, 解は上の $1$ つに定まります.
さて今,
U(x) = \dfrac{1}{\sqrt{1 - 4x}}
と定めると $G(x)$ は,
\begin{align}
G(x) &= \dfrac{1 - (1 - 4x)U(x)}{2} \\
&= \dfrac{1 - U(x)}{2} + 2xU(x)
\end{align}
であり $U(x)$ は,
U(x) = \sum_{n = 0}^{\infty} \binom{2n}{n}x^{n}
とTaylor展開できるので,
\begin{align}
G(x) &= -\dfrac{1}{2}\sum_{n = 1}^{\infty}\binom{2n}{n}x^{n} + 2x\sum_{n = 0}^{\infty}\binom{2n}{n}x^{n} \\
&= \sum_{n = 0}^{\infty} \left\{2\binom{2n}{n} - \dfrac{1}{2}\binom{2(n + 1)}{n + 1}\right\}x^{n + 1} \\
&= \sum_{n = 0}^{\infty}\dfrac{1}{n + 1}\binom{2n}{n}x^{n + 1}
\end{align}
とできます. 従って, $G(x) = xF(x)$ だったことを思い出せば係数を比較することにより, Catalan数の一般項
C_{n} = \dfrac{1}{n + 1}\binom{2n}{n}\quad (n \geq 0)
を得ることができました！
2.2. 簡単な応用
Catalan数の一般項を求めることができたので, この一般項を用いてCatalan数に関する簡単な漸化式や不等式を示すことができます.
まず, 定義とは別の漸化式を求めてみましょう.
$C_{n}$ の一般項表示より,
\begin{align}
C_{n + 1} &= \dfrac{1}{n + 2}\binom{2n + 2}{n + } \\
&= \dfrac{1}{n + 2} \dfrac{(2n + 2)!}{(n + 1)!(n + 1)!} \\
&= \dfrac{(2n + 2)(2n + 1)}{(n + 1)(n + 2)}C_{n} \\
&= \dfrac{4n + 2}{n + 2}C_{n}
\end{align}
となって,
C_{n + 1} = \dfrac{4n + 2}{n + 2}C_{n} \quad (n \geq 0)
が成り立ちます.
またこの表示を用いることで数学的帰納法により, 不等式
C_{n} > n + 2 \quad (n \geq 4)
を示すことができます.
是非挑戦してみてください.
2.3. PythonプログラムによるCatalan数の計算
以下に, Catalan数を計算するためのPythonスクリプトを示しておきます.
Catalan数を返却する関数を $3$種類 定義しています.
from sympy import catalan, binomial
def get_catalan1(n):
"""
sympy.catalanで求めたCatalan数をそのまま返却する
Parameters
----------
n : int
求めたいCatalan数のインデックス
Returns
----------
Cn : int
n番目のカタラン数
"""
return catalan(n)
def get_catalan2(n) :
"""
定義の漸化式によって計算したCatalan数を返却する
再帰呼び出しによりとても重いので注意！
Parameters
----------
n : int
求めたいCatalan数のインデックス
Returns
----------
Cn : int
n番目のカタラン数
"""
if n == 0 or n == 1:
return 1
else:
return sum([get_catalan2(k) * get_catalan2(n - k - 1) for k in range(0, n)])
def get_catalan3(n):
"""
一般項によって計算したCatalan数を返却する
Parameters
----------
n : int
求めたいCatalan数のインデックス
Returns
----------
Cn : int
n番目のカタラン数
"""
return binomial(2 * n, n) // (n + 1)
if __name__ == '__main__':
for n in range(1, 101):
# ここでは1つ目の関数を採用
Cn = get_catalan1(n)
print(f'n = {n} ---> Cn = {Cn}')
3. Catalan数はいつ素数になるか？
ところで, Catalan数はいつ素数になるのでしょうか？
気になりますよね. 夜も寝られませんよね.
上のPythonスクリプトを元に確かめてみると, $0$ ～ $100$ の間では以下のようになります.
n = 0 ---> Cn = 1 ,素数判定：False
n = 1 ---> Cn = 1 ,素数判定：False
n = 2 ---> Cn = 2 ,素数判定：True
n = 3 ---> Cn = 5 ,素数判定：True
n = 4 ---> Cn = 14 ,素数判定：False
n = 5 ---> Cn = 42 ,素数判定：False
n = 6 ---> Cn = 132 ,素数判定：False
n = 7 ---> Cn = 429 ,素数判定：False
n = 8 ---> Cn = 1430 ,素数判定：False
n = 9 ---> Cn = 4862 ,素数判定：False
n = 10 ---> Cn = 16796 ,素数判定：False
n = 11 ---> Cn = 58786 ,素数判定：False
n = 12 ---> Cn = 208012 ,素数判定：False
n = 13 ---> Cn = 742900 ,素数判定：False
n = 14 ---> Cn = 2674440 ,素数判定：False
n = 15 ---> Cn = 9694845 ,素数判定：False
n = 16 ---> Cn = 35357670 ,素数判定：False
n = 17 ---> Cn = 129644790 ,素数判定：False
n = 18 ---> Cn = 477638700 ,素数判定：False
n = 19 ---> Cn = 1767263190 ,素数判定：False
n = 20 ---> Cn = 6564120420 ,素数判定：False
n = 21 ---> Cn = 24466267020 ,素数判定：False
n = 22 ---> Cn = 91482563640 ,素数判定：False
n = 23 ---> Cn = 343059613650 ,素数判定：False
n = 24 ---> Cn = 1289904147324 ,素数判定：False
n = 25 ---> Cn = 4861946401452 ,素数判定：False
n = 26 ---> Cn = 18367353072152 ,素数判定：False
n = 27 ---> Cn = 69533550916004 ,素数判定：False
n = 28 ---> Cn = 263747951750360 ,素数判定：False
n = 29 ---> Cn = 1002242216651368 ,素数判定：False
n = 30 ---> Cn = 3814986502092304 ,素数判定：False
n = 31 ---> Cn = 14544636039226909 ,素数判定：False
n = 32 ---> Cn = 55534064877048198 ,素数判定：False
n = 33 ---> Cn = 212336130412243110 ,素数判定：False
n = 34 ---> Cn = 812944042149730764 ,素数判定：False
n = 35 ---> Cn = 3116285494907301262 ,素数判定：False
n = 36 ---> Cn = 11959798385860453492 ,素数判定：False
n = 37 ---> Cn = 45950804324621742364 ,素数判定：False
n = 38 ---> Cn = 176733862787006701400 ,素数判定：False
n = 39 ---> Cn = 680425371729975800390 ,素数判定：False
n = 40 ---> Cn = 2622127042276492108820 ,素数判定：False
n = 41 ---> Cn = 10113918591637898134020 ,素数判定：False
n = 42 ---> Cn = 39044429911904443959240 ,素数判定：False
n = 43 ---> Cn = 150853479205085351660700 ,素数判定：False
n = 44 ---> Cn = 583300119592996693088040 ,素数判定：False
n = 45 ---> Cn = 2257117854077248073253720 ,素数判定：False
n = 46 ---> Cn = 8740328711533173390046320 ,素数判定：False
n = 47 ---> Cn = 33868773757191046886429490 ,素数判定：False
n = 48 ---> Cn = 131327898242169365477991900 ,素数判定：False
n = 49 ---> Cn = 509552245179617138054608572 ,素数判定：False
n = 50 ---> Cn = 1978261657756160653623774456 ,素数判定：False
n = 51 ---> Cn = 7684785670514316385230816156 ,素数判定：False
n = 52 ---> Cn = 29869166945772625950142417512 ,素数判定：False
n = 53 ---> Cn = 116157871455782434250553845880 ,素数判定：False
n = 54 ---> Cn = 451959718027953471447609509424 ,素数判定：False
n = 55 ---> Cn = 1759414616608818870992479875972 ,素数判定：False
n = 56 ---> Cn = 6852456927844873497549658464312 ,素数判定：False
n = 57 ---> Cn = 26700952856774851904245220912664 ,素数判定：False
n = 58 ---> Cn = 104088460289122304033498318812080 ,素数判定：False
n = 59 ---> Cn = 405944995127576985730643443367112 ,素数判定：False
n = 60 ---> Cn = 1583850964596120042686772779038896 ,素数判定：False
n = 61 ---> Cn = 6182127958584855650487080847216336 ,素数判定：False
n = 62 ---> Cn = 24139737743045626825711458546273312 ,素数判定：False
n = 63 ---> Cn = 94295850558771979787935384946380125 ,素数判定：False
n = 64 ---> Cn = 368479169875816659479009042713546950 ,素数判定：False
n = 65 ---> Cn = 1440418573150919668872489894243865350 ,素数判定：False
n = 66 ---> Cn = 5632681584560312734993915705849145100 ,素数判定：False
n = 67 ---> Cn = 22033725021956517463358552614056949950 ,素数判定：False
n = 68 ---> Cn = 86218923998960285726185640663701108500 ,素数判定：False
n = 69 ---> Cn = 337485502510215975556783793455058624700 ,素数判定：False
n = 70 ---> Cn = 1321422108420282270489942177190229544600 ,素数判定：False
n = 71 ---> Cn = 5175569924646105559418940193995065716350 ,素数判定：False
n = 72 ---> Cn = 20276890389709399862928998568254641025700 ,素数判定：False
n = 73 ---> Cn = 79463489365077377841208237632349268884500 ,素数判定：False
n = 74 ---> Cn = 311496878311103321137536291518809134027240 ,素数判定：False
n = 75 ---> Cn = 1221395654430378811828760722007962130791020 ,素数判定：False
n = 76 ---> Cn = 4790408930363303911328386208394864461024520 ,素数判定：False
n = 77 ---> Cn = 18793142726809884575211361279087545193250040 ,素数判定：False
n = 78 ---> Cn = 73745243611532458459690151854647329239335600 ,素数判定：False
n = 79 ---> Cn = 289450081175264899454283846029490767264392230 ,素数判定：False
n = 80 ---> Cn = 1136359577947336271931632877004667456667613940 ,素数判定：False
n = 81 ---> Cn = 4462290049988320482463241297506133183499654740 ,素数判定：False
n = 82 ---> Cn = 17526585015616776834735140517915655636396234280 ,素数判定：False
n = 83 ---> Cn = 68854441132780194707888052034668647142985206100 ,素数判定：False
n = 84 ---> Cn = 270557451039395118028642463289168566420671280440 ,素数判定：False
n = 85 ---> Cn = 1063353702922273835973036658043476458723103404520 ,素数判定：False
n = 86 ---> Cn = 4180080073556524734514695828170907458428751314320 ,素数判定：False
n = 87 ---> Cn = 16435314834665426797069144960762886143367590394940 ,素数判定：False
n = 88 ---> Cn = 64633260585762914370496637486146181462681535261000 ,素数判定：False
n = 89 ---> Cn = 254224158304000796523953440778841647086547372026600 ,素数判定：False
n = 90 ---> Cn = 1000134600800354781929399250536541864362461089950800 ,素数判定：False
n = 91 ---> Cn = 3935312233584004685417853572763349509774031680023800 ,素数判定：False
n = 92 ---> Cn = 15487357822491889407128326963778343232013931127835600 ,素数判定：False
n = 93 ---> Cn = 60960876535340415751462563580829648891969728907438000 ,素数判定：False
n = 94 ---> Cn = 239993345518077005168915776623476723006280827488229600 ,素数判定：False
n = 95 ---> Cn = 944973797977428207852605870454939596837230758234904050 ,素数判定：False
n = 96 ---> Cn = 3721443204405954385563870541379246659709506697378694300 ,素数判定：False
n = 97 ---> Cn = 14657929356129575437016877846657032761712954950899755100 ,素数判定：False
n = 98 ---> Cn = 57743358069601357782187700608042856334020731624756611000 ,素数判定：False
n = 99 ---> Cn = 227508830794229349661819540395688853956041682601541047340 ,素数判定：False
n = 100 ---> Cn = 896519947090131496687170070074100632420837521538745909320 ,素数判定：False
$n = 2, 3$ のとき以外は全て合成数になっていますね.
実は, Catalan数 $C_{n}$ が素数となるのは $n = 2, 3$ のときのみ であることが知られています.
本章ではこの事実を示しましょう.2
まず, $0 \leq n \leq 4$ の範囲において素数となるのは $n = 2, 3$ のときのみであることが上記一覧よりわかります.
そこで, $n \geq 5$ において $C_{n}$ は素数にならないことを背理法で示しましょう.
背理法なので, ある自然数 $n_{0} \geq 5$ が存在して, $C_{n_{0}}$ が素数であると仮定します.
すると 2.2. 節で示した漸化式より,
C_{n_{0} + 1} = \dfrac{4n_{0} + 2}{n_{0} + 2}C_{n_{0}}
となります.
ここで 2.2. 節で示した不等式より $C_{n_{0}} > n_{0} + 2$ であることと $C_{n_{0}}$ が素数である仮定から, $C_{n_{0}}$ と $n_{0} + 2$ は互いに素となります.
よって, $n_{0} + 2$ は $4n_{0} + 2$ を割り切ることになります.
しかしこれは不等式
3(n_{0} + 2) < 4n_{0} + 2 < 4(n_{0} + 2)
が成り立つことに矛盾します.
従って, $5$ 以上の自然数 $n$ に対して $C_{n}$ は素数にならないため, $C_{n}$ が素数となるのは $n = 2, 3$ のときのみであることが示せました.
4. Catalan擬素数とちょっとした展望
本章ではCatalan数が満たすある合同式を紹介し, それをもとにCatalan擬素数を定義します.
また, Catalan擬素数と双子素数の関係について少しだけ触れます.
4.1. 素数とCatalan数が結びつく合同式
ここでは任意の奇素数 $p$ に対して成り立つ次の合同式
(-1)^{\frac{p - 1}{2}}C_{\frac{p - 1}{2}} \equiv 2 \quad (mod. p)
を示します.
任意の自然数 $i$ に対して, $p - i \equiv -i \quad (mod. p)$ が成り立つという自明な事実を用いると,
\begin{align}
(p - 1)! &= \left(p - 1\right)\left(p - 2\right) \cdots \left(p - \dfrac{p - 1}{2}\right)\dfrac{p - 1}{2} \cdots 2 \cdot 1 \\
& \equiv (-1)(-2) \cdots \left(- \dfrac{p - 1}{2}\right)\dfrac{p - 1}{2} \cdots 2 \cdot 1 \quad (mod. p)\\
& = ( - 1)^{\frac{p - 1}{2}}\left\{\left(\dfrac{p - 1}{2}\right)!\right\}^{2}
\end{align}
となります.
これとWilsonの定理 を用いると,
\begin{align}
(-1)^{\frac{p - 1}{2}}C_{\frac{p - 1}{2}} &= (-1)^{\frac{p - 1}{2}}\dfrac{2}{p + 1} \dfrac{(p - 1)!}{\left\{\left(\dfrac{p - 1}{2}\right)!\right\}^{2}} \\
&\equiv \dfrac{2}{p + 1} \quad (mod. p) \\
&\equiv 2 \quad (mod. p)
\end{align}
となって成立します.
4.2. Catalan擬素数と双子素数のかじり
4.1節では全ての奇素数に対して上記の合同式が成り立つことを示しました.
ではもう少し拡張して, 奇数の合成数のうち上記の合成を満たすものはどれくらいあるのでしょうか？
例えば, $1$ ～ $10000$ の間だとどれくらい存在するのでしょうか？
Pythonで簡単に試してみましょう.
ここではCatalan数の導出にはsympyの関数をそのまま使用しています.
from sympy import catalan, isprime
def is_catalan_pseudoprime(n):
"""
引数で指定した自然数が上の合同式を満たすかどうかをチェックする
Parameters
----------
n : int
チェック対象の自然数
Returns
----------
boolean
合同式を満たせばTrue, それ以外はFalse
"""
if n % 2 == 0 or isprime(n):
return False
k = (n - 1) // 2
return (pow(-1, k) * catalan(k)) % n == 2
if __name__ == '__main__':
for n in range(1, 10001, 2):
if is_catalan_pseudoprime(n):
print(n)
5907
どうやら $10000$ 以下で上記合同式を満たす奇数の合成数は $5907$ のみのようです.
一般的に, 上記合同式を満たす奇数の合成数は Catalan擬素数 と呼ばれています.3
現在判明しているCatalan擬素数は $5907$, $ 1194649$, $12327121$ のみです.
Catalan擬素数はかなりレアな数のようですね！
実は, Catalan擬素数はMersenne数や双子素数と関係があります.
例えば, 双子素数の積で書けるCatalan擬素数は存在しないことが知られています.
まだまだCatalan数の数論的性質には魅力がありそうです！
5. おわりに
本記事ではCatalan数について解説を行ってきました.
組み合わせ論でよく取り沙汰されるCatalan数ですが, 素数との絡みもあったりと数論的にもなかなか興味の尽きない対象ですね.
いずれ準備が済めば, 4.2. 節で触れた内容について1記事書きたいと思います.
そのときには是非ご覧くださいね！
参考文献
- Aebi, Christian; Cairns, Grant (2008). "Catalan numbers, primes and twin primes" (PDF). Elemente der Mathematik. 63 (4): 153–164.
- 山本幸一. 順列・組合せと確率. 岩波書店, 2015