右図のような道のある地域で、以下の問いに答える問題です。 (1) AからBまで行く最短経路は何通りあるか。 (2) AからCを通ってBまで行く最短経路は何通りあるか。 (3) AからCを通らずにBまで行く最短経路は何通りあるか。 また、りんご、バナナ、みかんの3種類の果物で10個盛りの果物かごを作るとき、何通りの作り方があるか。ただし、入らない果物があってもよい。

1. 問題の内容

右図のような道のある地域で、以下の問いに答える問題です。

(1) AからBまで行く最短経路は何通りあるか。

(2) AからCを通ってBまで行く最短経路は何通りあるか。

(3) AからCを通らずにBまで行く最短経路は何通りあるか。

また、りんご、バナナ、みかんの3種類の果物で10個盛りの果物かごを作るとき、何通りの作り方があるか。ただし、入らない果物があってもよい。

2. 解き方の手順

(1) AからBまでの最短経路

AからBまで行くには、右に4回、上に5回移動する必要があります。したがって、全移動回数は9回です。

このうち、右への移動を4回選ぶ場合の数を求めれば良いので、組み合わせの計算を行います。

$_{9}C_{4} = \frac{9!}{4!5!} = \frac{9 \times 8 \times 7 \times 6}{4 \times 3 \times 2 \times 1} = 126$

(2) AからCを通ってBまでの最短経路

AからCまでの最短経路は、右に2回、上に2回移動する必要があります。したがって、全移動回数は4回です。

このうち、右への移動を2回選ぶ場合の数を求めれば良いので、組み合わせの計算を行います。

$_{4}C_{2} = \frac{4!}{2!2!} = \frac{4 \times 3}{2 \times 1} = 6$

CからBまでの最短経路は、右に2回、上に3回移動する必要があります。したがって、全移動回数は5回です。

このうち、右への移動を2回選ぶ場合の数を求めれば良いので、組み合わせの計算を行います。

$_{5}C_{2} = \frac{5!}{2!3!} = \frac{5 \times 4}{2 \times 1} = 10$

したがって、AからCを通ってBまで行く最短経路は、$6 \times 10 = 60$通りです。

(3) AからCを通らずにBまでの最短経路

AからBまでの最短経路から、AからCを通ってBまでの最短経路を引けば、AからCを通らずにBまでの最短経路が求められます。

$126 - 60 = 66$

果物かごの問題

りんご、バナナ、みかんをそれぞれx, y, z個入れるとすると、$x + y + z = 10$を満たす非負整数の組(x, y, z)の数を求める問題になります。

これは、10個の〇と2本の仕切り｜を並べる場合の数と考えることができます。例えば、〇〇｜〇〇〇｜〇〇〇〇〇は、りんご2個、バナナ3個、みかん5個を表します。

したがって、全部で12個の場所から仕切りを入れる場所2つを選ぶ組み合わせを考えます。

$_{12}C_{2} = \frac{12!}{2!10!} = \frac{12 \times 11}{2 \times 1} = 66$

3. 最終的な答え

(1) 126通り

(2) 60通り

(3) 66通り

果物かご：66通り