载谭 Binomial Sum：多项式复合、插值与泰勒展开

Elegia · 2021-03-29 19:09:48 · 个人记录

对于微分有限（D-Finite） 的生成函数 F(x)，又设一生成函数 G(x)，有数列 a，我们已经对每个 0\leq k\leq n 知晓了

\sum_{j=0}^n a_j [x^j] G(x)^k

那么我们可以在 \Theta(n) 时间内计算

\sum_{j=0}^n a_j[x^j]F(G(x))

设 c=G(0)，考虑 F 在 c 处的泰勒展开式、带入 G(x)：

F(G(x)) = \sum_{k\ge 0} F^{(k)}(c) \frac{(G(x)-c)^k}{k!}

由于 x\mid G(x)-c，可知对于我们关心的 \sum_{j=0}^n a_j[x^j]F(G(x)) 之计算而言，只展开到 n 次项足够了。

设 F(x) 满足的微分方程为 \sum_{j=0}^m p_j(x)F^{(j)}(x)=0，可知

\sum_{j=0}^m p_j(x+c) F^{(j)}(x+c)=0

我们考虑对 F(x+c) 进行截取，设 \mathscr F(x + c) = F(x+ c) \bmod x^{n+1}，考察原微分方程的影响

\sum_{j=0}^m p_j(x+c) \mathscr F^{(j)} (x+c)

对于仅涉及 \leq n 的项来说，方程依旧成立。而对于仅涉及 > n 的项来说也成立，因此我们知道在这个区间内，有一个扰动因子 \sum_{j=0}^m p_j(x+c) \mathscr F^{(j)} (x+c) = \mathscr D(x)。因此有

\sum_{j=0}^m p_j(x) \mathscr F^{(j)}(x) = \mathscr D(x-c)

依此进行递推。由于此时 \mathscr F 只有不超过 n 次项，可以直接依据已有的信息得到答案。

目前能见到的问题多为 G(x)=\mathrm{e}^x 的情况。这是线性插值的基本推广。

根据这一直接推论，我们统一了以下问题的 \Theta(n) 结果。