【１】オイラーの三角形分割問題

　ところで，オイラーは，凸多角形を対角線によって三角形分割する方法は何通りあるかという問題を問うた．三角形は１通り，四角形は２通りと数えられる．

　五角形の場合は５通り，６角形では１４通り，七角形の場合は４２通り，８角形では１３２通り，・・・．小さい方から並べると

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

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

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

【２】オイラー問題の解答

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

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

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

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

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

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

　これはカタラン数の漸化式であって，カタラン数ｃ（ｎ）はｎの増加に応じて急激に増加する．

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

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

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

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

　カタラン数の一般項は

　　ｃ（ｎ）＝2nＣn／（ｎ＋１）＝（２ｎ）！／（ｎ＋１）！ｎ！

であるが，この公式は母関数を用いると簡明に得ることができる．

　カタラン数の母関数を

　　Ｃ（ｘ）＝ｃ（０）＋ｃ（１）ｘ＋ｃ（２）ｘ^2＋・・・＋ｃ（ｎ）ｘ^n＋・・・

とおく．これを２乗すると

　　Ｃ（ｘ）^2＝ｃ（０）ｃ（０）＋（ｃ（０）ｃ（１）＋ｃ（１）ｃ（０））ｘ＋ （ｃ（０）ｃ（２）＋ｃ（１）ｃ（１）＋ｃ（２）ｃ（０））ｘ^2＋・・・

　ここで，

　　ｃ（０）ｃ（０）＝ｃ（１）

　　ｃ（０）ｃ（１）＋ｃ（１）ｃ（０）＝ｃ（２）

　　ｃ（０）ｃ（２）＋ｃ（１）ｃ（１）＋ｃ（２）ｃ（０）＝ｃ（３）

であるから，

　　Ｃ（ｘ）^2＝ｃ（１）＋ｃ（２）ｘ＋ ｃ（３）ｘ^2＋・・・

次数を揃えるために，両辺にｘをかけて

　　ｘＣ（ｘ）^2＝ｃ（１）ｘ＋ｃ（２）ｘ^2＋ ｃ（３）ｘ^3＋・・・

　　ｘＣ（ｘ）^2＝Ｃ（ｘ）−ｃ（０）＝Ｃ（ｘ）−１

　Ｃ（ｘ）に関する２次方程式を解いて，母関数は

　　Ｃ（ｘ）＝｛１−（１−４ｘ）^1/2｝／２ｘ

ここでニュートンの二項展開により，一般項

　　ｃ（ｎ）＝2nＣn／（ｎ＋１）＝（２ｎ）！／（ｎ＋１）！ｎ！

が得られる．

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

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

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

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