最短経路について
- 正方形を横に5個、縦に4個ならべた碁盤を考える。左下にＡ地点、右上にＢ地点を置き、Ａ地点から2つ右上の地点にＰ地点を置くとする。Ｐ地点が右左折禁止の場合、Ａ地点からＢ地点まで行く最短経路は全部で何通りあるか。
- 答えには左から右へＰ地点を直進する場合と下から上へＰ地点を直進する場合に分けて、前者は3Ｃ1×4Ｃ2、後者は3Ｃ1×4Ｃ1通りでそれらとＰ地点が通行止めのときのＡ地点からＢ地点までの最短経路の全体を足している。
- 3Ｃ1×4Ｃ2と3Ｃ1×4Ｃ1がどういう意味か分かりません。
- ベストアンサー
最短経路について
正方形を横に5個、縦に4個ならべた碁盤を考える(つまり線の上を通る) このとき左下にＡ地点、右上にＢ地点を置き、Ａ地点から2つ右上の(つまりＡ地点から右に2つ、上に2つ行くと到達する)地点にＰ地点を置くとする (1)Ｐ地点が右左折禁止(つまり通過するときは直進することしかできない)の場合、Ａ地点からＢ地点まで行く最短経路は全部で何通りあるか 答えには左から右へＰ地点を直進する場合と下から上へＰ地点を直進する場合に分けて、前者は3Ｃ1×4Ｃ2、後者は3Ｃ1×4Ｃ1通りでそれらとＰ地点が通行止めのときのＡ地点からＢ地点までの最短経路の全体を足しているのですが3Ｃ1×4Ｃ2と3Ｃ1×4Ｃ1がどういう意味か分かりません 教えてください
- 数学・算数
- 回答数1
- ありがとう数1
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
左から右へＰ地点を通過する場合 (A) 上上右 右(P)右 上上右右 (B) みたいな経路を通るわけですよね。 Pの前後の右右は固定で、 AからPの上上右の部分が、3か所のうち１か所に右が入る場合、つまり3C1 PからBの上上右右の部分が、4か所のうち2か所に右が入る場合、つまり4C2 よって、3C1×4C2通りあるわけです。 下から上へP地点を通過する場合 (A) 右右上 上(P)上 上右右右 (B) みたいな経路を通るわけですよね。 Pの前後の上上は固定で、 AからPの右右上の部分が、3か所のうち１か所に上が入る場合、つまり3C1 PからBの上右右右の部分が、4か所のうち1か所に上が入る場合、つまり4C1 よって、3C1×4C1通りあるわけです。 あと、Pを通らない経路を足したら、全部の最短経路が得られる、と。
関連するQ&A
- 数学Ａ 場合の数 直交する道の最短経路の問題
東西に6本、南北に7本の道があり、これらの道は直交している。 一番左下の地点をＰ、一番右上の地点をＱとするとき次の問いに答えよ。 （１） Ｐ地点からＱ地点まで行く最短経路は何通りあるか？ （２） Ｐ地点からＱ地点まで行く最短経路のうち、 左折と右折を合わせて8回曲がるような、経路は何通りあるか？ (2007 岩手大 改) どなたか解説お願いします
- ベストアンサー
- 数学・算数
- 最短経路の問題（場合の数・順列）
極めてオーソドックスな最短経路の問題なのですが、数学から離れて久しいので、問題や、解答の本質を忘れていて困っています。 例えば縦３横５の四角形があるとき、左下のＡ地点から、右上のＢ地点まで行く最短距離は、 ８Ｃ３＝８！/３！×５！となるとあるのですが、 (1)この分子の８！＝８×７×・・・・・・・１はいったい何を意味しているんでしょうか。何故掛け算するのですか。この式だけで何を表しているのでしょうか。 (2)８Ｃ３とはどういう意味でしょうか。それが何故８！＝３！×５！と同じ意味になるのですか。 (3)同じく分母の３！×５！は何を表していますか。また、分子を分母を除する意味は何ですか＞＜ 以上どなたかわかりやすく教えていただければ幸いです。お願いします。
- ベストアンサー
- 数学・算数
- 数学の最短経路の問題を教えてください。
横に４マス、縦に４マスの道路があります。 一番左下を地点A、一番右上を地点Bとして、地点Aから縦に２マス行ってから横に３マスいき、縦に２マスいき最後に横に１マス行くと地点Bに到着するとき。 (１)地点Aから地点Bへの長さの最短の道は何通りありますか？ (２)地点Aから地点Bへの長さの最短の道で、左折の回数と右折の回数の和が多くとも３回であるものは何通りありますか？ (注 左折、右折は進行方向に向かって考える。例えば、地点Aから縦に２マス行ってから横に３マスいき、縦に２マスいき最後に横に１マス行くと地点Bの道路は左折、右折の数はそれぞれい１、２回でその和は３となる。) という問題の答えが (1)8C4(縦に4回横に4回なので縦縦縦縦横横横横を並び替える)=8・7・6・5/4・3・2=70通り (2)1回→2通り 2回→3C1+3=6通り 3回→5C2×2＋5C2=30通り 横 横 横 横 の隙間（場合によっては端にも）に縦を入れる感じのやり方 で38通りになったんですけどあっていますか？ もしも、間違っていたり、もっといい考えなどがありましたら教えてください。
- ベストアンサー
- 数学・算数
- 最短経路の場合の数の問題
縦５マス、横６マスの長方形。左下角から右にABCDとつける。左下Aから右上Cまで乙が移動。右下Bから甲が左上Dに移動。同時に出発し同じ速さで進む。 このとき、乙がAからCまで行くのに交差点で甲と出会う経路は何通りか の問題ですが、 ３マス進んだ地点の縦線すべてにおいて出会うと思います。そこで、 1×1×6C2=15 80-1×1×6C3=80-20=60 ///？？ ３マス目下からPQRSTとつけて場合の数を求めようとしましたが、重複部分に困り？ 解答の１００通りになりませんでした。 どのように考えるといいでしょうか？ちなみに１００通りが本当に正しいとは限りません。 よろしくお願いします。
- 締切済み
- 数学・算数
- 論理的にこの確率の問題がわかりません
右の図のような碁盤の目の道路（各碁盤の目は東西間、南北間の距離はすべて等しい）がある。 甲、乙２人が、それぞれA地点、B地点を同時に出発し、甲はBに、乙はAに向かって同じ速さで進むものとする。 ただし、２人とも最短距離を選ぶものとし、２通りの選び方のある交差点では、どちらを選ぶかは１/2の確率であるものとする。 このとき、次の確率を求めよ。 １甲がC地点を通る確率。 僕の解き方はまず確率とは場合の数を全事象で割ったにすぎないのでまず、甲がC地点を通る場合の数を考えます。 よって３C1×４C２＝１８通り よって全事象は７C３＝３５通り よって１８/３５としました。 しかし間違いでした。 なぜこのとき方では駄目なのでしょうか？？？ 論理的に教えて下さい。
- ベストアンサー
- 数学・算数
- 数学の問題教えて下さい。
問題 図のようにｐ、ｑが通れない道をAからBまで行くことを考える。最短経路の数はいくつあるか？ 解答 ｐを通ってAからBまで行く最短経路総数は、2C1×5C2=20 qを通ってAからBまで行く最短経路総数は、5C2×2C1=20 p,qを通ってAからBまで行く方法は、2C1×2C1×2C1=8 よってp,qの少なくとも一方を通ってAからBに行く方法は、 20＋20-8=32 p,qも通らないでAからBまで行く方法は、 56-32=24通り・・解答 質問は、 この解の時pだけ通る場合を考えないのは、何故ですか？ 教えてください。
- ベストアンサー
- 数学・算数
- 最短距離でいく経路の場合の数を教えてください。
最短距離でいく経路の場合の数を教えてください。 図のような道路で、点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. 考え方から全くわかりません。
- ベストアンサー
- 数学・算数
お礼
理解しました 回答ありがとうございました