next up previous
次: カタラン数 上: カタラン数 前: カタラン数

ある入試問題

耕一 最近次のような問題をしました.

例 1.2.1       [96九州大学]

原点 $\mathrm{O}$ から出発して座標平面上を $x$ 軸の正の方向,または $y$ 軸の正の方向に1だけ 進むことを次々行って得られる経路を道という.原点と点 $(i,j)$ を結ぶ, 領域 $\{(x,y) \vert x \ge y \}$ 内の道の総数を $N(i,j)$ とする.次の問に答えよ.

  1. $N(2,2)$$N(3,1)$$N(3,2)$ を求めよ.
  2. $n \ge 1$ のとき, $N(n,1)$ を求めよ.
  3. $n \ge 3$ のとき, $N(n,2)$$N(n,1)$$N(n-1,2)$ で表し $N(n,2)$ を求めよ.

南海     これは解けたのかな.

耕一 はい.解は

  1. $N(2,2)=2,\ N(3,1)=3,\ N(3,2)=5$
  2. $N(n,1)=n$
  3. $N(n,2)=N(n,1)+N(n-1,2),\ N(n,2)=(1/2)(n+2)(n-1)$
です.

それで質問は, この $N(i,j)$ は一般に求まるのか,またこの $N(i,j)$ にはどんな意味があるのか, ということです.



Aozora Gakuen