最短経路の組合せ
今回は、最短経路を求める問題です。下の図のように、
\(A\) から、右に \(5\) 回、上に \(6\) 回進むと \(B\) にたどり着くので、\(A\) から \(B\) までの進み方は、
→→→→→↑↑↑↑↑↑
の並び方の場合の数と一致する。
最短経路の問題
下の図のように、道路が碁盤の目のようになった街がある。地点 \(A\) から地点 \(B\) までの長さが最短の道を行く時、次の場合は何通りの道順があるか。
(1) 全部の道順
(2) 地点 \(C\) を通る
(3) 地点 \(P\) は通らない
(4) 地点 \(P\) も地点 \(Q\) も通らない
解説
(1) 全部の道順
\(A\) から、右に \(5\) 回、上に \(6\) 回進むと \(B\) にたどり着くので、\(A\) から \(B\) までの進み方は →→→→→↑↑↑↑↑↑の並び方の場合の数と一致する。
\({}_{11}C_5=\displaystyle\frac{{}_{11}P_5}{5!}\)
\(=\displaystyle\frac{11\times 10\times 9\times 8\times 7}{5\times 4\times 3\times 2\times 1}=462\)
(2) 地点 \(C\) を通る
\(A\) から\(C\) までの進み方
\({}_3C_1=3\)
\(C\) から \(B\) までの進み方
\({}_8C_4=\displaystyle\frac{{}_8P_4}{4i}\)
\(=\displaystyle\frac{8\times 7\times 6\times 5}{4\times 3\times 2\times 1}=70\)
よって、\(3\times 70=210\)
(3) 地点 \(P\) は通らない
（全体）\(-\)（\(P\) を通る）
地点 \(P\) を通る。
\({}_5C_2=\displaystyle\frac{{}_5P_2}{2i}=10\)
\({}_5C_2=\displaystyle\frac{{}_5P_2}{2i}=10\)
よって、\(10\times 10=100\)
したがって、\(462-100=362\)
(4) 地点 \(P\) も地点 \(Q\) も通らない
（全体）\(-\)（（\(P\) を通る）\(+\)（\(Q\) を通る）\(-\)（\(P\) と \(Q\) を通る））
全体
(1) より \(462\) 通り
\(P\) を通る
\({}_5C_2\times {}_5C_2=10\times 10=100\) 通り
\(Q\) を通る
\({}_7C_3\times {}_3C_1=35\times 3=105\) 通り
\(P\) と \(Q\) を通る
\({}_5C_2\times {}_3C_1=10\times 3=30\) 通り
よって、\(462-(100+105-30)=287\)
おわりに
さいごまで記事を読んでいただきありがとうございました！
数学は、時間をかけて勉強すれば誰でも成績を上げられます！
しかし、時間には限りがあります。
アプリや塾/家庭講師など自分に合ったサポートを取り入れることで、限りある時間を効率的に使うことができます。
▼自走して学習が進められる人
日々の悩みを解決できるコーチング面談や日々の学習計画を見直せるサポートがおすすめです。
▼自走して学習が進められない人
毎週講師による授業をしっかり受けて、宿題を設定してもらうサポートがおすすめです。
コメントはお気軽に♪