道順

概要

道順の問題は、一見何の分野の問題なのかわからないが、一時期大流行したダンスダンスレボリューションのようなイメージで、 「→」「↑」の並び替えと考えると、場合の数の問題になる。「→」は右に一マス、「↑」は上に一マスという意味。左とか下に行ってしまうと、最短経路にならなくなる。（もちろんスタートが左下ではない場合は別）

よく 「最短経路問題」 とも呼ばれるが、現実では碁盤目状の道があるのは、京都や札幌くらいで、我々の手にはGoogle Mapがあるので、あまり現実世界では役立たないように思う。

例

図のような道のある町で、 $A$ から $B$ までの最短経路のうち、次のものの総数を求めよ。

$(1)$ 最短経路すべて

$(2)P$ を意地でも通る

$(3)$ 道 $QR$ が工事中で通れない

$(1)$「→」$6$ 個、「↑」$5$ 個の並び替えと考えて、

$${}_{11} \mathrm{C} _ 5=462$$

で $462$ 通りと求められる。

$(2)A$ から $P$ までの道順は、「→」$2$ 個、「↑」$2$ 個の並び替えと考えて、

$${}_{4} \mathrm{C} _ 2=6$$

なので $6$ 通り。$P$ から $B$ までの道順は、「→」$4$ 個、「↑」$3$ 個の並び替えと考えて、

$${}_{7} \mathrm{C} _ 3=35$$

なので $35$ 通り。これらの道順は独立なので、掛け算ができて、

$$6\times 35=210$$

で $210$ 通りと求められる。

$(3)$ 余事象で考える。つまり、全体の道順の数から、$QR$ を通ってしまう道順の数を除けば良い。$QR$ を通ってしまう道順の数は、$(2)$ と同様に掛け算で考えることができる。

まず$A$から$Q$までの道順は、「→」$3$個、「↑」$3$個の並び替えと考えて、

$${}_{6} \mathrm{C} _ 3=20$$

なので $20$ 通り。$Q$ から $R$ までの道順は $1$ 通り。$R$ から $B$ までの道順は、「→」$2$ 個、「↑」$2$ 個の並び替えと考えて、

$${}_{4} \mathrm{C} _ 2=6$$

なので $6$ 通り。これらの道順は独立なので、掛け算ができて、

$$20\times 1\times 6=120$$

で $120$ 通りと求められる。よって、$(1)$ で求めた全体から引いて、

$$462-120=342$$

で、$342$ 通りと求められる。

補足

ここでは解説しなかったが、中学入試などでよく用いられる「書き込み方式」も威力を発揮することもある。