文献あり

二色Circular ladder graphとカタラン数

この記事でいうCircular ladder graph [1]とは，下図のようなグラフである．
$2 n$ 個の節点からなるCircular ladder graphを ${C L}_{n}$ とかく．
!FORMULA[2][623946087][0] ${C L}_{3}, {C L}_{4}, {C L}_{5}, \dots$

ふつうCircular ladder graphというと，上図のような形の無向グラフのことをいう．この記事では話の都合上，図のように枝に向きがついているものを考える．

Circular ladder graph ${C L}_{n}$ の $2 n$ 個の節点を， $n - 1$ 個の白色と $n + 1$ 個の黒色で塗り分けることを考える．
!FORMULA[7][-1105156488][0]の塗り方の例．図が煩雑になるのを避けるために枝の向きは省略した． ${C L}_{7}$ の塗り方の例．図が煩雑になるのを避けるために枝の向きは省略した．

回転することで互いに同じなる塗り方を，同値な塗り方と呼び，同値でない塗り方が何通りあるかを調べることにする．
本記事では以下の定理を示す．

グラフ ${C L}_{n}$ の $2 n$ 個の節点を， $n - 1$ 個の白色と $n + 1$ 個の黒色で塗り分ける同値でない塗り方の数は，カタラン数つまり
$\frac{1}{n + 1} (\binom{2 n}{n})$
通りである．

より正確に述べるために「 ${C L}_{n}$ の節点を塗り分ける同値でない塗り方」を巡回群の作用を使って以下のように言い換える．

集合 $X_{n}$ を， $n + 1$ 個の $+ 1$ と $n - 1$ 個の $- 1$ が書かれた二行配列の集合と定義する．つまり，
$\begin{array}{r} X_{n} ≜ {(\begin{array}{ccc} w_{1, 1} & \dots & w_{1, n} \\ w_{2, 1} & \dots & w_{2, n} \end{array}) | w_{1, 1}, \dots, w_{2, n} は n + 1 個の (+ 1) と n - 1 個の (- 1) からなる．} \end{array}$
と定める．
巡回群 $C_{n} ≜ ⟨ a ∣ a^{n} ⟩$ の $X_{n}$ への作用を
$\begin{array}{r} a \cdot (\begin{array}{cccc} w_{1, 1} & w_{1, 2} & \dots & w_{1, n} \\ w_{2, 1} & w_{2, 2} & \dots & w_{2, n} \end{array}) ≜ (\begin{array}{cccc} w_{1, 2} & \dots & w_{1, n} & w_{1, 1} \\ w_{2, 2} & \dots & w_{2, n} & w_{2, 1} \end{array}) \end{array}$
により定める．上でグラフを使って定義した「 ${C L}_{n}$ の節点を塗り分ける同値でない塗り方」は，この作用による軌道と同一視できる．

定理1の証明

二行配列 $w \in X_{n}$ の高さ列 $h (w) = (h_{0}, h_{1}, \dots, h_{n}) \in Z^{n + 1}$ を，

$h_{0} ≜ 0$ ,
$h_{i + 1} ≜ h_{i} + (w_{1, i + 1} + w_{2, i + 1}) / 2 (i = 0, 1, \dots, n - 1)$

により定める．高さ列の要素が，最初の要素 $h_{0}$ を除いて全て正であるとき，その二行配列はdominatingであるという．
以下が成り立つ．

Cycle ladder graph版のcycle lemma

任意の $w \in X_{n}$ に対して，それを含む軌道 $C_{n} w$ の元であってdominatingであるものが唯一つ存在する．

二行配列 $w$ の高さ列を $h (w) = (h_{0} (w), \dots, h_{n} (w))$ とする．
ここで添字 $i (0 \leq i \leq n)$ を， $i \in {a r g m i n}_{0 \leq i \leq n} h_{i} (w)$ かつ， $i < j$ なる全ての $j (j \leq n)$ に対して $h_{i} < h_{j}$ であるような唯一の $i$ ととる．

二重配列 $\tilde{w}$ を $\tilde{w} ≜ a^{i} \cdot w$ と定める．以下，
(1) この二重配列 $\tilde{w}$ がdominatingであることと，
(2) 軌道 $C_{n} w$ に含まれる $\tilde{w}$ 以外の二重配列はdominatingでないこと
を示す．

(1): $h_{i} (w) = k$ とする．添字 $i$ の決め方から， $h_{i + 1} (w), \dots, h_{n} (w)$ は $k$ より大きい．よって， $\tilde{w}$ の高さ列 $h (\tilde{w}) = (h_{0} (\tilde{w}), \dots, h_{n} (\tilde{w}))$ において， $h_{1} (\tilde{w}), \dots, h_{n - i} (\tilde{w})$ は $0$ より大きい．

