三角形分割
複雑な図形を扱う場合、小学校以来やっているように、いくつかの三角形に分割して考え
ることが多い。このページでは、一つの図形に対して、何通りの三角形分割の方法がある
かについて考えてみたい。
順列組合せの分野で学習するように、凸 n 角形の n 個の頂点から3個選び、それらを
結んでできる三角形の総数は、
で与えられる。
例 四角形の場合、三角形の総数は、上の公式を当てはめるまでもなく、4個である。
実際に、
このページで考えようとしていることは、上述のような三角形の個数ではなく、下記のよう
な三角形分割(互いに交わらないような対角線による分割)の方法の数である。
したがって、四角形の三角形分割の方法の数は、2通りあることが分かる。
それでは、一般の凸 n 角形において、三角形分割の方法の数は何通りあるであろうか?
この問題が、本ページでの主題である。
例 凸 5角形の場合は、明らかに、5通りある。
例 凸 6角形の場合は、少し大変であるが、実際に書いて数えてみると、14通りある。
このような場合の数を、一般の凸 n 角形について求める場合、凸 6角形の場合から推
察されるように、図を描いて数えるという方法には、おのずと限界があることが分かる。
もっと違う見方をして求めることにしよう。
凸 n 角形( n≧3 )において、三角形分割の方法の数が、F(n) 通りあるものとする。
明らかに、F(3)=1 である。 いま、n≧4 とする。 3<k<n において、凸
n 角形は
3つの部分に分割される。F(n) の定義より、 F(n) =1・F(n−1)+F(3)・F(n−2)+・・・ + F(k−1)・F(n−k+2) +・・・ + F(n−2)・F(3) +F(n−1)・1 が成り立つ。 |
例 F(4) =1・F(3)+F(3)・1=1・1+1・1=2
F(5) =1・F(4)+ F(3)・F(3)+F(4)・1=1・2+1・1+2・1=5
F(6) =1・F(5)+ F(3)・F(4)+ F(4)・F(3)+F(5)・1=1・5+1・2+2・1+5・1=14
・・・・・・・・・・・・・・・・・・・・・・・・・・・・・
この漸化式を用いると、ある程度機械的に所要の場合の数が求められる。
ところで、この漸化式の解は、
で与えられることが知られている。
この公式を用いると、凸 8 角形の三角形分割の方法の数が、132 通りあることが直ち
に分かる。
数列{F(n)}:1,2,5,14,・・・ について、その詳細を調べようと思って、いつもお世話
になっている 「オンライン整数列大辞典」 で検索してみると、その膨大な参考資料に圧
倒される。
( → 参考:「カタラン数」)
数列{F(n)}の一般項の計算、分割の方法に関わらず三角形の個数は変わらないなどは、
今後の研究課題としたい。
(参考文献: ゴロヴィナ、ヤグロム 著 松田信行 訳 幾何の帰納法 (東京図書))
(追記) 上記では、凸 n 角形における三角形分割の方法の数を考えた。凸
6角形の場合
の例示からも分かるように、三角形分割の際に生じる三角形の総数は、三角形分割
の仕方によらず一定である。
この事実は簡単に次のようにして確認することができる。
一つの三角形分割によって生じる三角形の総数を、K とおく。
一つの三角形の内角の総和は180°なので、三角形分割によって生じる三角形全ての
内角の総和は、180°K となる。一方、凸 n 角形の内角の総和は、180°× n −360°
なので、180°K=180°× n −360°より、
K= n −2
が成り立つ。
この式から分かるように、三角形分割の際に生じる三角形の総数は、三角形分割の仕方
によらず一定である。
また、凸 6角形の場合の例示からも分かるように、三角形分割の際に用いる対角線の総
数も、三角形分割の仕方によらず一定である。
この事実は簡単に次のようにして確認することができる。
一つの三角形分割によって生じる対角線の総数を、L とおく。
三角形分割によって生じる三角形の辺の総数は、上記の事実を用いて、3(n−2) である。
一方、三角形の辺となる対角線は2度数えられ、凸 n 角形の辺は1度しか数えられないので、
辺の総数は、2L+ n なので、2L+ n = 3(n−2)より、L= n −3 が成り立つ。
この式から分かるように、三角形分割の際に生じる対角線の総数は、三角形分割の仕方
によらず一定である。
以上の準備の下に、いよいよ本題に入ろう。
前述したように、凸 n 角形の三角形分割の方法の数を、F(n) 通りとすると、
F(n) =1・F(n−1)+F(3)・F(n−2)+・・・+ F(n−2)・F(3)
+F(n−1)・1
=2F(n−1)+F(3)・F(n−2)+・・・+ F(n−2)・F(3)
が成り立つ。
この式を用いると、 F(3)=1 から始まって帰納的に、F(n) を求めることができた。
しかし、一般の n に対して、直ちに F(n) を求めるということは、はなはだ困難であった。
このことについて、次のように、 F(n) に関する新しい関係式を導くことにより、簡単に解決
される。
左図において、一つの対角線(1−k)に注目して、 この対角線が三角形分割に用いられている場合の 三角形分割の方法の数は、 F(k)・F(n−k+2) 通り である。ただし、n≧4、3≦k≦n−1 とする。 一つの頂点(例えば、1)を固定して、この頂点を 通る全ての対角線について上記の計算を行い、そ の総和を求めると、 |
F(3)・F(n−1)+F(4) ・F(n−2)+・・・+ F(n−2)・F(4) +F(n−1)・F(3)
同様の計算を他の頂点に対しても行う。
このとき、対角線が三角形分割に用いられている場合の三角形分割の方法の総数は、1
本の対角線が2度重複して考えられていることに注意して、
n・(F(3)・F(n−1)+F(4) F(n−2)+・・・+ F(n−2)・F(4) +F(n−1)・F(3))/2
に等しい。
ところが、三角形分割の方法の数は、F(n) 通りで、上記の計算では対角線の本数
n−3
分だけ重複して数えられている。
したがって、n・(F(3)・F(n−1)+・・・+F(n−1)・F(3))/2=(n−3)・F(n) が成り立つ。
ところで、 F(n) =2F(n−1)+F(3)・F(n−2)+・・・+ F(n−2)・F(3) より、
F(n+1) =2F(n)+F(3)・F(n−1)+・・・+ F(n−1)・F(3)
なので、これを上式に代入すると、n・( F(n+1) −2F(n))/2=(n−3)・F(n) すなわち、
n・ F(n+1) =2(2n−3)・F(n)
が成り立つ。このとき、
(n−1)・F(n)=2(2n−5)・F(n−1)
(n−2)・F(n−1)=2(2n−7)・F(n−2)
・・・・・・・・・・・・・・・・・・・・・・・・・
4・F(5)=2・5・F(4)
3・F(4)=2・3・F(3)=2・3
これらを辺々かけて、
(n−1)!・F(n)/2=2n−3・(2n−5)!/(2n−3・(n−3)!)=(2n−5)!/(n−3)!
よって、
が成り立つ。
(参考文献: ア・ヤグロム、イ・ヤグロム 著 筒井孝胤 訳
初等的に解いた高等数学の問題(T) (東京図書))
(追記) 当HPがいつもお世話になっているHN「Seiichi Manyama」さんから、「正多角形の
三角形分割」と題して、ご投稿いただきました。(平成28年7月23日付け)
多角形の三角形分割がカタラン数と関係があるのは、ご存じだと思う。
1 = 1 、2 = 2 、5 = 5 、14 = 6 + 3 + 3 + 2 、42 = 7 * 6 、132 = 8 * 14 + 4
* 5 、…
さて、正多角形の三角形分割を考え回転移動により重なるものは一つと数えることにする。
(ただし、折り返しはなし)
すると、 1 、1 、1 、4 、6 、19 、… となると思うのだが、どんな規則かよくわからな
い。一般項はどのような漸化式を満たすのだろうか?
例 凸6角形の場合、次の4通り。
at さんからのコメントです。(平成28年7月24日付け)
この数列ですかね。 → 「A001683」 そこでは、母関数が、
(6 + (1 - 4*x)^(3/2) + 6*x - 3*(1 - 4*x^2)^(1/2) - 4*(1 - 4*x^3)^(1/2))/12
となっていますね。これを利用すればいいのではないでしょうか?
3つの数列 {b[n]}、{c[n]}、{d[n]} を以下の漸化式で定義します。
b[2]=1/2 、b[n]=((4*n-10)/n)*b[n-1] (n≧3)
c[2]=1/2 、c[3]=0 、c[n]=((4*n-12)/n)*c[n-2] (n≧4)
d[2]=0 、d[3]=2/3 、d[4]=0 、d[n]=((4*n-18)/n)*d[n-3] (n≧5)
そうすると、求める数列 {a[n]} の一般項 a[n] は、 a[n]=b[n]+c[n]+d[n] (n≧2) となります。
この関係式から、{a[n]}の漸化式を導けるのではないかと思います。
Seiichi Manyama さんからのコメントです。(平成28年7月24日付け)
ありがとうございます。これです!もう規則がわかったので、今更ですが、
1 、1 、1 、4 、6 、19 、49 、150
であることが確認できました。
以下、工事中!