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)
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/07 15:36:28
![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)](/uploads/image/z/13227789-21-9.jpg?t=Catalan%E6%95%B0+%E5%85%AC%E5%BC%8F%E6%8E%A8%E5%AF%BC%E8%AF%B7%E6%95%99%E5%A6%82%E4%BD%95%E6%8A%8A%E4%B8%8B%E5%88%97%E9%80%92%E5%BD%92%E5%85%AC%E5%BC%8Ff%28n%29%3Df%280%29%2Af%28n-1-0%29%2Bf%281%29%2A%28n-1-1%29%2Bf%282%29%2Af%28n-1-2%29%2B.%2Bf%28n-1-0%29%2Af%280%29%7B+f%280%29%3Df%281%29%3D1+%7D%E8%BD%AC%E5%8C%96%E4%B8%BAf%28n%29%3D+C%282n%2Cn%29%2F%28n%2B1%29)
xՒn@_.6&k\"1"ʢIJÐ4&@+5V(6BJYۧBwXIzoR^ݮ`oY#
`Ԥat~V?iBxjZy~*Vj,cES2U^|̉oYISN}4tC5p
w?A_Ipetv2cXvhp;fg89υI-[dlɔ,憮h&%Izmq?yNٹ#&ɥ\{.Y'4-fck&_^ NչAdH|3o]Á/([6)11.\^q{^RO[>L{h=yތ&Bx%^3KSX"t\s3~ɁUNģ6mrv\
ybnիFE<_
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)
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)
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)
可以利用母函数(发生函数)
令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)