差分序列与 Stirling 数

刚看完《组合数学》的这一节，写一点笔记。

差分序列

定义

设一个序列：

$$ h(0),\ h(1),\ h(2),\ h(3),\ h(4),\ ... $$

的一阶差分序列为：

$$ \Delta h(0),\ \Delta h(1),\ \Delta h(2),\ \Delta h(3),\ ... $$

其中：

$$ \Delta h(n) = h(n + 1) - h(n) $$

同样，将差分出来的序列再次进行差分，可以得到二阶差分序列。因此，我们定义零阶差分序列就是原序列，$p$ 阶差分序列为：

$$ \Delta^{(p)} h(n) = \Delta^{(p - 1)} h(n + 1) - \Delta^{(p - 1)} h(n) \;\;\;\; (p \gt 0) $$

差分序列有一种求导的意味。

多项式的差分序列

多项式 $h(n) = 2n^3 + 2n^2 - 4n + 233$ 的差分序列如下：

$$ 233,\ 233,\ 249,\ 293,\ 377,\ 513,\ ... \\ 0,\ 16,\ 44,\ 84,\ 136,\ ... \\ 16,\ 28,\ 40,\ 96,\ ... \\ 12,\ 12,\ 12,\ ... \\ 0,\ 0,\ ... \\ ... $$

我们发现 $h(n)$ 是个 $3$ 次多项式，而它的序列经过 $4$ 次差分就变成了全是 $0$ 的序列。

可以证明，一个 $p$ 次多项式的序列最多经过 $p + 1$ 次差分就会变为全 $0$ 序列。

首先考虑 $0$ 次多项式，它的序列值是一个常数，所以至多经过一次差分就可以变为 $0$。

现在进行归纳假设：假设对于 $p$ 次多项式的序列最多经过 $p + 1$ 次差分就会得到全 $0$ 序列，那么现在证明对于 $p + 1$ 次多项式最多差分 $p + 2$ 次就可以得到全 $0$ 序列。

观察最高次数的项，在每一次差分中的变化：

$$ \begin{aligned} \Delta^{(c)} h(n) & = \Delta^{(c-1)} h(n + 1) - \Delta^{(c-1)}h(n) \\ & = (n + 1)^{p} + \cdots - n^p - \cdots \\ & = \left(\sum_{k = 0}^p {p \choose k} n^k\right) + \cdots - n^p - \cdots \end{aligned} $$

由于 ${p \choose p} = 1$，所以最高次数的项在一次差分中被减去了，所以差分后的序列是一个至多 $p$ 次的多项式的序列。因此，根据归纳假设，$p + 1$ 次的多项式最多进行 $p + 2$ 次差分就可以对到全 $0$ 序列。

差分的线性性

如果：

$$ h(n) = af(n) + bg(n) $$

那么：

$$ \begin{aligned} \Delta h(n) & = \Delta (af(n) + bg(n)) \\ & = a(f(n + 1) - f(n)) + b(g(n + 1) - g(n)) \\ & = a\Delta f(n) + b\Delta g(n) \end{aligned} $$

由此我们证明了差分是一个线性变换。这称为差分的线性性。

特殊差分表

在差分表中：

$$ 233,\ 233,\ 249,\ 293,\ 377,\ 513,\ ... \\ 0,\ 16,\ 44,\ 84,\ 136,\ ... \\ 16,\ 28,\ 40,\ 96,\ ... \\ 12,\ 12,\ 12,\ ... \\ 0,\ 0,\ ... \\ ... $$

称第一横行为第 $0$ 行，表示原数列，如上面的 $233,\ 233,\ 249,\ 293,\ 377,\ 513,\ ...$。而左边的第一斜列为第 $0$ 条对角线，如上面的 $233,\ 0,\ 16,\ 12,\ 0,\ ...$。显然知道了这两个中的任意一个就可以确定整个差分表。

考虑一下由下面的对角线构成的差分表会是怎样的数列构成的：

$$ 0,\ 0,\ 0,\ 0,\ 1,\ 0,\ 0... $$

