文献あり

二色Circular ladder graphとカタラン数

この記事でいうCircular ladder graph [1]とは，下図のようなグラフである．
$2n$個の節点からなるCircular ladder graphを${\rm CL}_n$とかく．
!FORMULA[2][623946087][0] ${\rm CL}_3,{\rm CL}_4,{\rm CL}_5,\ldots$

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

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

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

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

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

集合$X_n$を，$n+1$個の$+1$と$n-1$個の$-1$が書かれた二行配列の集合と定義する．つまり，
\begin{align} X_n\triangleq \left\{ \left( \begin{array}{ccc} w_{1,1}&\cdots &w_{1,n}\\ w_{2,1}&\cdots &w_{2,n} \end{array} \right) \middle| w_{1,1},\ldots,w_{2,n}{\text は}n+1{\text 個の}(+1){\text と}n-1{\text 個の}(-1){\text からなる．} \right\} \end{align}
と定める．
巡回群$C_n\triangleq \langle a\mid a^n\rangle$の$X_n$への作用を
\begin{align} a\cdot\left(\begin{array}{cccc} w_{1,1}&w_{1,2}&\cdots &w_{1,n}\\ w_{2,1}&w_{2,2}&\cdots &w_{2,n} \end{array}\right)\triangleq \left(\begin{array}{cccc} w_{1,2}&\cdots &w_{1,n}&w_{1,1}\\ w_{2,2}&\cdots &w_{2,n}&w_{2,1} \end{array}\right) \end{align}
により定める．上でグラフを使って定義した「${\rm CL}_n$の節点を塗り分ける同値でない塗り方」は，この作用による軌道と同一視できる．

定理1の証明

二行配列$w\in X_n$の高さ列$h(w)=(h_0,h_1,\ldots,h_n)\in \mathbb{Z}^{n+1}$を，

$h_0\triangleq 0$,
$h_{i+1}\triangleq h_{i}+(w_{1,i+1}+w_{2,i+1})/2\quad (i=0,1,\ldots,n-1)$

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

Cycle ladder graph版のcycle lemma

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

二行配列$w$の高さ列を$h(w)=(h_0(w),\ldots,h_n(w))$とする．
ここで添字$i\ (0\leq i\leq n)$を，$i\in{\rm argmin}_{0\leq i\leq n}h_i(w)$かつ，$i< j$なる全ての$j\ (j\leq n)$に対して$h_i< h_j$であるような唯一の$i$ととる．

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

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

また，$h_{n-i}(\widetilde{w})=-k+1$であることと，$h_{0}(w),\ldots,h_{i-1}(w)$が$k$以上なことから，$h_{n-i+1}(\widetilde{w}),\ldots,h_{n}(\widetilde{w})$も$0$より大きい．以上から，$\widetilde{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な二行配列は，軌道あるいは言い換えると「${\rm CL}_n$の節点を塗り分ける同値でない方法」と一対一対応する．

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

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

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

任意の自然数$n$について，集合${\rm Mot}(n-1)$と集合${\rm Dyck}(n)$の間に一対一対応が存在する．

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

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

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

dominatingな二行配列
\begin{align} \left( \begin{array}{ccc} w_{1,1}&\cdots &w_{1,n}\\ w_{2,1}&\cdots &w_{2,n} \end{array} \right) \end{align}
が与えられたとする．dominatingという条件から一列目は必ず
\begin{align} \left( \begin{array}{c} w_{1,1}\\ w_{2,1} \end{array} \right)= \left( \begin{array}{c} +1\\ +1 \end{array} \right) \end{align}
である．二列目以降，$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$番目のステップを${\mathsf A},{\mathsf B},\widetilde{{\mathsf B}},{\mathsf C}$と定める．
こうして長さ$n-1$の二色Motzkin路ができる．この対応は一対一である．