■増加整数列(その27)

 カタラン数は三角形分割数や木の個数の数え上げに用いられる.

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

n 0,1,2,3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13

Cn=1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900

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

【1】漸近値

 スターリングの近似式から 

  Cn〜4^n/n^3/2√π{1−9/8n+145/128n^2−1155/1024n^3+36936/32758n^4+O(n^-5)}

  Cn-1/Cn=(n+1)/(4n−2)

であるが,|k|≦n/2のとき

  Cn-k/Cn=1/4^k{1+3k/2n+O(k^2/n^2)}

  Cn-1+Cn-2+・・・+C1=Cn(Cn-1/Cn+Cn-2/Cn+・・・+C1/Cn)=Cn/3{1+2/n+O(1/n^2)}

1

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

【2】母関数

  C(z)=1+C1z+C2z^2+・・・={1−(1−4z)^1/2}/2z

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