■完全グラフと同色の三角形(その18)

 カタラン数の一般項は

  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,・・・

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

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