4
高校数学解説
文献あり

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

788
0
$$$$

前回 は,カタラン数が組合せ論において様々なところで現れることを紹介しました.
今回からは,カタラン数を様々な形で拡張していきます.

カタラン数には様々な性質がありますが,今回特に注目するのは
前回一番最初に紹介した次の命題です.

$xy$平面上で,$(0,0)$$(n,n)$を向かい合う頂点とする正方形状の格子を考える.
この格子上における$(0,0)$から$(n,n)$への最短経路で,常に領域$x\geq y$を通るものの総数は,カタラン数$c_n$に等しい

今回は,「最短経路」というテーマを中心に,カタラン数を拡張していきます.

拡張1 〜任意の傾き1の直線を通らない最短経路の総数〜

前回紹介したカタラン数の一般項の1つ目の証明と同じ方法で,次が示せます.

$b< a+c$,$b\geq c >0$とする.$xy$平面上における$(0,0)$から$(a,b)$への最短経路で,常に領域$y< x+c$を通るものの総数は,次のように表せる.
$$ {_{a+b}}C_a-{_{a+b}}C_{b-c} $$

$(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)$までの最短経路がちょうど1つずつ現れる.よって,$y\ge x+c$を通る経路の総数は${_{a+b}}C_{b-c}$に等しい
すべての最短経路は${_{a+b}}C_a$個あるから,条件をみたす最短経路の総数は

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

拡張2 〜対角線を超えない(n,kn)への最短経路の総数〜

今度は,次のような拡張を考えてみましょう.
証明は,前回紹介したカタラン数の一般項の2つ目の証明と同じです.

$xy$平面上における$(0,0)$から$(n,kn)$への最短経路で,対角線$y=kx$を越えないものの総数を$C_k(n)$で表す.このとき,次が成立する.
$$C_k(n)=\frac{1}{kn+1}{_{(k+1)n}}C_n$$

$(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対1対応が構成できる.
このことから,$|T_0|=|T_1|=\cdots=|T_{kn}|$
$$\therefore C_k(n)=|T_0|=\frac{1}{kn+1}{_{(k+1)n}}C_n$$

漸化式

おさらいですが,カタラン数には次のような漸化式が成立しました.
$$ c_0=1, c_{n+1}=\sum_{k=0}^{n}c_k c_{n-k} $$

これに対応して,$C_k(n)$には次のような漸化式が成立することが知られています.

$$ C_k(0)=1, C_k(n+1)=\sum_{n_0+n_1+\cdots+n_{k}=n}C_k(n_0)C_k(n_1)C_k(n_2)\cdots C_k(n_k)$$
ただし,右辺の総和は,$n_0+n_1+\cdots+n_k=n$を満たすすべての非負整数の組$(n_0,n_1,\cdots,n_k)$について和をとる.

この証明は少し難しいですが,考え方は前回の漸化式の証明と一緒です.

証明

$i=0,1,2,\cdots,k$に対して,$y=k(x-1)+i$で表される直線を$l_i$とする.$l_k$は対角線である.
$i$に対し,次の条件を満たす点のうち$x$座標が最小のものを$P_i(a_i,b_i)$とする.

  • $a_i,b_i$は整数で,$1\le a_i\lt n$である
    また,2点$P_i(a_i,b_i),Q_i(a_i+1,b_i)$について,
  • $P_i,Q_i$はともの最短経路上の点である.
  • 線分$P_i Q_i$(両端を含む)と直線$l_i$が共有点をもつ

ただし,このような点が存在しなければ$a_i=n,b_i=k(n-1)+i,P_i(a_i,b_i)$とする.
さらに,後々の事情のため,
$a_{k+1}=n,b_{k+1}=kn,P_{k+1}(n,kn)$とする.
$P_i(a_i,b_i)$に対して,$Q_i(a_i+1,b_i)$とする.

!FORMULA[100][1922472911][0]の例 $n=4,k=2$の例

まず,次の補題が成り立つ.

$a_i$は広義単調増加である.

$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$となる.

$$n_i=a_{i+1}-a_i\ (i=0,1,2,3,\cdots,k)$$とする.

定義より,$n_0+n_1+\cdots+n_k=n-a_0$である.また,最短経路において$x=1$の直線上からどこで右に曲がっても必ずその線分が$l_0$と共有点を持つことから,$a_0=1$である.よって,$n_0+n_1+\cdots+n_k=n-1$である.これにより,最短経路に対して,総和が$n-1$である非負整数の組$(n_0,n_1,\cdots,n_k)$が得られる.

さらに次の補題により,組$(n_0,n_1,\cdots,n_k)$に対して$P_i(a_i,b_i)\ (i=1,2,3,\cdots,k+1)$は一意に定まる事がわかる.

$i=0,1,2,\cdots,k$に対し,$a_i$$n$でないとき,$m\ge i,n_m\neq 0$を満たす最小の$m$をとる.
$P_i$$y$座標$b_i$$b_i=k(a_i-1)+m$となる.すなわち$P_i$$l_m$上の点となる.

$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$となる.

これらを踏まえて,次の補題を示す.

定義2によって得られる非負整数の組が$(n_0,n_1,\cdots,n_k)$であるような最短経路の総数は,次のように表せる.
$$C_k(n_0)C_k(n_1)C_k(n_2)\cdots C_k(n_k)$$

$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)$に等しい.

