■カタラン数と漸化式(その2)

 カタラン数の一般項は

  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!

が得られる.

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