首先，这个差分表后面全部变成了 $0$，所以这肯定是一个 $4$ 次多项式的差分表。同时我们可以确定这个多项式有 $4$ 个零点，所以我们可以写出：

$$ f(n) = cn(n-1)(n-2)(n-3) $$

其中 $c$ 还是待确定的。

同时，我们注意到 $f(4) = 1$，所以：

$$ c \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 1 \implies c = \frac1{4!} $$

换言之：

$$ f(n) = {n! \over 4!(n - 4)!} = {n \choose 4} $$

是不是感觉很神奇？这一结论可以推广到任意位置的 $1$ 的差分表。同时，利用差分表的线性性，我们可以得到更加神奇的东西：

如果 $\Delta f(n)$ 的第 $0$ 条对角线为 $c_0,\ c_1,\ c_2,\ c_3,\ ...,\ c_p,\ 0,\ 0,\ ...$，那么¹：
$$ f(n) = \sum_{k=0}^p c_k{n \choose k}$$

此时你也许会想问这东西有什么用？由于它是对于一个多项式的差分分析得到的结论，因此，我们对于一个多项式，如果知道了第 $0$ 条对角线，那么我们可以直接计算这个多项式。

并且，根据 Pascal 公式，我们可以知道：

$$ \begin{aligned} \sum_{k=0}^n {k \choose p} &= {0 \choose p} + {1 \choose p} + \cdots {n \choose p} \\ &= {0 \choose p + 1} + {0 \choose p} + {1 \choose p} + \cdots {n \choose p} \\ &= {1 \choose p + 1} + {1 \choose p} + \cdots {n \choose p} \\ &\cdots \\ &= {n + 1 \choose p + 1} \end{aligned} $$

所以：

$$ \sum_{j = 0}^n f(j) = \sum_{k = 0}^p c_k \sum_{j = 0}^n {j \choose k} = \sum_{k = 0}^p c_k {n + 1 \choose k + 1} $$

所以，当我们拥有了这个结论之后，我们就可以以同样的代价来计算它的前缀和。

现在来考虑一个具体一点并且不是很复杂的问题，但是可能当场并不能解决它：

给你 $T$ 次询问，每次给出 $n$ 和 $p$，要求你计算：
$$ \sum_{a = 1}^n a^p \pmod{10^9 + 7} $$

$1 \leqslant T \leqslant 5000$，$1 \leqslant p \leqslant 5000$，$1 \leqslant n \leqslant 10^{18}$。

如果采用直接计算 $c_0,\ c_1,\ c_2,\ ...$ 的话，总的复杂度为 $\Theta(q^3 + Tq)$。这里出现的问题就是系数的预处理代价太高，因此我们需要寻找一种更快速的计算方法。

对此，我们设 $f_p(n) = n^p$，同时设它的系数为：

$$ c(p,\ 0),\ c(p,\ 1),\ c(p,\ 2),\ ...,\ c(p,\ p) $$

那么答案就是：

$$ \sum_{k = 0}^p c(p,\ k){n + 1 \choose k + 1} $$

第二类 Stirling 数

定义

有第二类 Stirling 数就有第一类 Stirling 数，但是由于第二类 Stirling 数可以帮助我们解决之前的问题，所以先介绍它。

第二类 Stirling 数的用途是使用下降幂来表示数的幂。下降幂是这样的一种东西：

$$ x^{\underline{n}} = {x! \over (x - n)!} = x(x - 1)(x - 2) \cdots (x - n + 1) $$

回到前面的问题，可以发现：

$$ \begin{aligned} n^p & = \sum_{k = 0}^p c(p,\ k){n \choose k} \\ & = \sum_{k = 0}^p \frac{c(p,\ k)}{k!} n^{\underline{k}} \end{aligned} $$

所以设：

$$ S(p,\ k) = {c(p,\ k) \over k!} $$

为第二类 Stirling 数。并且满足：

$$ n^p = \sum_{k = 0}^p S(p,\ k)n^{\underline{k}} $$

同时注意一下它的边界值：

