カタラン数と格子経路 ― 反射原理と全単射証明

カタラン数$C_n = \frac{1}{n+1}\binom{2n}{n}$の反射原理による証明，LGV公式，5つの組合せ的解釈の全単射構成，バロット問題，Narayana数を扱う．

2026年2月27日

1 格子経路と二項係数

定義 1 (格子経路).

Z^{2}

上の点

(a, b)

から

(c, d)

への格子経路（lattice path）とは，各ステップが右

(1, 0)

または上

(0, 1)

の移動である経路のことをいう．

定理 2.

(0, 0)

から

(m, n)

への格子経路の総数は

(m m + n)

である．

証明.

全体で

m + n

ステップのうち右方向に進む

m

ステップを選べばよいので

(m m + n)

通りである． □

2 反射原理とカタラン数

定義 3 (Dyck 経路).

(0, 0)

から

(2 n, 0)

への格子経路で，ステップが

(1, 1)

（上昇）と

(1, - 1)

（下降）であり，

y \geq 0

を常に満たすものをDyck 経路（Dyck path）という．

定理 4.

n

ステップの上昇と

n

ステップの下降からなる Dyck 経路の個数は

C_{n} = \frac{1}{n + 1} (n 2 n)

である．

証明.

(0, 0)

から

(2 n, 0)

への経路で上昇

n

回，下降

n

回のものの総数は

(n 2 n)

．このうち

y < 0

に達する「悪い」経路の数を求め差し引く．

反射原理（André

y = - 1

に初めて到達する点を持つ．その点以降の経路を

y = - 1

に関して反射すると，

(0, 0)

から

(2 n, - 2)

への経路と1対1に対応する．この経路は上昇

n - 1

回，下降

n + 1

回からなるので，その個数は

(n - 1 2 n)

．

よって Dyck 経路の数は

(n 2 n) - (n - 1 2 n) = (n 2 n) - \frac{n}{n + 1} (n 2 n) = \frac{1}{n + 1} (n 2 n) = C_{n}

□

3 LGV 公式

定理 5 (Lindstr\"om–Gessel–Viennot 公式).

有向非巡回グラフにおいて，始点の組

(s_{1}, \dots, s_{n})

と終点の組

(t_{1}, \dots, t_{n})

が与えられたとき，頂点を共有しない

n

本の道の組の（符号付き）個数は

det (e (s_{i}, t_{j}))_{1 \leq i, j \leq n}

で与えられる．ここで

e (s, t)

は

s

から

t

への道の本数である．

証明.

行列式を展開すると

\sum_{σ \in S_{n}} sgn (σ) \prod_{i = 1}^{n} e (s_{i}, t_{σ (i)})

となる．各

σ

に対して

s_{i}

から

t_{σ (i)}

への道の組を考える．道が交差する（頂点を共有する）組は，交差点で道を入れ替える操作によって別の

σ^{'}

と対になり，

sgn (σ)

と

sgn (σ^{'})

が逆符号であるため相殺する．残るのは頂点を共有しない道の組のみであり，これは

σ = id

（平面的な条件の下）に対応する． □

4 カタラン数の5つの解釈

定理 6.

以下の5つの対象はすべて

C_{n}

個存在し，互いに全単射で結ばれる：

$n$ 対の括弧の正しい対応（well-formed parentheses）
$n + 1$ 個の葉を持つ full binary tree の個数
$(0, 0)$ から $(n, n)$ への格子経路で対角線 $y = x$ を越えないもの
${1, 2, \dots, n}$ の非交差分割（non-crossing partition）の個数（ただし適切に解釈する場合）
凸 $(n + 2)$ 角形の三角形分割（triangulation）の個数

証明.

(1) と Dyck 経路の全単射：「(」を上昇ステップ，「)」を下降ステップに対応させる．正しい括弧列は

y \geq 0

の条件と同値である．

(2) と Dyck 経路の全単射：

n + 1

個の葉を持つ full binary tree の各内部ノードを左の子への移動（上昇）と右の子への移動（下降）に対応させると，木の深さ優先走査が Dyck 経路を定める．逆に，Dyck 経路の各上昇を左の子，各下降を右の子と読めば full binary tree が復元される．

(3) と Dyck 経路の全単射：

(0, 0)

から

(n, n)

への経路で

y \leq x

（対角線以下）のものは，右ステップを上昇，上ステップを下降と読み替えれば Dyck 経路に一致する．

(4) と Dyck 経路の全単射：

{1, 2, \dots, n}

の非交差分割において，各ブロックを構成する元を左から順に走査し，ブロックの開始を上昇，終了を下降に対応させると Dyck 経路が得られる．非交差条件が

y \geq 0

の条件に対応する．

(5) の証明は帰納法による：凸

(n + 2)

角形の1辺を固定し，その辺を含む三角形の選び方で場合分けすると漸化式

C_{n} = \sum_{k = 0}^{n - 1} C_{k} C_{n - 1 - k}

が得られ，カタラン数の漸化式に一致する． □

5 バロット問題

定理 7 (バロット問題).

候補

A

が

a

票，候補

B

が

b

票を獲得し

a > b

であるとき，開票の全過程で常に

A

が

B

をリードしている確率は

(a - b) / (a + b)

である．

証明.

(0, 0)

から

(a + b, a - b)

へのステップ

(1, 1)

（

A

に投票）と

(1, - 1)

（

B

に投票）の経路のうち，

y > 0

（常にリード）を満たすものの数を求める．反射原理を用いると，

y \leq 0

に到達する経路は

(0, 0)

から

(a + b, - (a - b) - 2 + 2) = (a + b, b - a + 2)

等の反射と対応する．最終的に条件を満たす経路の割合が

(a - b) / (a + b)

であることが示される． □

6 Narayana 数

定義 8 (Narayana 数).

N (n, k) = \frac{1}{n} (k n) (k - 1 n)

をNarayana 数という．

N (n, k)

はちょうど

k

個の山（peak）を持つ Dyck 経路の個数に等しい．

定理 9.

k = 1 \sum n N (n, k) = C_{n}

証明.

Dyck 経路を山の数で分類すれば，すべての Dyck 経路の総数はカタラン数であるから，

\sum_{k = 1}^{n} N (n, k) = C_{n}

が成り立つ． □

Narayana 数はカタラン数の精密化（refinement）であり， $q$ -アナログを考えることで $q$ -カタラン数や Carlitz $q$ -Narayana 数に拡張される．

カタラン数と格子経路 ― 反射原理と全単射証明

1 格子経路と二項係数

2 反射原理とカタラン数

3 LGV 公式

4 カタラン数の5つの解釈

5 バロット問題

6 Narayana 数

関連する「教科書の行間」記事

Share your expertise with the world

More from Folio公式

Folio LaTeXの基本 ― 標準LaTeXとの違いと始め方

カタラン数はなぜどこにでも現れるのか ― 括弧列・二分木・格子経路の不思議な一致

漸化式と母関数 ― 数列を「関数」にすると何が見えるか

包除原理はなぜ「足して引いて」を繰り返すのか ― ベン図からメビウス関数へ