ＮＯ４�C＜遊楽街＞さんの解答4回目　5/25　19:29受信　６月１５日更新


■問題の解釈
「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個だけ多いが、
総数が同じ方が以降の話が少しだけ簡単になるので、
最初の数字は固定してその数字は数えないことにすれば、満たさなければならない条件は
「それまでに現れた数字の個数 ≧ それまでに現れた演算子の個数」
と書き直せる。

次の図において、後置記法の式を先頭から順に見ていったとき、
数字が現れたらX方向へ+1進み、演算子が現れたらY方向へ+1進むとすると、
原点(0,0)から点(n-1,n-1)へ行く最短経路の内、
y≦xを常に満たす経路の総数が求める答ということになる。

演算子　　　　　　　　　　
　↑　│　│　│　│／　　
４├─┼─┼─┼─┼─　　
　│　│　│　│／│　　　
３├─┼─┼─┼─┼─　　
　│　│　│／│　│　　　
２├─┼─┼─┼─┼─　　
　│　│／│　│　│　　　
１├─┼─┼─┼─┼─　　
　│／│　│　│　│　　　
０└─┴─┴─┴─┴→数字
　０　１　２　３　４　　　

ここで、原点から0≦y≦xを満たす点(x,y)まで行く最短経路の総数をF(x,y)とする。
(つまりn人の手の繋ぎ方はF(n-1,n-1)である)
F(x,y)は以下の[1],[2],[3]の漸化式で表される。

[1]
y=0の場合は0≦xの任意のxに対して、
F(x,0) = 1

[2]
1≦y=xの任意のx,yに対して、
F(x,y) = F(x,y-1)

[3]
1≦y＜xの任意のx,yに対して、
F(x,y) = F(x-1,y) + F(x,y-1)



[2],[3]より、
F(x,y) = Σ[i=y〜x] F(i,y-1)
       = Σ[i=1〜x-y+1] F(i+y-1,y-1)
が得られるので、これを利用してF(x,3)までの一般項を求めると、

F(x,0) = 1
F(x,1) = Σ[i=1〜x] F(i,0) = Σ[i=1〜x] 1 = x
F(x,2) = Σ[i=1〜x-1] F(i+1,1) = Σ[i=1〜x-1] (i+1) = (x-1)(x+2)/2
F(x,3) = Σ[i=1〜x-2] F(i+2,2) = Σ[i=1〜x-2] (i+1)(i+4)/2 = (x-2)(x+2)(x+3)/6

これから、
F(x,4) = (x-3)(x+2)(x+3)(x+4)/4!
F(x,5) = (x-4)(x+2)(x+3)(x+4)(x+5)/5!
一般に
F(x,y) = (x-y+1)(x+y)!/{y!(x+1)!} … (2)
が予想される。

(2)式が漸化式[1],[2],[3]を満たすことを証明する。

[1]
y=0の場合は0≦xの任意のxに対して、
F(x,0) = (x+1)x!/{0!(x+1)!} = 1

[2]
1≦y=xの任意のx,yに対して、
F(x,y) = F(x,x) = (2x)!/{x!(x+1)!}
F(x,y-1) = F(x,x-1) = 2(2x-1)!/{(x-1)!(x+1)!}
         = 2x(2x-1)!/{x!(x+1)!}
         = (2x)!/{x!(x+1)!}
         = F(x,x) = F(x,y)

[3]
1≦y＜xの任意のx,yに対して、
F(x,y) = (x-y+1)(x+y)!/{y!(x+1)!}
F(x-1,y) + F(x,y-1) = (x-y)(x+y-1)!/{y!x!} + (x-y+2)(x+y-1)!/{(y-1)!(x+1)!}
                    = {(x+1)(x-y) + y(x-y+2)}(x+y-1)!/{y!(x+1)!}
                    = {(x-y)x+x-y + (x-y)y+2y}(x+y-1)!/{y!(x+1)!}
                    = {(x-y)(x+y)+x+y}(x+y-1)!/{y!(x+1)!}
                    = (x-y+1)(x+y)(x+y-1)!/{y!(x+1)!}
                    = (x-y+1)(x+y)!/{y!(x+1)!}
                    = F(x,y)

以上より(2)式が正しいことが証明された。
ここで、
F(x,y) = (x-y+1)(x+y)!/{y!(x+1)!}
       = (x-y+1)(x+y)!/{y!x!(x+1)}
       = (x-y+1)C(x+y,y)/(x+1) ← (Cは組み合わせ)
と変形できる。

ゆえに、n人の手の繋ぎ方は
F(n-1,n-1) = C(2n-2,n-1)/n

　　　　＜自宅＞　　mizuryu@aqua.ocn.ne.jp