【学习笔记】斯特林的试炼

前言

强烈建议有一定组合数学基础的读者阅读这篇文章。

---

由于式子较多，为增强直观性，笔者将用 $\displaystyle \binom{n}{m}$ 表示组合数 $\operatorname{C}_n^m$。

同理，笔者将用 $\displaystyle \begin{bmatrix}n \\ k\end{bmatrix}$ 和 $\displaystyle \begin{Bmatrix}n \\ k\end{Bmatrix}$ 分别表示第一类斯特林数 $s(n, k)$ 和第二类斯特林数 $S(n, k)$。

（注意：这些符号的意义下文将不会再次提及。）

---

前置知识

上升幂和下降幂

• 定义 $x^{\overline{n}}$ 为 $x$ 的 $n$ 次上升阶乘幂，又称上升幂，它的值为 $\displaystyle \prod_{i = 0}^{n - 1} (x + i)$。
• 定义 $x^{\underline{n}}$ 为 $x$ 的 $n$ 次下降阶乘幂，又称下降幂，它的值为 $\displaystyle \prod_{i = 0}^{n - 1} (x - i)$。

上升幂和下降幂的转换公式（证明显然，此处略去）：

$$\begin{aligned} (-x)^{\overline{n}} &= (-1)^n \cdot x^{\underline{n}} \\ (-x)^{\underline{n}} &= (-1)^n \cdot x^{\overline{n}} \end{aligned}$$

实际上，上升幂和下降幂与普通幂之间也有转换公式，不过由于公式中存在斯特林数，因此将在下文提及。

---

第一类斯特林数

把 $n$ 个互不相同的数划分为 $k$ 个圆排列的方案数被称为第一类斯特林数，也被称为斯特林轮换数。

递推式

若我们在一个长为 $n$ 的圆排列中插入一个数（一共有 $n$ 个位置可以插入），如此形成的 $n$ 种长为 $n + 1$ 的圆排列是互不相同的，因为它们互相之间不可以通过轮换得到。

所以，第一类斯特林数有递推式：

$$\begin{bmatrix}n \\ k\end{bmatrix} = \begin{bmatrix}n - 1 \\ k - 1\end{bmatrix} + (n - 1) \cdot \begin{bmatrix}n - 1 \\ k\end{bmatrix}$$

当然，该递推式也存在边界条件：

$$\begin{bmatrix}n \\ 0\end{bmatrix} = [n = 0]$$

如何证明这个递推式？

考虑从组合意义的角度入手：加入一个数，要么自己单独构成一个圆排列，要么插入已有的圆排列，它们分别对应了上述递推式的左右两项。

由于第一类斯特林数不存在通项公式，这个递推式就显得尤为重要了，它将辅助我们证明下文的诸多结论。

---

常用公式

和阶乘的关系：

$$n! = \sum_{i = 0}^n \begin{bmatrix}n \\ i\end{bmatrix}$$

等式的左边指的是 $1\sim n$ 的全排列。可以发现，每一个 $1 \sim n$ 的排列都能被划分为若干个圆排列，那么我们枚举圆排列的个数，把对应的第一类斯特林数相加，得到的实际上就是 $1 \sim n$ 的全排列。

---

和上升幂的关系（上升幂转普通幂）：

$$x^{\overline{n}} = \sum_{i = 0}^n \begin{bmatrix}n \\ i\end{bmatrix} \cdot x^i$$

如何证明？

• 生成函数
• 数学归纳法

首先考虑构造第一类斯特林数的生成函数：

$$f_n(x) = \sum_{i = 0}^\infty \begin{bmatrix}n \\ i\end{bmatrix} \cdot x^i$$

那么根据第一类斯特林数的递推式有：

