平成１４年６月１日

[流れ星]

　　　　　　　　第９８回数学的な応募問題解答

　　　　　　　　　　＜解答募集期間：５月１９日〜６月１日＞

［一列に手をつなぐ］

　　　

太郎さんは前日、「地球に優しく」という環境をテーマにしたテレビ番組を観ていると、何人かの人々が一列に手をつないでいる光景をみました。大勢の人ですから、途中で先に何人かの人が手をつないで、次に左隣りの人と手をつないでから、右隣りの一列のグループと手をつないでいました。ここで、ｎ人が一列に手をつなぐ方法が知りたくなりました。人は区別しません。

　例えば、１人ですと、当然相手がいませんが、便宜的に１通りとしましょう。２人だと、１−２とつなぎますから、これも１通りです。３人だと、１−２とつないで３とつなぐ場合と、２−３と先につないだ後、左から１とつなぐ場合がありますから、計２通りあります。

ここで、問題です。ただし、人と人が手をつなぐ場合は二人として、同時に３人以上は考えないでください。

問１．ｎ＝４のとき、手をつなぐ順序は何通りか。

問２．ｎ＝５のとき、手をつなぐ順序は何通りか。

問３．一般に、ｎ人のとき、手をつなぐ順序は何通りか。

＜１９日午後１０時記入：水の流れから修正コメント＞　一部解釈の違いで異なる解答が出ています。混乱を招く不手際をお許しください。今から修正します。

だから、こう解釈したから、この答えになるというものでもかまいません。作問者の意図は「同時に二人またはグループで手をつなぐ組があった場合は１つと考えてください。例えば　４人のとき　（１−２）−（３−４）とつなぐ場合は１つと数えてください。」

ＮＯ１�@＜ＫＡＳＨＩＷＡＧＩ＞さんの解答１回目　5/18　22:21受信　６月１日更新
お世話になります。以下に解答致します。
ｎ＝４，５，６，７，８人くらいまでを書き出すと、各々４，７，１２，２０，３３通りとなる。
そこで、これらをｆ（４）、ｆ（５）、ｆ（６）、ｆ（７）、ｆ（８）とし、ｎ＝３，２をｆ（３）、ｆ（２）とする。
これらを以下の様にならべる。
ｆ（３）−ｆ（２）＝１
ｆ（４）−ｆ（３）＝２
ｆ（５）−ｆ（４）＝３
ｆ（６）−ｆ（５）＝５
ｆ（７）−ｆ（６）＝８
ｆ（８）−ｆ（７）＝１３
これは差がフィボナッチ数列を形成している事を示しており、一般形で表すと
ｆ（ｎ）−ｆ（ｎ−１）＝ｆ（ｎ−１）−ｆ（ｎ−２）＋ｆ（ｎ−２）−ｆ（ｎ−３）
ｆ（ｎ−１）−ｆ（ｎ−２）＝ｆ（ｎ−２）−ｆ（ｎ−３）＋ｆ（ｎ−３）−ｆ（ｎ−４）
ｆ（ｎ−２）−ｆ（ｎ−３）＝ｆ（ｎ−３）−ｆ（ｎ−４）＋ｆ（ｎ−４）−ｆ（ｎ−５）
−−−
−−−

ｆ（５）−ｆ（４）＝ｆ（４）−ｆ（３）＋ｆ（３）−ｆ（２）
これらを加えると、
ｆ（ｎ）−ｆ（４）＝ｆ（ｎ−１）−ｆ（３）＋ｆ（ｎ−２）−ｆ（２）
因って、ｆ（ｎ）＝ｆ（ｎ−１）＋ｆ（ｎ−２）＋ｆ（４）−ｆ（３）−ｆ（２）
　　　　　　　　＝ｆ（ｎ−１）＋ｆ（ｎ−２）＋４−２−１
　　　　　　　　＝ｆ（ｎ−１）＋ｆ（ｎ−２）＋１
以上のことから
問１．４通り
問２．７通り
問３．ｆ（ｎ）＝ｆ（ｎ−１）＋ｆ（ｎ−２）＋１　　となる。

