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

関連入試問題

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

演習 1       ［01京都府医大］解答

$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$ のとき，次が成り立つことを示せ．
   
   $$f(n,\ k)=f(n-1,\ k)+f(n,\ k-1)$$
   
   

2. $n\ge 2$ のとき，次が成り立つことを示せ．
   
   $$f(n,\ n)=f(n,\ n-1)$$
   
   

3. 次が成り立つことを示せ．
   
   $$f(n,\ k)={}_{n+k} \mathrm{C}_k\dfrac{n-k+1}{n+1}$$