右の図のように、ある街には東西に 6 本、南北に 7 本の道がある。つぎのよ
うに移動する場合最短経路で行く道順は何通りありますか。
(1)P から Q まで行く。(2)P から R を通って、Q まで行く。
(3)P から S を通らずに、Q まで行く。
東に 1 区画進むことを a、北に 1 区画進むことを b とおく。
(1) 解)P から R まで最短経路で行く道順の総数は、5 個の a と 6 個の b を 1 列に
並べる順列の総数に等しい。a と b の合計 11 文字すべてを区別する。それを１列に
並べる方法は。11!通りある。その後、a6 つ、b5 つの区別をなくすとそれぞれ 6!通
り、5!通りずつ同じものが出てくる。したがって、全体の並べ方は
11!
6!5! = 11 × 10 × 9 × 8 × 7 × 6!
6!5! = 11 × 10 × 9 × 8 × 7
5 × 4 × 3 × 2 × 1 = 462 (通り) · · · (答)
2
(1) 別解)P から R までの最短経路は必ず a を 6 回 b を 5 回の合計 11 回行う。何番
目の移動で b を行うかを 5 回重複を許さず選べばよい。
したがって、全体の並び方は、
11C5 = 11 × 10 × 9 × 8 × 7
5 × 4 × 3 × 2 × 1 = 462 (通り) · · · (答)
(1) 別解)つぎの方法で、各地点に道順の総数を記載していく。
まず、Pから1直線で行ける地点に、1と記載する。
残りの地点について、南に１戻った地点と西に1戻った地点の道順の総数を記載する。
図3つ
(2) P から R まで最短経路で行く道順の総数は、2 個の a と 2 個の b を 1 列に並
べる順列の総数に等しい。また、R から Q まで最短経路で行く道順の総数は、4 個
の a と 3 個の b を 1 列に並べる順列の総数に等しい。
したがって、求める道順の総数は
4!
2!2! × 7!
3!4! = 6 × 35 = 210 (通り) · · · (答
(3)Sを通るPからQまでの道順の総数を求めて、(1)の答えから引けばよい。
Sを通る道順は、PからSの左の点に向かう道順の総数(ⅰ)と、Sの右の点からQに向かう点に向かう道順の総数(ⅱ)との積になる。
(ⅰ)3個のa, 2個のbを並べる順列の総数と等しいので、5!/3!2!(通り)
(ⅱ)2個のa, 3個のbを並べる順列の総数と等しいので、5!/3!2!(通り)
よってSを通り、PからQまでの道順の総数は、5!/3!2!×5!/3!2!=10×10=100(通り)
したがって、答えは、462-100=362(通り)
