検索用コード
次のような横4区画,\ 縦3区画の道路がある. \\  AからBまで最短距離で行く道順の総数を計算で求める方法を考えよう. \\[1zh]  どの道順を取るにせよ,\ \textbf{\textcolor{orange}{→\,方向に4回}},\ \textbf{\textcolor{green}{↑方向に3回}}移動することになる. \\[.2zh]  よって,\ 道順の総数は,\ \textbf{\textcolor{red}{→\,4個と↑3個を並べる順列の総数}}に等しい. \\[.2zh]  結局,\ \textbf{「\textcolor{blue}{同じものを含む順列}」}の考え方を用いると,\ $\bunsuu{7\kaizyou}{4\kaizyou3\kaizyou}$\ で計算できる. \\\\  これを一般化すると次の公式が得られる. \\[.5zh] \centerline{$\bm{\textcolor{cyan}{縦m区画,\ 横n区画の最短経路の数}は  \centerline{$(\textcolor{orange}{m個の\,→}\,と\textcolor{green}{n個の↑}を並べる順列の数)$} \\\\\\ \centerline{{\normalsize $\left[\textcolor{brown}{\begin{array}{l} 例えば,\ 上図の経路は,\ ただ1つの文字列「↑→→↑→↑→」を意味する. \\ 逆に,\ 文字列「↑→→↑→↑→」は,\ ただ1つの経路(上図)を意味する. \\ このように考えると,\ 最短経路と矢印の並びは\bm{1対1で対応}する. \\ よって,\ 最短経路は,\ 計算が容易な「同じものを含む順列」の扱いで求めれば済む. \\ 通常は同じものを含む順列として考えるので,\ 公式を覚える意味はない. 下図のような碁盤目の道路をAからBまで最短距離で行く. \\[.2zh] \hspace{.5zw}次の道順は何通りあるか. \\[1zh] \hspace{.5zw}(1)\ \ AからBまで行く.   (2)\ \ Pを通る.   (3)\ \ Pを通らない. \\[.5zh] \hspace{.5zw}(4)\ \ PもQも通る.    \ \ \ \hspace{.1zw}(5)\ \ PもQも通らない. \\[1zh] 右へ1区画進むことを\,→},\ \textcolor{green}{上へ1区画進むことを↑}で表す. \\[.2zh] \phantom{ (1)}\ \ AからBまでの道順は,\ \textcolor{orange}{6個の\,→}\,と\textcolor{green}{4個の↑}の順列の総数に等しい. \\[.8zh] \centerline{$\therefore 求める道順は \textcolor{red}{\bunsuu{10\kaizyou}{6\kaizyou4\kaizyou}}=\bm{210\ (通り)}$} \\\\[.5zh]  (2)\ \ \textcolor{cyan}{AからP}までは\,\textcolor{orange}{→\,2個},\ \textcolor{green}{↑1個}の順列であるから $\textcolor{red}{\bunsuu{3\kaizyou}{2\kaizyou1\kaizyou}}=3\ (通り)$ \\[.5zh] \phantom{ (1)}\ \ \textcolor{cyan}{PからB}までは\,\textcolor{orange}{→\,4個},\ \textcolor{green}{↑3個}の順列であるから $\textcolor{red}{\bunsuu{7\kaizyou}{4\kaizyou3\kaizyou}}=35\ (通り)$ \\[.8zh] \centerline{$\therefore 求める道順は \textcolor{red}{3\times35}=\bm{105\ (通り)}$} \\\\[.5zh]  (3)\ \ (1),\ (2)より $求める道順は \textcolor{red}{210-105}=\bm{95\ (通り)}$ \\\\[.5zh]  (4)\ \ (2)より,\ \textcolor{cyan}{AからP}までの道順は3通り. \\[.5zh] \phantom{ (1)}\ \ \textcolor{magenta}{Qの左隣の交差点をQ$’$,\ 右隣の交差点をQ$”$}とする. \\ \phantom{ (1)}\ \ \textcolor{cyan}{PからQ$’$}までは\,\textcolor{orange}{→\,2個},\ \textcolor{green}{↑1個}の順列であるから $\textcolor{red}{\bunsuu{3\kaizyou}{2\kaizyou1\kaizyou}}=3\ (通り)$ \\[.5zh] \phantom{ (1)}\ \ \textcolor{cyan}{Q$”$からB}までは\,\textcolor{orange}{→\,1個},\ \textcolor{green}{↑2個}の順列であるから $\textcolor{red}{\bunsuu{3\kaizyou}{1\kaizyou2\kaizyou}}=3\ (通り)$ \\[.8zh] \centerline{$\therefore 求める道順は \textcolor{red}{3\times3\times3}=\bm{27\ (通り)}$} \\\\[.5zh]  (5)\ \ \textcolor{cyan}{Pを通る}道順は,\ (2)より105通り. \\[.5zh] \phantom{ (1)}\ \ \textcolor{cyan}{Qを通る}道順は  \phantom{ (1)}\ \ \textcolor{cyan}{PもQも通る}道順は,\ (4)より27通り. \\[1zh] \centerline{$\therefore 求める道順は \textcolor{red}{210-(105+45-27)}=\bm{87\ (通り)}$} \\\\ AからPまでとPからB}までの道順をそれぞれ考えればよい. \\ \phantom{(1)}\ \ \text{AからPまでの3通りのいずれに対しても,\ PからBまでは35通りある.} \\ \phantom{(1)}\ \ よって,\ 積の法則を適用する. \\[1zh] (3)\ \ \textbf{\text{「Pを通らない」は,\ 総数から「Pを通る」を引く}}のが基本である. \\[1zh] (4)\ \ (2)と同様に分割して求めればよいが,\ \text{Q}が区画の中点にある. \\ \phantom{(1)}\ \ \text{Q}を通る場合,\ \bm{必ず\text{\textbf{Q}}の両隣の交差点を通る}はずである. \\ \phantom{(1)}\ \ よって,\ \text{Pから左隣の交差点Q}’までと\text{右隣の交差点Q}”から\text{B}までに分割する. \\ \phantom{(1)}\ \ 当然,\ \text{Q}’\,から\text{Q}”までは1通りである. \\[1zh] (5)\ \ \bm{総数から「\text{\textbf{P}}を通る」と「\text{\textbf{Q}}を通る」を引く.} \\ \phantom{(1)}\ \ しかし,\ \text{「Pを通る」と「Qを通る」}は\bm{排反ではない.} \\ \phantom{(1)}\ \ よって,\ 2重に引かないように,\ 重複部分(4)を引いた後で,\ 総数から引く. \\ \phantom{(1)}\ \ \bm{排反ではない2つの条件は,\ ベン図を元に考える}とわかりやすい. \\ \phantom{(1)}\ \ 求めるのは,\ 図の色塗り部分である. \\           下図の碁盤目の道路をAからBまで最短距離で行く道順は何通りか. \\[1zh]  どの道順も,\ \textcolor{red}{4つの交差点C,\ D,\ E,\ Fのうちの1つの交差点を必ず通る.} \\[1zh] 最短経路問題の中で厄介なのは,\ \bm{一部の道路が欠けているパターン}である. \\[1zh] 1つは,\ 欠けた道路を復元し,\ 総数からその道路を通る場合を引く方法がある. \\ 本問の場合,\ 欠けた2つの交差点\text{P,\ Q}を通る場合を引けばよい. \\ ただし,\ この方法は応用性に欠ける. \\ \text{「Pを通る」と「Qを通る」}は排反ではないから,\ 前問のように求めることになる. \\ しかし,\ 欠けた部分の大きさや形次第で複雑になり,\ 手に負えなくなる. \\[1zh] そこで知っておきたいのが,\ \bm{排反に場合分けして直接求める}方法である. \\ \bm{欠けた部分を中心に四角形の対角線で切断し,\ 通る交差点で場合分けする.} \\ どの道順も,\ 交差点\text{C,\ D,\ E,\ F}の1つを必ず通り,\ また複数を通ることはない. \\ よって,\ \text{「Cを通る」「Dを通る」「Eを通る」「Fを通る」は排反である.} \\ 後は,\ \text{[ACB],\ [ADB],\ [AEB],\ [AFB]}の道順の総数をそれぞれ求めればよい.  さて,\ 最短経路問題には,\ ある意味\textbf{\textcolor{blue}{最強の最終手段}}がある. \\  \textbf{\textcolor{red}{和の法則を利用して,\ 全て書き出して数える}}方法である. \\\\  ある交差点Pまでの道順の総数を考えるとする(左下図). \\  \textbf{\textcolor{magenta}{Pに到達するとき,\ 必ずSとTの一方を通ってくる}}はずである. \\  よって,\ 「S→P」と「T→P」は排反であり,\ 次の式が成立する. \\[.5zh] \centerline{$\bm{\textcolor{red}{(\text{\textbf{P}}まで道順の総数)}=\textcolor{orange}{(\text{\textbf{S}}までの道順の総数)}+\textcolor{green}{(\text{\textbf{T}}までの道順の総数)}}$} \\[.5zh]  この式を適用して,\ 右下図のように順に書き込んでいけば確実に求まる. \\  つまり,\ \textbf{\textcolor{red}{左の交差点と下の交差点の和を各交差点に書き込んでいく.}} \\  存在しない部分は0と考えればよい. \\\\ 最短経路の確率は, 落とし穴に要注意!}} \\  \ \text{\rei\ \textbf{上と右を等確率$\bm{\bunsuu12}$で選ぶとき, 右上の図の経路を通る確率} 35通りの最短経路のうちの1つであるから $\bunsuu{1}{35}$ ← \textbf{\textcolor{red}{間違い!}}} \\ \text{ \  \ \textbf{\textcolor{blue}{正解}} \maru1 \textcolor{red}{最初の4回は↑と→から→を選ぶが, 残り3回は↑しか選べない}から  \text{ \  \ *要するに, 注意すべきことは\textbf{\textcolor{magenta}{\underline{35通りの最短経路は同じ確からしさで選ばれるわけではない}}}ということである.}