next up previous
次: 生成関数の方法 上: カタラン数 前: カタラン数の意味

関連入試問題

南海  2001年にまた違うカタラン数の例が入試問題に登場した.

演習 3       [01京都府医大]解答3

$n,\ k$ は正の整数 $(n \ge k)$ で, $N=n+k$ とする. 図のように, $N$ 個の同じ大きさの空白の枠がある. 上段には n 個の枠があり,下段には $k$ 個の枠がある. 上段と下段の左端はそろっており,各段の枠は隣との間にすき間はない.

図では, $n=6,\ k=4$ である.

1から $N$ までの $N$ 個の自然数を各段の枠のなかに一つずつ次の二つの 条件を満たすように並べる.

  1. 各段においては,枠の中の数は右に行くに従って大きくなる.
  2. 左から $k$ 個の各列においては,下段の数は上段の数より大きい.
この二つの条件を満たすように1から $N$ を並べる並べ方の数を $f(n,\ k)$ とする. このとき
  1. $n>k\ge2$ のとき,次が成り立つことを示せ.

    \begin{displaymath}
f(n,\ k)=f(n-1,\ k)+f(n,\ k-1)
\end{displaymath}

  2. $n\ge 2$ のとき,次が成り立つことを示せ.

    \begin{displaymath}
f(n,\ n)=f(n,\ n-1)
\end{displaymath}

  3. 次が成り立つことを示せ.

    \begin{displaymath}
f(n,\ k)={}_{n+k} \mathrm{C}_k\dfrac{n-k+1}{n+1}
\end{displaymath}



Aozora Gakuen