$$\begin{aligned} &\because f_n(x) = x\cdot f_{n - 1}(x) + (n - 1)\cdot f_{n - 1}(x) \\ &\therefore f_n(x) = (x + n - 1)\cdot f_{n - 1}(x) \\ &\because f_1(x) = x \\ &\therefore f_n(x) = \sum_{i = 0}^n \begin{bmatrix}n \\ i\end{bmatrix} \cdot x^i = x^{\overline{n}} \end{aligned}$$

我们还可以考虑用数学归纳法证明。

显然当 $n = 0$ 时，原式左右两边相等。

设当前结论满足 $n$ 的情况，求证当前结论也满足 $n + 1$ 的情况。

问题转化为证明：

$$\sum_{i = 0}^{n + 1} \begin{bmatrix}n + 1 \\ i\end{bmatrix}\cdot x^i = (x + n) \cdot \sum_{i = 0}^n \begin{bmatrix}n \\ i\end{bmatrix}\cdot x^i$$

过程如下：

$$\begin{aligned} &\sum_{i = 0}^{n + 1} \begin{bmatrix}n + 1 \\ i\end{bmatrix}\cdot x^i \\ = &\sum_{i = 0}^{n + 1} (\begin{bmatrix}n \\ i - 1\end{bmatrix} + n\cdot\begin{bmatrix}n \\ i\end{bmatrix})\cdot x^i \\ = &\sum_{i = 0}^{n + 1} \begin{bmatrix}n \\ i - 1\end{bmatrix}\cdot x^i + \sum_{i = 0}^{n + 1} n\cdot\begin{bmatrix}n \\ i\end{bmatrix}\cdot x^i \\ = &\sum_{i = 0}^{n} \begin{bmatrix}n \\ i\end{bmatrix}\cdot x^{i + 1} + n \cdot\sum_{i = 0}^{n}\begin{bmatrix}n \\ i\end{bmatrix}\cdot x^i \\ = &x\cdot\sum_{i = 0}^{n} \begin{bmatrix}n \\ i\end{bmatrix}\cdot x^{i} + n \cdot\sum_{i = 0}^{n}\begin{bmatrix}n \\ i\end{bmatrix}\cdot x^i \\ = &(x + n)\cdot \sum_{i = 0}^n \begin{bmatrix}n \\ i\end{bmatrix}\cdot x^i \end{aligned}$$

---

同一行第一类斯特林数的求法

• P5408 第一类斯特林数 · 行

题解：

根据第一类斯特林数的递推式，我们可以得到一个 $\mathcal{O}(n^2)$ 的做法。

根据上文的结论（第 $n$ 行第一类斯特林数的生成函数为 $x^{\overline{n}}$），我们可以得到一个 $\mathcal{O}(n \log_2^2 n)$ 的做法：上升幂本质上是若干个二项式相乘，所以我们用分治加 $\mathcal{NTT}$ 做即可。

---

当然，还存在更快的做法。

考虑倍增，当前求出了 $x^{\overline{n}}$，要求 $x^{\overline{n \cdot 2}}$。

因为 $x^{\overline{n \cdot 2}} = x^{\overline{n}}\cdot (x + n)^{\overline{n}}$，所以我们只要能够求出 $(x + n)^{\overline{n}}$，就能够做到 $\mathcal{O}(n \log_2 n)$ 了。

考虑将二者的 $\mathcal{OGF}$ 展开：已知 $\displaystyle f(x) = \sum_{i = 0}^n a_i\cdot x^i$，要求 $\displaystyle f(x + n) = \sum_{i = 0}^n a_i\cdot (x + n)^i$。

我们对后面的这个式子做二项式展开：

$$\begin{aligned} &\sum_{i = 0}^n a_i\cdot (x + n)^i \\ = &\sum_{i = 0}^n a_i\sum_{j = 0}^i\displaystyle\binom{i}{j}\cdot x^j\cdot n^{i - j} \\ = &\sum_{i = 0}^n a_i\sum_{j = 0}^i\frac{i!}{j!\cdot(i - j)!}\cdot x^j\cdot n^{i - j} \\ = &\sum_{j = 0}^n\frac{x_j}{j!}\sum_{i = j}^n a_i \cdot i!\cdot\frac{n^{i - j}}{(i - j)!} \\ = &\sum_{j = 0}^n\frac{x_j}{j!}\sum_{i = 0}^{n - j} a_{i + j}\cdot(i + j)!\cdot\frac{n^{i}}{i!} \end{aligned}$$

