問題は2つあります。 (1) 等式 $x+y+z=9$ を満たす自然数 $x, y, z$ の組の個数を求める。 (2) 図のような街路において、PからQまで行く最短経路について、 (i) 総数 (ii) Rを通る経路の数 (iii) ×印の箇所を通らない経路の数を求める。

1. 問題の内容

問題は2つあります。

(1) 等式 $x+y+z=9$ を満たす自然数 $x, y, z$ の組の個数を求める。

(2) 図のような街路において、PからQまで行く最短経路について、

(i) 総数

(ii) Rを通る経路の数

(iii) ×印の箇所を通らない経路の数を求める。

2. 解き方の手順

(1)

$x, y, z$ は自然数なので、$x \ge 1, y \ge 1, z \ge 1$ である。

$x' = x - 1, y' = y - 1, z' = z - 1$ とおくと、$x', y', z' \ge 0$ であり、

$x = x' + 1, y = y' + 1, z = z' + 1$ となる。

$x+y+z = (x'+1) + (y'+1) + (z'+1) = x' + y' + z' + 3 = 9$

よって、$x' + y' + z' = 6$ を満たす非負整数 $x', y', z'$ の組の個数を求める。

これは、6個の〇と2本の仕切りの並び方の総数に等しい。

したがって、求める組の個数は、

$\binom{6+2}{2} = \binom{8}{2} = \frac{8 \times 7}{2 \times 1} = 28$

(2)

(i) PからQまでの最短経路の総数

PからQまで行くには、右に5回、上に4回移動する必要がある。

よって、最短経路の総数は、

$\binom{5+4}{4} = \binom{9}{4} = \frac{9 \times 8 \times 7 \times 6}{4 \times 3 \times 2 \times 1} = 126$

(ii) Rを通る経路の数

PからRまでの最短経路の数は、右に2回、上に2回移動する必要があるので、

$\binom{2+2}{2} = \binom{4}{2} = \frac{4 \times 3}{2 \times 1} = 6$

RからQまでの最短経路の数は、右に3回、上に2回移動する必要があるので、

$\binom{3+2}{2} = \binom{5}{2} = \frac{5 \times 4}{2 \times 1} = 10$

したがって、PからRを通ってQまで行く最短経路の数は、

$6 \times 10 = 60$

(iii) ×印の箇所を通らない経路の数

PからQまでの最短経路の総数は126通り。

×印の箇所を通る最短経路の数を求める。

Pから×印の箇所までの最短経路の数は、右に1回、上に2回移動する必要があるので、

$\binom{1+2}{2} = \binom{3}{2} = \frac{3 \times 2}{2 \times 1} = 3$

×印の箇所からQまでの最短経路の数は、右に4回、上に2回移動する必要があるので、

$\binom{4+2}{2} = \binom{6}{2} = \frac{6 \times 5}{2 \times 1} = 15$

したがって、Pから×印を通ってQまで行く最短経路の数は、

$3 \times 15 = 45$

したがって、×印の箇所を通らない経路の数は、

$126 - 45 = 81$

3. 最終的な答え

(1) 28個

(2)

(i) 126通り

(ii) 60通り

(iii) 81通り