悩んでいます

左上の図は碁盤の目状の道路とし、すべて等間隔である。この図において、点Aから点Bに行く最短経路は全部

締切済

質問者：mo_asuka
質問日時：2018/10/14 11:48
回答数：2件

左上の図は碁盤の目状の道路とし、すべて等間隔である。この図において、点Aから点Bに行く最短経路は全部で何通りか。ただし斜線の部分は通れないものとする。

この問が分かりません。解答には右下の図があり、各交差点を通過する経路の数を記入するとこのようになる。とありますが、どこからこのような数字で出てきたのですか？

通報する

この質問への回答は締め切られました。

質問の本文を隠す

回答 (2件)

最新から表示
回答順に表示

No.2

回答者： majimelon37
回答日時：2018/10/15 03:39

図１のすべて等間隔の碁盤の目状の道路において、点Aから点Bに行く最短経路は全部で何通りか。

ただし斜線の部分は通れないものとする。
図１の中に書いた数字の計算法を説明するために、図１の左下の部分を拡大して、図２から図４に示す。図１では数字が十字路から少しはずれた位置にあるが、図2では、数字は十字路の真上に書いてある。この数字は、Aから出発して、その十字路に到達する最短経路の数である。これを経路数という。
図２では出発点のAにも経路数1が書いてある。
図３は、経路の方向を矢印で示した。最短経路を進むためには、
右向きに進むか、上向きに進むしかないことを示す。
図4ではp，q，r，sと書いた４つの交差点により、経路数の計算のルールを説明する。
pと書いた交差点には、その下の経路数1の交差点から上向きの矢印が入っている。
この場合、下の交差点の経路数が1なら、ｐの交差点の経路数も1となる。pの交差点に行く行き方は、下の交差点の経路数から増えもせず減りもしないから、下の交差点の経路数をそのまま引き継いで、pの経路数は１になる。
qと書いた交差点には、その左の経路数1の交差点から右向きの矢印が入っている。
この場合、左の交差点の経路数が1なら、ｑの交差点の経路数も1となる。ｑの交差点に経路数行く行き方は、左の交差点の経路数をそのまま引き継いで、qの経路数は１になる。
次にrと書いた交差点には、その左のpの交差点から右向きの矢印が入り、またｒの交差点の下のｑの交差点から上向きの矢印が入っている。２本の矢印が入っているときは、
ｒ交差点の経路数はｐとｑの和となる。r=p+ｑ＝2となる。
次にs交差点には、ｒ交差点から上向きの矢印が入るだけだから、ｓの経路数はｒの経路数を引き継いでs=r＝2となる。こうして、出発点のAの経路数１から始めて、終点のB点まで、すべての交差点の経路数を計算することが出来て、その結果は図１となる。
交差点Bの経路数は132となるので、最短経路は全部で132通りである。
二項係数を計算するためによく知られたパスカルの三角形は、図１の右下の角を出発点にして、上向きと左向きに進む矢印の経路で作ることが出来る。出発点を上にして、ななめ左下とななめ右下向きの矢印で書くと図5ができる。
例えば(a+b)^4=a^4+4a^3b+6a^2b^2+4ab^3+b^4の係数14641が得られる。