计算小练习 5

· · 个人记录

已知递推关系

f_{1,1}=1 f_{i,j}=2(f_{i-1,j-1}+f_{i-2,j-1})+\sum_{l=1}^{i-3}\sum_{k=1}^{j-1}\binom{j-1}{k}f_{l,k}f_{i-3-l,j-1-k}+\sum_{l=1}^{i-2}\sum_{k=1}^{j-1}\binom{j-1}{k}f_{l,k}f_{i-2-l,j-k-1}

要求出

\sum_{i=1}^nf_{n,i}

这个递推式乍一看很恐怖，但是稍微注意一下，就会发现这个和式实际上是很漂亮的卷积形式。我们设

F=\sum_{i \geq0 }\sum_{j \geq 0}\frac{x^iy^j}{j!}f_{i,j}

然后将递推式两侧同除以 (j-1)!，这样那个二重和式就只是提取 F^2 的一项系数了。我们现在有 PDE

y\frac{\partial F}{\partial y}=2y(x+x^2)F+(x^3+2x^2)yF^2+R

这个 R 就是一个余项，可以将其它项移至一侧后提取系数，验证其为 xy。
这方程虽然是个 PDE，但形式特殊，很容易求解：

F=\frac{\text e^{2xy+C(x)}-1}{2+x-x\text e^{2xy+C(x)}}

现在需要确定 C(x)，可以待定其系数然后求出 F 的系数，发现其常数项为零，一次项也为零... 于是猜想 C(x)=0，代入验证，完全正确！

现在就可以来考虑答案

\sum_{i=0}^ni![x^ny^i] \frac{\text e^{2xy}-1}{2-x(\text e^{2xy}-1)} =\frac 12\sum_{i=0}^n i![x^ny^i]\sum_{j \geq 0}\frac{1}{2^j}x^j(\text e^{2xy}-1)^{j+1} =\frac 12 \sum_{i=0}^n i!\sum_{j \geq 0}\frac{1}{2^j}[x^{n-j}y^i](\text e^{2xy}-1)^{j+1}

在这里停顿一下，观察 (\text e^{2xy}-1)^{j+1} 的形式，发现其展开仅由形如 x^ty^t 的项组成。也就是说在内层和式中，只有 j=n-i 的那一项非零。于是答案为

\frac{1}{2^{n+1}} \sum_{i=0}^n 4^ii![u^i](\text e^u-1)^{n-i+1}

设

a_i=[u^i](\text e^u-1)^{n-i+1}=[u^0](\text e^u-1)^{n+1}(u(\text e^u-1))^{-i}

这样就把问题化为了标准形式，有 经典做法 可以在 \Theta(n \log n) 的时间复杂度内计算，这里就直接给出结果：

a_i=[u^{2i}]\left( \frac{u^2}{h(u)}\right)^{n+1} \frac{h'(u)u}{h(u)}

其中 h(u)\left( \text e^{h(u)}-1\right)=u^2，可以牛顿迭代求解。

至于「能不能给力一点啊？」这个问题，我个人是没法继续往下做了，欢迎好哥哥好姐姐来继续优化。

后记：第一次写朴素代码尝试计算时竟然写错了，于是就得到了一个错误的结果发到了群里。然后自己推式子时发现代码的输出和自己的总对不上，看了半天才发现式子没错，竟然是暴力写挂了... 丢死人了呜呜