【応用】最短経路の数
ここでは、最短経路の数について見ていきます。【標準】最短経路の数での内容を少し応用した問題を考えます。また、困ったときに使える技も紹介します。
通らない最短経路
(1) Cを通らない行き方は何通りあるか。(2) Dを通らない行き方は何通りあるか。
(3) CもDも通らない行き方は何通りあるか。
「通らない」経路を直接考えるのは面倒です。Cを通らない経路は、スタートしてすぐに右に進む経路や、上に2回進む経路、上に3回進む経路があり、ケースが多いです。直接数えるよりも、全体から「通る」経路を除いたほうが考えやすいです。【標準】反対側を数えるや【基本】補集合の要素の個数で見た、補集合を使った考え方ですね。
Cを通る場合は、Cの左の交差点、Cのすぐ右の交差点の2か所を両方とも通らなければなりません。他の道は自由です。Cの左の交差点への経路は1通りです。Cのすぐ右の交差点からBに行くには、5回の移動のうち、2回上に移動するので ${}_5 \mathrm{ C }_2$ 通りです。AからBまでは、7回の移動のうち3回上に移動すればいいので、(1)の答えは\[ {}_7 \mathrm{ C }_3 -1\times {}_5 \mathrm{ C }_2 = 35-10=25 \]通り、となります。
同じように、(2)も、Dを通る経路を考えましょう。AからDへは、5回の移動のうち2回上に行けばいいです。DからBへは、2回の移動のうち1回上に行けばいいですね。それぞれ独立に経路を選べるので、(2)の答えは\[ {}_7 \mathrm{ C }_3 -{}_5 \mathrm{ C }_2\times {}_2 \mathrm{ C }_1 = 35-20=15 \]通り、となります。
次に(3)ですが、これは少し注意が必要です。「CもDも通らない」経路以外というのは、「Cを通る、または、Dを通る」です。「かつ」ではないことに注意です（参考：【標準】補集合の要素の個数）。「または」なので、【基本】和集合の要素の個数で見たように、それぞれの個数の和から、共通部分を除外しないといけません。
共通部分というのは、「CもDも通る」経路ということです。Aを出発し、Cの左側の交差点を通り、Cのすぐ右側の交差点も通り、Dに移動してから、Bに移動する、という経路です。(1)や(2)と同様に考えると\[ 1\times {}_3 \mathrm{ C }_1 \times {}_2 \mathrm{ C }_1=6 \]通りとなります。(1)と(2)の計算途中から、「Cを通る」経路は10通り、「Dを通る」経路は20通り、先ほど求めた通り、「CもDも通る」行き方は6通りなので、「Cを通る、または、Dを通る」経路の数は\[ 10+20-6=24 \]通りとなります。よって、「CもDも通らない」行き方は\[ 35-24=11 \]通り、となります。
なお、「Cを通らない」ということは、図が次のようになっていることと同じです。
Cを通る道がない状態です。上の図に対してAからBへの最短経路の数を聞かれたときにも、今回の例題と同じように解きます。
では、「Dを通らない」というのは、道がどうなっているときでしょうか。次のように、Dを通るすべての道がない取り除いたときと同じです。
問題の設定が変わっても、同じように考えられるようになりましょう。
困ったときに使える技
さて、最短経路の個数を数える問題では、「〇回移動するうち、〇回上に移動する方法」を数える方法を使ってきました。しかし、上のように複雑な状況になってくると、本当に答えがあっているか不安になることもあると思います。そうしたときに使えるチェック方法があるので紹介しておきます。
【標準】最短経路の数#ゴール直前の状況についてでも書きましたが、ゴールは、左から来るか下から来るかしかありません。ただ、これはゴール時点だけでなく、すべての点で成り立ちます。
そのため、各点について、左の点への経路数と下の点への経路数を足すと、その点への経路数が出てくることになります。
ためしにやってみましょう。上の例題の(3)「CもDも通らない」行き方を考えます。3回目の移動までを書いた状態が、下の図です。
まず、点Aは1通りです。Aの右の点、Aの上の点も1通りです。Cの右の点は、Cを通らないため下から来るしかないから、1通りとなります。Aから右へ2、上へ1移動した点は、左からと下からの行き方があり、それぞれ1通りなので、この点への行き方は2通りとなります。
通らない道に注意して、左の点の数字と下の点の数字をどんどん足していくだけです。最後まで数字を書いていくと、次のようになります。
Dを通らないことに注意すると、上のようになります。Bへの経路数は、左の点の数字と下の点の数字を足して、11通りとなり、例題(3)の答えと一致します。道が大きくなると使えませんが、小さい場合には、このやり方で計算結果を確かめるために使えます。
おわりに
ここでは、最短経路の数を求める問題を考えました。今まで学んだことを組み合わせて解くので、不安な部分がある場合は、前に戻って復習しながら考えましょう。
また、困ったときに使える技も紹介しました。検算で使えるので、これも覚えておきましょう。
