最短距離でいく経路の場合の数を教えてください。

最短距離でいく経路の場合の数を教えてください。
図のような道路で、点Pから点Qまで最短距離でいく経路のうち、次の経路は何通りあるか。
問1.すべての経路
問2.Rを通る経路

答案1.
横道路が4本、縦道路が6本
最短距離でいくから階段状に行くのはいいけど、矩形上にジグザグにいくのはダメですよね。

和の法則＝「同時に起こらない場合｣＝排反事象
ある試行において、一方が起これば　他方は決して起こらないときの、それぞれの事象。

今回全くわかりません。

横道路4本のうち4本とも行くことが出来るので4C4 ?
縦道路6本のうち6本とも行くことが出来るので6C6 ?

たとえば
横1縦6
横1縦5横4
縦1横4
縦1横3縦6

規則は必ず横1か縦1を通る。
最後は横4か縦6を通る。

わかりません。


答案2.

考え方から全くわかりません。

No.1 ベストアンサー 回答者： gohtraw 回答日時： 2010/01/04 01:18

　ＰからＱに到達するには必ず右に５回、上に３回進むことになります。

　図の縦１から縦２に移動する右への動きを右１、以後順に右２・・・右５とし、上への移動も同様に上１～上３とします。
　動く順番を考えると、
　○右１○右２○右３○右４○右５○
となります。○には上の移動が０～３個入ることができます。ここで場合分けとして
（１）上１～上３が固まって入る場合
　　○は６個あるので６通り
（２）上１と上２が固まり、上３が単独で入る場合
　　上１と上２が一番左の○に入ると上３が入るのは５通り
　　上１と上２が左から二番目の○に入ると上３が入るのは４通り
　　以下、３通り、２通り、１通りとなり合計１５通り
（３）上１が単独、上２と上３が固まって入る場合
　　（２）と同様で１５通り
（４）上１～上３がバラバラで入る場合
　　　６個の○の中から３つ選ぶので６Ｃ３＝２０通り
これらを合計すると６＋１５＊２＋２０＝５６通り
となります。
　Ｒを通る場合はＰからＲに至る経路の数とＲからＱに至る経路の数をそれぞれ求め（やり方は上記と同じ）、両者の積をとればＲを通る経路の数になります。

この回答へのお礼

縦道、横道ではなく右と上に行く回数で考えていくことが思う浮かびませんでした。

＞動く順番を考えると、○右１○右２○右３○右４○右５○　
＞となります。○には上の移動が０～３個入ることができます。
実際入れてみると
上1　右1　上2　右2　上3　右3　上0　右4　上0　右5

なるほど、わかりました。
たとえば、以下は上が3連続で進むと最短距離ではないから

上1　上2　上3　右1　上0　右2　上0　右3　上0　右4　上0　右5・・ア

上上や右右の連続の進み方はないということですね。

上基準で考えると
○上１○上２○上３○
で○には右の移動が０～5個入ることができるということですね。

＞　（１）上１～上３が固まって入る場合
＞　　○は６個あるので６通り
固まっている場合とはどういう意味でしょうか

あれっ、もしかして上に連続に進むということですか。
たとえばアの進み方だと最短距離にはならないのでは?

あれっ、同じ最短距離ですか。
わかりました。

＞上１と上２が一番左の○に入ると上３が入るのは５通り
はわかりますが

＞上１と上２が左から二番目の○に入ると上３が入るのは４通り
上3が一番左の○に入るのも可能なので5通りでは?
?右１?右２?右３?右４?右５?とすると
上1.2が?に入っても上3が?????・・5通り
だから全部5通りでは?

わかりました。左に進むと最短距離ではなくなるからですね。

＞　（４）上１～上３がバラバラで入る場合
＞　　　６個の○の中から３つ選ぶので６Ｃ３＝２０通り
６個の○の中から３つ選ぶという考え方だと
左に進んでしまうのも含まれまれてしまいませんか。
その分を除外しないと。
含まれるか否かの判別さえわかりませんが・・
闇雲に3個選ぶと左進みも含まれていそうな気がするだけです。
ここは納得いきません。

他は理解できました。

回答2C.
先生のやり方でいくと
PからR迄の経路・・右進3回上進2回・・?右１?右２?右３?のどれかに上0～2を入れる
上１上2が固まって入る場合
　　○は4個あるので4通り

上１上2がバラバラで入る場合
　　　4個の○の中から2つ選ぶので4Ｃ2＝6通り
これらを合計すると4＋6＝10通り

RからQ迄の経路・・右進2回上進1回・・?右１?右２?のどれかに上0～1を入れる
上１しかないので

上１が入る場合
　　　3個の○の中から1つ選ぶので3Ｃ1＝3通り
ここの組み合わせでも左進みを含んでいるのではないかと思ってしまうのですが。

ここでまた疑問ですが先生は両者の積
PからR迄の経路の数×RからQ迄の経路の数=10×3=30通り
ということですが
和ではなく積ですか。

いや、もしかして
PからR迄の経路の10通りの、そのおのおのに対して、RからQ迄の経路の3通りずつあるから
積の法則なわけですね。

ありがとうございました。

お礼日時：2010/01/04 15:32

No.3 回答者： Quattro99 回答日時： 2010/01/04 17:39

8C5でもいいですよ。

8C5と8C3は同じです。
「8箇所から『右』を入れる5箇所を選ぶ（残りの3箇所に『上』を入れる）」か「8箇所から3箇所を選ぶ」かは同じことですから。
8C5より、8C3の方が計算が楽だからそっちにしてあるだけです。

順列・組み合わせの基本をおろそかにされているように思います。
なぜなのかを理解せずに公式だけ覚えても意味がないですよ。

