[答1430] 三角形に分割

[答1430] 三角形に分割
図のように、凸六角形を3本の対角線で三角形4個に分割する方法は 14通りあります。

では、凸十角形を7本の対角線で三角形8個に分割する方法は 何通り?
[解答1]
3以上の自然数nに対して、
凸n角形を (n-3)本の分割線で (n-2)個の三角形に分割する方法を Tn 通りとします。

凸十角形の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 になり、

最初の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)!} 通りです。
.
スポンサーサイト