■集合の分割(その17)
【4】カタラン数の母関数
カタラン数の母関数を
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)=x+{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!
が得られる.
===================================