$$ \begin{matrix} S(n,\ n) = 1 & \forall n \in \mathbb N \\ S(n,\ 0) = 0 & \forall n \in \mathbb N^+ \end{matrix} $$

不妨来考虑一下：

$$ \begin{aligned} n^{p-1} & = \sum_{k = 0}^{p-1} S(p-1,\ k)n^{\underline{k}} \\ n^p = n \cdot n^{p-1} & = n\sum_{k = 0}^{p-1} S(p-1,\ k)n^{\underline{k}} \\ & = \sum_{k = 0}^{p-1} S(p-1,\ k) \cdot n \cdot n^{\underline{k}} \\ & = \sum_{k = 0}^{p-1} S(p-1,\ k) \cdot (n - k + k) \cdot n^{\underline{k}} \\ & = \sum_{k = 0}^{p-1} S(p-1,\ k) n^{\underline{k + 1}} + \sum_{k = 0}^{p-1} kS(p-1,\ k) n^{\underline{k}} \\ & = \sum_{k = 1}^{p} S(p - 1,\ k - 1) n^{\underline{k}} + \sum_{k = 0}^{p-1} kS(p-1,\ k) n^{\underline{k}} \end{aligned} $$

通过比较同一项的系数，我们可以得知下面的递推式：

$$ S(p,\ k) = kS(p - 1,\ k) + S(p - 1,\ k - 1) $$

解决之前的问题

在之前的问题中，我们知道：

$$ \begin{aligned} \sum_{a = 1}^n a^p & = \sum_{k = 0}^p c(p,\ k){n + 1 \choose k + 1} \\ & = \sum_{k = 0}^p {S(p,\ k) \over k + 1}(n + 1)^{\underline{k + 1}} \end{aligned} $$

对于后面的式子，我们发现可以通过递推算出 $(n + 1)^{\underline{1}}$ 至 $(n + 1)^{\underline{p + 1}}$ 的值，同时，我们有了之前的递推式，我们可以在 $\Theta(p^2)$ 的时间内预处理出第二类 Stirling 数。所以这个问题我们可以以 $\Theta(p^2 + Tp)$ 的时间复杂度解决这个问题。

其实，根据第二类 Stirling 数的递推公式，我们也可以类似的推出 $c(p,\ k)$ 的递推公式：

$$ c(p,\ k) = k(c(p - 1,\ k - 1) + c(p - 1,\ k)) $$

读者可以自己试一试。

但是这还不是这个问题的最优解法。使用伯努利数和快速傅里叶变换，我们可以得到更好的复杂度。这里就没有介绍了。

另外，使用拉格朗日插值法也可以快速求解这个问题，具体的可以参见这篇博客。

组合意义

现在来考虑一下这个简单问题：

求 $p$ 个人，放入 $k$ 个相同的房子 (房子不可以为空) 的方案数。

不难我们可以想出一个递推²：设 $f(p,\ k)$ 为 $p$ 个人放入 $k$ 个相同的房子的方案数，那么它满足：

$$ f(p,\ k) = kf(p - 1,\ k) + f(p - 1,\ k - 1) $$

对于其正确性，考虑两点：

1. 如果第 $p$ 个人单独进入一个房间，那么方案数为 $f(p - 1,\ k - 1)$。
2. 如果第 $p$ 个人进入之前的房间，那么它可以挑选之前的 $k$ 个房间的任意一间，即方案数为 $kf(p - 1,\ k)$。

同时我们注意到：

$$ f(n,\ n) = 1 $$

并且：

$$ f(n,\ 0) = 0 \;\;\;\; \forall n \in \mathbb N^+ $$

也就是 $f$ 和第二类 Stirling 数满足一样的初始条件和递推公式，那么意味着 $f(p,\ k)$ 和 $S(p,\ k)$ 是一样的。所以这个问题的答案就是 $S(p,\ k)$。这也正是第二类 Stirling 数的组合意义。

对于这个问题，我们可以从容斥原理的角度来获得另外一个不同的公式。设 $A_1,\ A_2,\ A_3,\ ...,\ A_k$ 为第 $1$ 到第 $k$ 个房间为空的方案集合，那么我们的答案就是：

