以下のような横4区画,\ 縦3区画の道路がある.
AからBまで最短距離で行く道順の総数を計算で求める方法を考えよう.
どの道順を取るにせよ,\ →\,方向に4回,\ ↑方向に3回移動することになる.
よって,\ 最短経路の総数は,\ →\,4個と↑3個を並べる順列の総数に等しい.
結局,\ 同じものを含む順列に帰着するから,\ $7!}{4!3!}$\ として求められる.
一般化すると以下の公式が得られるので,\ 参考までに示しておく.
$縦m区画,\ 横n区画の最短経路の総数は
$(m個の\,→}\,とn個の↑}を並べる順列の総数)$}
公式の導出・意味合いが重要なのであり,\ 数式のみを丸暗記してはならない.
例えば,\ 上図の経路は,\ ただ1つの文字列「↑→→↑→↑→\,」を意味する.
逆に,\ 文字列「↑→→↑→↑→\,」は,\ ただ1つの経路(上図)を意味する.
つまり,\ 最短経路と矢印の並びは1対1で対応する.}
そして,\ この矢印の並びは同じものを含む順列にすぎないというわけである.
下図のような碁盤目の道路をAからBまで最短距離で行く.\ 次の道順は何通りあるか.
\ lll}
(1)\ \ AからBまで行く. & (2)\ \ Pを通る. & (3)\ \ Pを通らない.
(4)\ \ PもQも通る. & (5)\ \ PもQも通らない. & (6)\ \ Pで右折禁止.
\end{tabular} [-.5zh]
\ \ \ (7)\ \ 3回以上連続して右に進む.
\ \ \ (8)\ \ 交差点で4回曲がる.
右へ1区画進むことを\,→},\ 上へ1区画進むことを↑}で表す.
(1)\ \ AからBまでの道順は,\ 6個の\,→}\,と4個の↑}の順列の総数に等しい.
AからPまでとPからB}までの道順を分けて求めればよい.
AからPまでの道順の3通りのいずれに対しても,\ PからBまでの道順は35通りある.}
よって,\ 積の法則を適用する.
通らない点がある場合,\ 総数から通る場合の数を引く}のが基本である.
通る点が区画の途中にある場合,\ その両端の交差点を通る}と考えればよい.
よって,\ 本問の場合,\ A\ →\ P\ → Q’\ →\ Q”\ →\ B\ という道順の総数を求めることになる.
当然,\ Q}’\,からQ}”までは1通りである.
ある交差点までの道順の総数は,\
その1つ左の交差点までの道順の総数と
その1つ下の交差点までの道順の総数の
和に等しい.
よって,\ 右図より 87\ (通り)} \\[-12zh]
総数からPを通る場合とQを通る場合を除けばよい.}
しかし,\ 「\,Pを通る」と「\,Qを通る」}は互いに排反ではない.}
排反でない2つの条件は,\ ベン図でとらえる}とわかりやすい.\ 求めるべきは,\ 図の色塗り部分である.
通らない点が多くなると,\ 全体から通る場合を除いて求める方法は複雑で難しくなる.
そこで知っておきたいのが,\ 排反な場合分けにより直接的に求める}方法である(別解1).
まず,\ 通らない経路を除いてできる四角形の対角線を含むように斜めに切断する.}
そして,\ 切断線上のどこの交差点を通るかで場合分けする}と,\ 互いに排反な場合分けになる.
実際,\ どの道順もa,\ b,\ c}のうちただ1つを通る.
よって,\ 「\,aを通る」「\,bを通る」「\,cを通る」は互いに排反である.}
d,\ e,\ f,\ g}についても同様なので,\ 二段階で場合分けしてすべての場合を尽くす.
場合分けは多くなるが,\ 汎用性の高い解法である.\ リスクも少ない.
さて,\ 最短経路問題には,\ ある意味最強の最終手段がある.}
和の法則を利用して,\ すべて書き出して数える}方法である(別解2).
ある交差点 Pまでの道順の総数を考えるとする.
Pを通る\dot{す}\dot{べ}\dot{て}の道順は,\ 1つ左の交差点 Sまたは1つ下の交差点 Tの\dot{一}\dot{方}\dot{の}\dot{み}を通る.
よって,\ (P}までの道順の総数)=(S}までの道順の総数)+(T}までの道順の総数)}\ が成り立つ.
結局,\ 1つ左の交差点と1つ下の交差点の和を各交差点に書き込んでいく}としらみつぶしできる.
存在しない部分は0と考えればよい. \\[-17zh]
(6)\ \ Pの1つ下の交差点をP$’$,\ \ 1つ右の交差点をP$”$}とする.
総数から右折する場合の数を引く.\ 右折する場合は,\ 3つの交差点を通る}と考える.
(7)\ \ \.{最}\.{初}\.{に}3回以上連続して右に進むことが何区画目から始まるか}で場合分けする.
以下,\ →\ でも↑でもよいことを＊で表す.}\ ただし,\ 下線部に→→→は現れない.}
同じものを含む順列における連続条件}は,\ 以前取り上げた重複順列における連続条件と同様に扱う.}
最初に連続が始まるのがどこからかを基準とする}と,\ 互いに排反}な場合分けができるのであった.
また,\ 何個連続するかで場合分けする必要はなく,\ 3個以上連続する順列をまとめて考えられる.
本問が重複順列の場合と異なるのは,\ →\ と↑の個数がそれぞれ6個,\ 4個と決まっていることである.
最初の\ →→→\ の位置で場合分けした後,\ 残り3個の\ →\ の位置を＊から選べば全体の順列が決まる.}
最初の\ →→→\ の位置で場合分けしているのであるから,\ 下線部に\ →→→\ が含まれてはならない.
→\ は残り3個なので4個以上の\ →\ が連続することはなく,\ 容易に\ →→→\ を含む場合を除外できる.
解答は簡潔に済ませているが,\ ここに至るまでの過程は容易ではない.\ 初見では難しく感じるだろう.
そこで早々に諦めるか必死に粘るかが,\ 場合の数を得意源にできる人とできない人の違いである.
手を動かし頭を働かせる中で,\ 問題の本質に気付くことができれば後は容易である.
本問には,\ 大きく2つの気付くべきポイントがある.
交差点で曲がるとはいっても,\ 最短距離で行くのでその曲がり方は\ →↑か↑→\ の2通りしかない.}
それに応じて,\ 計4回曲がるのは[1],\ [2]の2つの場合に限られることが1つ目のポイントである.
2つのポイントは,\ 各場合の数をどのようにして求めるかである.
[1]}\ \ 5つの区画\ ①\ →･･･→\ |\ ②\ ↑･･･↑\ |\ ③\ →･･･→\ |\ ④\ ↑･･･↑\ |\ ⑤\ →･･･→\ に分けて考える.
\ \ 要は,\ →\ 6個と↑4個を5つの区画に分けて入れる方法が何通りあるか}を求めればよい.
\ \ ここで,\ →\ が入るのは①,\ ③,\ ⑤のみ,\ ↑が入るのは②,\ ④のみであり,\ 互いに影響しない.}
\ \ さらに,\ 1つの区画には少なくとも1つの矢印が入る}ことにも注意する.
\ \ →\ と↑は互いに影響しないから別々に考えて最後に掛ければよい.
\ \ まず,\ 6個の\ →\ を①,\ ③,\ ⑤に分けて入れる方法が何通りあるかを求める.
\ \ 同じものをいくつかの組に分ける場合,\ 間に仕切りを入れる}と考えるとよい(後に詳しく学習).
\ \ 6個を3組(0個の組不可)に分けることは,\ 間5ヶ所から2ヶ所選んで仕切りを入れること}である.
\ \ つまり,\ →\ _\land\ →\ _\land\ →\ _\land\ →\ _\land\ →\ _\land\ →}\ \ の5個の\ _\land\ から2個選べばよく,\ C52\,通りである.
\ \ ②,\ ④に分けて入れる方法についても同様に,\ ↑\ _\land\ ↑\ _\land\ ↑\ _\land\ ↑}\ \ の3個の\ _\land\ から1個選ぶ.
\ \ このように,\ 同じものを含む順列で変化の回数を考える問題は,\ 結局組分け問題に帰着する.}
以上の考え方が図形的にどのような意味合いをもつかも確認しておく.
計4回曲がるとき,\ 最短経路の長さを無視した大まかな形は[1],\ [2]の2通りのどちらかである.
[1]}\ \ 出発直後と到着直前に通る経路は,\ 右図の横線V,\ Z}上の一部であることは確定である(1通り).
\ \ VからZ}に至る間に,\ 2回の縦方向の移動と1回の横方向の移動がある.
\ \ この移動に使われる縦線2本と横線1本を選べば,\ AからB}までの1つの経路が定まる.
\ \ 例えば,\ 縦線c,\ f},\ 横線 Xを選んだ場合は,\ 図の青線の経路を通ることになる.
\ \ 結局,\ [1]の道順の総数は,\ 縦線2本と横線1本の選び方が何通りあるか}に等しい.
\ \ b,\ c,\ d,\ e,\ fから2本,\ W,\ X,\ Yから1本選ぶ}ときの場合の数が\,C52×C31\,となるわけである.
[2]}\ \ W,\ X,\ Yから2本,\ b,\ c,\ d,\ e,\ fから1本選ぶ}から,\ C32×C51\,となる.
