Catalan数公式推导请教如何把下列递归公式f(n)=f(0)*f(n-1-0)+f(1)*(n-1-1)+f(2)*f(n-1-2)+.+f(n-1-0)*f(0){f(0)=f(1)=1}转化为f(n)=C(2n,n)/(n+1)

Question

Catalan数 公式推导
请教如何把下列递归公式
f(n)=f(0)*f(n-1-0)+f(1)*(n-1-1)+f(2)*f(n-1-2)+.+f(n-1-0)*f(0)
{ f(0)=f(1)=1 }
转化为
f(n)= C(2n,n)/(n+1)

Answer 1

可以利用母函数（发生函数）
令F(x)=f(0)+f(1)x+f(2)x^2+...
那么递归公式左边就是F(x)的n次项系数.右边是F(x)^2的n-1次项系数.所以我们有(注意到零次项系数这个小问题,所以加1）
F(x)=xF(x)^2+1
解出F(x)=(1+sqrt(1-4x))/2x
sqrt(1-4x)可以用广义的二项式定理展开,并且写成关于x的形式幂级数（就是无限项的多项是）,他的n次项系数就是我们要求的,恰好是C(2n,n)/(n+1)