$$ S(p,\ k) = \frac1{k!}\left|\overline{A}_1 \cup \overline{A}_2 \cup \cdots \cup \overline{A}_k\right| $$

注意在之前的推导里面我们区分了这 $k$ 个房间，而第二类 Stirling 数是没有区分的，所以要乘以 $1/k!$。

考虑到如果有 $t$ 个房间为空，那么对于每一个人而言，就只有 $k - t$ 个选择，所以对于此的方案数的就是 $(k - t)^p$。所以我们可以知道：

$$ S(p,\ k) = \frac1{k!}\sum_{t = 0}^k (-1)^t{k \choose t}(k - t)^p $$

这也就是计算单个第二类 Stirling 数的公式。

第一类 Stirling 数

定义

现在来介绍第一类 Stirling 数。与第二类 Stirling 数相反，第一类 Stirling 数是使用整数的幂次来表示下降幂。

现在来观察一下规律：

$$ \begin{aligned} & n^{\underline{0}} = 1 \\ & n^{\underline{1}} = n \\ & n^{\underline{2}} = n(n - 1) = n^2 - n \\ & n^{\underline{3}} = n(n - 1)(n - 2) = n^3 - 3n^2 + 2n \\ & n^{\underline{4}} = n(n - 1)(n - 2)(n - 3) = n^4 - 6n^3 + 11n^2 - 6n \\ & ... \end{aligned} $$

可以发现，下降幂展开以后是一个系数正负号交替的多项式。与在第二类 Stirling 数中类似的，我们设 $s(p,\ k)$ 为第一类 Stirling 数，并且满足：

$$ n^{\underline{p}} = \sum_{k = 0}^p (-1)^{p - k}s(p,\ k)n^k $$

以及边界值：

$$ \begin{matrix} s(n,\ n) = 1 & \forall n \in \mathbb N \\ s(n,\ 0) = 0 & \forall n \in \mathbb N^+ \end{matrix} $$

类似的，我们可以据此推出第二类 Stirling 数的递推公式：

$$ \begin{aligned} n^{\underline{p - 1}} & = \sum_{k = 0}^{p-1} (-1)^{p - k - 1}s(p - 1,\ k)n^k \\ n^{\underline{p}} & = (n - p + 1)\sum_{k = 0}^{p-1} (-1)^{p - k - 1}s(p - 1,\ k)n^k \\ & = \sum_{k = 0}^{p-1} (-1)^{p - k - 1}s(p - 1,\ k)n^{k+1} + \sum_{k = 0}^{p-1} (-1)^{p - k}(p - 1)s(p - 1,\ k)n^k \\ & = \sum_{k = 1}^{p} (-1)^{p - k}s(p - 1,\ k - 1)n^{k} + \sum_{k = 0}^{p-1} (-1)^{p - k}(p - 1)s(p - 1,\ k)n^k \end{aligned} $$

通过比较同次项的系数可以得知：

$$ s(p,\ k) = (p - 1)s(p - 1,\ k) + s(p - 1,\ k - 1) $$

组合意义

同样的，第一类 Stirling 数也具有其组合意义。通过考虑下面的问题就可以证明：

求 $p$ 个人围成 $k$ 个圈 (圈不能为空) 的方案数。
注意这里的圈中的人的顺序不同也会视为圈不同。

对于这个问题，我们证明其答案 $f(p,\ k)$ 满足下面的递推关系：

$$ f(p,\ k) = (p - 1)f(p - 1,\ k) + f(p - 1,\ k - 1) $$

证明：

1. 如果第 $p$ 个人独自站成一个圈，那么共有 $f(p - 1,\ k - 1)$ 种方案。
2. 如果第 $p$ 个人与之前的人站在一起，那么他有 $p - 1$ 种方案站在一个人的右边，所以共有 $(p - 1)f(p - 1,\ k)$ 中方案。

不难验证这个问题的初始条件与第一类 Stirling 数一致，所以 $f(p,\ k)$ 和 $s(p,\ k)$ 就是一样的啦～

---