ＮＯ４B＜遊楽街＞さんの解答3回目 5/25 ６:１６受信 ６月１５日更新
■問題の解釈
「4人のとき(1-2)-(3-4)とつなぐ場合は1つと数える」という補足から、
「このような最終形が何通りあるか」という問題だと解釈します。
■問1
((1-2)-3)-4
(1-(2-3))-4
1-((2-3)-4)
1-(2-(3-4))
(1-2)-(3-4)
答) 5通り
■問2
(((1-2)-3)-4)-5
((1-(2-3))-4)-5
(1-((2-3)-4))-5
1-(((2-3)-4)-5)
(1-(2-(3-4)))-5
1-(2-(3-4)))-5)
1-(2-((3-4)-5))
((1-2)-(3-4))-5
(1-2)-((3-4)-5)
((1-2)-3)-(4-5)
(1-2)-(3-(4-5))
(1-(2-3))-(4-5)
1-((2-3)-(4-5))
1-(2-(3-(4-5)))
答) 14通り
■問3
(1-2)-(3-4)のような手の繋ぎ方の組み合わせを数式に見立てます。
(以降、演算子は+に置き換えます)
このままの形では難しそうなので、中置記法ではなく後置記法で書き直してみます。
このとき、数字は小さい順に並べることにすれば、後置記法の数式は一意に決まります。
n=4の場合を書き出すと
((1-2)-3)-4 → 12+3+4+
(1-(2-3))-4 → 123++4+
1-((2-3)-4) → 123+4++
1-(2-(3-4)) → 1234+++
(1-2)-(3-4) → 12+34++
となります。
後置記法の計算方法は、先頭から順に見ていき演算子が出てきたら、
その演算子と直前の2つの数字を計算結果に置き換えるという手順を繰り返します。
(例 123+4++ → 154++ → 19+ → 10)
このことから、後置記法の記述が計算可能であるためには、
先頭から数字の個数と演算子の個数を数えていったとき、常に
「それまでに現れた数字の個数 > それまでに現れた演算子の個数」
という条件が成り立っていなければならないことがわかります。
今、演算子の総数より数字の総数の方が1個だけ多いですが、
総数が同じ方が以降の話が少しだけ簡単になるので、
最初の数字は固定してその数字は数えないことにすれば、満たさなければならない条件は
「それまでに現れた数字の個数 ≧ それまでに現れた演算子の個数」
と書き直せます。
(★ここからn=5の例なので注意★)
次の図1において、後置記法の式を先頭から順に見ていったとき、
数字が現れたらX方向へ+1進み、演算子が現れたらY方向へ+1進むとすると、
n=5の場合、(n-1)×(n-1) = 4×4の正方形の左下の頂点(◆)から
右上の頂点(●)へ行く経路の内、対角線より上にはみ出さない(対角線上はOK)経路の総数が
求める答ということになります。
演算子 演算子
↑ │ │ │ │／ ↑ │ │ │ │／
├─┼─┼─┼─●─ ├─┼─┼─┼─●─
４│ │ │ │／│ ４│ │ │ │／│
├─┼─┼─┼─┼─ ├─┼─┼─┼D4┼─
３│ │ │／│ │ ３│ │ │／│ │
├─┼─┼─┼─┼─ ├─┼─┼C3┼D3┼─
２│ │／│ │ │ ２│ │／│ │ │
├─┼─┼─┼─┼─ ├─┼B2┼C2┼D2┼─
１│／│ │ │ │ １│／│ │ │ │
◆─┴─┴─┴─┴→数字 ◆A1┴B1┴C1┴D1┴→数字
１ ２ ３ ４ １ ２ ３ ４
図１ 図２
ここで、N×Nの正方形について条件を満たす経路の総数をf(N)とする。
(つまりn人の手の繋ぎ方はf(n-1)である)
図２において、A1〜D4まで辿り着く経路の総数をそれぞれa1〜d4とすると、
f(4) = d4 + d3 + d2 + d1
である。
d4 = c1 + c2 + c3
d3 = c1 + c2 + c3
d2 = c1 + c2
d1 = c1
より
f(4) = 2*c3 + 3*c2 + 4*c1
さらに、
c3 = b1 + b2
c2 = b1 + b2
c1 = b1
より
f(4) = 5 * b2 + 9 * b1
さらに、
b2 = a1
b1 = a1
より
f(4) = 14 * a1
a1 = 1であるから、f(4) = 14
f(4)を表す式の係数に着目すると、
１ １ １ １
２ ３ ４
５ ９
１４
と変化している。上記の計算式からも明らかなように、
m+1行i列目はm行の1列目からi+1列目までの和になっている。
つまり、m行目の数列のi項目をF(m,i)とすると、
F(m+1,i) = Σ[j=1〜i+1] F(m,j)
である。F(m,i)の一般項がわかれば、
f(N) = F(N,1)
となる。
(★ここから先はちゃんと証明していません★)
F(m,i)の一般項をm=4まで計算してみると、
F(1,i) = 1
F(2,i) = Σ[j=1〜i+1] 1 = i+1
F(3,i) = Σ[j=1〜i+1] (i+1) = (i+1)(i+4)/2
F(4,i) = Σ[j=1〜i+1] (i+1)(i+4)/6 = (i+1)(i+5)(i+6)/6
これから、
F(5,i) = (i+1)(i+6)(i+7)(i+8)/4!
F(6,i) = (i+1)(i+7)(i+8)(i+9)(i+10)/5!
を予想した。F(5,1)とF(6,1)を計算すると42と132となり、
下の結果と一致したので、証明はできていないがどうやら正しそうである。
m=1 １ １ １ １ １ １
m=2 ２ ３ ４ ５ ６
m=3 ５ ９ １４ ２０
m=4 １４ ２８ ４８
m=5 ４２ ９
m=6 １３２
上記の予想からF(m,i)の一般項は
F(m,i) = (i+1)(i+2m-2)!/{(m-1)!(i+m)!}
従って、
f(N) = F(N,1)
= 2(2N-1)!/{(N-1)!(N+1)!}
= 2N(2N-1)!/{N(N-1)!(N+1)!}
= (2N)!/{N!N!(N+1)}
= C(2N,N)/(N+1) ← (Cは組み合わせ)
となる。
ゆえに、n人の手の繋ぎ方は
f(n-1) = C(2n-2,n-1)/n
(n=1, n=2でも正しい値となる)
＜自宅＞ mizuryu@aqua.ocn.ne.jp