这是一个典型的差卷积形式，我们直接用 $\mathcal{NTT}$ 做即可。

求出 $(x + n)^{\overline{n}}$ 后，我们再将其和 $x^{\overline{n}}$ 做卷积即可。

注意要特判 $n$ 为奇数的情况，此时我们还需要再乘上一个二项式，直接 $\mathcal{O}(n)$ 地乘即可。

---

例题

• P4609 [FJOI2016] 建筑师

题解：

做组合数学的题，光有推式子能力还不行，还得通过组合意义列出答案的式子。

例如这道题目，我们要思考的是，如何在其中加入组合意义。

可以发现，无论是从左边还是从右边，都一定会看到最高的楼。

设 $H$ 为最高的楼，$\lambda$ 为能够看到的楼，$.$ 为不能够看到的楼，那么建筑一定呈这种形式：

$$\lambda....\lambda..\lambda..\lambda...H.\lambda.....\lambda..\lambda$$

现在我们从左侧的视角出发，解释这个图中蕴含的细节（右侧同理）：

• $H$ 左侧的 $\lambda$ 数量为 $A - 1$；
• 左侧要么不存在 $\lambda$，要么第一个字符即为 $\lambda$，每一个 $\lambda$ 的右边存在若干个 $.$，这个 $\lambda$ 的高度高于这些 $.$；
• 对于左侧的一个 $\lambda$，右侧的 $.$ 顺序随意。

“顺序随意” 给了我们一定的启发，如果耐心把式子列出来，可以发现：如果我们把一个 $\lambda$ 和其右侧的 $m$ 个 $.$ 看作一个整体，那么一共有 $(m - 1)!$ 种排列方式。

如果你对排列数十分敏感，可以一眼看出来 —— 这就是圆排列。

圆排列！我们能想到什么？第一类斯特林数！

所以，我们只要在 $n - 1$ 个数中选出 $A + B - 2$ 个圆排列，并任选 $A-1$ 个放在 $H$ 的左边，$B - 1$ 个放在 $H$ 的右边，即为一种方案。

那么，答案就呼之欲出了：

$$\begin{bmatrix}n - 1 \\ A + B - 2\end{bmatrix} \cdot \displaystyle\binom{A + B - 2}{A - 1}$$

直接预处理即可，时间复杂度在可承受范围内。

---

第二类斯特林数

把 $n$ 个互不相同的数划分为 $k$ 个互不区分、互不相交的集合，这样的方案数称为第二类斯特林数。

第二类斯特林数相对于第一类的用处会更加广泛。

---

递推式

第二类斯特林数有递推式：

$$\begin{Bmatrix}n \\ k\end{Bmatrix} = \begin{Bmatrix}n - 1 \\ k - 1\end{Bmatrix} + k\cdot \begin{Bmatrix}n - 1 \\ k\end{Bmatrix}$$

证明还是考虑从组合意义的角度入手：

加入一个数，要么自己单独构成一个集合，要么加入已有的 $k$ 个集合。

边界条件同样是：

$$\begin{Bmatrix}n \\ 0\end{Bmatrix} = [n = 0]$$

---

通项公式

第二类斯特林数是存在通项公式的：

$$\begin{Bmatrix}n \\ k\end{Bmatrix} = \frac{1}{k!}\cdot\sum_{i = 0}^k(-1)^i\cdot\displaystyle\binom{k}{i} \cdot(k - i)^n$$

证明：

设将 $n$ 个互不相同的数划分为 $k$ 个互不相交的集合的方案数为 $f_k$ 和 $g_k$，前者允许空集，后者不允许空集。

