文献あり

始点をずらした2-Dyck路もどきの数え上げ

140

本記事では，始点$(-1,0)$で終点$(2n,n)$の正方格子路のうち直線$y=(1/2)x$より上を動くものの数が積公式を持つことを全単射的に示す．

Dyck路とカタラン数の復習

ベクトル$\mathsf{e}(1,0)$とベクトル$\mathsf{n}(0,1)$をそれぞれ「東向きステップ」「北向きステップ」と呼ぶ．
パスとは，$\mathbb{Z}^2$上の点の有限列
\begin{align} \omega=(\omega_1,\ldots,\omega_r),\qquad\omega_i\in\mathbb{Z}^2,\ i=1,\ldots,r \end{align}
で，$\omega_{i+1}-\omega_i\in\{\mathsf{e,n}\}\ (i=1\ldots,r-1)$を満たすものである．

補足

パスとは点$\omega_1\in\mathbb{Z}^2$から点$\omega_r\in\mathbb{Z}^2$まで，上か右に$1$づつ進みながら行くときの最短経路のことだと言っても同じである．

パス$\omega=(\omega_1,\ldots,\omega_r)$に対して，点$\omega_1$を$\omega$の始点といい，点$\omega_r$を$\omega$の終点という．

パス$\omega$の全ての点が，領域$y\geq ax\ (a\in\mathbb{R})$に含まれるとき，パス$\omega$は直線$y=ax$より下に行かないという．

数え上げ組合せ論では以下の定理は基本的である．

Dyck路の数え上げ＝カタラン数

非負整数$n$に対し，点$(0,0)$を始点として点$(n,n)$を終点とする，直線$y=x$より下に行かないパスは
\begin{align} \frac{1}{n+1}\binom{2n}{n} \end{align}
個存在する．

証明は例えば[3]を参照せよ．
このようなパスはDyck路と呼ばれ，数$\frac{1}{n+1}\binom{2n}{n}$はカタラン数と呼ばれる．

$k$-Dyck路と$k$-カタラン数の復習

前節では終点が$(n,n)$であるパスを考えたが，終点を$(kn,n)\ r\in\mathbb{N}$にし，直線を$y=\frac{1}{k}x$にしても似たようなことが言える．

$k$-Dyck路の数え上げ＝$k$カタラン数

$n$を非負整数とし，$k$を正の整数とする．
点$(0,0)$を始点として点$(kn,n)$を終点とするパスで，直線$y=(1/k)x$より下に行かないものは
\begin{align} \frac{1}{kn+1}\binom{(k+1)n}{n} \end{align}
個存在する．

この定理の証明は[1]や[2]を参照せよ．
このようなパスは$k$-Dyck路と呼ばれていて，数$\frac{1}{kn+1}\binom{(k+1)n}{n}$は$k$-カタラン数と呼ばれている．

始点をずらした$2$-Dyck路の数え上げ

次に，パスの始点を$(0,0)$以外の点にすることを考える．ここでは西に始点をずらし，$(-1,0)$を始点にして$(2n,n)$を終点とするパスを考えてみる．すると，この場合も以下の積公式を与えることができる．

始点をずらした$2$-Dyck路の数え上げ

自然数$n$に対し，$(-1,0)$を始点として$(2n,n)$を終点とするパスで，直線$y=(1/2)x$より下に行かないものは
\begin{align} \frac{1}{n+1}\binom{3n+1}{n} \end{align}
個存在する．

この内容は，オンライン数列大百科の A006013 [4]に書かれたI. M. Gesselによるコメント

a(n) is the number of paths in the plane with unit east and north steps, never going above the line x=2y, from (0,0) to (2n+1,n). - Ira M. Gessel, Jan 04 2018

と同じ主張である．

本記事では，定理3に全単射的証明を与える．

始点$(-1,0)$で終点$(2n,n)$のパス全体を$\mathcal{P}$とする．パス$\omega\in\mathcal{P}$に対して整数$t(\omega)$を
\begin{align} t(\omega)\triangleq\#\left\{i\mid \omega_{i+1}-\omega_i=\mathsf{n},\ \omega_i\in\{(x,y)\mid y\lt (1/2)x\}\right\} \end{align}
と定める．これはつまり，パス$\omega$に含まれる北向きステップのうち，ステップの始点が$y=(1/2)x$よりも真に下にあるものの数を$t(\omega)$と定義するということである．

!FORMULA[61][1134102610][0]のときのあるパス． $n=10$のときのあるパス．
図1を見ると理解が捗るかもしれない．図1は$n=10$のときのあるパス$\omega$を黒い線で描いたもので，$t(\omega)=5$である．$t(\omega)$にカウントされる北向きステップに赤い丸印をつけている．

集合$T_0,\ldots,T_{n}$を
\begin{align} T_i\triangleq\{\omega\in\mathcal{P}\mid t(\omega)=i\},\qquad i=0\ldots,n \end{align}
と定める．
定理の主張は$|T_0|=\frac{1}{n+1}\binom{3n+1}{n}$である．
$|\mathcal{P}|=\binom{3n+1}{n}$なので，主張を示すには$|T_0|=\cdots=|T_{n}|$を言えばよく，そのためには$T_{k+1}$から$T_k$への全単射を作ればよい ($k=0,\ldots,n$)．

以下，そのような全単射を作る．
パス$\omega\in\mathcal{T}_{k+1}$を始点$(-1,0)$から順に見てゆき，初めて
\begin{align} \omega_i\in\{(x,y)\mid y\lt (1/2)x\},\ \omega_{i+1}\in\{(x,y)\mid y\gt (1/2)x\} \end{align}
かつ$\omega_{i+1}-\omega_i=\mathsf{n}$となる点$\omega_i$があったとする．
このとき，パス$\omega$を次の三つの部分に分ける：

$p_1$：始点から$\omega_i$までの部分，
$p_2$：$\omega_i$から$\omega_{i+1}$までの部分，
$p_3$：$\omega_{i+1}$から終点までの部分．
そして，新しいパス$\omega'$を，$\omega$のステップを$p_3,p_2,p_1$の順になるよう並べ替えてできるパスと定義する．（図2の例を見よ．）

全単射の例，第一の場合．赤い線で描いたのが，初めて!FORMULA[90][-912753311][0]にまたがる北向きステップ．全単射の例，第一の場合．赤い線で描いたのが，初めて$y=(1/2)x$にまたがる北向きステップ．

次に，そのような点$\omega_i$が存在しない場合を考える．
この場合，再びパス$\omega$を始点から順に見てゆくと初めて$\omega_{i}\in\{(x,y)\mid y= (1/2)x\}$かつ$\omega_{i}-\omega_{i-1}=\mathsf{n}$となる点$\omega_{i}$が必ず存在する．
このとき，前と同様にパス$\omega$を次の三つの部分に分ける：

$p_1$：始点から$\omega_{i-1}$までの部分，
$p_2$：$\omega_{i-1}$から$\omega_{i}$までの部分，
$p_3$：$\omega_{i}$から終点までの部分．
そして，新しいパス$\omega'$を，$\omega$のステップを$p_3,p_2,p_1$の順になるよう並べ替えてできるパスと定義する．（図3の例を見よ．）