多角形を三角形分割
四角形を三角形に分割する方法は2通り、5角形を三角形に分割する方法は5通りある。この個数は一般にカタラン数というもので与えられ、一般にn+2角形を三角形に分割する方法は
通りである。
さて、実は上の定義は平面上における凸多角形の三角形分割の個数である。より一般に高次元の多角形、または単に組み合わせ的な三角形への分割を考えると、少し分割の仕方が増える。たとえば5角形の場合、頂点を1,2,3,4,5とすると
[1,2,4] [1,3,4] [1,3,5] [2,3,5] [2,4,5]
のような分割がある。これは5角形の辺をメビウスの輪の境界にするような分割の方法である。
6角形の場合は
[1,2,3] [1,3,5] [1,4,5] [1,4,6] [3,4,6] [3,5,6]
のようなメビウスの輪の境界にするような分割のほかに
[1,2,4] [1,3,5] [1,3,6] [1,4,5] [2,3,5] [2,4,6] [2,5,6] [3,4,6]
のような、トーラスに穴を開けた曲面の境界(穴の部分)が6角形の辺となるような分割の方法もある。これは6角形が非自明な結び目になるときの組み合わせ的なザイフェルト曲面になると考えられる。
さて、このような拡張された三角形分割の個数を表にしてみた。
頂点数 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 一般形 |
---|---|---|---|---|---|---|---|---|
三角形分割数 | 1 | 2 | 5 | 14 | 42 | 132 | 429 | カタラン数 |
拡張された三角形分割数 | 1 | 2 | 6 | 30 | 337 | ? | ? | ? |
一般形は何だろう?三角形分割数がカタラン数を介して括弧のつけ方やヤング図形と関連しているのと同様に、拡張された三角形分割数は他の何かと関連しているのだろうか??
もう少し詳しい表(Tをトーラス、Pを射影平面、Sを球面、Dを開円板とする)
? は計算中の値
頂点数n | 三角形分割の位相 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 一般形 |
---|---|---|---|---|---|---|---|---|---|---|
(n-2)個の三角形分割数 | S-D(閉円板) | 1 | 2 | 5 | 14 | 42 | 132 | 429 | 1430 | カタラン数 http://oeis.org/A000108 |
n個の三角形分割数 | P-D(メビウスの輪) | 0 | 0 | 1 | 14 | 113 | 720 | 4033? | ? | http://oeis.org/A007817 |
(n+2)個の三角形分割数 | T-D | 0 | 0 | 0 | 2 | 70 | 1144 | 12354? | ? | ? |
(n+2)個の三角形分割数 | 2P-D | 0 | 0 | 0 | 0 | 112 | 2400 | 28593? | ? | ? |
(n+4)個の三角形分割数 | 3P-D | 0 | 0 | 0 | 0 | 0 | 3944? | ? | ? | ? |
(n+6)個の三角形分割数 | 2T-D | 0 | 0 | 0 | 0 | 0 | 0? | ? | ? | ? |
(n+6)個の三角形分割数 | 4P-D | 0 | 0 | 0 | 0 | 0 | 1772? | ? | ? | ? |
(n+8)個の三角形分割数 | 5P-D | 0 | 0 | 0 | 0 | 0 | 32? | ? | ? | ? |
拡張された三角形分割数 | 1 | 2 | 6 | 30 | 337 | 10144? | ? | ? | ? |