1. 問題の内容
ある地域の道が図で示されています。交差点Aから交差点Bまで、遠回りをせずに最短の道順で行く方法は全部で何通りあるかを求める問題です。
2. 解き方の手順
この問題は、同じものを含む順列の考え方を使うか、各交差点に到達する経路数を書き込んでいく方法で解くことができます。ここでは後者の方法で説明します。
* まず、各交差点に到達する方法の数を書き込んでいきます。
* 交差点Aから出発して、右と上に進むことしかできません。
* 各交差点に到達する方法の数は、その交差点に到達できる2つの交差点から来る経路数の和になります。
* 例えば、Aから右に1つ進んだ交差点には1通りの方法でしか到達できません。同様に、Aから上に1つ進んだ交差点にも1通りの方法でしか到達できません。
* Aから右に1つ進んだ交差点のすぐ上の交差点には、左から来る1通りと下から来る1通りがあるので、1 + 1 = 2通りの方法で到達できます。
* 同様にして、すべての交差点に到達する方法の数を書き込んでいきます。
* 最終的に、交差点Bに到達する方法の数が答えとなります。
図に書き込むと以下のようになります。
```
1 4 10 20
1 3 6 10
A 1 2 3 4 B
```
3. 最終的な答え
20通り