場合の数について(通行禁止点が対角線上になっている時)

質問

今、ある粒子が(x,y)平面上の (1,0) にいます。

この粒子は1回の動きで次のいずれかの動きをします。
(1) x軸方向に　＋1
(2) y軸方向に　＋1

途中、(i,i) [i=1,2,…n-1] は通らずに
(n,n) に達する経路は何通りあるのでしょうか

nが具体的な数字の時は数えられるのですが、
nと一般的になってしまうととっかかりが掴めません。
よろしくお願いします。

回答No.2

cfv21

この問題と同等の問題が慶大環境情報学部の数学の入試問題の2005年[５]，2007年[５]に出題されています。
入手可能かどうかわかりませんが、雑誌「大学への数学」臨時増刊2007-7「合否を分けたこの一題」(東京出版)のp.70以降を参照してください。
もしくは、「カタラン数」というキーワードで検索してみてください。例えば、
http://ja.wikipedia.org/wiki/%E3%82%AB%E3%82%BF%E3%83%A9%E3%83%B3%E6%95%B0

回答No.1

koko_u_u

>nが具体的な数字の時は数えられるのですが、

それを補足にどうぞ。というか、それが「とっかかり」だと思いますけど。

補足

題意を満たす経路数を　a(n) とします。
コンビネーション mCn を、C[m,n] と表すとします。
また、(n,n)に到達する総経路数は　C[2n-1,n] です。

余事象のうち,
初めて通る通行禁止点が(i,i)の経路数は
a(i)*C[2(n-i),n-i]
となると思います。

よって、
a(n)=C[2n-1,n]－Σ[i=1～n-1]a(i)*C[2(n-i),n-i]
となると思います。

a(1)=1
なので
a(2)=1,a(3)=2
と順番に求めていくことはできます。
ただ、漸化式から一般項 a(n) をどう導けばいいのかわかりません。