【学习笔记】斯特林数

这东西看过一遍就忘还是要手敲一遍 $L_AT_EX$ 才可以啊

第一类斯特林数：$n$ 元置换分为 $k$ 个轮换的方案数。有：$\sum\limits_{k = 0}^n {n \brack k} = n!$

第二类斯特林数：$n$ 个元素划分为 $k$ 个非空集合的方案数。有：$\sum\limits_{k = 0}^n {n \brace k} = B_n$，其中 $B_n$ 为贝尔数，表示 $n$ 的划分方案数。

---

naive 的递推：

$${n \brack k} = {n - 1 \brack k - 1} + (n - 1) {n - 1 \brack k}$$ $${n \brace k} = {n - 1 \brace k - 1} + k {n - 1 \brace k}$$

---

展开式 + 通常求法：

第二类斯特林数的：

$${n \brace k} = \frac{1}{k!} \sum\limits_{i = 0}^{k}(-1)^{k - i} \binom{k}{i} i^n$$

（证明可以考虑组合意义 + 二项式反演，$k^n = \sum\limits_{i = 0}^k P_k^i {n \brace i} = \sum\limits_{i = 0}^k i!\binom{k}{i} {n \brace i} \Longleftrightarrow k! {n \brace k} = \sum\limits_{i = 0}^k (-1)^{k - i} \binom{k}{i} i^n$）

$${n \brace k} = \sum\limits_{i = 0}^k (-1)^{k - i} \frac{i^n}{i!(k - i)!}$$

FFT 即可。

---

幂之间转换：

$$x^{\underline{n}} = \sum\limits_{k = 0}^n (-1)^{n - k} {n \brack k} x^k \Longleftrightarrow x^n = \sum\limits_{k = 0}^n {n \brace k} x^{\underline{k}}$$ $$x^{\overline{n}} = \sum\limits_{k = 0}^n {n \brack k} x^k \Longleftrightarrow x^n = \sum\limits_{k = 0}^n (-1)^{n - k} {n \brace k} x^{\overline{k}}$$

---

设 $L(n, k) = \sum_j {n \brack j} {j \brace k} = \binom{n - 1}{k - 1} \frac{n!}{k!}$，则有

$$x^{\overline{n}} = \sum\limits_{k = 0}^n L(n, k)x^{\underline{k}} \Longleftrightarrow x^{\underline{n}} = \sum\limits_{k = 0}^n (-1)^{n - k} L(n, k) x^{\overline{k}}$$

（这是由前两条推出的，目前不知道有什么用

upd on 2021.3.20: $L(n, k)$ 就是第三类斯特林数，即拉赫数。。