2
大学数学基礎解説
文献あり

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

120
0
$$$$

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

Dyck路とネックレスの対応

Dyck路(Dyck path)

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

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

$n=3$の場合

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

それぞれに対応するワードは$UDUDUD$$UDUUDD$$UUDUDD$$UUDDUD$$UUUDDD$である.

Dyck路のピーク(peak)

Dyck路の$UD$という形の部分列をピークという.

ネックレス(necklace)

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

Catalan数(Catalan number)

$n \geq 0$に対し,$n$番目のCatalan数
\begin{equation} C_n = \cfrac{1}{n+1} \binom{2n}{n} \end{equation}
で定義する.

Dyck路とネックレスの対応

長さ$2n$のDyck路の集合を$D_n$$n$個の$U$$n+1$個の$D$からなるネックレスの集合を$N_n$$n$個の$U$$n$個の$D$からなるワードの集合を$W_n$とする.
(1) $f_1 (w) = [wD]$で定まる写像$f_1 \colon D_n \to N_n$は全単射である.
(2) $f_2 (w) = [wD]$で定まる写像$f_2 \colon W_n \to N_n$$n+1$$1$である.
(3) $|D_n| = |N_n| = C_n.$

  1. 写像$g_1 \colon N_n \to D_n$を以下で定める.$[w] \in N_n$とする.$w$$xy$平面における原点から出発する経路と同一視する.$w$における$y$座標が最も小さい点で最も左にあるものを$P$とする.$w$を原点から点$P$までの経路$w_1 D$と点$P$以降の経路$w_2$に分ける.このとき$g_1 ([w]) = w_2 w_1$と定める.この写像$g_1$はwell-definedであり,$f_1$の逆写像となることがわかる.
  2. $n$個の$U$$n$個の$D$$1$個の$X$からなるネックレスの集合を$M_n$とする.$g_2 (w) = [wX]$で定まる写像$g_2 \colon W_n \to M_n$は明らかに全単射である.また$X$$D$へ置き換えることで定まる写像$g_3 \colon M_n \to N_n$は明らかに$n+1$$1$である.$f_2 = g_3 \circ g_2$より,$f_2$$n+1$$1$である.
  3. (1)より$|D_n| = |N_n|$.また(2)より$|N_n| = \cfrac{1}{n+1} |W_n| = C_n$

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

ピークに印を付けたDyck路

$w$をDyck路とする.$w$のあるピーク$U D$$U \bullet D$に置き換えたワードを$\widehat{w}$で表し,ピークに印を付けたDyck路という.$\widehat{w}$$w$のある部分列$w_1,w_2$を用いて$\widehat{w} = w_1 U \bullet D w_2$と表すことができる.$\widehat{w}$ピークに印を付けたDyck路としての長さ$w$の長さで定める.

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

$n=3$の場合

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

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

ピークに印を付けた長さ$2n$のDyck路の集合を$\widehat{D}_n$$n-1$個の$U$$n$個の$D$からなるワードの集合を$V_n$とする.
(1) $f(w_1 U \bullet D w_2) = w_2 D w_1$で定まる写像$f \colon \widehat{D}_n \to V_n$は全単射である.
(2) $|\widehat{D}_n| = |V_n| = \binom{2n-1}{n}.$

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

参考文献

[1]
Nicholas Loehr, Combinatorics, Discrete Mathematics and its Applications, CRC Press, 2017
投稿日:2023612
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

Oddie
Oddie
4
590
整数論と組合せ論が好きです

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中