其实还是可以提取对角线的

· · 算法·理论

前情提要

其实还是可以提取对角线的！

前几步基本相同：

F(x)=&\sum_{i,j \geq 0}\binom{i+j}{i}\sum_{n\geq 0}\binom{n-j}{i}\binom{n-i}{j}x^n \\ =&\sum_{i,j \geq 0}\binom{i+j}{i}x^{i+j}\sum_{n\geq 0}\binom{n+i}{i}\binom{n+j}{j}x^n \\ =&\sum_{n\geq 0}x^n\sum_{i,j \geq 0}\binom{i+j}{i}x^{i+j}\binom{n+i}{i}\binom{n+j}{j} \\ \end{aligned}

这里有

\binom{i+j}{i}=[t^i] (1+t)^{i+j}=[t^0] t^{-i}(1+t)^{i+j}

代入：

F(x)=&[t^0]\sum_{n\geq 0}x^n\sum_{i,j \geq 0} t^{-i}(1+t)^{i+j}x^{i+j}\binom{n+i}{i}\binom{n+j}{j} \\ =&[t^0]\sum_{n\geq 0}x^n(\sum_{i\geq 0} t^{-i}(1+t)^ix^i\binom{n+i}{i})(\sum_{j\geq 0}(1+t)^jx^j\binom{n+j}{j}) \\ \end{aligned}

后面两个求和是二项式求和的形式：

F(x)=&[t^0]\sum_{n\geq 0}x^n(1-(1+t)xt^{-1})^{-n-1}(1-(1+t)x)^{-n-1} \\ \end{aligned}

又是一个等比序列的形式：

F(x)=&[t^0]\frac{1}{(1-(1+t)xt^{-1})(1-(1+t)x)-x} \\ \end{aligned}

此时已经可以直接求留数了。有个小结论：对于二次结构可以发现其结果为 1/\sqrt{\Delta}，直接代入系数有：

F(x)=&[t^{-1}]\frac{1}{(t-x-xt)(1-x-xt)-xt} \\ =&\frac{1}{\sqrt{(2x^2-3x-1)^2-4(x^2-x)^2}} \\ =&\frac{1}{(1-x)\sqrt{1-4x}} \\ \end{aligned}

这里考虑到 x \rightarrow 0 故取 (1-x).