【１】カタラン数の漸化式とオイラーの問題

　ｎ角形は，対角線によってｎ−２個の三角形に分割することができる．ここでは，凸多角形（ｎ＋２角形）に対角線を描いて，それをいくつかの凸多角形に分けるのではなく，対角線を互いに交わらないように引いて三角形分割する問題を考えよう．

［Ｑ］凸ｎ＋２角形に互いに交わらないｎ−１本の対角線を引いて三角形分割する仕方の数ｃ（ｎ）は？

［Ａ］この問題はオイラーが提起した幾何学問題である（オイラーの問題）．三角形は１通りと数える．４角形では２通り，５角形では５通りあることは数えられても，６角形ではそう簡単にはいかない（６角形に対しては１４通りある）．

　６角形の場合，たとえばある対角線を引いて３角形と５角形，４角形と４角形，５角形と３角形に分割することができるが，そのような分割の仕方を場合分けすることで，積和型の漸化式

　　ｃ（ｎ＋１）＝ｃ（０）ｃ（ｎ）＋ｃ（１）ｃ（ｎ−１）＋・・・＋ｃ（ｎ）ｃ（０）

が得られる．ただし，ｃ（０）＝ｃ（１）＝１とする．

カタラン数ｃ（ｎ）はｎの増加に応じて急激に増加するが，漸化式を用いると簡明に得ることができる．

　　ｃ（０）＝１，ｃ（１）＝１，ｃ（２）＝２，ｃ（３）＝５，

　　ｃ（４）＝１４，ｃ（５）＝４２，ｃ（６）＝１３２，

　　ｃ（７）＝４２９，ｃ（８）＝１４３０，ｃ（９）＝４８６２，・・・

　なお，凸ｎ角形を対角線で三角形分割する仕方は何通りあるかという問題は，回転や反転で同型になるものを同じと数えると，

　　１，１，１，３，４，１２，２７，８２，２２８，７３３，２２８２，７５２８，・・・

となることを付記しておく．

　カタラン数はいろいろなシーンで登場し，２００を超える応用問題があるという．そのひとつがオイラーの問題である．オイラーは，凸多角形を対角線によって三角形分割する方法は何通りあるかという問題を問うた．小さい方から並べると

　　１，２，５，１４，４２，１３２，４２９，・・・

　オイラーは研究を深め，これらの数がカタラン数であることをつきとめた．円卓を囲む人たちが手を交差せずに握手できる方法の数は，カタラン数になっているのである．応用問題をいくつか掲げたい．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