カタラン数とその拡張 その2 〜最短経路を通したカタラン数の拡張〜

$(0,0)$から$(a,b)$までのすべての最短経路から，$y\geq x+c$を通る経路の総数を引くと考える．
$y\geq x+c$を通る経路$\lambda$において，最初に通る直線$y=x+c$上の点を$P$とする．
$\lambda$における$(0,0)$から$P$までの経路と，
$\lambda$における$P$から$\lambda$までの経路を$y=x+c$に対して対称移動させてできる経路を
つなげてできる経路$\lambda'$を考える．

$(a,b)$を$y=x+c$に対して対称移動させた点は$(b-c,a+c)$であり，
このとき，$\lambda'$には$(0,0)$から$(b-c,a+c)$までの最短経路がちょうど１つずつ現れる．よって，$y\ge x+c$を通る経路の総数は${_{a+b}}C_{b-c}$に等しい
すべての最短経路は${_{a+b}}C_a$個あるから，条件をみたす最短経路の総数は

$$ {_{a+b}}C_a-{_{a+b}}C_{b-c} $$

$(0,0)$から$(n,kn)$までのすべての最短経路のうち,$y=kx$より
上側で$y$軸方向に進む回数が$i$回であるものの集合を$T_i$とする.
また，常に領域$x\geq y$を通るものの総数を$a_n$とする．
定義より,
$$|T_0|+|T_1|+\cdots+|T_{kn}|={_{(k+1)n}}C_n$$また,$|T_0|=C_k(n)$
$0\le i\le kn-1$のとき,$T_i$と$T_{i+1}$が1対1に対応することを示す.
$T_i$の要素について,最初に$y=kx$を踏むときの座標を
$(a,ka)$とする.この経路を次の3つの部分に分ける.
$p_1$: $(0,0)$から$(a,ka-1)$までの経路
$p_2$: $(a,ka-1)$から$(a,ka)$までの経路
$p_3$: $(a,ka)$から$(n,kn)$までの経路

ここで,$p_1p_2p_3$の順番を入れ替えて,$p_3p_2p_1$とした経路を考える．
$p_2$の分だけ上にはみ出る部分が増えるので,この経路は$T_{i+1}$の要素になる．
よって,$T_i$と$T_{i+1}$の間で1対１対応が構成できる．
このことから,$|T_0|=|T_1|=\cdots=|T_{kn}|$
$$\therefore C_k(n)=|T_0|=\frac{1}{kn+1}{_{(k+1)n}}C_n$$

$a_1,a_2,\cdots,a_k$は$a_{k+1}=n$以下なので，
$i=0,1,2,\cdots,k-1$に対して，$a_{i+1}\ge a_i$であることを示せばよい．$a_{i+1}=n$のとき明らかに成立するので，それ以外の場合を考える．
$P_{i+1}$は最短経路上の点であり，$P_{i+1}Q_{i+1}$が$l_{i+1}$上にあることから，$P_{i+1}$は$l_{i+1}$と$l_k$の間の領域(境界を含む)にある．
すなわち$P_{i+1}$は領域$k(x-1)+i+1\le y\le kx$上にある．
$y\le ka_i$より$y\le k((a_i+1)-1)+i$だから，線分$P_{i+1} Q_{i+1}$は直線$l_i$とも共有点を持つ．よって，$P_{i+1} Q_{i+1}$は$l_i$に対しても定義1の条件を満たすから，$a_{i+1}\ge a_i$となる．

$1\le x\lt n$を満たす各整数$x$に対して，2点$P(x,y),Q(x+1,y)$がともに最短経路上の点であるような$y$は高々1つしか存在しない．
このことから，$n_i=0$すなわち$a_i=a_{i+1}$のとき，$P_i$と$P_{i+1}$は一致する．

よってこの$m$に対し，$P_i=P_{i+1}=\cdots=P_m$であり，
$P_m$は$l_m$上またはその上側にあるから，$b_i\ge k(x-a_i)+m$となる．
また，$b_i= k(x-a_i)+M, M>m$と仮定すると，
$a_i=a_{i+1}=\cdots=a_{M-1}=a_M$となるので，$n_m \neq 0$に矛盾．
よって，$b_i=k(x-a_i)+m$となる．

