画像の問題16は、ある街の道路網が与えられ、点Aから点Bへ行く最短経路の数、点Cを通る最短経路の数、そして点Cを通り点Dを通らない最短経路の数を求める問題です。

1. 問題の内容

画像の問題16は、ある街の道路網が与えられ、点Aから点Bへ行く最短経路の数、点Cを通る最短経路の数、そして点Cを通り点Dを通らない最短経路の数を求める問題です。

2. 解き方の手順

まず、AからBへの最短経路の総数を求めます。AからBへは、右に5回、上に3回移動する必要があります。したがって、8回の移動のうち、右への移動を5回選ぶ組み合わせの数が最短経路の総数となります。これは組み合わせの数 ${}_8C_5$で計算できます。

次に、AからCを通ってBへ行く最短経路の数を求めます。AからCへは、右に2回、上に1回移動する必要があります。CからBへは、右に3回、上に2回移動する必要があります。AからCへの最短経路の数は${}_3C_2 = 3$であり、CからBへの最短経路の数は${}_5C_3 = 10$です。したがって、AからCを通ってBへ行く最短経路の数は$3 \times 10 = 30$です。

最後に、AからCを通るがDを通らない最短経路の数を求めます。AからCを通る経路数はすでに求めました。AからCを通ってDを通る経路数を計算し、それを全体の経路数から引けば、AからCを通りDを通らない経路数が求まります。AからCへの経路数は${}_3C_2 = 3$です。CからDへの経路数は右に1回、上に1回移動するので${}_2C_1 = 2$です。DからBへの経路数は右に2回、上に1回移動するので${}_3C_2 = 3$です。したがって、AからCを通ってDを通ってBに行く経路数は$3 \times 2 \times 3 = 18$です。よって、AからCを通りDを通らない経路数は、$30 - 18 = 12$です。

3. 最終的な答え

* AからBへ行く最短経路は ${}_8C_5 = \frac{8!}{5!3!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56$通り。

* そのうち、Cを通るものは30通り。

* また、AからBへ行く最短経路のうち、Cを通りDを通らないものは12通り。