前ページ


だから、$n+2$角形だと$C_{n}$通りだと予想できる。つまり頂点の個数から2を引いた数を引数とするカタラン数が、求める場合の数であろう。ここで例によって便宜的に$2$角形なら(そんな図形は存在しないのだから、分割数は任意に決めてよい)、分割方法は$C_{0}=1$通りとしよう。

$C_{n+1}$に対応するのは$n+3$角形だから、$n+3$角形から漸化式を導こう。
    

任意の辺$AB$を固定する。
   
三角形分割の細胞の中に$\triangle ABP$があるはずだ。この三角形を挟み撃ちにする2つの多角形がある。片方を
   $k$角形($k \geq 2$)
とすると、他方は
   $n+4-k$角形($n+4-k \geq 2 \Rightarrow k \leq n+2$)
になる。$\triangle ABP$と合わせると頂点の個数は
   $3+k+(n+4-k)=n+7$
だが点$A,B$で2度ダブって数え、点$P$では3度数えているから、ダブりの計4を引くとたしかに$n+3$になる。漸化式を作ると
   $C_{n+1}= \displaystyle \sum_{k=2}^{n+2} C_{k-2} \times C_{n+2-k}$
インデックスを$k$から$k-2=i$に変えて
   $C_{n+1}= \displaystyle \sum_{i=0}^{n} C_{i} \times C_{n-i}$
ただし
   $C_{0}=1$
これまた、括弧の問題や最短経路と同じ漸化式だ。だからこれもカタラン数になる。

PageTopへ


§∞. 参考文献

[1] 瀬山士郎著『読む数学記号』角川ソフィア文庫、2017年11月刊、pp.72-74

[2] 松坂和夫著『現代数学序説-集合と代数』ちくま学芸文庫、2017年12月刊、pp.129-131

[3] 遠山啓著作集 数学教育論シリーズ12『数楽への招待-U』太郎次郎社、1981年10月刊、pp.23-32

PageTopへ



[婆茶留高校数学科☆HP] Top pageに戻る このページを閉じる 探したい言葉はここへ→