両側Dyck路と(3,3,4,5,6,...)型数列の全単射

二次元平面において点 $(0,0)$ から出発し，ステップ $\nearrow(+1,+1)$ と $\searrow(+1,-1)$ を用いて点 $(2n,0)$ までゆくパスをサイズ $n$ の両側Dyck路という．
サイズ $n$ の両側Dyck路の数は $\binom{2n}{n}$ である．

サイズ $n$ の両側Dyck路のうち，最初のステップが $\nearrow$ であるものの集合を $\mathbf{B}_n$ とする．
$|\mathbf{B}_n|=\frac{1}{2}\binom{2n}{n}$
である．

次に「 $(3,3,4,5,6,\ldots)$ 型数列」を定義する．
写像 $f:\mathbb{N}\to \mathbb{N}$ が与えられているとする．
自然数の列 $s=(s_1,s_2,\ldots,s_n)$ で条件

$s_1=1$ ，
$s_i=r$ ならば， $1\leq s_{i+1}\leq f(r)\ (1\leq i\leq n-1)$

を満たすものを， $f$ -型数列，あるいは $(f(1),f(2),f(3),\ldots)$ 型数列と呼ぶことにする．

サイズ $n$ の $(3,3,4,5,6,\ldots)$ 型数列とは，長さ $n$ の自然数の列
$s=(s_1,s_2,\ldots,s_n)$
であって，以下の条件を満たすものである．

$s_1=1$ ，
$s_i\leq 2$ のとき， $s_{i+1}\in\{1,2,3\}$ ． $s_{i}\geq 3$ のとき， $s_{i+1}\in \{1,2,\ldots,s_i+1\}$ ，

ただし $1\leq i\leq n-1$ ．
サイズ $n$ の $(3,3,4,5,6,\ldots)$ 型数列の集合を $\mathbf{S}_n$ とする．

例えば， $(1,3,4,4,2)\in\mathbf{S}_5$ である．

本稿では以下を証明する．
命題
集合 $\mathbf{S}_n$ と集合 $\mathbf{B}_n$ の間に全単射が作れる．

またここから， $|\mathbf{S}_n|=\frac{1}{2}\binom{2n}{n}$ がわかる．

この命題を証明するために，いくつか準備をする．
以下では集合 $\mathbf{B}_n$ の両側Dyck路を $B=(B_1,B_2,\ldots,B_{2n})\in\mathbf{B}_n,\ B_i\in\{\nearrow,\searrow\}$ とかく．
このとき集合 $\mathbf{B}_n$ の定義から $B_1=\nearrow$ である．
両側Dyck路 $B\in\mathbf{B}_n$ に対し自然数 ${\rm add}(B)\in\mathbb{N}$ を以下のように定義する．

$B_2=\nearrow$ のとき， ${\rm add}(B)\triangleq \min\{i\mid i\geq 3, B_i=\searrow\}$ ，
$B_2=\searrow$ のとき， ${\rm add}(B)\triangleq \min\{i\mid i\geq 3, B_i=\nearrow\}$ ．

集合 $\mathcal{B}_n\subset \mathbf{B}_{n}\times\mathbb{N}$ を
$\mathcal{B}_n\triangleq\{(B,i)\mid B\in\mathbf{B}_{n}, 1\leq i\leq {\rm add}(B), i\in\mathbb{N}\}$
と定める．

補題
集合 $\mathcal{B}_n$ と集合 $\mathbf{B}_{n+1}$ の間に全単射が作れる．
証明
集合 $\mathcal{B}_n$ と集合 $\mathbf{B}_{n+1}$ の間の全単射 $g$ を作る．
$(B,i)\in\mathcal{B}_n$ をとる．サイズ $n+1$ の両側Dyck路 $B'$ を

$i=1$ または， $i>1$ かつ $B_{i-1}=\nearrow$ のとき

$B'\triangleq(B_1,\ldots,B_{i-1},\nearrow,\searrow,B_{i},\ldots,B_{2n})$

$i>1$ かつ $B_{i-1}=\searrow$ のとき

$B'\triangleq(B_1,\ldots,B_{i-1},\searrow,\nearrow,B_{i},\ldots,B_{2n})$
と定める．
すると，上記で $\nearrow,\searrow$ または $\searrow,\nearrow$ を入れた場所は，
パス $B'$ が $B'=(\nearrow,\searrow,\searrow,\ldots)$ という形のときは最初に現れる谷として，また
パス $B'$ がそれ以外の形のときは最初に現れる頂上として同定可能である．
ゆえに $B'$ を見れば $(B,i)$ が復元できるので対応 $g\colon(B,i)\mapsto B'$ は全単射である．
（証明終わり）

$B=(\nearrow,\searrow,\searrow,\searrow,\nearrow,\nearrow)\in\mathbf{B_3}$ としたときの， $g(B,i),\ i=1,2,3,4,5$ を説明する図．

$B=(\nearrow,\searrow,\searrow,\searrow,\nearrow,\nearrow)\in\mathbf{B_3}$ としたときの， $g(B,i),\ i=1,2,3,4,5$ を説明する図．

補題
$(B,i)\in\mathcal{B}_n$ とする．上記で定めた全単射 $g$ について，
$i\leq 2$ のとき， ${\rm add}(g(B,i))=3$ ，
$i\geq 3$ のとき， ${\rm add}(g(B,i))=i+1$ ，
が成り立つ．
証明
$B_2=\nearrow$ のときと $B_2=\searrow$ のときの両方について，
$i=1,\ i=2, \geq 3$ の場合に場合分けして確かめればわかる．

命題の証明
数列 $s=(s_1,s_2,s_3,_\ldots,s_n)\in\mathbf{S}_n$ をとる．
上記補題により，ある $i\ (1\leq i\leq n-1)$ とある $B\in\mathbf{B}_{k}$ に対して $(B,s_{i})\in\mathcal{B}_k$ ならば， $(g(B,s_i),s_{i+1})\in\mathcal{B}_{k+1}$ である．よって，
$s\in\mathbf{S}_n$ に対応する $\mathbf{B}_n$ の元を
$g(\cdots g(g(g(\nearrow\searrow,s_2),s_3),s_4)\cdots),s_n)$
と定めることができる．
$g$ が可逆なのでこの対応は可逆である．
（証明終わり）

$s=(1,3,4,4,2)$ に対応する両側Dyck路を作る様子．上から順に $g(\nearrow\searrow,3)$ ， $g(g(\nearrow\searrow,3),4)$ ， $g(g(g(\nearrow\searrow,3),4),4)$ ， $g(g(g(g(\nearrow\searrow,3),4),4),2)$

$s=(1,3,4,4,2)$ に対応する両側Dyck路を作る様子．上から順に $g(\nearrow\searrow,3)$ ， $g(g(\nearrow\searrow,3),4)$ ， $g(g(g(\nearrow\searrow,3),4),4)$ ， $g(g(g(g(\nearrow\searrow,3),4),4),2)$

数学の命題示しました

主に組合せ論について，読んだ本で出てきたことや，考えたことを書きます．

両側Dyck路と(3,3,4,5,6,...)型数列の全単射