この回答へのお礼

＞「8箇所から『右』を入れる5箇所を選ぶ（残りの3箇所に『上』を入れる）」か「8箇所から3箇所を選ぶ」
＞ かは同じことですから。
異なると思っていましたが計算したら確かに同じでした。

答案2D.
を続けます。

PからRまで右右右上上の5回の中から上2回を選ぶ選び方は5C2=10通り
RからQまで右右上の3回の中から上1回選ぶ選び方は3C1=3通り

PからRまでの行き方10通りの、おのおのについて、RからQまでの行き方3通りずつあるから
10×3=30通り

＞右右右右右上上上を並べる並べ方、
と書かれたので順列がよぎりました。
未熟でした。

ありがとうございました。

お礼日時：2010/01/04 19:25

No.2 回答者： Quattro99 回答日時： 2010/01/04 07:36

最短経路なので、右に進むか上に進むかどちらかです。

すでにお考えのように、横に5回、縦に3回進むわけですが、ということは計8回進むわけです。従って、右右右右右上上上を並べる並べ方、つまり8C3が求める答えです。

他には各地点へ進む進み方を順に書き込んでいく方法があります。
例えば、その図で、縦2横1地点へ進む進み方は1通り、縦1横2地点へ進む進み方は1通り、縦2横2地点へ進む進み方は先程の2つの地点からしか進めませんから1+1=2通り……となります。
道の一部が欠けているような問題ではこの方法の方が早い場合もあります。

Rを通る場合は、RまでとR後を分けて考えます。

この回答へのお礼

＞右右右右右上上上を並べる並べ方、
おー、順列や組み合わせに持ちこめるようにするわけですね。
でも、並べ方ですから組み合わせではなく、順列8P3ではないですか。
8C3=56通り
8P3=336通り

という前に8C3の8は8回の8だとわかりますが、3は何の3ですか。
上に3回進むから3?
でも右にも5回進むからどうして8C5ではないでしょうか。

答案1C.
縦1横2地点へ進む進み方は1通り
縦1横3地点へ進む進み方は1通り
縦1横4地点へ進む進み方は1通り
縦2横1地点へ進む進み方は1通り
縦2横2地点へ進む進み方は縦2横1地点まで1通り×そこから縦2横2地点へ1通り
　　　縦1横2地点まで1通り×そこから縦2横2地点へ1通り　計2通り
縦2横3地点へ進む進み方は縦2横2地点まで2通り×そこから縦2横3地点へ1通り
　　　縦1横3地点まで1通り×そこから縦2横3地点へ1通り　計3通り
縦2横4地点へ進む進み方は縦2横3地点まで3通り×そこから縦2横4地点へ1通り
　　　縦1横4地点まで1通り×そこから縦2横4地点へ1通り　計4通り
縦3横1地点へ進む進み方は1通り
縦3横2地点へ進む進み方は縦3横1地点まで1通り×そこから縦3横2地点へ1通り
　　　縦2横2地点まで2通り×そこから縦3横2地点へ1通り　計3通り
縦3横3地点へ進む進み方は縦3横2地点まで3通り×そこから縦3横3地点へ1通り
　　　縦2横3地点まで3通り×そこから縦3横3地点へ1通り　計6通り
縦3横4地点へ進む進み方は縦3横3地点まで6通り×そこから縦3横4地点へ1通り
　　　縦2横4地点まで4通り×そこから縦3横4地点へ1通り　計10通り
縦4横1地点へ進む進み方は1通り　
縦4横2地点へ進む進み方は縦4横1地点まで1通り×そこから縦4横2地点へ1通り
　　　縦3横2地点まで3通り×そこから縦4横2地点へ1通り　計4通り
縦4横3地点へ進む進み方は縦4横2地点まで4通り×そこから縦4横3地点へ1通り
　　　縦3横3地点まで6通り×そこから縦4横3地点へ1通り　計10通り
縦4横4地点へ進む進み方は縦4横3地点まで10通り×そこから縦4横4地点へ1通り
　　　縦3横4地点まで10通り×そこから縦4横4地点へ1通り　計20通り
縦5横1地点へ進む進み方は1通り
縦5横2地点へ進む進み方は縦5横1地点まで1通り×そこから縦5横2地点へ1通り
　　　縦4横2地点まで4通り×そこから縦5横2地点へ1通り　計5通り
縦5横3地点へ進む進み方は縦5横2地点まで5通り×そこから縦5横3地点へ1通り
　　　縦4横3地点まで10通り×そこから縦5横3地点へ1通り　計15通り
縦5横4地点へ進む進み方は縦5横3地点まで15通り×そこから縦5横4地点へ1通り
　　　縦4横4地点まで20通り×そこから縦5横4地点へ1通り　計35通り
縦6横1地点へ進む進み方は1通り
縦6横2地点へ進む進み方は縦6横1地点まで1通り×そこから縦6横2地点へ1通り
　　　縦5横2地点まで5通り×そこから縦6横2地点へ1通り　計6通り
縦6横3地点へ進む進み方は縦6横2地点まで6通り×そこから縦6横3地点へ1通り
　　　縦5横3地点まで15通り×そこから縦6横3地点へ1通り　計21通り
縦6横4地点へ進む進み方は縦6横3地点まで21通り×そこから縦6横4地点へ1通り
　　　縦5横4地点まで35通り×そこから縦6横4地点へ1通り　計56通り

大変だった。もうやりたくないです。

答案2D.
PからRまで右右右上上の5回の中から何回選べばいいですか
RからQまで右右上の3回の中から何回えらべばいいですか

ありがとうございました。

お礼日時：2010/01/04 17:02