■ピックの公式と三角形分割(その3)

【1】オイラーの三角形分割問題

 ところで,オイラーは,凸多角形を対角線によって三角形分割する方法は何通りあるかという問題を問うた.三角形は1通り,四角形は2通りと数えられる.

 五角形の場合は5通り,6角形では14通り,七角形の場合は42通り,8角形では132通り,・・・.小さい方から並べると

  1,2,5,14,42,132,429,・・・

 オイラーは研究を深め,これらの数がカタラン数であることをつきとめた.円卓を囲む人たちが手を交差せずに握手できる方法の数は,カタラン数になっているのである.

===================================

【2】オイラー問題の解答

 凸多角形(n+2角形)に対角線を描いて,それをいくつかの凸多角形に分けるのではなく,対角線を互いに交わらないように引いて三角形分割する問題を考えよう.

[Q]凸n+2角形に互いに交わらないn−1本の対角線を引いて三角形分割する仕方の数c(n)は?

[A]この問題はオイラーが提起した幾何学問題である(オイラーの問題).4角形では2通り,5角形では5通りあることは数えられても,6角形ではそう簡単にはいかない(6角形に対しては14通りある).

 6角形の場合,たとえばある対角線を引いて3角形と5角形,4角形と4角形,5角形と3角形に分割することができるが,そのような分割の仕方を場合分けすることで,積和型の漸化式

  c(n+1)=c(0)c(n)+c(1)c(n−1)+・・・+c(n)c(0)

が得られる.ただし,c(0)=c(1)=1とする.

 これはカタラン数の漸化式であって,カタラン数c(n)はnの増加に応じて急激に増加する.

  c(0)=1,c(1)=1,c(2)=2,c(3)=5,

  c(4)=14,c(5)=42,c(6)=132,

  c(7)=429,c(8)=1430,c(9)=4862,・・・

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

 カタラン数の一般項は

  c(n)=2nCn/(n+1)=(2n)!/(n+1)!n!

であるが,この公式は母関数を用いると簡明に得ることができる.

 カタラン数の母関数を

  C(x)=c(0)+c(1)x+c(2)x^2+・・・+c(n)x^n+・・・

とおく.これを2乗すると

  C(x)^2=c(0)c(0)+(c(0)c(1)+c(1)c(0))x+ (c(0)c(2)+c(1)c(1)+c(2)c(0))x^2+・・・

 ここで,

  c(0)c(0)=c(1)

  c(0)c(1)+c(1)c(0)=c(2)

  c(0)c(2)+c(1)c(1)+c(2)c(0)=c(3)

であるから,

  C(x)^2=c(1)+c(2)x+ c(3)x^2+・・・

次数を揃えるために,両辺にxをかけて

  xC(x)^2=c(1)x+c(2)x^2+ c(3)x^3+・・・

  xC(x)^2=C(x)−c(0)=C(x)−1

 C(x)に関する2次方程式を解いて,母関数は

  C(x)={1−(1−4x)^1/2}/2x

ここでニュートンの二項展開により,一般項

  c(n)=2nCn/(n+1)=(2n)!/(n+1)!n!

が得られる.

 なお,凸n角形を対角線で三角形分割する仕方は何通りあるかという問題は,回転や反転で同型になるものを同じと数えると,

  1,1,1,3,4,12,27,82,228,733,2282,7528,・・・

となることを付記しておく.

===================================