[場合の数・カタラン数]多角形を対角線で区切り、3角形に分割することを考えます。このとき対角線どうしは互いに交わらないように引きます。すると、4角形は左図のように2通り、5角形は5通りの分け方があります。6角形の場合は何通りの分け方があるでしょうか?2.解答例1(PYQさん他)n角形を3角形に分割する分け方の数(分割数と呼びます)をE(n)とします。E(2)=1、E(3)=1、E(4)=4、E(5)=5までは分かっています。6角形の頂点をP1、P2、・・・P6とします。6角形を3角形で分割したとき、各辺は必ずどれかの3角形の1辺となるので、辺P1P2を1辺とする3角形に着目して分類します。P3のとき(5通り)P4のとき(2通り)P5のとき(2通り)P6のとき(5通り)すると、P1、P2以外の頂点はP3、P4、P5、P6のいずれかとなり、それぞれ三角形P1P2Pm(3≦m≦6)の左側の多角形の分割数と右側の多角形の分割数の積となる。従って、E(6)=E(2)・E(5)+E(3)・E(4)+E(4)・E(3)+E(5)・E(2)=1×5+1×2+2×1+5×1=14通りとなります。答:14通り以上3.解答例2:一般解(カタラン数)カタラン数については、「算数チャレンジャーに挑戦!」第6問でも取り上げています。縦n×横nの格子上を対角線より右側へは行かないように進むときの最短経路数をH(n)とすると、H(n)=2nCn/(n+1)となります。実は、E(n)=K(n−2)が成り立ちます。(補題)この事実を用いると、E(6)=K(4)=8C4/(4+1)=(8・7・6・5)/(4・3・2・1・5)=14通りと分かります。いう漸化式が導かれます。一般に、K(n)=K(0)・K(n-1)+K(1)・K(n-2)+・・・+K(n-2)・K(1)+K(n-1)・K(0)となります。E(n)=K(n-2)を帰納法で示すことにします。1)n=2のとき、E(2)=1、K(0)=1よりE(n)=K(n-2)が成り立つ2)n≦m-1(m≦3)で成り立つとします。n=mのとき、E(n)=E(2)・E(n-1)+E(3)・E(n-2)+・・・+E(n-2)・E(3)+E(n-1)・E(2)=K(0)・K(n-3)+K(1)・K(n-4)+・・・+K(n-4)・K(1)+K(n-2)・K(0)=K(n-2)以上から、帰納法によりE(n)=K(n-2)が示された。