那么有：

$$\begin{matrix} f_k = k^n \\ \displaystyle f_k = \sum_{i = 0}^k\displaystyle\binom{k}{i}\cdot g_i \end{matrix}$$

考虑二项式反演：

$$g_k = \sum_{i = 0}^k (-1)^{k - i}\cdot\displaystyle\binom{k}{i}\cdot f_i = \sum_{i = 0}^k(-1)^i\cdot\displaystyle\binom{k}{i}\cdot (k - i)^n$$

由于 $g_k$ 中的集合相互区分，所以有：

$$\begin{Bmatrix}n \\ k\end{Bmatrix} = \frac{g_k}{k!} = \frac{1}{k!}\cdot\sum_{i = 0}^k(-1)^i\cdot\displaystyle\binom{k}{i}\cdot (k - i)^n$$

---

常用公式

和下降幂的关系（普通幂转下降幂）：

$$x^n = \sum_{i = 0}^x \displaystyle\binom{x}{i}\cdot\begin{Bmatrix}n \\ i\end{Bmatrix}\cdot i! = \sum_{i = 0}^n \begin{Bmatrix}n \\ i\end{Bmatrix}\cdot x^{\underline{i}}$$

证明：

考虑组合意义，等式左侧即为将 $n$ 个互不相同的数划分为 $x$ 个互相区分的可空集合的方案数，等式右侧即为选出 $i$ 个集合并强制它们非空的方案数。

（当然，你也可以考虑用上面的数学归纳法证明，这里就留给读者当作练习吧。)

---

同一行第二类斯特林数的求法

• P5395 第二类斯特林数 · 行

题解：

其实非常简单，我们将通项公式变形得到：

$$\begin{Bmatrix}n \\ k\end{Bmatrix} = \sum_{i = 0}^k \frac{(-1)^i}{i!} \cdot \frac{(k - i)^n}{(k - i)!}$$

这是一个典型的和卷积形式，我们直接用 $\mathcal{NTT}$ 做即可。

---

例题

• BZOJ5093 图的价值

题意：

“简单无向图” 是指无重边、无自环的无向图（不一定连通）。
一个带标号的图的价值定义为每个点度数的 $k$ 次方之和。
给定 $n$ 和 $k$，请计算所有包含 $n$ 个点的带标号的简单无向图的价值之和。
答案对 $998244353$ 取模。
$\mathcal{Data~Range}$：$1 \le n \le 10^9, 1\le k\le 2\times 10^5$。

题解：

显然每个点对答案的贡献是相同的，所以我们只需要算出一个点对答案的贡献，最后乘上 $n$ 即可。

我们枚举一个点的度数，那么有：

$$\mathcal{Answer} = n \cdot 2^{\binom{n - 1}{2}}\cdot \sum_{i = 0}^{n - 1}i^k\cdot\displaystyle\binom{n - 1}{i}$$

这个时候，如果只用一般的方法，大概率会无从下手。

回顾普通幂转化为第二类斯特林数的公式，我们可以得到：

