FC2ブログ

Welcome to my blog

[答1430] 三角形に分割

ヤドカリ

ヤドカリ

P8290011.jpg



[答1430] 三角形に分割


 図のように、凸六角形を3本の対角線で三角形4個に分割する方法は 14通りあります。
1430-三角形分割0
 では、凸十角形を7本の対角線で三角形8個に分割する方法は 何通り?


[解答1]

 3以上の自然数nに対して、

 凸n角形を (n-3)本の分割線で (n-2)個の三角形に分割する方法を Tn 通りとします。
1430-三角形分割1
 凸十角形の1辺に着目すると、それを1辺とする三角形は黄色の三角形の8種類あり、

 それ以外の水色の部分の分割方法を考えれば、

 T10=T9+T3・T8+T4・T7+T5・T6+T6・T5+T7・T4+T8・T3+T9

 同じように、凸n角形の1辺に着目すると、それを1辺とする三角形は (n-2)種類あり、

 それ以外の部分の分割方法を考えれば、

 Tn=Tn-1+T3・Tn-2+T4・Tn-3+……+Tn-2・T3+Tn-1 です。

 T3=1 ,T4=2 ですので、

 T5=T4+T3・T3+T4=2+1・1+2=5 、

 T6=T5+T3・T4+T4・T3+T5=5+1・2+2・1+5=14 、

 T7=T6+T3・T5+T4・T4+T5・T3+T6=14+1・5+2・2+5・1+14=42 、

 T8=T7+T3・T6+T4・T5+T5・T4+T6・T3+T7=132 、

 T9=T8+T3・T7+T4・T6+T5・T5+T6・T4+T7・T3+T8=429 、

 T10=T9+T3・T8+T4・T7+T5・T6+T6・T5+T7・T4+T8・T3+T9=1430

 になります。


[解答2]

 凸十角形の頂点を順に1から9の番号をつけます。

 下図の例のように、凸十角形の辺と分割の線を 端点の大きい方の番号で表し、昇順に並べると、

 12334556677789999 になり、
1430-三角形分割2
 最初の1を除き、2,3,4,5,6,7,8,9の最初を●,最初以外を○に書き換えると、

 ●●○●●○●○●○○●●○○○ になります。

 これは、●8個と○8個の並べ方で、どこで区切っても その前は ●の個数≧○の個数 です。

 ●8個と○8個の並べ方は 16!/(8!・8!)=12870 通りですが、

 このうち、●○○●●○●○●○●○●○○● のように途中で○が多くなる場合は、

 最初に多くなる ●○○ の次から ●と○を逆にすれば、●○○○○●○●○●○●○●●○ で、

 必ず ●7個と○9個の並べ方になり、16!/(7!・9!)=11440 通りです。

 従って、12870-11440=1430 通りになります。


 一般に、凸n角形の場合は、

 (2n-4)!/{(n-2)!・(n-2)!}-(2n-4)!/{(n-3)!・(n-1)!}

  =(2n-4)!・(n-1)/{(n-2)!・(n-1)!}-(2n-4)!・(n-2)/{(n-2)!・(n-1)!}

  =(2n-4)!/{(n-2)!・(n-1)!} 通りです。

.
スポンサーサイト



Comments 0

There are no comments yet.