ページ1:

Question (道順の個数)
右のような道路がある(1) A地点からB地点まで最
短経路をたどって進む方法は何通りあるか.
(2) また, 点Cを通る最短経路は何通りあるか.
L
注
この問題の場合, 最短経路とは右向きまたは上向きのみ
に進んでA地点から B 地点にたどり着く経路をいう.
00
B
(1)
最も単純な最短経路は、下図
解
B よって、AからBへの最短経路、
を3個、↑を4個並べることで表される。
したがって
A
←
↑の並べ方の個数は、同じものを含む順列の総数より、
(3+4)!
3.4:
7!
3!4!
7.00066.5.4!
03..41
2
76.5
3.2.1
=35(通り)
(2)
すぐあ
下図のように2点P,Qをとると、Cを通る経路では必ずP,Qを通過する。
B
P
Q

ページ2:

(1AからPまでの最短経路の個数
1個の、3個の↑の並べ方の総数匹からに一致するから、
→
(1+3)!
7!3!
4!
3!
=
=
4-31 4(通り)
31
(ii) PからCを通Qへ行く経路は通り
(1)QからBへの最短経路の個数
1個の→
1個の↑の並べ方の総数に一致するから、
(7+1)!
=
21 2(通り)
AからPへ最短で行った後、PからCを通って@へ行き、その後QからBへ最短で行く経路は、
→積の測
4x1×2
=
8(通り)
これが求める場合の数となる。
(1)
解2
ある交差点までの道順の総数を考えるとする。
IP
右向きまたは上向きのみに進んでPに到達するとき、
必ずSTのどちらか一方を通ってくるので、
和の法則
道順
(Pまでの経路の総数
(Sまでの道順の数)+(下までの道順の総数)…(☆)

ページ3:

Aからスタートして、(戊)の考え方を、すべての交差点に適用すると/
通り
10+5
B
3515+20
7+3
4+6
10+10
1+2通り
3+3
1644
10
ここまで来る経路は
ここまで来る経路は()より、
通り
2 (1+1通り
7+2通り
3
4
A
ここまで来る経路は
通り

ページ4:

<碁盤の目状の道の最短経路>
m
1
1
2
n
たて区画、横に区画の碁盤目状の道において、
AからBまで移動する最短経路は
(m+n)!
(m+n)!
=
m!n!
ml(m+n-m)!
=
With Con
meCr (通り)

ページ5:

Question ()
VV 17
右のような, 分岐点と分岐点の間の長
さが1である道がある. したがって,
A から B までの長さは 2n になる.)
B
↓
A から B までの最短経路の個数を求
めよ.
A
-n
Aを原点とするとay座標軸を定め、Bの座標を(n,n)とする。
Aを直線y=xに関するして対移動させた点をAとする
n
n
点線部も通ってよければ、AからBまでの最短経路は、
n
(nth)!
(2n)!
(通り)
h!n!
nin!」
ここから、点線部を通る場合のAからBまでの最短経路の個数をひけばよい。
食
22.

ページ6:

ここで、Aを原点とするxy座標軸を定め、Bの座標を(n,n)とする。
Aを直線y=x+1に関して対称移動させた点をAとする。
Ao
y
n
/y=x+1
B(n.n)
n
Aから、点線部を通ってBへ行く場合、必ず直線y=x+1上の点を通る。
初めて通った直線y=x+1上の点をPFとおく。と、
「Aから、点線部を通ってBへ行くことは、「AからPを通ってBへ行く」ことと言いかえられる。
した面を、直線y=x+1に関して対移動
このとき、A-P
間の通過
経済
A-P間の道はA'-P間の道におきかわる。
A'
P
y=x+1
させると、

ページ7:

このように限
経
このよう
T
AからPを通ってBへ行く道のり」は、
y=x+)に関して
経路
A-P間の道を対称移動させることで、「A'からPを通ってBへ行く道@」におきかえることができる。
ay
すべてのAからPを通ってBへ行く通りについて、
同様の操作が可能なので、
AからPを通ってBへ行く道の数=AからPを通ってBA行経路の…①
また、A' y=x+1よりも側、BQy=x+1よりも右側にある。から、
AからBへ行くためには、直線y=x+1上を通ること必要がある。
SEP
y=x+1
画を乗りこえるために
通る
よって、「AからPを通ってBへ行く経路の数」は、「AからBへ行く経路の数」といえるので、①より
(n+19+n-1)!
k=AからBへ行く経路の数=
n+T
n-1
AQ
(n+1)!(n-1)!
n
(2n)!
(n+1)!·(n-1)
h

ページ8:

したがって、()より、
(求める場合の数
(2n)!
nin!
k
(2n)!
(24)
h!n!
(n+1)! (n-1)!
(2n)!
(24)
=
n! n.(n-1)!
(n+1)h! (n-1)!
(2n)..n. (n+1)
(24).n
n(n-1). n. (n+1)
(2n): (2. (n+1))
(2n)!-n
=
=
n! (n=7) !n (n+1)
$(2n)! (n+1-72
ni (n-1)\n(+1)
Densions
(2)
n! (n-1)!
(2n)!
(2n)
n! (ny)! n nich-)! n+1
(2n)! (一)
n! (n-1)!\n
(2n)! h+i
n! (n-1)] [n(n+1) h (n+1))
(2n)!
n! (n-1)! non+1)
(2n)!
h! (n+1). n. (n-1)!
(2n)!
n! (n+1)-h!
(2n)!
n! (n+1)!