$$\begin{aligned} \mathcal{Answer} &= n \cdot 2^{\binom{n - 1}{2}} \cdot\sum_{i = 0}^{n - 1}i^k\cdot\displaystyle\binom{n - 1}{i} \\ &= n \cdot 2^{\binom{n - 1}{2}} \cdot\sum_{i = 0}^{n - 1}\displaystyle\binom{n - 1}{i} \sum_{j = 0}^{\min(i, k)}\displaystyle\binom{i}{j}\cdot \begin{Bmatrix}k \\ j\end{Bmatrix}\cdot j! \\ &=n \cdot 2^{\binom{n - 1}{2}}\cdot \sum_{j = 0}^{\min(n - 1, k)} \begin{Bmatrix}k \\ j\end{Bmatrix}\cdot j! \sum_{i = j}^{n - 1} \displaystyle\binom{n - 1}{i}\cdot\displaystyle\binom{i}{j} \\ &= n \cdot 2^{\binom{n - 1}{2}}\cdot \sum_{j = 0}^{\min(n - 1, k)} \begin{Bmatrix}k \\ j\end{Bmatrix}\cdot j! \cdot\displaystyle\binom{n - 1}{j} \sum_{i = j}^{n - 1} \displaystyle\binom{n - j - 1}{i - j} \\ &= n \cdot 2^{\binom{n - 1}{2}}\cdot \sum_{j = 0}^{\min(n - 1, k)} \begin{Bmatrix}k \\ j\end{Bmatrix}\cdot j! \cdot\displaystyle\binom{n - 1}{j} \sum_{i = 0}^{n - j - 1} \displaystyle\binom{n - j - 1}{i} \\ &= n \cdot 2^{\binom{n - 1}{2}} \cdot\sum_{j = 0}^{\min(n - 1, k)} \begin{Bmatrix}k \\ j\end{Bmatrix}\cdot j! \cdot\displaystyle\binom{n - 1}{j}\cdot 2^{n - j - 1} \end{aligned}$$

做部分预处理后直接计算即可。

---

斯特林反演

常用公式

根据上文，我们知道有如下两个等式：

$$\begin{matrix} (-x)^{\overline{n}} = (-1)^n\cdot x^{\underline{n}} \\ \displaystyle x^{\overline{n}} = \sum_{i = 0}^n \begin{bmatrix}n \\ i\end{bmatrix}\cdot x^i \end{matrix}$$

那么有：

$$(-x)^{\overline{n}} = \sum_{i = 0}^n \begin{bmatrix}n \\ i\end{bmatrix}\cdot (-x)^i$$

即：

$$(-1)^n\cdot x^{\underline{n}} = \sum_{i = 0}^n \begin{bmatrix}n \\ i\end{bmatrix}\cdot (-1)^i \cdot x^i$$

所以有：

$$x^{\underline{n}} = \sum_{i = 0}^n \begin{bmatrix}n \\ i\end{bmatrix} \cdot(-1)^{n - i}\cdot x^i$$

类似的，我们可以由如下两个公式：

$$\begin{matrix} (-x)^{\underline{n}} = (-1)^n\cdot x^{\overline{n}} \\ \displaystyle x^n = \sum_{i = 0}^n \begin{Bmatrix}n \\ i\end{Bmatrix}\cdot x^{\underline{i}} \end{matrix}$$

推出如下的公式：

$$x^n = \sum_{i = 0}^n \begin{Bmatrix}n \\ i\end{Bmatrix}\cdot (-1)^{n - i}\cdot x^{\overline{i}}$$

请读者自行推导。

---

总结一下，我们已经得到了所有的六个普通幂、上升幂和下降幂和之间的转换公式：

$$\begin{aligned} (-x)^{\overline{n}} &= (-1)^n\cdot x^{\underline{n}} \\ (-x)^{\underline{n}} &= (-1)^n\cdot x^{\overline{n}} \\ \displaystyle x^{\overline{n}} &= \sum_{i = 0}^n \begin{bmatrix}n \\ i\end{bmatrix}\cdot x^i \\ \displaystyle x^n &= \sum_{i = 0}^n \begin{Bmatrix}n \\ i\end{Bmatrix}\cdot x^{\underline{i}} \\ \displaystyle x^{\underline{n}} &= \sum_{i = 0}^n \begin{bmatrix}n \\ i\end{bmatrix}\cdot (-1)^{n - i}\cdot x^i \\ \displaystyle x^n &= \sum_{i = 0}^n \begin{Bmatrix}n \\ i\end{Bmatrix}\cdot (-1)^{n - i}\cdot x^{\overline{i}} \end{aligned}$$

下文分别称它们为公式一 ～ 公式六。

---

如果我们将公式三代入公式六，可以得到：

