「括弧の正しい組み合わせは何通り？」「凸多角形を三角形に分ける方法は？」「格子を対角線を超えずに進む経路は？」
一見バラバラに見えるこれらの問題、実は全て同じ答えになることをご存知ですか？
その答えがカタラン数（Catalan number）です。
カタラン数は、組合せ論において最も重要で美しい数列の一つで、驚くほど多くの場面に登場します。
今回は、このカタラン数について、定義から具体例、性質、応用まで、分かりやすく解説していきます。
カタラン数とは？
定義
カタラン数（Catalan number）とは、次の式で定義される自然数の数列です。
Cₙ = (1/(n+1)) × ₂ₙCₙ = (2n)! / ((n+1)! × n!)
ここで、₂ₙCₙは「2n個からn個を選ぶ組合せの数」（二項係数）です。
数列の具体例
最初のいくつかのカタラン数を計算してみましょう。
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, …
- C₀ = 1
- C₁ = 1
- C₂ = 2
- C₃ = 5
- C₄ = 14
- C₅ = 42
- C₆ = 132
- C₇ = 429
- C₈ = 1430
例えば、C₃を実際に計算すると：
C₃ = (1/(3+1)) × ₆C₃
= (1/4) × (6×5×4)/(3×2×1)
= (1/4) × 20
= 5
もう一つの表式
カタラン数は、次のようにも表せます。
Cₙ = ₂ₙCₙ – ₂ₙCₙ₊₁
つまり、「2n個からn個選ぶ」方法から「2n個からn+1個選ぶ」方法を引いたものです。
この式から、カタラン数が必ず整数になることが分かります。
カタラン数の名前の由来
ウジェーヌ・カタラン
カタラン数は、ベルギーの数学者ウジェーヌ・シャルル・カタラン（Eugène Charles Catalan, 1814-1894）に因んで名付けられました。
カタランは、19世紀にこの数列の性質を体系的に研究しました。
実はオイラーが先に発見
実は、カタラン数はカタランよりも約100年前の18世紀に、スイスの数学者レオンハルト・オイラー（Leonhard Euler, 1707-1783）やヨハン・アンドレアス・フォン・ゼーグナー（Johann Andreas von Segner, 1704-1777）によって発見されていました。
彼らは、凸多角形を三角形に分割する方法の数を求める際に、この数列に出会いました。
しかし、カタランがより詳しく研究したため、彼の名前が付けられています。
カタラン数の漸化式
カタラン数には、美しい漸化式（再帰的関係式）があります。
基本的な漸化式
C₀ = 1
Cₙ₊₁ = Σ(i=0からnまで) Cᵢ × Cₙ₋ᵢ
つまり、
Cₙ₊₁ = C₀×Cₙ + C₁×Cₙ₋₁ + C₂×Cₙ₋₂ + … + Cₙ×C₀
漸化式の使用例
この漸化式を使って、順番にカタラン数を計算してみましょう。
C₀ = 1（定義）
C₁ = C₀×C₀ = 1×1 = 1
C₂ = C₀×C₁ + C₁×C₀ = 1×1 + 1×1 = 2
C₃ = C₀×C₂ + C₁×C₁ + C₂×C₀
= 1×2 + 1×1 + 2×1 = 5
C₄ = C₀×C₃ + C₁×C₂ + C₂×C₁ + C₃×C₀
= 1×5 + 1×2 + 2×1 + 5×1 = 14
このように、前の値を使って次の値を計算できます。
もう一つの漸化式
カタラン数には、次のような漸化式もあります。
Cₙ₊₁ = (2(2n+1)/(n+2)) × Cₙ
これを使えば、一つ前のカタラン数から直接計算できます。
例：
- C₄ = (2×7/5) × C₃ = (14/5) × 5 = 14 ✓
- C₅ = (2×9/6) × C₄ = 3 × 14 = 42 ✓
カタラン数が現れる問題【具体例】
カタラン数の最大の魅力は、一見無関係に見える様々な問題で同じ答えとして現れることです。
ここでは、代表的な例を詳しく見ていきます。
例1：正しい括弧の組み合わせ
問題：n組の括弧 () を正しく並べる方法は何通りあるか？
「正しく並べる」とは、開き括弧と閉じ括弧が対応していて、順序も正しいことを意味します。
n = 3の場合（答え：C₃ = 5通り）
- ((()))
- (()())
- (())()
- ()(())
- ()()()
不正な例
- ())(() ← 閉じ括弧が先に来ている
- (()(() ← 括弧が対応していない
これらは数に含まれません。
一般に、n組の括弧を正しく並べる方法はCₙ通りです。
例2：格子経路問題（最も重要）
問題：n×n の格子上で、左下(0,0)から右上(n,n)まで、右(→)と上(↑)だけで進み、かつ対角線y=xより下に出ない経路は何通りあるか？
n = 3の場合（答え：C₃ = 5通り）
↑↑↑→→→
↑↑→↑→→
↑↑→→↑→
↑→↑↑→→
↑→↑→↑→重要なポイント
対角線より下に出る（つまり、ある時点で右への移動数が上への移動数を上回る）経路は数えません。
この条件は、「常にy ≥ x」と同じ意味です。
一般に、n×n格子上でこの条件を満たす経路はCₙ通りです。
例3：二分木の数
問題：n個の内部ノード（分岐点）を持つ二分木は何通りあるか？
別の表現：n+1個の葉（端点）を持つ完全二分木は何通りあるか？
n = 3の場合（答え：C₃ = 5通り）
○ ○ ○ ○ ○
/ \ / \ / \ / \ / \
○ ○ ○ ○ ○ ○ ○ ○ ○ ○
/ \ / \ / \ / \ / \
○ ○ ○ ○ ○ ○ ○ ○ ○ ○一般に、n個の内部ノードを持つ二分木の数はCₙ通りです。
例4：多角形の三角形分割
問題：n+2個の頂点を持つ凸多角形を、頂点を結ぶ線で三角形に分割する方法は何通りあるか？（線は交差しない）
n = 3の場合：5角形の分割（答え：C₃ = 5通り）
五角形ABCDEを考えると：
- ACとADで分割
- ACとCEで分割
- ADとBDで分割
- BDとBEで分割
- CEとBEで分割
一般に、n+2角形の三角形分割の方法はCₙ通りです。
例5：トーナメント表の場合の数
問題：n+1チームによる勝ち抜き戦（トーナメント）の組み方は何通りあるか？
n = 2の場合：3チーム（答え：C₂ = 2通り）
パターン1： パターン2：
決勝 決勝
/ \ / \
A B-C A-B Cn = 3の場合：4チーム（答え：C₃ = 5通り）
トーナメント表の構成方法が5通りあります。
一般に、n+1チームのトーナメント表の組み方はCₙ通りです。
例6：演算の結合順序
問題：n+1個の数に対してn回の二項演算を適用する順序は何通りあるか？
n = 3の場合：4つの数a, b, c, dに3回の乗算（答え：C₃ = 5通り）
- (((ab)c)d)
- ((a(bc))d)
- ((ab)(cd))
- (a((bc)d))
- (a(b(cd)))
これは括弧の付け方の問題と同じです。
一般に、n+1個の因数にn回の演算を適用する結合方法はCₙ通りです。
例7：円周上の点を結ぶ弦
問題：円周上に2n個の点があるとき、これらをn本の交わらない弦で結ぶ方法は何通りあるか？
n = 2の場合：4点をペアにする（答え：C₂ = 2通り）
点A, B, C, Dを円周上に配置したとき：
- A-BとC-Dを結ぶ
- A-DとB-Cを結ぶ
（A-CとB-Dは交差するのでNG）
一般に、2n個の点をn本の交わらない弦で結ぶ方法はCₙ通りです。
例8：山の描き方
問題：n回の上り坂「/」とn回の下り坂「\」で、地平線より下に行かない山を描く方法は何通りあるか？
n = 3の場合（答え：C₃ = 5通り）
1. /\/\/\
2. /\\/\
3. /\/\
4. //\\/\
5. //\\一般に、このような山の描き方はCₙ通りです。
カタラン数の証明【格子経路問題から】
ここでは、格子経路問題を使ってカタラン数の一般項を証明します。
問題の設定
n×n格子上で、(0,0)から(n,n)まで、対角線y=xより下に出ない経路の数を求めます。
ステップ1：全経路数
まず、(0,0)から(n,n)までの全経路数（対角線を無視）を計算します。
右にn回、上にn回の合計2n回の移動なので：
全経路数 = ₂ₙCₙ
ステップ2：不適な経路数（対角線を超える経路）
対角線を超える経路（つまり、ある時点でy < x となる経路）の数を求めます。
重要なテクニック：折り返し法
対角線を超える経路は、必ず直線y = x + 1上のどこかを通ります。
この直線上を初めて通る点をPとします。
点P以降の経路を、直線y = x + 1に関して折り返し（鏡像反転）します。
すると、この経路は(0,0)から(n-1, n+1)への経路に変換されます。
逆に、(0,0)から(n-1, n+1)への任意の経路は、直線y = x + 1で折り返すことで、対角線を超える経路に戻せます。
つまり、対角線を超える経路の数 = (0,0)から(n-1, n+1)への経路数
(0,0)から(n-1, n+1)へは、右にn-1回、上にn+1回なので：
不適な経路数 = ₂ₙCₙ₋₁
ステップ3：カタラン数の公式
Cₙ = (全経路数) – (不適な経路数)
Cₙ = ₂ₙCₙ – ₂ₙCₙ₋₁
これを展開すると：
Cₙ = (2n)!/(n!×n!) – (2n)!/((n-1)!×(n+1)!)
= (2n)!/(n!×(n-1)!) × (1/n – 1/(n+1))
= (2n)!/(n!×(n-1)!) × ((n+1-n)/(n(n+1)))
= (2n)!/(n!×(n-1)!) × 1/(n(n+1))
= (2n)!/((n+1)!×n!)
∴ Cₙ = (1/(n+1)) × ₂ₙCₙ
これが、カタラン数の一般項です！
カタラン数の性質
カタラン数には、興味深い性質がたくさんあります。
性質1：奇数と偶数
Cₙが奇数になるのは、n = 2^k – 1（メルセンヌ数）の形の時だけです。
つまり、n = 0, 1, 3, 7, 15, 31, 63, 127, …
- C₀ = 1（奇数）
- C₁ = 1（奇数）
- C₂ = 2（偶数）
- C₃ = 5（奇数）← 3 = 2² – 1
- C₄ = 14（偶数）
- C₅ = 42（偶数）
- C₆ = 132（偶数）
- C₇ = 429（奇数）← 7 = 2³ – 1
それ以外のnでは、Cₙは偶数になります。
性質2：素数判定
C₂以外のカタラン数で素数になるものはありません。
実際、Cₙの素因数はすべてn未満の素数です。
例外：
- C₂ = 2（素数）
それ以外：
- C₀ = 1（素数ではない）
- C₁ = 1（素数ではない）
- C₃ = 5（素数）
- C₄ = 14 = 2 × 7（合成数）
- C₅ = 42 = 2 × 3 × 7（合成数）
実は、C₃ = 5とC₂ = 2だけがカタラン素数です。
性質3：末尾の数字（奇数の場合）
奇数のカタラン数（n = 2^k – 1）の末尾の数字には規則があります。
- C₀ = 1 → 末尾1
- C₁ = 1 → 末尾1
- C₃ = 5 → 末尾5
- C₇ = 429 → 末尾9
- C₁₅ = 9694845 → 末尾5
n+1を5進数で表したときに0, 1, 2のみを含む場合を除き、末尾は5になります。
性質4：成長率（漸近挙動）
nが大きいとき、カタラン数は次のように近似できます。
Cₙ ≈ 4ⁿ / (n^(3/2) × √π)
これはスターリングの公式を使って証明できます。
つまり、カタラン数は約4ⁿに比例して急速に増加します。
性質5：生成関数
カタラン数の生成関数は：
Σ(n=0 to ∞) Cₙ × xⁿ = (1 – √(1-4x)) / (2x)
この式から、様々な性質を導けます。
カタラン数の計算方法
方法1：一般項を使う
Cₙ = (1/(n+1)) × (2n)! / (n! × n!)
例：C₅を計算
C₅ = (1/6) × 10! / (5! × 5!)
= (1/6) × 3628800 / (120 × 120)
= (1/6) × 3628800 / 14400
= (1/6) × 252
= 42
方法2：漸化式を使う（動的計画法）
def catalan(n):
if n <= 1:
return 1
cat = [0] * (n + 1)
cat[0] = cat[1] = 1
for i in range(2, n + 1):
for j in range(i):
cat[i] += cat[j] * cat[i-1-j]
return cat[n]
# 使用例
print(catalan(5)) # 42方法3：簡単な漸化式を使う
Cₙ₊₁ = (2(2n+1)/(n+2)) × Cₙ
def catalan_simple(n):
if n == 0:
return 1
c = 1
for i in range(n):
c = c * 2 * (2*i + 1) // (i + 2)
return c
# 使用例
print(catalan_simple(5)) # 42計算量の比較
- 方法1（一般項）：O(n)（階乗計算）
- 方法2（漸化式）：O(n²)
- 方法3（簡単な漸化式）：O(n)
実用的には、方法3が最も効率的です。
カタラン数の応用
カタラン数は、理論的な興味だけでなく、実用的な応用もあります。
1. コンピュータサイエンス
構文解析（パーサ）
プログラミング言語の構文解析では、正しい括弧の組み合わせを判定する必要があります。
これはカタラン数の問題と直結しています。
二分探索木（BST）の数え上げ
n個のキーを持つ二分探索木の数はCₙです。
これは、データ構造の設計や最適化に役立ちます。
2. 組合せ最適化
行列連鎖乗算問題
n+1個の行列を掛け合わせる順序の数はCₙです。
最適な順序を見つけることで、計算コストを最小化できます。
3. 確率論
投票問題（Ballot problem）
選挙で候補Aがn票、候補Bがm票（n > m）を得たとき、開票の全過程でAが常にリードしている確率は：
(n – m + 1) / (n + 1)
n = mの場合、常に同点以上である場合の数はCₙです。
4. グラフ理論
平面グラフの数え上げ
特定の条件を満たす平面グラフの数を数える際に、カタラン数が現れます。
5. 暗号理論
最近の研究では、カタラン数を使った疑似乱数生成や、テキスト暗号化の手法が提案されています。
カタラン数の分解や組合せを暗号鍵として利用します。
6. バイオインフォマティクス
顔認証などの生体認証技術で、多角形の三角形分割アルゴリズム（カタラン数ベース）が使われています。
カタラン数の一般化
カタラン数には、いくつかの一般化があります。
1. Fuss-Catalan数
Cₙ^(p) = (1/((p-1)n+1)) × ₚₙCₙ
p = 2の場合が通常のカタラン数です。
p = 3の場合：三分木の数を数えます。
2. q-Catalan数
量子群の表現論で現れる一般化です。
通常のカタラン数をq-類似に拡張したものです。
3. Super Catalan数
S(m, n) = (2m)!(2n)! / (m!(m+n)!n!)
m = nの場合、特別な性質を持ちます。
カタラン数の豊富な解釈
カタラン数の最も驚くべき性質は、無数の異なる組合せ問題で同じ答えとして現れることです。
Stanley’s Exerciseが示す多様性
組合せ論の専門家Richard P. Stanleyの著書『Enumerative Combinatorics: Volume 2』では、66通りの異なる解釈が紹介されています。
さらに、2009年の時点で170通り以上の解釈が知られています！
主な解釈のカテゴリー
- 経路問題：格子経路、ダイク経路、山の描画
- 木構造：二分木、完全木、planted tree
- 括弧問題：正しい括弧の組み合わせ、ダイク語
- 幾何問題：多角形分割、非交差弦
- 順列問題：特定のパターンを避ける順列
- 代数問題：演算の結合順序
- スタック問題：スタックソート可能な順列
これらすべてが、同じカタラン数という答えを持つのです。
カタラン数の歴史的背景
オイラーとゼーグナー（18世紀）
1751年、ゼーグナーが凸多角形の三角形分割問題を提起しました。
1759年、オイラーがこの問題を解き、カタラン数を初めて発見しました。
オイラーは再帰的な方法でこの数列を求めました。
カタランの貢献（19世紀）
1838年、ウジェーヌ・カタランが括弧の組み合わせ問題を研究し、この数列の性質を体系的に調べました。
カタランは、一般項の公式を導き、様々な性質を明らかにしました。
現代の研究（20世紀以降）
20世紀に入り、組合せ論が発展すると、カタラン数が多くの問題に現れることが分かってきました。
1970年代：Richard Stanleyらが、カタラン数の様々な解釈を体系化
1980年代以降：コンピュータサイエンスでの応用が広がる
現在：暗号理論、量子情報など、新しい分野でも応用が研究されています
カタラン数を実際に使ってみよう
問題1：括弧の組み合わせを全列挙
課題：n=3の場合の正しい括弧の組み合わせを全て出力するプログラムを書いてみましょう。
def generate_parentheses(n):
def backtrack(s, left, right):
if len(s) == 2 * n:
result.append(s)
return
if left < n:
backtrack(s + '(', left + 1, right)
if right < left:
backtrack(s + ')', left, right + 1)
result = []
backtrack('', 0, 0)
return result
# 使用例
print(generate_parentheses(3))
# ['((()))', '(()())', '(())()', '()(())', '()()()']問題2：格子経路の数を計算
課題：n×n格子で対角線を超えない経路の数を、実際に数え上げて確認してみましょう。
def count_paths(n):
# 動的計画法で経路数を計算
dp = [[0] * (n + 1) for _ in range(n + 1)]
# 対角線上とその上側のみ計算
for i in range(n + 1):
for j in range(i, n + 1):
if i == 0 and j == 0:
dp[0][0] = 1
else:
if i > 0:
dp[i][j] += dp[i-1][j]
if j > 0:
dp[i][j] += dp[i][j-1]
return dp[n][n]
# 使用例
for n in range(6):
print(f"C_{n} = {count_paths(n)}")
# C_0 = 1
# C_1 = 1
# C_2 = 2
# C_3 = 5
# C_4 = 14
# C_5 = 42問題3：二分木の生成
課題：n個のノードを持つ全ての二分木を生成してみましょう。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def generate_trees(n):
if n == 0:
return [None]
def build_trees(start, end):
trees = []
if start > end:
return [None]
for i in range(start, end + 1):
left_trees = build_trees(start, i - 1)
right_trees = build_trees(i + 1, end)
for left in left_trees:
for right in right_trees:
root = TreeNode(i)
root.left = left
root.right = right
trees.append(root)
return trees
return build_trees(1, n)
# 使用例
trees = generate_trees(3)
print(f"3個のノードで作れる二分木の数: {len(trees)}")
# 3個のノードで作れる二分木の数: 5カタラン数に関する面白い問題
問題1：500円玉と1000円札
n人が500円玉を持ち、n人が1000円札を持って、500円の商品を買うため列に並んでいます。店員は最初おつりを持っていません。全員が商品を買えるような並び方は何通りあるでしょうか？
答え：Cₙ通り
これは、「500円玉の人」を「上への移動」、「1000円札の人」を「右への移動」に対応させると、格子経路問題と同じになります。
常に「500円玉の人の数 ≥ 1000円札の人の数」である必要があります。
問題2：トランプの山分け
2n枚のカードを、左右2つの山に分けます。
ただし、左の山のカード枚数が常に右の山のカード枚数以上になるように、1枚ずつ分けていきます。分け方は何通りあるでしょうか？
答え：Cₙ通り
左の山に置くことを「上」、右の山に置くことを「右」とすれば、格子経路問題になります。
まとめ
カタラン数について、詳しく見てきました。
カタラン数の定義
Cₙ = (1/(n+1)) × ₂ₙCₙ = (2n)! / ((n+1)! × n!)
数列：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …
漸化式
C₀ = 1
Cₙ₊₁ = Σ(i=0からn) Cᵢ × Cₙ₋ᵢ
または
Cₙ₊₁ = (2(2n+1)/(n+2)) × Cₙ
主な応用（一部）
- 正しい括弧の組み合わせの数
- 格子経路（対角線を超えない）の数
- 二分木の数
- 多角形の三角形分割の数
- トーナメント表の組み方
- 演算の結合順序の数
重要な性質
- Cₙが奇数 ⟺ n = 2^k – 1（メルセンヌ数）
- カタラン素数は C₂ = 2 と C₃ = 5 のみ
- 成長率：Cₙ ≈ 4ⁿ / (n^(3/2) × √π)
- 170通り以上の異なる組合せ問題で同じ答えとして現れる
歴史
- 18世紀：オイラーとゼーグナーが発見
- 19世紀：カタランが体系的に研究
- 現代：コンピュータサイエンス、暗号理論など幅広い分野で応用
カタラン数の魅力
カタラン数の最大の魅力は、全く異なる問題が同じ答えを持つという驚きです。
括弧の問題も、経路の問題も、木の問題も、全て同じカタラン数という答えになる。
これは、数学の美しさと深さを示す素晴らしい例です。
コメント