■多角形の三角形分割(その2)

カタラン数列{Cn}

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

の補足をしたいと思います.

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

【1】カタラン数

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

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

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

あるいは

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

と表されます.

 カタラン数から一般項が何かを予想するのは難しいのですが,ここでは

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

がわかっているものとして,母関数

  F(t)=ΣCnt^n   

を求めてみます.

 この級数は,第0項:C0=1から始まるので,そのまま項比をとると

  an+1xn+1/anxn=(n+1/2)(n+1)/(n+2)*4x/(n+1)

したがって,

  F(x)=2F1(1/2,1,2,4x)=2/{1+(1-4x)^(1/2)}

      ={1-(1-4x)^(1/2)}/2x

  (1-4x)^(1/2)=Σ(-4)^k1/2Ck・x^k

より

  Cn=-1/2(-4)^(n+1)1/2C(n+1)

これをさらに式変形すれば,

  Cn=2nCn/(n+1)

になる.この結果,二項展開を丹念に使えば

  {1-(1-4x)^(1/2)}/2x=Σ2nCnx^n/(n+1)

が得られるはず・・・.

 この方法は試してはいないのですが,かなり面倒そうです.実はカタラン数に対しては,漸化式

  Cn=ΣCkCn-k-1=C0Cn-1+C1Cn-2+・・・+Cn-1C0

が成り立つので,母関数は

  F(t)=ΣCnt^n=ΣCkt^kΣCn-k-1t^n-k+1

      =F(t)・tF(t)+1

すなわち,

  tF(t)^2−F(t)−1=0

なる2次方程式を満たすことが知られています.

 C0=1を満足させなければならないので,複号は負号をとると,

  F(t)={1-(1-4x)^(1/2)}/2x

がでてきます.

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

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

となることを付記しておきたいと思います.

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