「实验性讲稿」载谭 Binomial Sums 详解

如 [G. Pólya](https://en.wikipedia.org/wiki/George_P%C3%B3lya) 在他的教育著作[《怎样解题》](https://en.wikipedia.org/wiki/How_to_Solve_It)中所说：_“尽可能形式地证明我们所直观看到的，以及尽可能直观地看出我们所形式证明过的，这是一种增进智力的练习。不幸，在教学中，并不总有时间来这样做。”_ 我想这对于撰写介绍性的个人博客来说也是颇有可借鉴学习之处的。 这体现于，把东西用**简洁、严谨**的方式讲述出来，以方便同行理解，和以**外延、启发**的方式让更多的人群理解，是需要不同的策略的。_“对于说明某一特定点而言，欧几里得论证展开方式是优越的，但在阐述论证的主要思路方面，则不那么好。‘聪明的读者’很容易看到每步是正确的，但要看出其来龙去脉、目的以及整个论证的联系，则具有很大的困难。造成困难的原因是：欧几里得论证展开方式所遵循的顺序，相当经常地与创造它时的自然顺序刚好相反。”_ 我们可以认为，探索问题的过程的主要工具是归纳，而收尾时的工具是演绎。_“许多数学结果是首先由归纳所发现，以后再加以证明的。已严格地提出来的数学是一门系统的演绎科学，而正在形成过程中的数学是一门实验性的归纳科学。”_ 所以，如果我们不满足于认识现有的结果，就要发掘出问题背后的脉络，认识到看起来“神机妙算”的证明，拆掉之前的**脚手架**长什么样。 > Carl Friedrich Gauss: “凡是有自尊心的建筑师，在瑰丽的大厦建成之后，决不会把**脚手架**留在那里。” 不再多说了，接下来我们将尝试以《怎样解题》这本书里介绍的教师引导学生的风格，来尝试~~把几个月前这碗冷饭炒得更香一点~~。 ---------- 艾：兰。 兰：我来了。 艾：你还记得我们今天要讨论什么对吧？ 兰：嗯，我们希望探讨一类求和问题：$\sum_x f(x)p(x)$，其中 $p(x)$ 是一个 $n$ 次多项式。我们希望对于一类性质够好的输入，可以在 $\Theta(n)$ 的时间内计算出这个求和。 艾：你能举几个已经解决的例子吗？ 兰：让我回顾一下……我想首先是幂和问题 $\sum_{x=0}^{k-1} x^n$，另一个就是这篇文章的标题来源，Min25 首先指出可以 $\Theta(n+\log k)$ 内计算的带着二项式的情况 $\sum_{x=0}^k \binom k xx^n$。 艾：你能大概叙述一下幂和问题的解决思路吗？ 兰：嗯……首先问题的第一步是把 $x^n$ 看做一个一般的多项式 $p(x)$，然后它的和函数 $q(x)=\sum_{y=0}^{x-1}p(y)$ 就是 $n+1$ 次多项式，我们就把问题分解成了两部分：一是求出 $q$ 的连续点值，二是线性 Lagrange 插值。 艾：嗯，线性 Lagrange 插值公式是对任意多项式都正确的，那么这个幂和问题为了能将 $p(x)$ 一般化，需要什么前提吗？ 兰：嗯……如果对于任意的 $p(x)$ 的话，我们需要在 $\Theta(n)$ 时间内得到其部分和的点值，其实也就是 $p(x)$ 需要在 $\Theta(n)$ 时间内算出。 艾：“算出”是一种看待问题的角度，如果从“给信息”的角度来说，什么信息的合适的呢？你都了解哪些常见的表示多项式的方法？ 兰：唔，最常见的形式我想是一下几种。单项式系数 $\sum a_ix^i$ 的数列 $\{a_i\}$，下降幂系数 $\sum b_i x^{\underline i}$ 的数列 $\{b_i\}$ 以及直接给出连续点值 $f(i)$。而我们这里用到的线性拉格朗日插值，和它最匹配的就是连续点值了。如果我们想通过下降幂得到连续点值，需要 $\Theta(n\log n)$ 做卷积；如果我们想通过单项式系数得到连续点值，现在我们似乎只知道 $O(n\log^2n)$ 的算法，按照目前的学术界进展来看，这类问题似乎比在线卷积问题还要困难…… 艾：看来你对这方面是相当清楚的。而且我们现在已经将问题泛化成有一个输入的向量了，这个问题现在其实可以看成一个“线性算法”，你能尝试通过转置原理，或者说，根据线性代数的观点来考虑这个差异吗？ 兰：哦，我懂了。对于前缀和来说，我们算的东西就等价于得到一组和输入用于点乘的向量。那么对于不同的基来说，我们就是算出基的每一个组成元素算出前缀和。对于连续点值，我们其实就是对每一个 $\prod_{j\neq i} (x-j)$ 算前缀和，对于下降幂基，我们就是对每一个 $\prod_{j\le i} (x-j)$ 算前缀和，对于多项式基，我们就是对每一个 $x^i$ 算前缀和。 艾：可以从复杂度的角度继续考虑这里的差异吗？ 兰：嗯，我们求连续点值，就相当于对输入向量乘以了一个用于进行基变换的矩阵 $\mathbf M$，但是输入是任意的，所以一般而言会比较困难，但我们可以考虑在运算顺序中让 $\mathbf M$ 先和右边相乘。原本的答案向量是有规律的，所以我们就有可能基于它优化复杂度了。对这个问题而言，下降幂的前缀和还是下降幂，所以我们对于下降幂来说也可以 $\Theta(n)$ 算出，而单项式幂的前缀和，我们…… 艾：用什么适合处理数列？生成函数！我们目前为止还没有使用过这个强大的工具呢！ 兰：我明白了，我们可以直接把这个问题挂在生成函数上，那么 $\sum_{x=0}^{k-1} x^i = \sum_{x=0}^{k-1} [z^i/i!] \exp(xz) = [z^i/i!] \frac{\exp(kz)-1}{\exp(z)-1}$。所以基于形式幂级数求逆，我们就有 $\Theta(n\log n)$ 的方法计算所有了。 艾：你可以对于单项式基目前的问题，都用 GF 风格来表述吗？ 兰：嗯，我这里做的重要替换就是 $x^i= [z^i/i!] \exp(xz)$，那么对于一般的和式 $\sum_x f(x)x^i$，其实就是 $[z^i/i!] \sum_x f(x) \exp(xz)$，如果数列 $f$ 的生成函数是 $F$ 的话，我们无非就是计算 $F(\exp z)$ 了。 艾：再回顾转置原理，你看出复杂度的分歧所在了吗？ 兰：哦，对于 $F(\exp z)$ 来说，如果 $F$ 是任意的，那么就只能考虑怎么基于右复合算 $F(\exp z)$ 了，但是如果 $F$ 有好的性质，我们其实是根据如何计算任何一个 $F(G)$ 的左复合来优化复杂度的。 艾：很好，现在让我们来看看前面提到的另一个问题吧：$\sum_{x=0}^k \binom k xx^n$，你能用 GF 来叙述这个问题吗？ 兰：太简单了！我想直接使用二项式定理就可以得到结果，我们的目的是计算 $[x^n/n!] (1 + \exp z)^k$。 艾：好，本来在 Min25 的做法之前，我们有一个 $\Theta(n\log n)$ 的做法，它和你顺着这条思路直接想到的一样吗？ 兰：我根据这个结果，直接得到的是一个 $\Theta(n\log n)$ 计算形式幂级数的幂函数的方法，但另一个做法似乎是基于 Stirling 数？ 艾：确实另一个做法的起手式是 Stirling 数，事实上 Min25 第一步也这么做了。你能写出它的原理吗？ 兰：嗯，Stirling 数的用途是试图将幂转化为下降幂，公式是 $x^n = \sum_j {n\brace j} j! \binom{x}{j}$。 艾：为了比较我们两个做法的差异，最好先把做法尝试用在一个体系里表述，你觉得该怎么做？ 兰：这样的话，我应该把这个恒等式的两边都用 GF 套起来，那么 $x^n=[z^n/n!]\exp {xz}$，而 ${n\brace j}j! = [z^n/n!](\exp z-1)^j$，合起来看的话，等式的两边无非是说 $\exp xz = [(\exp z - 1) + 1]^x$？ 艾：很好，这个看起来平凡的恒等式，其实是我们接下来解决问题的枢纽。我们先来看一个简单些的问题吧。你还记得 Bell 数的 EGF $\exp(\exp x - 1)$ 吧，你能否在 $\Theta(n)$ 内计算其第 $n$ 项？ 兰：让我试试……如果我直接将外层的 $\exp$ 展开的话，就是一个 $\sum_{i\ge 0} \frac 1{i!}(\exp x-1)^i$ 的形式，但如果我们要提取 $[x^n/n!]$，当 $i>n$ 的时候就没有贡献了，所以我们可以试试展开 $\sum_{i=0}^n \frac 1{i!}(\exp x-1)^i$。那么二项式定理会消去外部的 $1/i!$，就变成了 $$ \begin{aligned} &\quad \sum_{i+j\le n} \exp ix \cdot (-1)^j \cdot \frac{1}{i!j!}\\ &= \sum_{i\le n} \frac 1{i!}\exp ix \sum_{j\le n-i} \frac{(-1)^j}{j!}\\ [x^n/n!] \exp(\exp x -1) &= \sum_{i\le n} \frac {1}{i!} i^n\sum_{j\le n-i} \frac{(-1)^j}{j!} \end{aligned} $$ 咦……这样就可以了？后面是一个前缀和的形式，然后 $i^n$ 和我们算幂和的时候一样，可以线性筛在 $\Theta(n)$ 时间内计算！ 艾：很好，你能描述这个推导的核心原理是什么吗？ 兰：我认为是利用了 $\exp x-1$ 没有常数项这个性质，因此在我们提取一个指定项系数的时候，它是幂零的。无限和就变成看起来好一点的有限和了。但是对于后面的推导……我还不确定怎么推广…… 艾：不必着急，没人指望从孤例中归纳出一般的结果。我们再来看另一个问题，你能先尝试将 $\sum_{i} 2^i i!\cdot {n\brace i}$ 写成某个 GF 的系数吗？ 兰：我想大概就是 $[x^n/n!]\sum_i 2^i \cdot (\exp x-1)^i = [x^n/n!] \dfrac{1}{1-2(\exp x-1)}$。 艾：嗯，你能仿照之前的策略，再来解决这个问题吗？ 兰：我想，根据提取一个特定系数时候的幂零性质，可以将 GF 截断到 $\sum_{i {\color{red}\le n}} 2^i(\exp x-1)^i$，这样我们就将其表示成了一个关于 $u=\exp x$ 的多项式了，可以写作 $\dfrac{1-2^{n+1}(u-1)^{n+1}}{1-2(u-1)} = \dfrac{1-2^{n+1}(u-1)^{n+1}}{3-2u}$。我们就可以在 $\Theta(n)$ 递推出每个 $\exp ix$ 的系数了。 艾：很好，先前我们提到了，问题解决的关键在于我们考虑的 $F(\exp x)$ 其 $F$ 性状如何。那么对于刚刚这个问题，你应该清楚 $F$ 的特点吧。 兰：嗯，$F$ 是一个有理分式。 艾：对于有理分式的运算有很多好处，你能回顾一下你的做法，看看有哪里用到了有理分式的性质吗？ 兰：我想，我们是先写出的 $F(u-1)$ 的这个 $F$ 的形式，然后尝试考虑把 $F$ 进行截断，变成 $F \bmod x^{n+1}$。对于 $F=\dfrac 1{1-2x}$ 来说，它的截断是比较简单的，仍然可以写成一个有理分式的形式：$\dfrac {1-(2x)^{n+1}}{1-2x}$。接下来我们还是得把 $u=x+1$ 带入，但是带入过程就直接体现成了对分子分母的一个简单变换。所以在整个过程中，有理分式运算的封闭性就得到了体现，我们就可以在最后仍然依据有理分式来进行递推。 艾：很好，但刚刚这个例子作为有理分式还是太平凡了，我们来尝试将 $2^i$ 替换成 Fibonacci 数 $[x^i] \dfrac 1{1-x-x^2}$。你能将原先的做法修改来解决这个问题吗？ 兰：我想想……关键就在于我们如何计算 $\dfrac 1{1-x-x^2} \bmod x^{n+1}$，对么？ 艾：嗯，继续尝试下去！ 兰：我想想……对于 $\dfrac 1{1-2x}$，我们其实考虑的是一个函数 $F_0(x) \cdot (1-2x) = 1-(2x)^{n+1}$，那么对于现在的问题，我应该还是可以设 $F_0(x) = \dfrac 1{1-x-x^2} \bmod x^{n+1}$，然后考虑 $F_0(x)\cdot (1-x-x^2)$。我明白了！我们这里可以回归系数提取时候的情况，对于 $0\sim n$ 次项的系数，情况和 $F(x) \cdot (1-x-x^2)$ 是一样的，而 $1-x-x^2$ 总共关联了 $a_i,a_{i-1},a_{i-2}$，所以当 $i-2>n$ 的时候，一定是 $0$，关键就在于 $i=n+1,n+2$ 这两项的情况。那么应该就有 $F_0(x)\cdot(1-x-x^2) = 1 + ux^{n+1} + vx^{n+2}$，而 $u,v$ 也并不难具体地算出来，它们就是 $u=-F_n-F_{n-1},v=-F_n$。因此，我们就得到了 $F_0 = \dfrac{1-(F_{n-1}+F_n)x^{n+1} - F_n x^{n+2}}{1-x-x^2}$。然后我们就又可以带入 $u=x+1$ 继续了。 艾：很好，我想这就是所谓的“扰动法”在 GF 上的体现了。你已经发现，我们其实对有理分式的情况得到了一个比较完满的解答。那么，你觉得有理分式可以如何合理地进一步扩展呢？ 兰：有理分式对应的数列是满足线性递推的，那么我们的下一个目标就是……对整式递推的数列解决？ 艾：确实。而且你有没有发现，整式递推已经包含了我们之前提到的两个问题？ 兰：嗯，$\exp x$ 是 $F'=F$ 的一个解，而 $(1+x)^k$ 是 $F'\cdot(1+x)=kF$ 的一个解。 艾：好，那么接下来我们就开始考虑如何解决 $[x^n/n!](1+\exp x)^k$ 吧。你能继续尝试把刚刚的步骤运用到这个问题上吗？ 兰：我看看……首先我们可以拆成 $[2 + (\exp x - 1)]^k$，那么问题的第一步就是考虑如何计算 $(2+x)^k \bmod x^{n+1}$ 了……接下来该怎么办呢？ 艾：还记得我们刚刚提到的吗？问题的关键在于整式递推，你能尝试利用这个性质吗？想想我们对线性递推是怎么做的！ 兰：我来看看，首先 $F(x)=(2+x)^k$ 是满足 $F'\cdot(2+x)=kF$ 的，这导出了它的系数有一个递推式 $2(i+1)f_{i+1}+if_i=kf_i$，如果全都整理到一边也就是 $2(i+1)f_{i+1} + (i-k)f_i=0$。我们如果还是考虑 $F_0 = F \bmod x^{n+1}$，可以尝试将这个递推式作用于 $F_0$ 的系数。它应该只会在 $i=n$ 的时候出问题！也就是说，当 $i=n$ 的时候，$g_i=[x^i]F_0 = f_i$，但 $g_{i+1}=0$，这样对 $F_0$ 来说，就会多出一个修正项，$2(i+1)g_{i+1}+(i-k)g_i=[n=i]\cdot (n-k)f_n$。反映在微分方程上，就是 $F_0'\cdot(2+x)-kF_0 = (n-k)f_nx^{n} = (n-k) 2^{k-n} \binom k n x^n$！ 艾：很好！继续下去。 兰：接下来我们就可以通过换元 $G(x)=F_0(x-1)$ 来解决了。把微分方程两边都带入 $x-1$，就会得到 $G'\cdot(1+x)-kG= (k-n) 2^{k-n} \binom k n (x-1)^n$，再提取系数 $h_i=[x^i]G$，那么就有 $(i+1)h_{i+1} + (i-k)h_i = [x^i] (k-n) 2^{k-n} \binom k n (x-1)^n$，就可以依此递推了。 艾：嗯。现在，你能将前面的步骤，用一般的语言来概括吗？ 兰：我想已经不难了。对于整式递推数列，我们知道递推式 $\sum_{i=0}^m P_i(n)f_{n-i} = 0$ 对应于一个其 GF 满足的微分方程 $\sum_{i=0}^k Q_i(x) F^{(i)}(x)=0$。那么我们为了提取 $[x^N/N!] F(\exp x)$ 的第一步，就是将其展开成 $F((\exp x-1)+1)$ 的形式，进行截断；也就是计算 $F(x+1) \bmod x^{N+1}$。我们首先可以对微分方程整体带入 $x+1$ 得到 $\sum_{i=0}^k Q_i(x+1) F^{(i)}(x+1)=0$，这也将对应于一组递推式 $\sum_{i=0}^{l} R_i(n)[x^{n-i}]F(x+1) = 0$。进行截断的时候，$\sum_{i=0}^{l} R_i(n)[x^{n-i}]F(x+1)$ 会在 $N+1,\cdots, N+l$ 的地方产生扰动。因此，$\sum_{i=0}^k Q_i(x+1) \partial^i$ 对于 $F(x+1)\bmod x^{N+1}$ 的作用，会多出一个扰动多项式 $D(x)$。我们最后的目的是将截断的部分再次带回 $x-1$，也就得到了 $\sum_{i=0}^k Q_i(x) G^{(i)}(x)=D(x-1)$。当整式递推式的相关部分规模皆为常数的时候，我们可以认为是在 $\Theta(n)$ 的时间内算出每个数列的初值，算出扰动项，以及递推出整个数列。 艾：很好。你还能将我们之前提到的其他问题容纳到整式递推吗？ 兰：我想对于幂和也属此列，因为 $\frac{x^k-1}{x-1}$ 也可以表示成整式递推。 艾：再找找看，有没有更基本的问题？ 兰：是说……线性 Lagrange 插值吗？哦！因为 $x^k$ 就是 $F'\cdot x - kF=0$ 的解！ 艾：嗯，但这里其实就不是提取 $[x^n/n!]$ 了，你能修改其表述吗？ 兰：嗯……我们的工作实际上是将 $F(\exp x)$ 变换成一个 $n$ 次多项式 $G$ 使得 $G(\exp x)$ 和 $F(\exp x)$ 的前 $n$ 项一致，那么对于插值来说，其实是对 $0\le i\le n$ 给定了一组系数，使得 $a_i = b \cdot \exp ix$，这里的 $\cdot$ 表示点乘，其中 $b$ 是一个 $0\sim n$ 次项有值的多项式。 艾：好，从插值角度理解，你还能以其他方式重写问题吗？ 兰：嗯，我们知道 $n$ 次多项式的差分有限性，也就是 $\Delta^{n+1} f = 0$，对于多项式插值而言，如果我们想算出 $F(x)$ 的第 $i$ 次项和 $f(i)$ 对应相乘求和，就可以通过 $F \bmod (x-1)^{n+1}$ 转化为 $f(0),\dots,f(n)$ 了。这也和之前把截断通过多项式取模来描述是一致的。 艾：所以你看到，我们的方法最后在多大程度上解决了 $\sum_x f(x)p(x)$ 这个求和问题？ 兰：$f$ 是规模为常数的整式递推式，同时我们知晓多项式 $p(x)$ 的信息足够的连续点值。在其作为一般的点值 $\rightarrow$ 答案的线性变换的角度下，我们已经达到下界了，因为输入就是 $\Theta(n)$ 量级的。 艾：很好，最后我们再做一点点延伸吧。回归复合 $F(\exp x)$ 的角度，你觉得 $\exp x$ 能否替换成别的什么东西？ 兰：嗯……似乎没有什么额外的限制？对于任意一个生成函数 $G$，我们只需要把常数项分离展开 $(G-c)+c$，就可以完成类似的事情。这个手段……我似乎在通过 Lagrange 反演解决一般的 $k\le n$ 求算 $[x^n]G^k$ 中也见到过。 艾：嗯，如果我们通过矩阵来思考，也可以用特征多项式来解释……个中道理大概是讲不尽的。 兰：很有意思的一次讨论，我回去也继续想想。 艾：我想待你继续学习和思考，总能对问题有新的理解；新的理解又推动出新的方法，在这一轮轮绕圈的过程中，我们都会进步。我们刚刚讨论中的每一步，大概都不算是非常令人惊叹的转化罢，但当我们完整走过一路，蓦然回首——却已经解决了一大类问题。这也是我颇为欣赏的一类工作：解决问题的方法是朴实的，甚至**在问题被以正确的方式提出**的时候，叙述本身就足以使人一步步走向结果。而难得之处在于，这种工作的运作方式就像疫苗如何作用于免疫系统一样，提出之后，**原先看起来复杂的问题，就被抓住了繁杂表象下的实质**。当然，我们今天讨论的这个问题也归功于我的朋友们。一切的伊始来源于我高一时误打误撞得到了 [TJOI / HEOI2016 求和](https://loj.ac/p/2058) 的一个线性做法，后来 [zjc 的独立发现](https://www.cnblogs.com/mathematician/p/12693500.html) 也给了不同的视角。又有 NaCly_Fish 首先[提示](https://www.luogu.com.cn/problem/P5748)到 Bell 数可以线性求单项，以及与 djq 进行的讨论，还有[其对珍珠的无 FFT 解法](https://codeforces.com/blog/entry/76447)。他们启发了这最后一块拼图该如何拼上。