$$\begin{aligned} x^n &= \sum_{i = 0}^n \begin{Bmatrix}n \\ i\end{Bmatrix}\cdot (-1)^{n - i}\cdot x^{\overline{i}} \\ &= \sum_{i = 0}^n \begin{Bmatrix}n \\ i\end{Bmatrix}\cdot (-1)^{n - i}\sum_{j = 0}^i \begin{bmatrix}i \\ j\end{bmatrix}\cdot x^j \\ &= \sum_{j = 0}^nx^j\sum_{i = j}^n\begin{Bmatrix}n \\ i\end{Bmatrix}\cdot \begin{bmatrix}i \\ j\end{bmatrix}\cdot (-1)^{n - i} \end{aligned}$$

可以发现有：

$$\sum_{i = j}^n\begin{Bmatrix}n \\ i\end{Bmatrix}\cdot \begin{bmatrix}i \\ j\end{bmatrix}\cdot (-1)^{n - i} = [j = n]$$

类似地，将公式四代入公式五也可以得到十分类似的结果：

$$\sum_{i = j}^n\begin{bmatrix}n \\ i\end{bmatrix}\cdot \begin{Bmatrix}i \\ j\end{Bmatrix}\cdot (-1)^{n - i} = [j = n]$$

这俩公式合称反转公式。

---

当 $j = 1$ 时，有：

$$\sum_{i = 1}^n(-1)^{n - 1}\cdot(i - 1)!\cdot\begin{Bmatrix}n \\ i\end{Bmatrix} = [n = 1]$$

这个公式在和斯特林反演相关的题目中经常被用到。

---

由反转公式，我们可以得到斯特林反演的一般形式：

$$\begin{matrix} \displaystyle f_n = \sum_{i = 0}^n \begin{bmatrix}n \\ i\end{bmatrix}\cdot g_i \\ \Downarrow \\ \displaystyle g_n = \sum_{i = 0}^n(-1)^{n -i}\cdot \begin{Bmatrix}n \\ i\end{Bmatrix} \cdot f_i \end{matrix}$$

和

$$\begin{matrix} \displaystyle f_n = \sum_{i = 0}^n \begin{Bmatrix}n \\ i\end{Bmatrix}\cdot g_i \\ \Downarrow \\ \displaystyle g_n = \sum_{i = 0}^n(-1)^{n -i}\cdot \begin{bmatrix}n \\ i\end{bmatrix} \cdot f_i \end{matrix}$$

这个形式会显得有许些亲切感，因为其便是反演最标准的形式。

---

例题

• BZOJ4671 异或图

题解：

直接从连通入手并不好做，相反，强制不联通却简单得多。

考虑容斥，设 $f_i$ 为把 $n$ 个点划分为 $i$ 个互不相交且互不连通的点集的方案数，$g_i$ 为图中恰好有 $i$ 个连通块的方案数。

那么对于 $g_j$，它对 $f_i$ 的贡献系数即为第二类斯特林数：

$$\begin{Bmatrix}j \\ i\end{Bmatrix}$$

（因为 $g_j$ 中的 $j$ 个连通块互不相同，同时 $f_i$ 中的 $i$ 个点集又互不区分，这恰好满足了第二类斯特林数的要求。）

即：

$$f_i = \sum_{j = i}^n \begin{Bmatrix}j \\ i\end{Bmatrix}\cdot g_j$$

对其反演可得：

$$g_i = \sum_{j = i}^n(-1)^{j - i}\cdot\begin{bmatrix}j \\ i\end{bmatrix}\cdot f_j$$

依题意，现在我们仅需求出 $\displaystyle g_1 = \sum_{j = 1}^n (-1)^{j - 1}\cdot(j - 1)!\cdot f_j$，那么最大的问题便是求 $f_j$。

首先我们可以枚举子集划分（时间复杂度为贝尔数级别，在可承受范围内），然后我们强制让两个点集之间不连任何一条边。