以上より,
$$ C_k(0)=1, C_k(n+1)=\sum_{n_0+n_1+\cdots+n_{k}=n}C_k(n_0)C_k(n_1)C_k(n_2)\cdots C_k(n_k)$$
が成立する.$ \blacksquare $

応用

この漸化式が成立することから,最短経路以外にも$C_k(n)$は組合せ論において様々な応用ができることがわかります.前回紹介した多角形の3角形分割を一般化することを考えてみましょう.

まずはその準備として,次の補題を証明します

$N$角形が$k+2$角形で分割できることの必要十分条件は,
$N=kn+2$を満たす正の整数$n$が存在することである.

  • $kn+2$角形が$k+2$角形で分割できることの証明
    $n$に関する数学的帰納法で示す.$n=1$のとき,$kn+2$角形それ自身が$k+2$角形分割となる.$k(n-1)+2$角形が$k+2$角形分割可能であると仮定して,$kn+2$角形が$k+2$角形分割可能であることを示す.
    与えられた$kn+2$角形の頂点を1つ選んで$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$角形を$k+2$角形で分割する方法の総数を考えてみましょう.

$kn+2$角形を$k+2$角形で分割する方法の総数は,$C_k(n)$通りである

与えられた$kn+2$角形を$P$とする.$P$の辺を1つ選んで$e_0$とする.$e_0$を辺に含む$k+2$角形がただ1つ存在するので,それを$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$を2つの多角形に分割する.そのうち$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)$となる.

拡張3 〜長方形上で対角線を越えない最短経路の総数〜

もう少し一般化して,次を考えてみます.

Dyckパス

$xy$平面上における$(0,0)$から$(a,b)$への最短経路で,対角線$y=\frac{b}{a}x$を越えないものをDyckパスと呼び,その総数を$C(a,b)$で表す.

定義より,$C(a,b)=C(b,a)$が成り立ちます.
拡張2から,$(a,b)$の一方が一方の整数倍となっている場合については,Dyckパスの総数は$$C(n,kn)=\frac{1}{kn+1}{_{(k+1)n}}C_n$$
となることがわかりました.

一般の$a,b$に対して$C(a,b)$を求めることは難しそうですが,$a,b$が互いに素という条件であれば,一般項を与えることができます.
この証明はアクロバティックでとても面白いです.

$a,b$が互いに素のとき,
$$C(a,b)=\frac{1}{a+b}{_{a+b}}C_a$$

$O(0,0)$から$A(a,b)$への任意の最短経路$P$(Dyckパスでなくてもよい)に対し,
それを2つつなげてできる$(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$の共有点の1つであり,$2P$$A$から$B$までの部分は1つのDyckパスとなっている.これを$Q$とする.
任意のDyckパス$Q$に対して,$Q$$2P$の一部分になっている経路を考える.
このとき,$2P$における点$(a,b)$$Q$のどの点に置くかを選べば,$2P$は一意に定まる.(ただしこのとき,$Q$の始点すなわち$A$を選ぶことはできない)
よって,$Q$$2P$の1部分になっている経路は$a+b$個あり,そのうちDyckパスはただ1つ存在する.
よって$2P$のうちDyckパスの個数は,$(a,b)$への最短経路の個数${_{a+b}}C_a$
$a+b$で割ったものに等しいので,
$$C(a,b)=\frac{1}{a+b}{_{a+b}}C_a$$
となる.

いかがでしたでしょうか.次回は,「フック長の公式」と呼ばれる飛び道具を使って,カタラン数を高次元に拡張していきます.

標準ヤング盤を通したカタラン数の高次元化

参考文献

[1]
枡田幹也,福川由貴子, 格子から見える数学
投稿日:2022325

この記事を高評価した人

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

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

バッジはありません。

投稿者

dragoemon
dragoemon
113
22630
大学二年生です

コメント

他の人のコメント

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