7段の階段を1回に1段または2段ずつ上る方法は何通りあるか。また、図のような碁盤目状の街路において、指定された区間を通らずにPからQへ行く最短経路は何通りあるか、という問題です。

1. 問題の内容

7段の階段を1回に1段または2段ずつ上る方法は何通りあるか。また、図のような碁盤目状の街路において、指定された区間を通らずにPからQへ行く最短経路は何通りあるか、という問題です。

2. 解き方の手順

(3) 階段の問題：

* $a_n$ を $n$ 段の階段を上る方法の数とします。

* 1段上るか、2段上るかのいずれかなので、漸化式は $a_n = a_{n-1} + a_{n-2}$ となります。

* 初期条件は $a_1 = 1$ (1段を1回で上る)と、$a_2 = 2$ (1段ずつ上る、または2段一度に上る)です。

* $a_3 = a_2 + a_1 = 2 + 1 = 3$

* $a_4 = a_3 + a_2 = 3 + 2 = 5$

* $a_5 = a_4 + a_3 = 5 + 3 = 8$

* $a_6 = a_5 + a_4 = 8 + 5 = 13$

* $a_7 = a_6 + a_5 = 13 + 8 = 21$

(4) 街路の問題：

* PからQへの最短経路は、右に4回、上に3回移動するものです。

* 経路の総数は $_{4+3}C_4 = _7C_4 = \frac{7!}{4!3!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$ 通りです。

* aを通る経路の数を計算します。Pからaの左下の点まで1通り、aの右上の点からQまで $_{2+2}C_2 = _4C_2 = \frac{4!}{2!2!} = \frac{4 \times 3}{2 \times 1} = 6$ 通り。したがって、aを通る経路は $1 \times 6 = 6$ 通り。

* bを通る経路の数を計算します。Pからbの左下の点まで $_{3+1}C_3 = _4C_3 = 4$ 通り、bの右上の点からQまで1通り。したがって、bを通る経路は $4 \times 1 = 4$ 通り。

* aとbの両方を通る経路の数を計算します。Pからaの左下の点まで1通り、aの右上の点からbの左下の点まで $_{1+1}C_1 = 2$通り、bの右上の点からQまで1通り。したがって、aとbの両方を通る経路は $1 \times 2 \times 1 = 2$ 通り。

* aまたはbを通る経路の数は、$6 + 4 - 2 = 8$ 通り。

* したがって、aもbも通らない経路の数は、$35 - 8 = 27$ 通り。

3. 最終的な答え

(3) 21通り

(4) 27通り