順路，経路，最短経路の問題

■順路（道順，最短経路）の問題1
　　　　　　　　　　　　※該当する選択肢をクリックせよ．採点は下端でまとめて行う．　　　（※過去問ではありません．）

(1) 　下図のような街路があるとき， A 地点から B 地点まで遠回りせずに行く．途中，P 地点も Q 地点も通る道順は何通りあるか．１．　45 通り２．　60 通り３．　840 通り４．　2400 通り５．　2422 通り
(2) 　(1)と同じ図で P 地点も Q 地点も通らない道順は何通りあるか．１．　1197 通り２．　2037 通り３．　2968 通り４．　3808 通り５．　5005 通り
(3) 　次の図において，A 地点から B 地点まで遠回りせずに行くとき，途中，○印の地点は通り，×印の地点は通らない道順は何通りあるか．１．　64 通り２．　140 通り３．　210 通り４．　1015 通り５．　1225 通り
(4) 　次の図において，A 地点から B 地点まで遠回りせずに行く道順は何通りあるか．　１．　1980 通り２．　2400 通り３．　2460 通り４．　2545 通り５．　4772 通り
(5) 　次の図において，A 地点から B 地点まで遠回りせずに行く道順は何通りあるか．　１．　180 通り２．　210 通り３．　240 通り４．　270 通り５．　300 通り [採点する]

○===メニューに戻る
《基本の要約》

■順路（経路，道順）の総数は組合わせで求められる　右図のような道路があるときに，A 地点から B 地点まで（遠回りせずに）行く順路（経路，道順）の総数を数えるには： 1○　順列の総数　東に１つ進むことを e で，北に１つ進むことを n で表わすと，右図の赤線で示した道順（全体で１つの道順と数える）は，enennee で表せる．（この綴りを eeeennn などと並び換えれば別の道順を表わす．）　遠回りしない道順は，どれも e を４個，n を3個計7文字を並べ替えてできる順列で表わすことができる． 2○　同じ文字を含むときの順列の総数　例えば，異なる 5 個の文字 abcde を１列に並べる方法の総数は　先頭の並べ方：5 個のどれでもよいから5通り　２番目の並べ方：先頭に使ったもの以外 4 通り　･･･　５×４×３×２×１＝5!＝120 通りとなるが，　そのうち３文字が同じもの（abccc ）であるときは，それらだけを入れ換えても何も新しいものはできないから，異なるものがあるときと比較して 3! 倍だけ数え過ぎている．　したがって，abccc を並べ替えてできる順列の総数は通り　さらに，aabbb のように2個と3個が各々同じ文字のときは，通りになる．したがって，右図のように東行き（e）を４個，北行き（n）を３個含む文字列 eeeennn を並べ替えてできる順列の総数，すなわち道順の総数は =35 通り 3○　同じ文字を含むときの順列の総数=組合わせ　2○ で述べたように同じものがあるときの順列の考え方で問題は解けるが，一般に道順の総数は組合わせ nCr を用いて解説されることが多いので，これらの関係を示す．　aabbb のように同じものを2個と3個含む文字列を並べ替えてできる順列の総数は，通りであるが，これは a （または b）の場所さえ決めれば残りは他方に決まる．　例えば abbab は a の番号を1番と４番の２つに決めれば残り２，３，５番は b になる．したがって，異なる５個の番号札から a の行き先の番号札２個をもらう方法の数 5C2 に等しくなる． =5C2 これは組合せの公式 nCr= からも確かめられる．	《要約》 ○　異なるｎ個のものを１列に並べる順列の総数は n! 通り ○　同じもの a が m 個，b が n 個，合計 m+n 個あるとき，これらを1列に並べる順列の総数は通り ○　同じもの a が m 個，b が n 個，合計 m+n 個あるとき，これらを1列に並べる順列の総数は =m+nCm 通り例上の図で A 地点から B 地点まで（遠回りせずに）行く順路（経路，道順）の総数は，（東行きを e 北行きを n で表わすと，eeeennn を並らび換えてできる順列の総数になるから） 7C4==35 通り 3○の解説図
■形が変っても道順の総数には関係ない．　右のアとイで，A 地点から B 地点まで（遠回りせずに）行く順路（経路，道順）の総数は同じである．　いずれも東（e）行き４回，北（n）行き４回移動するが，イの図において２番目の n の幅が小さく，３番目の e の幅が大きいという事情は，enennnee から図に対応させるときに自動的に満たされるからである．　他の道順で nneeeene となっても，図に対応させれば，自動的に２番目の n の幅は小さく，３番目の e の幅は大きくなる．
■論理的に「かつ」で結ぶときは積の法則でまとめる　論理的に「または」で結ぶときは和の法則でまとめる ○　右図において，A 地点から B 地点まで行くときに途中 P 地点を通る道順の総数を求めるには：　「A 地点から P 地点まで」行き（15通り），かつ「P 地点から B 地点まで」行かなければならない（6通り）から，求める総数は積の法則でまとめて15×6＝90通りとなる． ○　右図において，A 地点から B 地点まで行くときに途中 Q 地点または R 地点を通る道順の総数を求めるには：　「Q 地点を通る」または「R 地点を通る」（両方通ることはできない）ということだから，10×5=50と10×10=100の結果を和の法則でまとめて，150通りとなる．
■通れない箇所があるとき　ア）　簡単な制限の場合は，全体からその箇所を通る道順を引けばよい．　　　右図アのように道路のない箇所があるとき，道路があるとして点Ｐを通る道順を引けばよい． - 　　　右図イで，×印が通行止めの時，これらを通らない道順はＡ→Ｒ，Ｓ→Ｂの道順を計算し，全体から引けばよい． - 　イ）　複雑な制限の場合は，関所を作ってそこを通過する道順を調べるとよい・・・ただし，関所の作り方に注意　右図ウでは，関所ＰＱを通過する道順を加えればよいが，関所をQRとするときは両方を通過する道順があるので重複分を引かなければならない． A→P→(R)→B： A→Q→B：これらの和が道順の総数．

○===メニューに戻る