＜水の流れ：コメント＞5月19日発信
９８回の問題で解釈があいまいな点がでてきました。
このように考えてください。後で、問題の方は修正しますが・・・
　「　ここで、同時に二人が手をつなぐ組があった場合は　１つと考えてください
例えば　４人のとき　（１−２）ー（３−４）とつなぐ場合は１つと数えてください。
　これで　、考えてください。混乱をまねく問題でお許しください結果は　意味ある数になっていますからね。

ＮＯ１�A＜ＫＡＳＨＩＷＡＧＩ＞さんの解答２回目　5/19　17:39受信　６月１日更新
お世話になります。本日MAILを再検討しましたら、肝腎の一般形を送付してないことに気づきました。申し訳ございません。面倒な計算を何回か間違えながらやりました。以下に解答致します。
問３．一般形をAｎで表すと、
　　　An＝（５−√５）{［（１−√５）／２］＾ｎ−１}／１０＋
　　　　　　（５＋√５）{［（１＋√５）／２］＾ｎ−１}／１０
　　となります。長い上に見にくくて恐縮です。

ＮＯ１�B＜ＫＡＳＨＩＷＡＧＩ＞さんの解答３回目　5/20　14:01受信　６月１日更新
私は今回の問題は以下の様に解釈致しました。
　何人かの中で最初に二人が手をつないでおき、次に全員が手をつなぐ組み合わせはいくつかと言うものです。即ち、階差がフィボナッチ数列になるというのが狙いだと解釈致しました。
　最初に二人で手をつなぐ組み合わせを＝で表します。
　０人：０
　１人：０
　２人：１
　３人：２　　１＝２ー３
　　　　　　　 １ー２＝３
　４人：４     １＝２ー３ー４
　　　　　　　 １ー２＝３ー４
                 １ー２ー３＝４
                 １＝２ー３＝４
　５人：７　　１＝２ー３ー４ー５
　　　　　　　 １ー２＝３ー４ー５
　　　　　　　 １ー２ー３＝４ー５
　　　　　　 　１ー２ー３ー４＝５
　　　　　　　 １＝２ー３＝４ー５
　　　　　　　 １＝２ー３ー４＝５
　　　　　　　 １ー２＝３ー４＝５
 　以下同様にして、
　 ６人：１２
　 ７人：２０
   ８人：３３           因ってこの階差がフィボナッチ数列になることが分かります。
　そこで、既にMAIL致しましたような関係とｎ人での一般項をだしました。一般項は汚くて申し訳ございません。

ＮＯ２＜ＳＩＮ＞さんの解答　5/18　22:31受信　６月１日更新
第９８回の問題を見たので，解答を考えてみました。間違っていたらすみません。
問１．人の間は３箇所であり，どこかをつないだ後につなぐ所は２箇所，最後に１箇所つなぐことになるからつなぎ方は６通り。
問２．人の間は４箇所であり，どこかをつないだ後につなぐ所は３箇所，同様に，２，１箇所となるからつなぎ方は２４通り。
問３．一般にｎ人の手をつなぐつなぎ方は，上の考え方より（ｎ−１）！通り。
　これでどうでしょう？間違ってますか？
＜水の流れ：コメント＞5月19日発信
９８回の問題で解釈があいまいな点がでてきました。
このように考えてください。後で、問題の方は修正しますが・・・
　「　ここで、同時に二人が手をつなぐ組があった場合は　１つと考えてください
例えば　４人のとき　（１−２）ー（３−４）とつなぐ場合は１つと数えてください。
　これで　、考えてください。混乱をまねく問題でお許しください結果は　意味ある数になっていますからね。

ＮＯ３�@＜Ｈ７Ｋ＞さんの解答１回目　5/18　22:31受信　６月１日更新
ｎ人が手をつなぐ順序をｆ（ｎ）とすると、問１：ｆ（４）＝２・C（０＋２，０）ｆ（１）ｆ（３）＋２・C（１＋１，１）ｆ（２）ｆ（２）＝２・１・２＋２・１・１＝６通り
問２：ｆ（５）＝２・C（０＋３，０）ｆ（１）ｆ（４）＋２・C（１＋２，１）ｆ（２）ｆ（３）＝２・１・６＋２・１・２＝１４通り
問３：ｆ（ｎ）＝Σ（ｋ＝１〜n-1）C（ｎ−２，ｋ−１）ｆ（ｋ）ｆ（ｎーｋ）
＜水の流れ：コメント＞上の３人の方の答えが同じでありません。出題者としては、混乱を招くような事になっています。反省します。昨日の修正で考えてくだされば幸いです。

