犀角(Diceros Horn)

多角形の三角形分割（その２）

平面上の凸ｎ角形と言う制限をなくして考えてみる。 つまり、三角形分割したときの面の張り方がメビウスの輪みたいになっていることを許すことにするとどうなるか。 ｎ＝５の場合は、平面の場合以外に、

• [0,2,3]
• [1,3,4]
• [2,4,0]
• [3,0,1]
• [4,1,2]

の５つの三角形で分割する方法がある。普通の平面上だと当然自己交差が起こってしまうけれども、ここではそれは考えないことにする。

力技でｎが小さいときに数えてみる

まだ規則性が見えていません。

posted at 00:59 | category: /Math/Discrete | 固定リンク(多角形の三角形分割（その２）)

多角形の三角形分割

凸ｎ角形を三角形に分割する方法が何通りあるかを考えてみた。 ｎ＝４の時は、対角線の引き方だから２通り。 ｎ＝５の時は、頂点を順に0,1,2,3,4とすると、

• [0,2][0,3]
• [1,3][1,4]
• [2,4][2,0]
• [3,0][3,1]
• [4,1][4,2]

の辺を追加する５通り。ｎ＝６の時は１４通りである。

一般にはｎ角形（ｎ≧３） の時

Π_{k=2}^{n-1} (4k-6)/k

通りになる。小さいところを計算すると

• n=3のとき1
• n=4のとき1*(6/3)=2
• n=5のとき1*(6/3)*(10/4)=5
• n=6のとき1*(6/3)*(10/4)*(14/5)=14
• n=7のとき1*(6/3)*(10/4)*(14/5)*(18/6)=42

のようになる。

上の式の (4k-6)/k の部分は

• 4k-6 = 2(2k-3) = 2*(k角形の三角形分割が与えられた時の辺と対角線の本数)
• k = k角形の頂点の回転による同一視

をあらわす。すなわち、n角形の三角形分割と、三角形分割を与える頂点の順序つきの組が与えられた時に、(n+1)角形の三角形分割が与えられることをいう。さらにそれが、頂点の番号付けに対して対称であることを言えばよい。

1. 頂点の組[p,q]が辺の場合は、1点rを外部に追加して[p,r,q]を新たな三角形として、(n+1)角形の三角形分割を得る。ここで、[p,q]が順方向なら頂点の番号は r = q として、新たな q は r+1 とする。逆方向なら r = q+1 として、新たな p = r+1 とする。
2. 頂点の組[p,q]が対角線の場合は、[p,q,r=q+1] を新たな三角形として追加する。p>q の場合は p もひとつ増やす。

n=4 の時の例として計算してみると、[0,1,2][0,2,3] を4角形の三角形分割として、

• [0,1]を追加した場合[0,1,2][0,2,3][0,3,4]という5角形の三角形分割を得る
• [1,0]を追加した場合[0,1,2][0,2,3][0,3,4]という5角形の三角形分割を得る
• [1,2]を追加した場合[0,1,3][1,2,3][0,3,4]という5角形の三角形分割を得る
• [2,1]を追加した場合[0,1,3][1,2,3][0,3,4]という5角形の三角形分割を得る
• [2,3]を追加した場合[0,1,2][0,2,4][2,3,4]という5角形の三角形分割を得る
• [3,2]を追加した場合[0,1,2][0,2,4][2,3,4]という5角形の三角形分割を得る
• [3,0]を追加した場合[0,1,4][1,2,3][1,3,4]という5角形の三角形分割を得る
• [0,3]を追加した場合[0,1,2][0,2,3][0,3,4]という5角形の三角形分割を得る
• [0,2]を追加した場合[0,1,2][0,2,3][0,3,4]という5角形の三角形分割を得る
• [2,0]を追加した場合[0,1,3][1,2,3][0,3,4]という5角形の三角形分割を得る

が得られ、[0,1,3][1,2,3]からも同様に得られて、頂点の回転対象性から、同じ三角形分割が 4つずつ得られるので、２＊１０／４＝５通りの三角形分割が得られる。

追加情報

The On-Line Encyclopedia of Integer Sequences によると、この数列は Catalan numbers として知られているみたいです。

posted at 23:37 | category: /Math/Discrete | 固定リンク(多角形の三角形分割 )