次： 関連入試問題 上： カタラン数 前： カタラン数

カタラン数の意味

耕一　カタラン数にどんな意味があるのですか．

南海　三つの例を練習問題にしよう．

例 1.5.3        次の確率を求めよ．

切符売場に１列に $2n$ 人の人がならんでいる．このうち $n$ 人が500円硬貨をもち，残りの $n$ 人は1000円札しかもっていない．切符は１枚500円である．切符を売りはじめるとき売場 にはお金がない．切符を買う人が誰も釣り銭ができるのを待たずにすむ確率はいくらか．

解答

500円硬貨を持った人が来れば右へ, 1000円札を持った人が来れば上へそれぞれ1区画ずつ進むこ とにすれば, おつりがいらないのは次のような場合に実現する.

$$\begin{eqnarray*} &&どの場合においても, \ そのときまでに来た人のうち500円硬貨を \\ &&持った人の方が1000円札を持った人よりも多い. \end{eqnarray*}$$

したがって, この事象の数は A から B へ対角線を越えて上半分に入ることなく, B に 至る最短経路の総数に等しい. そして, 全事象の数は A から B へ至る最短経路の総数に 他ならないから, 求める確率は

$$\dfrac{c_n}{{}_{2n} \mathrm{C}_{n}}=\dfrac{1}{n+1}$$

□

例 1.5.4        次の個数を求めよ．

円周上に $2n$ 個の点がある．これらの点を２点ずつ結んで内部で互いに交わらない $n$ 個の弦をひくとき，いく通りの違った方法があるか．

解答

求める方法の数を $\mit\Phi_n$ とする. そして, 円周上の点を順に $\mathrm{A_1},\ \mathrm{A_2},\ \cdots,\ \mathrm{A}_{2n}$ とおく. このとき, 2点を結ぶ弦を $(\mathrm{A}_i,\ \mathrm{A}_j)\ (i<j)$ のように表すことにし, $\mathrm{A}_i$ を始点, $\mathrm{A}_j$ を終点とよぶことにする.

さて, 題意のような $n$ 本の弦が引けた状態のうちの一つを考える. この状態におい て, $\mathrm{A_1},\ \mathrm{A_2},\ \cdots,\ \mathrm{A}_{2n}$を始点と終点に分け,

