数学の最短経路の問題を教えてください。

横に４マス、縦に４マスの道路があります。
一番左下を地点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通りになったんですけどあっていますか？
もしも、間違っていたり、もっといい考えなどがありましたら教えてください。

No.1 ベストアンサー 回答者： kumipapa 回答日時： 2007/12/21 00:01

こんばんは。

（１）は同じように考えました。縦４マス、横４マスの合計８マス進んでＡからＢへ行くのが最短。８マス進むうちの４マス分が縦（または横）なので、計８マスから縦４マスを選ぶ選び方を考えればよく、8Ｃ4 = ７０ 通り
または、「縦」４つ、「横」４つの順列を考えて、8! / (4!×4!) = 70 通り
（２）
１回のとき）
縦４マス→横４マス、または、横４マス→縦４マスの２通り
２回のとき）
縦ｎマス→横4マス→縦 (4 - n) マス ・・・ 1≦n≦3 の３通り
さらに、縦、横の順を逆にして横→縦→横で考えても同様に３通り。
ゆえに２回曲がる行き方は６通り
３回のとき）
縦 n マス→横 m マス→縦 (4 - n) マス→横 (4 - m) マス　で、1≦n≦3, 1≦m≦3 なので、３×３＝９通り。
縦の横の順を逆にして横→縦→横→縦も同様に９通り。
ゆえに３回曲がる行き方は１８通り

以上より、たかだか３回曲がってＡからＢへ行く道順は合計２６通り。

２回のときは、縦→横→縦ならば、縦○縦○縦○縦の３箇所の○のうち１箇所に横５個を入れる入れ方で 3Ｃ1 = ３通り、横→縦→横も同様に３通りで、計６通りと考えても同じ。

３回のときは、縦を２つにわけ、横も２つにわけ、それらを縦横縦横または横縦横縦に並べれば良い、と考えても良いでしょう。縦４マスを２つに分けるわけ方は縦○縦○縦○縦の３箇所の○のうち１箇所に衝立を立てると考えて 3Ｃ2 = ３通り。横を２つにわけるのも同様に３通り。故に、3Ｃ2×3Ｃ2×２＝１８通り。

この回答へのお礼

教えていただきありがとうございます。
他にもわからない問題があるので教えてもらえませんか？
放物線ｙ＝ｘ(二乗)＋４ｘ＋５・・・(1)、ｙ＝－ｘ(二乗)＋ｂｘ＋ｃ・・・(2)(ｂ＞０)について、(1)の頂点をV,(1)の軸とｘ軸の交点をH、 (1)とｙ軸の交点をCとする。また、(2)の頂点をW(2)の軸とｘ軸の交点をKとする。
(１)頂点Vの座標を求めよ。
(２)直線VCの方程式を求めよ。
(３)(2)の頂点が直線VC上にあり、四角形VHKWの面積が１２であるとき、ｂ、ｃの値を求めよ。

８個の異なる品物をA、B、Cの３人に分ける方法について
(１)Aに３個、Bに２個、Cに３個分ける方法は何通りあるか？
(２)品物を一個ももらえない人がいてもよいとすれば、分け方は何通りあるか
？
(３)A、B、Cがいずれも、少なくとも１個の品物をもらう分け方は何通りあるか？と言う問題の途中式と答えが
(1)V(-2,1)
(2)y=2x+5
(3)kのx座標をaとすると，四角形（台形）ＶＨＫＷの面積＝（１＋２a＋５）（a＋２）/2
よりa^2＋５a＋６＝１２
これを解いて，（a＋６）（a-１）＝０ここでa>0より
a=1
よって，Wの座標は（１，７）
一方，(2)はｙ＝－（ｘ－ｂ／２）＾２＋c＋ｂ＾２／４と表せるから
ｂ＝２，ｃ＝６

（１）８Ｃ３×５Ｃ２（Ａが３個選んで，Ｂが残りから２個選ぶから）
（２）３＾８（それぞれの品物に対して，Ａ，Ｂ，Ｃの３通りだから）
（３）品物が１人に集中するのは，８＾１×３
品物が２人に集中するのは，８＾２×３だから
求める答えは３＾８－３－８＾２×３になったんですけどあっていますか？
もしも、間違った答えややり方ならもっといいのを教えてもらえませんか？
ダイレクト本当にすみません

お礼日時：2007/12/22 20:45

No.2 回答者： 0lmn0lmn0 回答日時： 2007/12/21 18:07

向きを変える回数をnとして、場合の数をF(n)とします。

n=1,2,3,4,5,6,7
F(1)+F(2)+F(3)+F(4)+F(5)+F(6)+F(7)=8!/(4!4!)=70

F(1)= 2,,F(2)= 6,,F(3)=18,,F(4)=18,,F(5)=18,,F(6)= 6,,F(7)= 2
となるようです。

センタのような問題で、ＰやＣは使わずに、巧みにcountするように思われます。
かといって、規則性もあるらしく、

２＋６＋１８＋１８＋１８＋６＋２＝７０　と対称性もあります。
４×４　だから、count できますが、それ以上になると予測もできません。

以下の図は、図ごとにcountの仕方が異なっています。７０通り全て書いた方が速そうです。
説明を書く/読むのは隔靴掻痒で、F(3)は数え上げた方がよさそうです。むしろ、F(4)以降の方が判り良いかもしれません。


F(1)の図　
●●●●○○○○ ・・・・・１＊２＝２

F(2)の図　
●○○○○●●●・・・・・３＊２＝６

F(3)の図　
●○（●●●○○）○　（　）内のずらしが３通り。
●●○（●●○○）○　（　）内のずらしが３通り。
●●●○（●○○）○　（　）内のずらしが３通り。・・・・・３＊３＊２＝１８

F(4)の図　
●○○●○○●●
●○○●●○○●
●●○○●○○●

●○○○●○●●
●○○○●●○●
●●○○○●○●・・・・・（３＋６）＊２＝１８

F(5)の図　
●○●○●●○○
●○●○○●●○
●○○●○●●○・・・・・３＊３＊２＝１８

F(6)の図　
●○●○●○○●・・・・・３＊２＝６

F(7)の図
●○●○●○●○・・・・・１＊２＝２

　　計　２＋６＋１８＋１８＋１８＋６＋２＝７０通り。