また， $h_{n - i} (\tilde{w}) = - k + 1$ であることと， $h_{0} (w), \dots, h_{i - 1} (w)$ が $k$ 以上なことから， $h_{n - i + 1} (\tilde{w}), \dots, h_{n} (\tilde{w})$ も $0$ より大きい．以上から， $\tilde{w}$ はdominatingである．

(2): $j \neq i (0 \leq j \leq n - 1)$ のとき， $a^{j} \cdot w$ はdominatingではないことを示す．まず $j < i$ のとき， $i$ の選び方から $h_{i - j} (a^{j} \cdot w) \leq 0$ となるから， $a^{j} \cdot w$ はdominatingではない．次に $i < j$ のとき． $h_{i} (w) = k$ とし， $h_{j} (w) = r (r > k)$ とする．すると， $h_{n - j} (a^{j} \cdot w) = - r + 1$ である．よって $h_{n - j + i} (a^{j} \cdot w) = - r + 1 + k < 1$ ．よって $a^{j} \cdot w$ はdominatingではない．

補足：Cycle lemmaと呼ばれる定理は色々なバージョンがあり [2,3]，上の補題とその証明は他のバーションのcycle lemmaとほとんど同じである．

補題2より，集合 $X_{n}$ に含まれるdominatingな二行配列は，軌道あるいは言い換えると「 ${C L}_{n}$ の節点を塗り分ける同値でない方法」と一対一対応する．

次に，集合 $X_{n}$ に含まれるdominatingな二行配列と，カタラン数で数えられるオブジェクトの間の一対一対応を作る．

二色Motzkin路 [4]とは，四つの基本ステップ
$A ≜ (1, 1), B = \tilde{B} ≜ (1, 0), C ≜ (1, - 1),$
よりなる上半平面上のパスである．
点 $(0, 0)$ から点 $(0, n)$ まで行く二色Motzkin路の集合を $M o t (n)$ とかく．
!FORMULA[77][-260848016][0]の元の例． $M o t (6)$ の元の例．

二色Motzkin路のうち，ステップ $B, \tilde{B}$ を使わないものをDyck路という．集合 $M o t (2 n)$ に含まれるDyck路の集合を $D y c k (n)$ とかく．以下のことが知られている [4]．

任意の自然数 $n$ について，集合 $M o t (n - 1)$ と集合 $D y c k (n)$ の間に一対一対応が存在する．

補題3は有名なので，ここでは図で対応の例を挙げるだけにとどめる．
(上)一対一対応の作り方． (下)この方法で一対一対応する!FORMULA[84][-182755916][0]と!FORMULA[85][-379933206][0]の元の例． (上)一対一対応の作り方． (下)この方法で一対一対応する $M o t (6)$ と $D y c k (7)$ の元の例．
よく知られているように（例えば[4]を参照）
$\begin{array}{r} # D y c k (n) = \frac{1}{n + 1} (\binom{2 n}{n}) \end{array}$
なので，補題3から
$\begin{array}{r} # M o t (n - 1) = \frac{1}{n + 1} (\binom{2 n}{n}) \end{array}$
がわかる．

最後に，集合 $X_{n}$ に含まれるdominatingな二行配列の集合と， $M o t (n - 1)$ との間に一対一対応を作ることで，証明が完了する．

集合 $X_{n}$ に含まれるdominatingな二行配列の集合と，集合 $M o t (n - 1)$ との間に一対一対応が存在する．

dominatingな二行配列
$\begin{array}{r} (\begin{array}{ccc} w_{1, 1} & \dots & w_{1, n} \\ w_{2, 1} & \dots & w_{2, n} \end{array}) \end{array}$
が与えられたとする．dominatingという条件から一列目は必ず
$\begin{array}{r} (\begin{array}{c} w_{1, 1} \\ w_{2, 1} \end{array}) = (\begin{array}{c} + 1 \\ + 1 \end{array}) \end{array}$
である．二列目以降， $i$ 列目の情報 $(w_{1, i} w_{2, i})^{T}$ から，二色Motzkin路の $i - 1$ 番目のステップを決める．
二行配列の $i$ 列目が $(+ 1 + 1)^{T}, (+ 1 - 1)^{T}, (- 1 + 1)^{T}, (- 1 - 1)^{T}$ のとき，それぞれ二色Motzkin路の $i - 1$ 番目のステップを $A, B, \tilde{B}, C$ と定める．
こうして長さ $n - 1$ の二色Motzkin路ができる．この対応は一対一である．