| ■1484 / inTopicNo.2) |
Re[1]: 場合の数
|
□投稿者/ みっちぃ 一般人(38回)-(2005/06/25(Sat) 02:41:00)
 | この問題，はっきり言って難しいです．
難関大学が誘導を付けて出してくるくらいのレベルだと思います．
(カタラン数という，高校数学で扱っている場合の数の最高レベルの問題だから…)
ちなみに，問題で矛盾点がありますね．『前後6列・左右2列』ではなく，『前後2列・左右6列』ですね．
1から順に自然数を，箱の中に入れてゆくという考え方でやってみましょう．
このとき，問題の条件にあうように，次のように並べ方のルールを決めます．
1) 前・後列とも，左から順に詰めて自然数を入れる．
(つまり，前の左から2列目に自然数が入っていないのに，前の左から3列目以降には自然数は入れられない)
2) 左右各列において，前の列に自然数が入っていなければ，後ろの列には自然数は入れられない．
さて，このルールを定めた下で，f(n,k)を『前列にn個，後列にk個自然数が入っている場合の数』と定めます．
つまり，自然数(n+k)までを箱に入れた状態が何通りあるかを考えます．当然，n≧kとなります．
f(n,k)の漸化式を立てましょう．(立てるだけで一般項は求めない)
i)n=kのとき ⇒ 自然数2nは，必ず後列に入っているので，f(n,n)=f(n,n-1)
ii)n>k=0のとき ⇒ 自然数nは，必ず前列に入っているので，f(n,0)=f(n-1,0)
i)n>k≧1のとき ⇒ 自然数n+kは，前列に入っている場合と，後列に入っている場合が考えられるので，f(n,k)=f(n-1,k)+f(n,k-1)
ここから，地道にf(1,0)=1からf(6,6)までを計算していきましょう．
f(1,0)=1,f(2,0)=f(1,0)=1，f(1,1)=f(1,0)=1，f(3,0)=f(2,0)=1，f(2,1)=f(1,1)+f(2,0)=2，f(4,0)=…
という具合にすると，f(6,6)=132と求まります．
ちなみに，この漸化式の立て方は，http://aozoragakuen.sakura.ne.jp/taiwaN/taiwaNch04/node25.html
の問題の立て方と全く同じです．
恐らく，この問題に式一発でバシッと解ける方法はアイデア的に超高校級じゃないかなと思います．
12C6 -12C5なのですが，この導出ができる受験生は1万人に1人もいないと思われます．
|
|