ＮＯ３�A＜Ｈ７Ｋ＞さんの解答２回目　5/19　19:37受信　６月１日更新
そうすると、
1.f(4)=f(1)f(3)+f(2)f(2)=5
2.f(5)=f(1)f(4)+f(2)f(3)+f(3)f(2)+f(4)f(1)=5+5+4=14
3.f(n)=\sum^{n-1}_{k=2}f(k)f(n-1-k)
      =C_{n-1}←カタラン数ですね。
＜水の流れ：コメント＞実は、＜Ｈ７Ｋ＞さんは高校１年生です。すでにカタラン数を知っているとは驚きです。
ＮＯ４�@＜遊楽街＞さんの解答１回目　5/20　23:58受信　６月１日更新

今回の応募問題、私も初めは(n-1)!だと思っていました。
簡単すぎるので、たぶん問題を読み違えてるのだろうと思い、様子を見ていたら、追記されていたので再考してみました。
それでも一部解釈に困るところがありましたが、コメントに書かれた((1-2)-(3-4))のような最終形が何種類あるかということだろうと目星を付けて、
f(n)=Σ[i=1〜n-1]f(i)*f(n-i)という漸化式を立てました。コンピューターで計算した値を調べてみると、カタラン数になっているので、きっと問題の解釈はこれで良いのでしょう(^^ということで、今はこの漸化式をどうやって簡単化するか考えているところです。
でも、なかなか良いアイディアが浮かばないんですよね…別な視点でf(n)を考えた方が早いかも(笑)
以上、途中報告でした。

ＮＯ４�A＜遊楽街＞さんの解答２回目　5/23　01:56受信　６月１日更新
応募問題の途中経過その2です。添付ファイルを見てください。一応答えまでは辿り着きましたが、途中できちんと証明していない箇所があります。
前回考えていた漸化式の変形は結局諦めて別な方法を探しました。なかなか奇抜なアイディアかなと思っているんですが、どうでしょう？
答えに辿り着くまでにかなり遠回りしている気がしますが(笑)
ちなみに、一番初めにGoogleで「カタラン数」を調べたときにhttp://www.interq.or.jp/student/suugaku/taiwa/node85.html
を見つけていたのですが、チラッと見ただけどうやって計算しているかまでは見ないようにしています。ここに私が探し求める物があるのはわかっているのですが(^^;
やっぱり自力でやらないと悔しいですからね。それにしても、どういう考え方をしたらあんなに短く答えに辿り着けるんだ！(^^
ということで、もう少し頑張ってみます。カタラン数って難しいですね…

問題の解釈　「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)経路の総数が求める答ということになります。

ここで、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でも正しい値となる)

ＮＯ４�B�C＜遊楽街＞さんの解答3・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個だけ多いですが、総数が同じ方が以降の話が少しだけ簡単になるので、
最初の数字は固定してその数字は数えないことにすれば、満たさなければならない条件は
「それまでに現れた数字の個数 ≧ それまでに現れた演算子の個数」と書き直せます。

(★ここからn=5の例なので注意★)

次の図1において、後置記法の式を先頭から順に見ていったとき、




数字が現れたらX方向へ+1進み、演算子が現れたらY方向へ+1進むとすると、




n=5の場合、(n-1)×(n-1) = 4×4の正方形の左下の頂点(◆)から





 
 
 

右上の頂点(●)へ行く経路の内、対角線より上にはみ出さない(対角線上はOK)経路の総数が求める答ということになります。

 
 
　　　




ここで、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)!} … (2)　で表される。そこで、この一般項の予想が正しいことを証明する。
 
 

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

= 1　となり正しい。

[2]　m≧1の任意のmに対してi=1の場合は(1)式より　F(m+1,1)

= F(m,1) + F(m,2)　となるので、(2)式がこの関係式を満たすことを示す。

F(m+1,1) = 2(2m+1)!/{m!(m+2)!}

F(m,1) + F(m,2) = 2(2m-1)!/{(m-1)!(m+1)!} + 3(2m)!/{(m-1)!(m+2)!}

