[答1430] 三角形に分割

[答1430] 三角形に分割


　図のように、凸六角形を３本の対角線で三角形４個に分割する方法は 14通りあります。

　では、凸十角形を７本の対角線で三角形８個に分割する方法は 何通り？


[解答1]

　３以上の自然数ｎに対して、

　凸ｎ角形を (n－3)本の分割線で (n－2)個の三角形に分割する方法を T_n 通りとします。

　凸十角形の１辺に着目すると、それを１辺とする三角形は黄色の三角形の８種類あり、

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

　T₁₀＝T₉＋T₃･T₈＋T₄･T₇＋T₅･T₆＋T₆･T₅＋T₇･T₄＋T₈･T₃＋T₉ 、

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

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

　T_n＝T_n-1＋T₃･T_n-2＋T₄･T_n-3＋……＋T_n-2･T₃＋T_n-1 です。

　T₃＝1 ，T₄＝2 ですので、

　T₅＝T₄＋T₃･T₃＋T₄＝2＋1･1＋2＝5 、

　T₆＝T₅＋T₃･T₄＋T₄･T₃＋T₅＝5＋1･2＋2･1＋5＝14 、

　T₇＝T₆＋T₃･T₅＋T₄･T₄＋T₅･T₃＋T₆＝14＋1･5＋2･2＋5･1＋14＝42 、

　T₈＝T₇＋T₃･T₆＋T₄･T₅＋T₅･T₄＋T₆･T₃＋T₇＝132 、

　T₉＝T₈＋T₃･T₇＋T₄･T₆＋T₅･T₅＋T₆･T₄＋T₇･T₃＋T₈＝429 、

　T₁₀＝T₉＋T₃･T₈＋T₄･T₇＋T₅･T₆＋T₆･T₅＋T₇･T₄＋T₈･T₃＋T₉＝1430

　になります。


[解答2]

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

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

　１２３３４５５６６７７７８９９９９ になり、

　最初の１を除き、２,３,４,５,６,７,８,９の最初を●，最初以外を○に書き換えると、

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

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

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

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

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

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

　従って、12870－11440＝1430 通りになります。


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

　(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)!} 通りです。

.