由于一条边的选择情况取决于包含这条边的图的选择情况，因此对于一条横跨两个点集的边 $(u, v)$，我们设包含它的图为 $G'_{1\sim m}$，同时设每个图的选择情况为 $x_{1\sim m}$（$0$ 表示不选，$1$ 表示选），那么我们可以列出方程：

$$\texttt{xor}_{i = 1}^m x_i = 0$$

枚举每条边后，我们可以得到一个异或方程组，那么其解的数量就是这个子集划分对 $f_j$ 的贡献。

这是一个经典问题，我们用线性基解决即可，在此不多赘述。

---

更多例题

• CF961G Partitions

题解：

• 组合意义
• 代数推导

我们从组合意义思考一下，集合大小的本质是什么？不就是集合里的每一个数都贡献 $1$ 吗！

还是考虑计算单个物品 $i$ 的贡献。

首先，总划分方案数为：

$$\begin{Bmatrix}n \\ k\end{Bmatrix}$$

每个方案中，自己都会对自己造成 $1$ 的贡献。

其次，对于其它的每一个物品 $j$，抛开这个物品 $j$ 不谈，我们把剩下的 $n - 1$ 个物品分成 $k$ 组，再把物品 $j$ 加入到 $i$ 所在的组内，这样 $j$ 就对 $i$ 造成了 $1$ 的贡献。这样的方案数为：

$$\begin{Bmatrix}n - 1\\ k\end{Bmatrix}$$

所以单个物品的贡献即为：

$$\begin{Bmatrix}n \\ k\end{Bmatrix} + (n - 1)\cdot\begin{Bmatrix}n - 1 \\ k\end{Bmatrix}$$

做部分预处理后直接计算即可。

当然，你也可以尝试代数推导。

抛开 $w_i$ 不谈，可以发现单个物品的贡献是一定的，所以我们只要把 $w_i$ 求和，乘上单个物品的贡献 $\delta$ 即可。

现在考虑计算 $\delta$：

$$\begin{aligned} \delta =&\sum_{i = 1}^n i \cdot\displaystyle\binom{n - 1}{i - 1} \cdot\begin{Bmatrix}n - i \\ k - 1\end{Bmatrix} \\ =&\sum_{i = 1}^n i \cdot\displaystyle\binom{n - 1}{i - 1} \sum_{j = 0}^{k - 1}\frac{(-1)^{k - j - 1}}{(k - j - 1)!}\cdot\frac{j^{n - i}}{j!} \\ =&\sum_{j = 0}^{k - 1} \frac{(-1)^{k - j - 1}}{(k - j - 1)! \cdot j!}\sum_{i = 1}^ni \cdot j^{n - i}\cdot \displaystyle\binom{n - 1}{i - 1} \end{aligned}$$

前面的式子没有什么问题，考虑如何求后面的式子：

$$\begin{aligned} &\sum_{i = 1}^ni \cdot j^{n - i}\cdot \displaystyle\binom{n - 1}{i - 1} \\ =&\sum_{i = 1}^n(i - 1 + 1) \cdot j^{n - i}\cdot \displaystyle\binom{n - 1}{i - 1} \\ =&\sum_{i = 1}^n(i - 1)\cdot j^{n - i}\cdot\displaystyle\binom{n - 1}{i - 1} + \sum_{i = 1}^nj^{n - i}\cdot\displaystyle\binom{n - 1}{i - 1} \\ =&\sum_{i = 1}^n(i - 1)\cdot j^{n - i}\cdot\displaystyle\binom{n - 1}{i - 1} + (j + 1)^{n - 1} \\ =&(n - 1)\cdot\sum_{i = 1}^n j^{n - i}\cdot\displaystyle\binom{n - 2}{i - 2} + (j + 1)^{n - 1} \\ =&(n - 1)\cdot(j + 1)^{n - 2} + (j + 1)^{n - 1} \\ =&(j + 1)^{n - 2}\cdot(n + j) \end{aligned}$$

直接计算即可。

---

未完待续 ……