■いろいろの漸化式と母関数(その6)

 フィボナッチ数列の漸化式:an=an-1+an-2 (n≧2),a0=1,a1=1を考える.

 その母関数を

  f(x)=Σanx^n (n≧0)

とおくと,

  anx^n=xan-1x^n-1+x^2an-2x^n-2 (n≧2)

  Σanx^n=xΣan-1x^n-1+x^2Σan-2x^n-2

  f(x)−1−x=x{f(x)−1}+x^2f(x)

  f(x)=1+xf(x)+x^2f(x)

f(x)=1/(1−x−x^2)

f(x)=1/(1−αx)+1/(1−βx)

  α+β=1,αβ=−1

  α=(1+√5)/2,β=(1−√5)/2

  an=(α^n+1−β^n+1)/√5

  n→∞のとき,(an)^1/n→α

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

[おまけ]カタラン数

B(4)={{1,2,3,4}},{{1,2,3},{4}},・・・{{1},{2},{3},{4}}などの分割は「源氏香」方式の図式で表すことができる.

 その際,弧が交差しないようにとれる分割を非交差分割という.B(4)=15であるが,{{1,3},{2,4}}のみが交差分割で,その他は飛行差分勝である.

 非交差分割の個数は,カタラン数

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

で与えられる.n+4のとき,

  (8,4)/5=8・7・6・5/24・5=14

 また,カタラン数の母関数は

  C(z)=x+{C(z)}^2

  C(z)={1−√(1−4z)}/2z

で与えられる.

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