今回のコラムでは多角形の三角形分割を取り上げることにしますが，その前に，凸ｎ角形の対角線は何本あるか考えてみることにします．

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

［Ｑ１］凸ｎ角形の対角線の本数は？

［Ａ１］ひとつの頂点から引ける対角線はｎ−３本．また，頂点はｎ個あるから，ｎ（ｎ−３）本のように思えるが，これでは同じ対角線が重複して数えられているから２で割って，ｎ（ｎ−３）／２本．

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

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

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

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

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

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

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

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

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

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

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

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

　カタラン数の一般項は

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

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

　カタラン数の母関数を

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

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

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

　ここで，

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

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

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

であるから，

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

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

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

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

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

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

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

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

が得られる．

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