最短経路

問題

　上の図のような道がある．

(1)　地点Aから地点Bまでの最短な道順は何通りか．

(2)　地点Pと地点Qが通れないとき，最短な道順は何通りか．

【中部大学　2020　(文言変更)】

解答

(1)　→に5回，↑に5回移動すればよい．同じものを含む順列と考えると，

${\displaystyle \frac{10!}{5!\cdot 5!}}={\displaystyle \frac{10\cdot 9\cdot 8\cdot 7\cdot 6}{5\cdot 4\cdot 3\cdot 2\cdot 1}}=252$通り

(2)

　上記のように点C、D、E、Fを設定する．

(A)　Pを通るとき，特にA→C→D→Bのとき

${\displaystyle \frac{3!}{2!1!}}\cdot 1\cdot {\displaystyle \frac{6!}{3!}}=60$通り

(B)　Qを通るとき，特にA→E→F→Bのとき

${\displaystyle \frac{7!}{3!4!}}\cdot 1\cdot {\displaystyle \frac{2!}{1!}}=70$通り

(C)　PとQを通るとき，特にA→C→D→E→F→Bのとき

${\displaystyle \frac{3!}{1!}}\cdot 1\cdot {\displaystyle \frac{3!}{1!}}\cdot 1\cdot {\displaystyle \frac{2!}{1!}}=18$通り

(A)～(C)よりPまたはＱを通るものは

$60+70-18=112$通り

よって，P，Qが通れないときの最短経路は

$252-112=140$通り