从n=1起始用生成函数求解卡特兰递推式得到错误结果的原因咨询
从n=1起始用生成函数求解卡特兰递推式得到错误结果的原因咨询
我尝试用生成函数求解从n=1而非n=0开始索引的卡特兰递推式,但得到的结果总是有点偏差,真心希望有人能帮我分析下我的方法哪里出了问题。
我们已知卡特兰递推式:
$$P(n) = \begin{cases}
1& n=1\
\sum\limits_{k=1}^{n-1}P(k)P(n-k)& n\geq 2
\end{cases}$$
我想用生成函数方法来解这个递推式,选择从n=1开始定义生成函数——这看起来很合理,毕竟上面的递推式没有n=0的情况,那不如直接避开它。
我定义的生成函数是:
$$G(x) = \sum\limits_{n=1}^\infty P(n)x^n\
= x + \sum\limits_{n=2}^\infty P(n)x^n$$
之后我把n≥2时的递推关系代入这个式子,可最终得到的结果却和预期的卡特兰数对应不上,实在搞不懂问题出在哪。
备注:内容来源于stack exchange,提问作者Rohit Pandey
相关产品推荐
相关产品推荐

