最短経路の数

質問

AからBへの道順を考える。
道は一方通行で横には右、縦には上、斜めの道は、左下から右上へしか行けない。
道順は全部で何通りあるか。
答え３２１通り

斜めの道を使わないのが、７０通り、
斜めに１回のみ移動するのが１４０通りと求められたのですが、他が求められません。
解き方を教えてください。
解説が詳しいとありがたいです。

回答No.9

ferien · ベストアンサー

ANo.5，ANo.7です。ANo.8さん　ご丁寧にありがとうございます。

＞クドくて恐縮だが、ついでに０！も。

通らない道についても考えるということですか？

上、右、斜めに順番も統一して書くと、

８！／（４！・４！・０！）＝７０通り
７！／（３！・３！・１！）＝１４０通り
６！／（２！・２！・２！）＝９０通り
５！／（１！・１！・３！）＝２０通り
４！／（０！・０！・４！）＝１通り

のように訂正をお願いします。

回答No.11

noname#157574

No.10補足　起こり得る場合の数は
1，9，41，129，321
1，7，25， 63，129
1，5，13， 25， 41
1，3， 5， 7， 9
1，1， 1， 1， 1
です。

回答No.10

noname#157574

添付画像のように，各交点に起こり得る場合の数を書き込む。

回答No.8

alice_44

クドくて恐縮だが、ついでに０！も。

回答No.7

ferien

ANo.5です。　ANo.6さん　ありがとうございます。

８！／（４！・４！）＝７０通り
７！／（３！・３！・１！）＝１４０通り
６！／（２！・２１・２！）＝９０通り
５！／（３！・１！１！）＝２０通り
４！／４！＝１通り

のように訂正をお願いします。

回答No.6

alice_44

それを言うなら、
7!/(3!・3!・1!) とか
5!/(1!・1!・3!) とか
書いたほうが解りよくない？

回答No.5

ferien

AからBへの道順を考える。
道は一方通行で横には右、縦には上、斜めの道は、左下から右上へしか行けない。
道順は全部で何通りあるか。
答え３２１通り

斜めの道を使わないのが、７０通り、
＞斜めに１回のみ移動するのが１４０通りと求められたのですが、他が求められません。

斜めを使わないとき、道の選び方は８通りで、上へ４通り右へ４通りを同じと見なすから、
８！／４！・４！＝７０通り
斜め１回のとき、道の選び方は７通りで、上へ３通り右へ３通りを同じと見なすから、
７！／３！・３！＝１４０通り
斜め２回のとき、道の選び方は６通りで、上２通り右２通り斜め２通りを同じと見なすから、
６！／２！・２１・２！＝９０通り
斜め３回のとき、道の選び方は５通りで、斜め３通りを同じと見なすから、
５！／３！＝２０通り
斜め４回のときは、道の選び方は、斜めだけ４通りだから、
４！／４！＝１通り
よって、７０＋１４０＋９０＋２０＋１＝３２１通り

でどうでしょうか？

回答No.4

kabaokaba

>いや、最短経路は、
>斜めまっしぐらの
>一通りだけだから。

あ。。。。。コソッ・・・・

回答No.3

alice_44

いや、最短経路は、
斜めまっしぐらの
一通りだけだから。

回答No.2

151A48

下辺と左辺の頂点に１を記入。
各頂点にはその左，下，左下にある数字を足して記入。
これを続けてＢまで行けばよい。

回答No.1

kabaokaba

どうして
斜め一回で140通りと求められたのに
斜め二回，三回，四回がわからないの？

というか・・・斜め四回って計算するまでもないでしょう．

斜め一回は
七つの箱から一つ選んで，残り六つから三つ選べばいいから
7 * (6*5*4)/(1*2*3) = 140

斜め二回は
六つの箱から二つ選んで，残り四つから二つ選べばいいから
(6*5/(1*2)) * (4*3/(1*2)) = 90

斜め二回は
五つの箱から三つ選んで，残り二つから一つ選べばいいから
(5*4*3)/(1*2*3) * 2 = 20

70 + 140 + 90 + 20 + 1 = 321