■カタラン数の漸近挙動(その3)

 カタラン数の一般項は

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

  Cn=2n+1Cn/(2n+1)

あるいは

  Cn=2nCn−2nCn-1=1,2,5,14,42,・・・

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

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

【1】カタラン数の母関数

 カタラン数の母関数を

  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(0)=1を満足させなければならないので,複号は負号をとると,母関数は

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

 ここでニュートンの二項展開

  d^n/dx^n(1−4x)^1/2=−2^n(2n−3)!!(1−4x)^(1/2-n)

により,一般項

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

      =(2n−2)!/n!(n−1)!

      =(2n−1)!/n!(n−1)!/(2n−1)

が得られる.

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

【2】カタラン数

 カタラン数

  {Cn}={1,2,5,14,42,132,429,1430,4862,16796,・・・}

は,凸n角形を対角線で三角形分割する仕方は何通りあるかとか,n対のかみ合い括弧の種類数などいろいろな場面で登場する数なのですが,

  Cn=2nCn/(n+1)=(2n)!/n!(n+1)!,

  Cn=2n+1Cn/(2n+1),

あるいは

  Cn=2nCn−2nCn-1=1,2,5,14,42,・・・

と表されます.

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

【3】カタラン数の漸近挙動

  Cn=2nCn/(n+1)=(2n)!/(n!)^2(n+1)

に対して,スターリングの漸近公式

  k!=√2π・k^(k+1/2)・exp(−k)=√(2πk)・(k/e)^k

を適用すると,

  Cn〜2^2n/√(nπ)(n+1)〜4^nn^(-3/2)/√π

  Cn/4^nn^(-3/2)→1/√π

に収束することがわかる.

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