计算小练习 16：我说把有限和改成无限的你二龙吗

· · 算法·理论

题目来源未知。

f_k= [x^k] \sum_{i=0}^\infty (i+n-k)! (-1)^{k-i} \left( \frac{x+x^2}{1-x}\right)^i

给定 n，尝试对于 k=1,\cdots,n 计算 f_k。

虽然一般生成函数的推导不会在中途拆开系数，但这里不是一般情况。

\begin{aligned}f_k &= \sum_{i=1}^k (i+n-k)! (-1)^{k-i} [x^{k-i}] \left( 1+\frac{2x}{1-x}\right)^i \\ &= \sum_{i=1}^k (i+n-k)! (-1)^{k-i} \sum_{j=0}^{k-i} 2^j\binom ij\binom{k-i-1}{j-1} \\ &= \sum_{i=0}^{k-1}(n-i)!(-1)^{i}\sum_{j=0}^{i}2^j \binom{k-i}{j} \binom{i-1}{j-1}\end{aligned}

好了，我们现在设 F(t) 为 \{ f_k\}_{k \geq 1} 的生成函数，则：

\begin{aligned} F(t) &\equiv \sum_{k = 0}^n t^k \sum_{i=0}^{k-1}(n-i)!(-1)^{i}\sum_{j=0}^{k-i}2^j \binom{k-i}{j} \binom{i-1}{j-1} \pmod{t^{n+1}} \\ &\equiv\sum_{i = 0}^n(n-i)! (-1)^{i} \sum_{j=0}^i 2^j \binom{i-1}{j-1} \sum_{k=0}^{\red{\infty}} \binom{k-i}{j}t^k \pmod{t^{n+1}} \\ &\equiv\sum_{i=0}^n (n-i)!(-1)^{i} \sum_{j=0}^i 2^j \binom{i-1}{j-1} t^i \frac{t^j}{(1-t)^{j+1}} \pmod{t^{n+1}} \\ &\equiv \frac{1}{1-t}\left(n!+\sum_{i=1}^n (n-i)! (-t)^i \frac{2t}{1-t}\left( 1+\frac{2t}{1-t}\right)^{i-1}\right) \pmod{t^{n+1}}\end{aligned}

显然最终得到了一个微分有限的幂级数，可以机械化求出其 ODE。