犀角(Diceros Horn) 2006 08

多角形の三角形分割

凸ｎ角形を三角形に分割する方法が何通りあるかを考えてみた。 ｎ＝４の時は、対角線の引き方だから２通り。 ｎ＝５の時は、頂点を順に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 | 固定リンク(多角形の三角形分割 )