文献あり

Dyck路とピークに印を付けたDyck路の数え上げ

120

長さ $2 n$ のDyck路の集合から $n$ 個の $U$ と $n + 1$ 個の $D$ からなるネックレス（高校数学でいう円順列のこと）の集合への全単射を与えます．後者の集合のサイズは容易に求まるので，これにより長さ $2 n$ のDyck路の総数を求めることができます．
また，ピークに印を付けた長さ $2 n$ のDyck路の集合から $n - 1$ 個の $U$ と $n$ 個の $D$ からなるワードの集合への全単射を与え，ピークに印を付けた長さ $2 n$ のDyck路の総数が $(\binom{2 n - 1}{n})$ であることのbijective proofを与えます．

Dyck路とネックレスの対応

Dyck路（Dyck path）

$x y$ 平面における $(0, 0)$ から $(2 n, 0)$ への経路で，各ステップが $U := (1, 1)$ または $D := (1, - 1)$ からなり， $x$ 軸より下を通らないものを長さ $2 n$ のDyck路という．長さ $2 n$ のDyck路には $n$ 個の $U$ と $n$ 個の $D$ からなるワードが自然に対応する．これをDyckワードという．

以下ではDyck路と対応するDyckワードを断りなく同一視します．またDyck路を $w$ で表します．

n = 3

の場合

長さ $6$ のDyck路は以下の $5$ 個である．

それぞれに対応するワードは $U D U D U D$ ， $U D U U D D$ ， $U U D U D D$ ， $U U D D U D$ ， $U U U D D D$ である．

Dyck路のピーク（peak）

Dyck路の $U D$ という形の部分列をピークという．

ネックレス（necklace）

$w, v = a_{1} a_{2} \dots a_{l}$ を二つのワードとする．ただし $a_{1}, a_{2}, \dots, a_{l}$ は文字である．ある巡回置換 $σ \in ⟨ (1, 2, \dots, l) ⟩$ が存在して $w = a_{σ (1)} a_{σ (2)} \dots a_{σ (l)}$ であるとき， $w \sim v$ と定める．この同値関係 $\sim$ により定まるワードの同値類 $[w]$ をネックレスという．

Catalan数（Catalan number）

$n \geq 0$ に対し， $n$ 番目のCatalan数を
$C_{n} = \frac{1}{n + 1} (\binom{2 n}{n})$
で定義する．

Dyck路とネックレスの対応

長さ $2 n$ のDyck路の集合を $D_{n}$ ， $n$ 個の $U$ と $n + 1$ 個の $D$ からなるネックレスの集合を $N_{n}$ ， $n$ 個の $U$ と $n$ 個の $D$ からなるワードの集合を $W_{n}$ とする．
(1) $f_{1} (w) = [w D]$ で定まる写像 $f_{1} : D_{n} \to N_{n}$ は全単射である．
(2) $f_{2} (w) = [w D]$ で定まる写像 $f_{2} : W_{n} \to N_{n}$ は $n + 1$ 対 $1$ である．
(3) $| D_{n} | = | N_{n} | = C_{n} .$

写像 $g_{1} : N_{n} \to D_{n}$ を以下で定める． $[w] \in N_{n}$ とする． $w$ を $x y$ 平面における原点から出発する経路と同一視する． $w$ における $y$ 座標が最も小さい点で最も左にあるものを $P$ とする． $w$ を原点から点 $P$ までの経路 $w_{1} D$ と点 $P$ 以降の経路 $w_{2}$ に分ける．このとき $g_{1} ([w]) = w_{2} w_{1}$ と定める．この写像 $g_{1}$ はwell-definedであり， $f_{1}$ の逆写像となることがわかる．
$n$ 個の $U$ と $n$ 個の $D$ と $1$ 個の $X$ からなるネックレスの集合を $M_{n}$ とする． $g_{2} (w) = [w X]$ で定まる写像 $g_{2} : W_{n} \to M_{n}$ は明らかに全単射である．また $X$ を $D$ へ置き換えることで定まる写像 $g_{3} : M_{n} \to N_{n}$ は明らかに $n + 1$ 対 $1$ である． $f_{2} = g_{3} \circ g_{2}$ より， $f_{2}$ は $n + 1$ 対 $1$ である．
(1)より $| D_{n} | = | N_{n} |$ ．また(2)より $| N_{n} | = \frac{1}{n + 1} | W_{n} | = C_{n}$ ．

ピークに印を付けたDyck路とワードの対応

ピークに印を付けたDyck路

$w$ をDyck路とする． $w$ のあるピーク $U D$ を $U ∙ D$ に置き換えたワードを $\hat{w}$ で表し，ピークに印を付けたDyck路という． $\hat{w}$ は $w$ のある部分列 $w_{1}, w_{2}$ を用いて $\hat{w} = w_{1} U ∙ D w_{2}$ と表すことができる． $\hat{w}$ のピークに印を付けたDyck路としての長さを $w$ の長さで定める．

ピークに印を付けたDyck路 $\hat{w}$ のワードとしての長さは $(w の長さ) + 1$ である．

n = 3

の場合

ピークに印を付けた長さ $6$ のDyck路は以下の $10$ 個である．

ピークに印を付けたDyck路とワードの対応

ピークに印を付けた長さ $2 n$ のDyck路の集合を ${\hat{D}}_{n}$ ， $n - 1$ 個の $U$ と $n$ 個の $D$ からなるワードの集合を $V_{n}$ とする．
(1) $f (w_{1} U ∙ D w_{2}) = w_{2} D w_{1}$ で定まる写像 $f : {\hat{D}}_{n} \to V_{n}$ は全単射である．
(2) $| {\hat{D}}_{n} | = | V_{n} | = (\binom{2 n - 1}{n}) .$

定義5を一般化し， $U$ と $D$ からなるワード $w$ のある部分列 $U D$ を $U ∙ D$ に置き換えたワードを $\hat{w}$ で表し，その同値類 $[\hat{w}]$ をピークに印を付けたネックレスということにする． $n$ 個の $U$ と $n + 1$ 個の $D$ からなるピークに印を付けたネックレスの集合を ${\hat{N}}_{n}$ とする．定理1(1)の全単射 $f_{1}$ は，Dyck路のピークとネックレスのピークの $1$ 対 $1$ 対応を与えるから， $g (w_{1} U ∙ D w_{2}) = [w_{1} U ∙ D w_{2} D]$ で定まる写像 $g : {\hat{D}}_{n} \to {\hat{N}}_{n}$ は全単射である．一方 $h ([w_{1} U ∙ D w_{2}]) = w_{2} w_{1}$ で定まる写像 $h : {\hat{N}}_{n} \to V_{n}$ は明らかにwell-definedかつ全単射である． $f = h \circ g$ より， $f$ は全単射である．
(1)より $| {\hat{D}}_{n} | = | V_{n} |$ ．また $| V_{n} | = (\binom{2 n - 1}{n})$ は明らかである．