数学A / 場合の数

対角線を越えない最短経路(カタラン数と反射原理)

実戦編数え上げ最短経路二項係数反射原理単元横断

問題

格子を右または上へ1歩ずつ進んで $(0, 0)$ から $(n, n)$ へ行く最短経路のうち、つねに $y \leq x$ (対角線 $y = x$ を上に越えない)ものの総数を求めよ。

ヒントを見る

全経路から“ダメな経路(対角線を越える= $y = x + 1$ に触れる)”を引く。触れた後を対角線で折り返す反射で、ダメな経路が別の端点への全経路と1対1に対応する。

解答・解説

方針

全経路は $(n 2 n)$ 。 $y \leq x$ を破る経路(直線 $y = x + 1$ に触れる)を、最初に触れた後を対称移動する反射原理で $(- 1, 1)$ → $(n, n)$ の経路 $(n - 1 2 n)$ と1対1対応させ、引く。

解答

⓪ 発想 — どう考え始めるか。 「越えない経路」を直接数えるのは難しい。全体から悪い経路を引く方針に切り替える。

全経路は右 $n$ 歩・上 $n$ 歩の並べ方で $(n 2 n)$ 。悪い経路(直線 $y = x + 1$ に触れる)を数えるのが勝負だ。

急所は反射原理: 悪い経路を「最初に $y = x + 1$ に触れた後の部分を、その直線について折り返す」と、 $(- 1, 1)$ から $(n, n)$ への経路と1対1に対応する。折り返しで数えにくいものが数えやすいものに化ける。

定理反射原理:直線

ℓ

に触れる経路は、初めて触れた後を

ℓ

で折り返すと、始点を

ℓ

で対称移動した点からの経路と1対1に対応する

① 全経路。 $(0, 0) \to (n, n)$ の最短経路は右 $n$ 回・上 $n$ 回の並べ方で $(n 2 n)$ 通り。

例(n=3): 対角線 y=x(破線)を上に越えず (0,0) から (3,3) へ行く経路の一例。総数はカタラン数 C₃=5。

② 越える経路を反射で数える。 $y \leq x$ を破る経路は直線 $y = x + 1$ に触れる。初めて触れた点以降を $y = x + 1$ で折り返すと、始点 $(0, 0)$ の鏡像 $(- 1, 1)$ から $(n, n)$ への経路になる。これは右 $n - (- 1) = n + 1$ 回・上 $n - 1$ 回の並べ方で $(n - 1 2 n)$ 通り。逆にたどれるので1対1対応、越える経路はちょうど $(n - 1 2 n)$ 通り。

③ 引く。 よって越えない経路は $(n 2 n) - (n - 1 2 n) = (n 2 n) (1 - \frac{n}{n + 1}) = \frac{1}{n + 1} (n 2 n) .$ これがカタラン数 $C_{n} = \frac{1}{n + 1} (n 2 n)$ 。

まとめ 「対角線を越えない経路」は、全経路 $(n 2 n)$ から越える経路を反射原理で $(n - 1 2 n)$ と数えて引く。差はカタラン数 $\frac{1}{n + 1} (n 2 n)$ 。数え上げ・最短経路・二項係数(反射)の融合。 $n = 3$ なら $C_{3} = 5$ 。

発展 — 一歩先へ。 カタラン数 $1, 2, 5, 14, 42, \dots$ は、対になった括弧の列( $n$ 組)、凸多角形の三角形分割、二分木の形 — と、まるで違う顔の問題に繰り返し現れる「数え上げの王様」だ。どれも本問の経路と1対1対応が作れる。また票数の一般形(A が $a$ 票、B が $b$ 票、 $a > b$ 、開票中つねに A が優勢である確率 $= \frac{a - b}{a + b}$ )は「投票の問題」と呼ばれ、反射原理がそのまま働く。

答

全経路 $(n 2 n)$ から、対角線を越える“悪い経路”を反射原理で $(n - 1 2 n)$ と数え、差 $(n 2 n) - (n - 1 2 n) = \frac{1}{n + 1} (n 2 n)$ (カタラン数)。

別解

「最初に対角線へ戻る場所」で分解する(カタラン数の再帰構造)。 反射原理と別の顔として、良い経路を最初に $y = x$ に戻る点で切る見方がある。

良い経路が最初に対角線に戻るのが $(k + 1, k + 1)$ だとすると、経路は「最初の右1歩+内側で対角線に触れない長さ $2 k$ の部分+上1歩」と「残りの長さ $2 (n - k - 1)$ の良い経路」に割れる。個数を $C_{n}$ と書くと

$C_{n + 1} = k = 0 \sum n C_{k} C_{n - k}$

という再帰の分解が出る( $C_{0} = 1$ )。実際 $1, 1, 2, 5, 14, 42, \dots$ がこの式で次々に生成される。

反射原理(本解)は閉じた式 $\frac{1}{n + 1} (n 2 n)$ への最短路、再帰分解は「カタラン数が括弧の対応・二分木・多角形の三角形分割にも現れる」理由を説明する構造の道 — 同じ数列の2つの顔だ。

ポイント

全経路 $(n 2 n)$ から越える経路を引く(余事象)。
越える経路は反射原理で $(- 1, 1) \to (n, n)$ の経路 $(n - 1 2 n)$ と1対1。
差はカタラン数 $\frac{1}{n + 1} (n 2 n)$ 。

よくある間違い

反射の対応先を $(1, - 1)$ からの経路と取り違える(直線 $y = x + 1$ に関する $(0, 0)$ の対称点は $(- 1, 1)$ )。
「触れたら悪い」の基準線を $y = x$ と混同する( $y \leq x$ は $y = x$ に触れてよい。破るのは $y = x + 1$ に達したとき)。
反射が1対1対応であること(悪い経路のどれもが対応し、逆向きも作れる)の説明を落とす。