数学の道のりの問題です。

質問

図(下に写真でのせてます)のような道をもつ町がある。この町の地点Aから地点Bへ行く最短な道筋について、次の問に答えよ。

(1)道筋は全部で何通りあるか。

(2)途中で道を直角にn回曲がる道筋の数をa[n]とするとき、a[2]を求めよ。

(3)地点Aから地点Bへ行くのに、東西にN+1本、南北にN+1本の道路があるとし(図はN=4)、(2)と同様の道筋の数をa[n]とする。a[2k]を求めよ。ただし、k=1,2…,N-1とする。

(1)、(2)は解答ができたのですが、(3)が分かりません。
解答の方法また解答をお願いします。

回答No.3

島崎 崇（@tadopika） · ベストアンサー

(3) は、かなり難しい!

a[2k] ということは、曲がる回数が偶数回になります。
つまり、初め、Aから北に進んだ場合は、最後も北に進んでBに着くことになります。
初めに東に進めば、最後も東向きになります。

縦横の対称性により、初めに東に進んだ場合のa[2k]と、初めに北に進んだ場合のa[2k]は、等しくなります。
従って、初めに東に進むとしてa[2k]を求め、これを2倍すれば、答えが得られます。

以下、東に進む場合を - 、北に進む場合を + で表します。

N=4の場合は、次の通りです。

初めに東に進んで、2回曲がる道順は、
- + + + + - - -
- - + + + + - -
- - - + + + + -
の3通りですから、a[2]=3*2=6
これは、C(3,1)*2 と計算されています。
ここで、C(3,1)=3!/(1!*2!)

又、初めに東に進んで、4回曲がる道順は、
(i) +が(3,1)となる場合
- + + + - + - -
- + + + - - + -
- - + + + - + -
(ii) +が(2,2)となる場合
- + + - + + - -
- + + - - + + -
- - + + - + + -
(iii) +が(1,3)となる場合
- + - + + + - -
- + - - + + + -
- - + - + + + -
よって、a[4]=9*2=18
この計算は、C(3,1)*C(3,2)*2 です。
4個の+を2つに分ける分け方がC(3,1)通り、4個の-を3つに分ける分け方がC(3,2)通りあるからです。

そして、6回曲がる道順は、
a[6] = C(3,2)*C(3,3)*2 = 6通りになります。

次に、N=5の場合の計算式を示すと、次の通りです。
a[2*1] = C(4,0)*C(4,1)*2 = 8
a[2*2] = C(4,1)*C(4,2)*2 = 48
a[2*3] = C(4,2)*C(4,3)*2 = 48
a[2*4] = C(4,3)*C(4,4)*2 = 8

これで、a[2k]の一般式が予想できましたか?

お礼

(3)の解答ありがとうございます!!
詳しい説明でa[2k]の一般項が見えてきました!!

回答No.2

f272

(2)
4つの→を2つのグループに分ける方法は3C1=3通り。
→，→→→
→→，→→
→→→，→
4つの↑を1つのグループに分ける方法は3C0=1通り。
↑↑↑↑
→のグループと↑のグループを交互に並べる方法は3*1*2通り（*2は→を先にするか↑を先にするかの2通り）

(3)も全く同じです。

お礼

解答ありがとうございました。
出来れば、(3)もやっていただきませんか？

回答No.1

Tacosan

どこで曲がりましょうかねぇ.