対角線から離れない最短経路

方針

解答

⓪ 発想 — どう考え始めるか。 制約なしなら ${}_{16}{\mathrm{C}}_8$ だが、「一度も帯から出ない」経路を全体からの引き算で出すのは難しい。はみ出しの回数や場所の分類が絡まるからだ。

制約つきの経路数は、使える点だけで「各点への経路数 =(左の点)+(下の点)」の表を左下から埋めるのが確実で速い。

しかも帯の幅は5(差 $x-y$ が $-2$ 〜 $2$)しかない。埋めるうちに強い規則が現れる。それを見抜けば $(8,8)$ まで一気に届く。

① 使える点。 $|x-y|\le 2$ の帯の中の格子点だけ。対角線 $y=x$ と、その上下2本ずつの線上に並ぶ。

② 表を左下から埋める。 対称性 $f(x,y)=f(y,x)$ に注意しながら、対角線とその近くだけ追う:

• $f(1,0)=f(0,1)=1$、$f(1,1)=1+1=2$
• $f(2,0)=f(0,2)=1$、$f(2,1)=f(1,2)=1+2=3$、$f(2,2)=3+3=6$
• $f(3,1)=f(1,3)=3$(帯の縁: 片側からしか入れない)、$f(3,2)=f(2,3)=3+6=9$、$f(3,3)=9+9=18$
• $f(4,2)=f(2,4)=9$、$f(4,3)=f(3,4)=9+18=27$、$f(4,4)=27+27=54$

③ 3倍の規則を見抜き、保たれることを確かめる。 対角線上は $2,6,18,54,\dots$。縁は $1,3,9,27,\dots$。どちらも3倍ずつだ。そこで「$f(k,k)=2\cdot 3^{k-1}$、$f(k+1,k)=f(k+2,k)=3^k$($x,y$ を入れ替えても同じ)」というパターンを仮定して1段進めると

$$f(k+1,k+1)=3^k+3^k=2\cdot 3^k,f(k+2,k+1)=2\cdot 3^k+3^k=3^{k+1},f(k+3,k+1)=3^{k+1}$$

同じパターンが $k+1$ でも成り立つ(帯の縁 $f(k+3,k+1)$ は外から入れないので、$f(k+2,k+1)$ の値がそのまま)。よってすべての $k$ で成り立ち

$$f(8,8)=2\cdot 3^7=4374\text{通り}$$

まとめ: 制約つき経路は「表の足し込み」が最強の正攻法。さらに帯が狭いおかげで3倍の規則が現れ、$(n,n)$ までなら $2\cdot 3^{n-1}$ 通りという閉じた式まで手に入る。規則は「1段進めても保たれるか」を確かめて初めて使ってよい。

発展 — 一歩先へ。 この問題は、カタラン数で有名な「対角線を越えない経路」の親戚だ(あちらは壁が片側、こちらは両側)。壁が両側にあると、全体からの引き算は「反射を何度も往復させる」無限の補正になる。表の足し込みが正攻法になるのは、そのためでもある。

別解

差の折れ線で見る(1次元に潰すルート)。 $x$ と $y$ の2次元を追う代わりに、差 $d=x-y$ だけを見る。

1歩進むたびに、$d$ は $+1$($x$ 方向)か $-1$($y$ 方向)に動く。条件 $|x-y|\le 2$ は「$d$ が $-2$ 〜 $2$ の廊下から出ない」こと。求めるものは、$d=0$ から出発して16歩で $d=0$ に戻る、廊下の中の折れ線の本数だ。

各時刻に「いまどの高さにいるか」の本数を5つ($d=-2,\dots ,2$)並べて、1歩ずつ更新する。両隣の合計が次の値になる(廊下の外は0)。16歩ぶん回すと、$d=0$ の本数はちょうど $4374$ になる。

この見方の収穫は2つ。2次元の格子が「幅5の廊下を歩く点」という1次元の絵に変わること。そして偶数歩後には $d$ が偶数($-2,0,2$ の3か所)にしかいないから、実質3状態の繰り返しで、3倍の規則(本解③)がこの構造から来ていると分かることだ。