$i=0,1,2,\cdots,k$に対し$P_i$から$P_{i+1}$への経路を定めれば，経路は一意に定まる．よって，$P_i$から$P_{i+1}$への経路が$C_k(n_i)$通りあることを示せば良い．
$n_i=0$すなわち$a_i=a_{i+1}$のとき明らかに$C(0,0)=1$通りとなるから，
$n_i\neq 0$の場合を考えよう．各$i$に対して，$A_i(a_i,k(a_i-1)+i),B_i(a_i,k(a_i-1)+i-1)$とする．
$n_i\neq 0$なので補題6から，$P_i=A_i$である．また，経路が$l_0$を越えてはいけないことを考えると，$P_i$から$P_{i+1}$までの間に必ず$B_{i+1}$を通過する必要がある．($P_{i+1}$が$B_{i+1}$と一致する場合もあることに注意)
$B_{i+1}$から$P_{i+1}$までの経路は1通りなので，求めたい場合の数は，
$A_i$から$B_{i+1}$までの最短経路であって，$l_i$を越えないものの総数に一致する．
これは$C_k(n_i)$に等しい．

• $kn+2$角形が$k+2$角形で分割できることの証明
  $n$に関する数学的帰納法で示す．$n=1$のとき，$kn+2$角形それ自身が$k+2$角形分割となる．$k(n-1)+2$角形が$k+2$角形分割可能であると仮定して，$kn+2$角形が$k+2$角形分割可能であることを示す．
  与えられた$kn+2$角形の頂点を１つ選んで$P$とし，そこから$k+1$個隣にある頂点を$Q$とする．線分$PQ$は$kn+2$角形を$k(n-1)+2$角形と$k+2$角形に分割する．仮定より$k(n-1)+2$角形は$k+2$角形分割可能なので$kn+2$角形は$k+2$角形分割可能である．
• $N$角形が$k+2$角形分割できるとき，$N=kn+2$を満たす正の整数$n$が存在することの証明
  $k+2$角形の内角の和は$2k\pi$であるから，$N$角形を$n$個の$k+2$角形に分割するとき，$N$角形の内角の和は$2kn\pi$である．よって$N=kn+2$となる

与えられた$kn+2$角形を$P$とする．$P$の辺を１つ選んで$e_0$とする．$e_0$を辺に含む$k+2$角形がただ１つ存在するので，それを$P_0$とする．
$P_0$について$e_0$から反時計回りに$i$番目にある辺を$e_i$で表す．$i=0,1,\cdots,k+1$
$i=1,2,\cdots,k+1$に対し，$e_i$は$P$の辺または対角線であり，$P$を２つの多角形に分割する．そのうち$P_0$を含まない方を$P_i$とする．補題より$P_i$は非負整数$n_i$を用いて$kn_i+2$角形と表わせる．($e_i$が$P$の辺である場合は，$P_i$は2角形とみなし，$n_i=0$とする)
また，$i=1,2,\cdots,k+1$に対し$P_i$の辺で$P$の辺であるものは$kn_i+1$個あるから，$P$の辺の本数に注目して，$1+\sum_{i=1}^{k+1}(kn_i+1)=kn+2$
よって，$n_1+n_2+\cdots+n_{k+1}=n-1$
$kn+2$角形を$k+2$角形に分割する方法の総数を$A_k(n)$で表すとする．
各$P_i$に対して，$k+2$角形分割の総数は$A_k(n_i)$個だから，
$$A_k(n)=\sum_{n_1+n_2+\cdots+n_{k+1}=n-1}A_k(n_1)A_k(n_2)A_k(n_3)\cdots A_k(n_{k+1})$$
となり，拡張したカタラン数の漸化式と一致する．$A_k(0)=1$も加味して，
$A_k(n)=C_k(n)$となる．

$O(0,0)$から$A(a,b)$への任意の最短経路$P$(Dyckパスでなくてもよい)に対し，
それを２つつなげてできる$(0,0)$から$(2a,2b)$への経路$2P$を考える．
$2P$に上から接する傾き$\frac{b}{a}$の直線を$l$とすると，
$P$がDyckパスでないとき$l$は$2P$と2つの共有点をもち，Dyckパスのとき3つの共有点をもつ．($a,b$が互いに素であることから成立)
$l$と$2P$の共有点で$x$座標が最小のものを$A(s,t)$とすると，$B(s+a,t+b)$も$l$と$2P$の共有点の１つであり，$2P$の$A$から$B$までの部分は1つのDyckパスとなっている．これを$Q$とする．
任意のDyckパス$Q$に対して，$Q$が$2P$の一部分になっている経路を考える．
このとき，$2P$における点$(a,b)$を$Q$のどの点に置くかを選べば，$2P$は一意に定まる．（ただしこのとき，$Q$の始点すなわち$A$を選ぶことはできない）
よって，$Q$が$2P$の１部分になっている経路は$a+b$個あり，そのうちDyckパスはただ１つ存在する．
よって$2P$のうちDyckパスの個数は，$(a,b)$への最短経路の個数${_{a+b}}C_a$
を$a+b$で割ったものに等しいので，
$$C(a,b)=\frac{1}{a+b}{_{a+b}}C_a$$
となる．