数学A / 場合の数

最短経路の数

★ 基礎最短経路同じものを含む順列

問題

図のような格子状の道路がある。横に4区画、縦に3区画である。左下の地点 A から右上の地点 B まで、遠回りせずに(右または上にだけ進んで)行く。最短経路は全部で何通りあるか。

横4区画・縦3区画の格子。A から B へ右・上のみで進む

ヒントを見る

右へ進む回数と上へ進む回数はどちらも決まっている。最短経路は『→ を何個・↑ を何個、どの順で並べるか』と同じ — 同じ矢印の並べ替え(同じものを含む順列)として数える。

解答・解説

方針

最短経路は図形の問題に見えるが、実は「同じものを含む順列」に化ける。

右へ1区画進むことを「→」、上へ1区画進むことを「↑」と書いてみよう。すると、AからBへの1つの道は、→と↑を並べた記号の列と、ぴったり1対1で対応する。

あとは、その記号の並べ方を数えればよい。

解答

⓪ 発想 — どう考え始めるか。 「右か上にだけ進む」ので、 $A$ から $B$ へ行くには右に $4$ 区画、上に $3$ 区画、合わせて必ず $7$ 回進む。どんな経路でも、この回数は変わらない。

違うのは順番だけだ。

だから経路は、 $\to$ を $4$ 個、 $↑$ を $3$ 個並べた文字列と $1$ 対 $1$ で対応する。

$\to\to↑\to↑↑\to, ↑\to\to\to↑\to↑, \dots$

道の問題が、同じものを含む順列の問題に化けた。

$\frac{7 !}{4 ! \times 3 !} = \frac{5040}{24 \times 6} = 35$

$7$ 回のうち、どの $3$ 回を上にするかと読めば、 $_{7} C_{3} = 35$ でも同じこと。経路を、記号の列に翻訳する — これがこの問題の発想だ。

公式最短経路 = 「→ を

a

個・↑ を

b

個」並べる順列

\frac{( a + b )!}{a ! b !}

AからBへ最短で行くには、右へ4区画、上へ3区画進む必要がある。右への1歩を「→」、上への1歩を「↑」で表すと、1つの道は「→を4個、↑を3個」並べた記号の列で表せる。

たとえば $\to\to↑\to↑↑\to$ のように、並べる順番が道の形を決める。

だから、求める道の数は「→を4個、↑を3個(合わせて7個)を1列に並べる」同じものを含む順列だ。

$\frac{7 !}{4 ! \times 3 !} = \frac{5040}{24 \times 6} = \frac{5040}{144} = 35 (通り)$

矢印は全部で7個(右4回 + 上3回)。これは、はしからはしまで進むのに必ず7歩かかることを表している。「→の数 = 横の区画数、↑の数 = 縦の区画数」を図から正しく読み取るのが出発点だ。

まとめ:組合せの形で書けば、7個の場所から→を置く4か所を選ぶ $_{7} C_{4} = 35$ 、あるいは↑を置く3か所を選ぶ $_{7} C_{3} = 35$ でも同じだ。

発展 — 一歩先へ。 最短経路の数え上げは「問題を、別の言葉に翻訳する」という数学の中心的な手口の実例だ。

道 $\to$ 矢印の列 $\to$ 席の選び方 $\to$ 組合せ

翻訳するたびに、問題は解きやすい形になっていく。もとの「道を数える」は幾何の問題に見えるが、最後は $_{7} C_{3}$ というただの計算になった。難しさは、翻訳の前後で移動しているのだ。

この技は先へ行くほど効いてくる。

確率の問題を、場合の数に翻訳する
図形の問題を、座標やベクトルに翻訳する
漸化式を、等比数列に翻訳する

「これは、何の言い換えか?」と問う癖をつけたい。

なお格子の書き込み法は、コンピュータの動的計画法という手法そのものである。「小さい問題の答えを表に記録し、それを足して大きい問題を解く」— カーナビの経路探索も、文章の類似度計算も、この考え方で動いている。紙の上の $35$ という数が、現代の技術と地続きなのだ。

答

35通り

別解

公式を使わず、交差点に数を書き込んでいく方法がある。地図に直接書き込むだけで答えが出る、目で見える解き方だ。

ルールはたった $1$ つ。

「その交差点への行き方の数」 $=$ 「左隣への行き方」 $+$ 「下隣への行き方」

なぜか。ある交差点にたどり着く最後の一歩は、左から来たか、下から来たかのどちらかしかない。だから $2$ つを足せばよい。

まず、 $A$ のある左端の列と、下端の行に $1$ を書く(まっすぐ進むしか行き方がないから、どこも $1$ 通り)。あとは左下から順に足していく。


$1$	$4$	$10$	$20$	$35$
$1$	$3$	$6$	$10$	$15$
$1$	$2$	$3$	$4$	$5$
$1$	$1$	$1$	$1$	$1$

(いちばん下の行が $A$ のある行、右上の $35$ が $B$ である。)

たとえば下から $2$ 行目の $6$ は、左の $3$ と下の $3$ を足したもの。 上の行の $10$ は、左の $4$ と下の $6$ を足したもの。足し算だけで、右上に $35$ が現れる ✓。

この方法の強みは、 $2$ つある。

$1$ つ目: 途中に通れない道があっても使える。 「工事中で通れない交差点」があれば、そこに $0$ を書き込んで先へ進むだけ。公式は通行止めを扱えないが、書き込み法なら何でも来いである。

$2$ つ目: 「必ずこの点を通る」条件も楽勝。 その点までの数と、その点から $B$ までの数を掛ければよい。

そして、この表をよく見てほしい。 $1, 1, 1, 1$ / $1, 2, 3, 4$ / $1, 3, 6, 10$ — 斜めに読むと $1, 3, 3, 1$ や $1, 4, 6, 4$ が現れる。パスカルの三角形が、格子の上に横たわっているのだ。

$_{n} C_{r} =_{n - 1} C_{r - 1} +_{n - 1} C_{r}$

というパスカルの法則は、まさに「左から来るか、下から来るか」の $2$ 択を式にしたものだった。組合せの公式と、格子の足し算は、同じ $1$ つの事実の表と裏である。

パスカルの三角形を「意味のない数の並び」として覚えた人は多い。しかしその正体は、道の数え上げだった — こう分かると、数学の風景が少し違って見えるはずだ。

ポイント

最短経路 → 「→」と「↑」を並べる同じものを含む順列に置きかえる
→の数 = 横の区画数、↑の数 = 縦の区画数
$\frac{7 !}{4 ! 3 !} =_{7} C_{4} =_{7} C_{3} = 35$ 、どの形で書いてもよい

よくある間違い

矢印の数を、区画数ではなく交差点の数で数えてしまう
分母を $4! + 3!$ とたし算にする(正しくはかけ算)
書き込み法で、左端の列や下端の行に $1$ を書き忘れる(端はまっすぐ進むだけで1通り)