下図のような碁盤目の道路をAからBまで最短距離で行く.
対角線ABより上側の点を通らない道順は何通りあるか(AB上の点は通ってもよい).
常に$y≦ x}$を満たす最短経路の総数とカタラン数$c_n}$ \\
有名パターン問題である.\ まずは,\ 標準解法を示す.
AからBまでの\.{す}\.{べ}\.{て}の道順は,\ 必ず下図の点P,\ Q,\ Rのどれか1つのみを通る.}対称性}より,\ 求める場合の数は
本問の一般論を知らない場合,\ 最短経路問題の最終手段「すべて書き込む」}が標準解法となる.
ある交点までの道順の総数は,\ 1つ左と1つ下の交点までの道順の総数の和に等しい}のであった.
本問には対称性がある}ので,\ これを考慮すると大幅に計算量を減らすことができる.
対称性により,\ A\ →\ Pが5通りならばP\ →\ Bも5通りである}から,\ A\ →\ P\ →\ B}は5×5通りある.
Q,\ R}についても同様である.\ 「\,Pを通る」「\,Qを通る」「\,Rを通る」}は互いに排反なので,\ 最後に足す.
ちなみに,\ C\ →\ D}の道順の総数も42通りである.\ \ A\ →\ C,\ D\ →\ B}が1通りだからである.
さて,\ 以上の方法は,\ マス目が多くなると難しくなる.
実は,\ 縦横が$nマス× nマス$の場合にも通用する一般的な方法が存在するので紹介する.
非常に高級な発想を必要とする割には入試での出題率が高く,\ 上級者は要確認である.}
一般化の前に,\ 下図のような座標平面上の$5マス×5マス$の道路で具体的に考える.
求めるのは,\ 原点から点(5,\ 5)までの道順のうち,\ 常に$y≦ x}$を満たすものの総数である.
{原点からB(5,\ 5)までの最短経路(無条件)の総数}は,\ $C{10}{5}$}通りである.
ここから,\ $y=x+1$上の点を少なくとも1つ通る道順の総数}を引けばよい.
\.{初}\.{め}\.{て}$y=x+1$上を通る点をXとし,\ 経路A\ →\ Xを$y=x+1$に関して対称移動する.
$y=x+1$上の点を通る最短経路A\ →\ Bと,\ 最短経路A$’$\ →\ Bは1対1で対応する.
よって,\ $y=x+1$上の点を通る最短経路A\ →\ Bの総数}は 原点Aから点B$(n,\ n)$までの最短経路の総数}は,\ $C{2n}{n$通りである.
点A$'(-\,1,\ 1)$から点B$(n,\ n)$までの最短経路の総数}は,\ $C{2n}{n-1$通りである. 原点Aから点B$(n,\ n)}$までの最短経路($y≦ x}$)の総数は
条件$y≦ x}$が加わると,\ 総数が無条件の場合の$1}{n+1$になることがわかる.
$c_n=1}{n+1}\,C{2n}{n$をカタラン数という.\ ベルギーの数学者カタランに由来する.
5個の\ →\ と5個の↑の並びは\ 10!}{5!5!}\ だが,\ ここでは組合せ記号 Cを用いて表すのが普通である.
10ヶ所から5個の\ →\ が入る5ヶ所を選べばよいから,\ C{10}{5}\,である.
補集合の利用はそこまで不自然な発想ではない.
しかし,\ y=x+1上の点を通る最短経路の総数を求めるには天才的な発想が必要になる.
最短経路問題において,\ ある直線\,ℓ\,上の点を必ず通るとき,\ 直線\,ℓ\,に関して対称移動して考える.}
y=x+1を通る全経路A\ →\ B}は,\ それぞれ対称移動でA}’\ →\ Bの1つの経路に移る.
逆に,\,A}’\ →\ B}の全経路は,\,それぞれ対称移動でy=x+1上の点を通るA\ →\ B}の1つの経路に移る.
結局,\,$y=x+1上の点を通る最短経路数を求めることはA}’\ →\ bf Bの最短経路数を求めること}である.$
一般化したときの計算は,\ 階乗の形\
最終的に\,1}{n+1}C{2n}{n}\,にできること覚えておき,\ これを目指して変形していくのが普通である.,より,\ 分母は共通因数n!(n-1)!\,をくくり出せる.
括弧内の分数の差を計算した後,\ (n-1)!･ n=n!\,とすると\,C{2n}{n}\,の形が現れる.
5個の白球と5個の黒球から1個ずつとって袋に入れていく.
\ \ すべての球が袋に入るまで常に袋の中が$(白球の個数)≧(黒球の個数)$となって
\ \ いるような入れ方は何通りあるか.
(2)\ \ (1)で,\ 最初と最後を除いて$(白球の個数)(黒球の個数)$となるのは何通りあるか.
座標平面における常に条件x≧ yを満たす最短経路は,\ 次のように言い換えられる.
「常に(\,→\ の個数)≧(↑の個数)となるように進む(\,→↑を並べていく)」}
(1)\ \ ○を\ →,\ ●を↑と考えれば,\ 常に条件x≧ yを満たす最短経路問題と本質的に同じ}である.
\ \ 例えば,\ ○○●○●●○○●●の順の入れ方は,\ 左上図の赤線の経路に対応する.
(2)\ \ 最初と最後を除いて常に条件を満たす最短経路問題と本質的に同じ}である.
\ \ 右上図のA\ →\ Bの最短経路の総数は,}\ bf A’\ →\ bf B’\,の最短経路の総数c_4\,に等しい.}
\ \ A\ →\ A}’\,とB}’\ →\ Bはそれぞれ1通りだからである.
\ \ 本問の条件は,\ 後に確率で学習するランダムウォークの問題で頻出する.
