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

Elegia · 2021-08-08 22:06:59 · 个人记录

如 G. Pólya 在他的教育著作《怎样解题》中所说：“尽可能形式地证明我们所直观看到的，以及尽可能直观地看出我们所形式证明过的，这是一种增进智力的练习。不幸，在教学中，并不总有时间来这样做。” 我想这对于撰写介绍性的个人博客来说也是颇有可借鉴学习之处的。

这体现于，把东西用简洁、严谨的方式讲述出来，以方便同行理解，和以外延、启发的方式让更多的人群理解，是需要不同的策略的。“对于说明某一特定点而言，欧几里得论证展开方式是优越的，但在阐述论证的主要思路方面，则不那么好。‘聪明的读者’很容易看到每步是正确的，但要看出其来龙去脉、目的以及整个论证的联系，则具有很大的困难。造成困难的原因是：欧几里得论证展开方式所遵循的顺序，相当经常地与创造它时的自然顺序刚好相反。”

我们可以认为，探索问题的过程的主要工具是归纳，而收尾时的工具是演绎。“许多数学结果是首先由归纳所发现，以后再加以证明的。已严格地提出来的数学是一门系统的演绎科学，而正在形成过程中的数学是一门实验性的归纳科学。” 所以，如果我们不满足于认识现有的结果，就要发掘出问题背后的脉络，认识到看起来“神机妙算”的证明，拆掉之前的脚手架长什么样。

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!，就变成了

咦……这样就可以了？后面是一个前缀和的形式，然后 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 求和 的一个线性做法，后来 zjc 的独立发现 也给了不同的视角。又有 NaCly_Fish 首先提示到 Bell 数可以线性求单项，以及与 djq 进行的讨论，还有其对珍珠的无 FFT 解法。他们启发了这最后一块拼图该如何拼上。