= {2m(m+2)(2m-1)! + 3m(2m)!}/{m!(m+2)!}

= {(m+2)(2m)! + 3m(2m)!}/{m!(m+2)!}

= {m+2+3m}(2m)!/{m!(m+2)!}

= 2(2m+1)(2m)!/{m!(m+2)!}

= 2(2m+1)!/{m!(m+2)!}

= F(m+1,1)

[3]　m≧1,i≧1の任意のm,iに対して(1)式より

F(m+1,i) = Σ[j=1〜i+1] F(m,j)

F(m+1,i+1) = Σ[j=1〜i+2] F(m,j)

であるから、

F(m+1,i+1) = F(m+1,i) + F(m,i+2)

という関係式を得る。

(2)式がこの関係式を満たすことを示す。

F(m+1,i+1) = (i+2)(i+2m+1)!/{m!(i+m+2)!

F(m+1,i) + F(m,i+2) = (i+1)(i+2m)!/{m!(i+m+1)!} + (i+3)(i+2m)!/{(m-1)!(i+m+2)!}

= {(i+1)(i+m+2) + m(i+3)}(i+2m)!/{m!(i+m+2)!}

= {i^2+(m+3)i+m+2 + mi+3m}(i+2m)!/{m!(i+m+2)!}

= {i^2+(2m+3)i+2(2m+1)}(i+2m)!/{m!(i+m+2)!}

= (i+2)(i+2m+1)(i+2m)!/{m!(i+m+2)!}

=

(i+2)(i+2m+1)!/{m!(i+m+2)!}

= F(m+1,i+1)

[1],[2],[3]より、m≧1,i≧1のすべての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でも正しい値となる)

■副産物

F(m,i)でi=0を許せば、

m=1 　　１　　１　　１　　１　　１　　１

m=2 　　１　　２　　３　　４　　５

m=3 　　２　　５　　９　１４

m=4 　　５　１４　２８

m=5 　１４　４２

m=6 　４２

となる。

X-Y座標上の原点(0,0)からY≦Xを常に満たしながら任意の点(x,y)(0≦y≦x)へ行く

最短経路の総数は、F(y+1,x-y)と一致する。

F(y+1,x-y)=(x-y+1)C(x+y,y)/(x+1)　である。

解答を修正したので、添付します。ここからは４回目の原稿です。

■変更点

  (★ここからn=5の例なので注意★)という記述以降を

  前回書いた副産物の方を中心とする証明に変更しました

 
 
■問題の解釈
「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
 

＜水の流れ：コメント＞６月１５日発信
何とお詫びすればよいか分かりませんが、大変申し訳ありませんでした。私の未熟なタグ知識でこんな状態で載せていました。
お許しください。改めて、ＮＯ４�B＜遊楽街＞さんの解答3回目　5/25　６:１６受信　６月１５日更新

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

以上の解答を別なファイルで載せた。

ＮＯ５�@＜ＢｏｓｓＦ＞さんの解答１回目　5/22　21:50受信　６月１日更新

こんにちは,今日こちらは,とても暑かったですよ。

[解]　題意は　1+1+1+・・・+1=n における、n-1 個の +

の演算の順序の個数と同値だから　 (n-1)!　…答

簡単過ぎて.不安です,題意の取り違いでしょうか？

ＮＯ５�A＜ＢｏｓｓＦ＞さんの解答２回目　5/23　14:14受信　６月１日更新

こんにちは、BossFです。

カタラン数をいいたかったんですね…

[解]

n人が、手をつなぐ順序を f(n) とする

(i)f(1)=1

 最後には、必ず、二つのグループの端同士が手をつなぐから、

f(n)=Σ(k=1〜n-1){f(k)・f(n-k)} 但し f(2)=1 …�@

�@はカタラン数であることを示す

i.e. f(n)=2(n-1)C(n-1)/n …�A

�A式は n=1 でも成立

よって一般にｎ人の時

手をつなぐ順序は,2(n-1)C(n-1)/n通り　■

＜水の流れ：コメント＞今回多くの方から解答があり、ありがとうございます。「遊楽街」さんの原稿はカタラン数を明快にしてあります。感謝します。

以前は　「第59回机の積み方」や「第36回大縄跳び」　にあります。作問って楽しいでしょう。

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