- 数学A｜場合の数と確率「最短経路と同じものを含む順列」の基本例題解説ページです。
- 目次をクリックすると各セクションへ移動します。
問題｜最短経路と同じものを含む順列
場合の数と確率 29下の図のような格子状の道路があり、\({\rm A}\) から \({\rm B}\) への最短経路は何通りか？また、\({\rm C}\) を通る最短経路と \({\rm C}\) を通らない最短経路はそれぞれ何通りか？さらに、\({\rm C}\) から \({\rm D}\) の道を通る最短経路は何通りか？
高校数学A｜場合の数と確率
解法のPoint
最短経路と同じものを含む順列
Point：最短経路と同じものを含む順列
進む道順を→の個数と↑の同じものを含む順列として考える。
\({\rm A}\) から \({\rm B}\) に進むとき、右→へ \(4\) 回、上↑へ \(5\) 回の合計 \(9\) 回進む同じものを含む順列として、
\(\displaystyle \frac{\,9!\,}{\,4!\cdot 5!\,}\) 通り
\({\rm A}\) から \({\rm C}\) までの道順
\({\rm C}\) から \({\rm B}\) までの道順
これらをそれぞれ求めて、連続して起こるので、積の法則を用いる。
最短経路の道順は、
進む道順を→の個数と↑の同じものを含む順列として考える。
\({\rm A}\) から \({\rm B}\) に進むとき、右→へ \(4\) 回、上↑へ \(5\) 回の合計 \(9\) 回進む同じものを含む順列として、
\(\displaystyle \frac{\,9!\,}{\,4!\cdot 5!\,}\) 通り
途中の点 \({\rm C}\) を経由する場合
\({\rm A}\) から \({\rm C}\) までの道順
\({\rm C}\) から \({\rm B}\) までの道順
これらをそれぞれ求めて、連続して起こるので、積の法則を用いる。
©︎ 2026 教科書より詳しい高校数学 yorikuwa.com
詳しい解説｜最短経路と同じものを含む順列
場合の数と確率 29
下の図のような格子状の道路があり、\({\rm A}\) から \({\rm B}\) への最短経路は何通りか？また、\({\rm C}\) を通る最短経路と \({\rm C}\) を通らない最短経路はそれぞれ何通りか？さらに、\({\rm C}\) から \({\rm D}\) の道を通る最短経路は何通りか？
高校数学A｜場合の数と確率
\({\rm A}\) から \({\rm B}\) まで進むときの最短経路は、右へ \(4\) 回、上へ \(5\) 回の合計 \(9\) 回進むので、
→が \(4\) 個と↑が \(5\) 個の同じものを含む順列となり、
\(\begin{eqnarray}\require{cancel}~~~&&\displaystyle \frac{\,9!\,}{\,4!\cdot 5!\,}\\[5pt]~~~&=&\displaystyle \frac{\,9 \cdot 8 \cdot 7 \cdot 6 \cdot \cancel{5} \cdot \cancel{4} \cdot \cancel{3} \cdot \cancel{2} \cdot \cancel{1}\,}{\,4 \cdot 3 \cdot 2 \cdot 1 \cdot \cancel{5} \cdot \cancel{4} \cdot \cancel{3} \cdot \cancel{2} \cdot \cancel{1}\,}\\[5pt]~~~&=&\displaystyle \frac{\,9 \cdot \cancel{8}^2 \cdot 7 \cdot \cancel{6}\,}{\,\cancel{4} \cdot \cancel{3} \cdot \cancel{2} \cdot 1\,}\\[5pt]~~~&=&9 \cdot 2 \cdot 7\\[3pt]~~~&=&126\end{eqnarray}\)
したがって、\(126\) 通りとなる
\({\rm A}\) から \({\rm C}\) を経由して \({\rm B}\) に進むとき、
\({\rm A}\) から \({\rm C}\) は右→へ \(2\) 回、上↑へ \(2\) 回の合計 \(4\) 回の同じものを含む順列より、
\(\begin{eqnarray}~~~\displaystyle \frac{\,4!\,}{\,2!\cdot 2!\,}&=&\displaystyle \frac{\,4 \cdot 3 \cdot \cancel{2} \cdot \cancel{1}\,}{\,2 \cdot 1 \cdot \cancel{2} \cdot \cancel{1}\,}\\[5pt]~~~&=&2 \cdot 3\\[3pt]~~~&=&6\end{eqnarray}\)
\({\rm C}\) から \({\rm B}\) は右→へ \(2\) 回、上↑へ \(3\) 回の合計 \(5\) 回の同じものを含む順列より、
\(\begin{eqnarray}~~~\displaystyle \frac{\,5!\,}{\,2!\cdot 3!\,}&=&\displaystyle \frac{\,5 \cdot 4 \cdot \cancel{3} \cdot \cancel{2} \cdot \cancel{1}\,}{\,2 \cdot 1 \cdot \cancel{3} \cdot \cancel{2} \cdot \cancel{1}\,}\\[5pt]~~~&=&5 \cdot 2\\[3pt]~~~&=&10\end{eqnarray}\)
\({\rm A}\) → \({\rm C}\) → \({\rm B}\) と連続して進むので、積の法則より、
\(6{\, \small \times \,}10=60\)
したがって、\(60\) 通りとなる
\({\rm C}\) を通らない最短経路は、
\({\rm A}\) から \({\rm B}\) のすべての経路が \(126\) 通り
\({\rm C}\) を経由する経路が \(60\) 通り
これより、
\(126-60=66\)
したがって、\(66\) 通りとなる
\({\rm A}\) から \({\rm CD}\) を通り、\({\rm B}\) に進むとき、
\({\rm A}\) から \({\rm C}\) は右→へ \(2\) 回、上↑へ \(2\) 回の合計 \(4\) 回の同じものを含む順列より、
\(\begin{eqnarray}~~~\displaystyle \frac{\,4!\,}{\,2!\cdot 2!\,}&=&\displaystyle \frac{\,4 \cdot 3 \cdot \cancel{2} \cdot \cancel{1}\,}{\,2 \cdot 1 \cdot \cancel{2} \cdot \cancel{1}\,}\\[5pt]~~~&=&2 \cdot 3\\[3pt]~~~&=&6\end{eqnarray}\)
\({\rm C}\) から \({\rm D}\) の道順は \(1\) 通り
\({\rm D}\) から \({\rm B}\) は右→へ \(1\) 回、上↑へ \(3\) 回の合計 \(4\) 回の同じものを含む順列より、
\(\begin{eqnarray}~~~\displaystyle \frac{\,4!\,}{\,1!\cdot 3!\,}&=&\displaystyle \frac{\,4 \cdot \cancel{3} \cdot \cancel{2} \cdot \cancel{1}\,}{\,1 \cdot \cancel{3} \cdot \cancel{2} \cdot \cancel{1}\,}\\[5pt]~~~&=&4\end{eqnarray}\)
\({\rm A}\) → \({\rm C}\) → \({\rm D}\) → \({\rm B}\) と連続して進むので、積の法則より、
\(6{\, \small \times \,}1{\, \small \times \,}4=24\)
したがって、\(24\) 通りとなる