$$\mathrm{A}_{i_1},\ \mathrm{A}_{i_2},\ \cdots,\ \mathrm{A}_{i... ..._{j_1},\ \mathrm{A}_{j_2},\ \cdots,\ \mathrm{A}_{j_n}\,;\,終点$$

とする. このとき, この始点と終点の組が題意をみたす(どの弦も互いに交わらない)ための 必要十分条件が

$$\begin{eqnarray*} &&すべての\ k\ (k=1,\ 2,\ \cdots,\ n)\ に対し, \ \mathrm{A}_1... ... までの \\ &&点の中で始点となるものが半分以上あること\cdots(*) \end{eqnarray*}$$

であることを, $n$ についての数学的帰納法で証明しよう.

1. $n=1$ のとき, $\mathrm{A}_1$ が始点, $\mathrm{A}_2$ が終点となるので, 明らかに成立する.
2. $n=m(\ge 1)$ のときの成立を仮定し, $n=m+1$ のときを考える.
   最初の設定より, $\mathrm{A}_1$ はつねに始点となる. そこで, $\mathrm{A}_1$ から順に見ていき, 最初に現れた終点を $\mathrm{A}_{j_1}$ とおく. すると, この点を終点とする弦が他の弦と交わらないの であるから, $\mathrm{A}_{j_1}$ に対応する始点は $\mathrm{A}_{j_1}$ の直前の 点, つまり $\mathrm{A}_{j_1-1}$ しかあり得ない.
   すると, 弦 $(\mathrm{A}_{j_1-1},\ \mathrm{A}_{j_1})$ とこの2点を結 ぶ弧によってできる弓形(他の点を含まない方)の内部には他に弦がないから, $2(m+1)$ 個の点から2個の点 $\mathrm{A}_{j_1-1},\ \mathrm{A}_{j_1}$ を除いた残りの点について は, それらを結ぶ弦が互いに交わらない. よって, 仮定よりこれら $2m$ 個の点に ついては $(*)$ が成り立ち, これに $(\mathrm{A}_{j_1-1},\ \mathrm{A}_{j_1})$ を加え ても, 始点, 終点がこの順に1個ずつ加えられるだけであるから, $n=m+1$ のと きも $(*)$ が成立する.

以上より, 求める方法の数は点 $\mathrm{A}_1,\ \mathrm{A}_2,\ \cdots,\ \mathrm{A}_{2n}$ から始 点, 終点を順に終点の前にある始点の個数が終点の個数よりも少なくないように選ぶ場合の 数, すなわち $c_n$ に他ならないから,

$$\mit\Phi_n=\dfrac{{}_{2n} \mathrm{C}_{n}}{n+1}$$

となる.□

注意 直接意味を考えて,

$$\mit\Phi_n=\mit\Phi_0\mit\Phi_{n-1}+\mit\Phi_1\mit\Phi_{n-2}... ..._{n-2}\mit\Phi_1 +\mit\Phi_{n-1}\mit\Phi_0\quad(\mit\Phi_0=1)$$

を示すこともできる. すると, $\mit\Phi_n, \ c_n$ は同一の漸化式をみたすので

$$\mit\Phi_n=c_n$$

となる.

例 1.5.5  

凸 $n$ 角形をその内部で交わらない対角線で三角形に分割するとき， 違った分割の仕方はいく通りあるか．

解答

条件を満たす分割の方法の総数を $T_n$ とする．頂点を A₁，A₂，…A_n とおく. $\mathrm{A_1}\mathrm{A}_{k}$ が対角線の一つであるような分割の仕方は,

$$\mathrm{A_1},\ \cdots,\ \mathrm{A}_{k}\,;\,T_k(通り)\quad \m... ...,\ \cdots,\ \mathrm{A}_{n},\ \mathrm{A_1}\,;\,T_{n-k+2}(通り)$$

あるので, 結局,

$$T_kT_{n-k+2}(通り)$$

ある. よって, $\mathrm{A}_1$ を通る対角線が関係するような分割の仕方は,

$$T_3T_{n-1}+T_4T_{n-2}+\cdots+T_{n-1}T_3(通り)$$

である. そして, これをすべての頂点について和をとると, 一つ一つの分割方法は, その分割 における対角線の数の2倍だけ繰り返し数えあげられることになる.
そこで, 一つの分割で用いられている対角線の本数を考えることにする. いま, $n$ 角形の内部に3角形は $n-2$ 個できている. そして, 内部の対角線は二つずつの3角形に共有され, 辺は一つずつ用いられているので, 対角線の本数を $q$ とすれば,

$$\dfrac{2q+n}{3}=n-2\qquad∴\quad q=n-3$$

よって,

$$n(T_3T_{n-1}+T_4T_{n-2}+\cdots+T_{n-1}T_3)=2(n-3)T_n\quad(n\geq 4)$$

ただし, $T_3=1$ である. すると,

$$\begin{eqnarray*} &&4T_3^2=2T_4\qquad∴\quad T_4=2 \\ &&5(T_3T_4+T_4T_3)=2\cd... ...=5 \\ &&6(T_3T_5+T_4T_4+T_5T_3)=2\cdot3T_6\qquad∴\quad T_6=14 \end{eqnarray*}$$

であるから,

$$T_{n+2}=c_n=\mit\Phi_n$$

と予想することができる. そこで, これを数学的帰納法で証明する.

1. $n=1$ のとき,
   
   $$T_3=c_1=1$$
   
   
   より明らかに成立する.
2. $n\leq m(m\geq1)$ をみたすすべての $n$ についての成立を仮定する. このとき,
   $$\begin{eqnarray*} 2mT_{m+3}&=&(m+3)(T_3T_{m+2}+T_4T_{m+1}+\cdots+T_{m+2}T_3) \\ &=&(m+3)(c_1c_m+c_2c_{m-1}+\cdots+c_mc_1) \end{eqnarray*}$$
   
   
   そして,
   
   $$c_{m+2}=c_0c_{m+1}+c_1c_m+\cdots+c_{m+1}c_0$$
   
   
   なので,
   
   $$2mT_{m+3}=(m+3)(c_{m+2}-2c_{m+1})$$
   
   
   よって,
   $$\begin{eqnarray*} T_{m+3}&=&\dfrac{m+3}{2m}(c_{m+2}-2c_{m+1}) \\ &=&\dfrac{m+... ...}{(m+2)!(m+1)!}=\dfrac{{}_{2m+2} \mathrm{C}_{m+1}}{m+2}=c_{m+1} \end{eqnarray*}$$
   
   
   となるので, $n=m+1$ のときも成立する.

したがって

$$T_n=c_{n-2}=\dfrac{{}_{2(n-2)} \mathrm{C}_{n-2}}{n-1}$$

となる．□

次： 関連入試問題 上： カタラン数 前： カタラン数