第一类斯特林数 $\texttt{(Fisrt Stirling)}$
记 $\operatorname{stir_1}(n,k)$ 或 ${n \brack k}$ 表示 $n$ 个不同小球放在 $k$ 个置换环中的方案数。其中环之间的小球编号不同或置换顺序不同均算作不同的方案。
递推：${n \brack k}={n-1 \brack k-1}+(n-1)\cdot {n-1 \brack k}$
*组合意义：对于第 $n$ 个球，一种选择是新开一个未放过任何小球的环，另一种选择是放在之前的环中，因为小球互不相同且置换不同算作不同方案，那么放在任意已经放过的小球之后都是不同的方案，因此有 $(n-1)$ 种选择。
边界：${0 \brack 0}=1,{n \brack 0}=0(n>0),{n\brack k}=0(n<k)$
代码实现 $\mathcal{O}(nk)$
stir1[0][0] = 1;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= min(i, k); ++j) {
stir1[i][j] = (stir1[i - 1][j - 1] + (ll)stir1[i - 1][j] * (i - 1) % Mod) % Mod;
}
}
不知道有什么用的性质
- ${n \brack 1}=(n-1)!$
- ${n \brack 2}=(n-1)!\sum\limits_{i=1}^{n-1}\dfrac{1}{i}$
- $n!=\sum\limits_{k=0}^n{n \brack k}$
上升幂
记 $x$ 的 $n$ 阶上升幂为 $x^{\overline{n}}$ ，其值为 $\prod\limits_{i=x}^{n+x-1}i$。特殊地，记 $x^{\overline{0}}=1$。
不难看出 $x^{\overline{n}}$ 是一个关于 $x$ 的 $n$ 次多项式，具体来说，有 $x^{\overline{n}}=\sum\limits_{k=0}^{n}{n \brack k}x^k$。
*组合意义：对于将 $n$ 个小球放在 $k$ 个置换环中，再对环染 $[1,x]$ 中的某种颜色。等式左边含义为对于当前的球，要么新开一个环染 $[1,x]$ 的颜色，要么放在任意一个之前的球之后并继承颜色；等式右边含义为枚举环的数量 $k$，用第一类斯特林数求出 $n$ 个球放 $k$ 个环的方案数后每个环染 $[1,x]$ 的颜色。
第二类斯特林数 $\texttt{(Second Stirling)}$
记 $\operatorname{stir_2}(n,k)$ 或 ${n \brace k}$ 表示 $n$ 个不同小球放在 $k$ 个集合中的方案数。其中集合之间的小球编号不同视作不同的方案。
递推：${n \brace k}={n-1 \brace k-1}+k\cdot {n-1 \brace k}$
*组合意义：对于第 $n$ 个球，一种选择是新开一个未放过任何小球的集合，另一种选择是放在之前的集合中，有 $(k-1)$ 种可选择的集合。
边界：${0 \brace 0}=1$
代码实现 $\mathcal{O}(nk)$
stir2[0][0] = 1;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= min(i, k); ++j) {
stir2[i][j] = (stir2[i - 1][j - 1] + (ll)stir2[i - 1][j] * j % Mod) % Mod;
}
}
容斥（通项公式）
${n \brace k}=\dfrac{1}{k!}\sum\limits_{i=0}^k(-1)^i\cdot {k \choose i}\cdot (k-i)^n$
组合意义：考虑 $n$ 个球，放进 $k$ 个不同集合，可以有空盒子的方案数。
下降幂
记 $x$ 的 $n$ 阶下升幂为 $x^{\underline{n}}$ ，其值为 $\prod\limits_{i=x}^{x-n+1}i$。特殊地，记 $x^{\underline{0}}=1$。
下降幂与 $n$ 次幂的关系：$x^n=\sum\limits_{k=0}^n{n \brace k}x^{\underline{k}}$
*组合意义：对于将 $n$ 个小球染 $[1,x]$ 的某种颜色。等式左边为一般乘法原理；等式右边为先枚举不同的颜色数 $k$，然后将 $n$ 个小球分成 $k$ 个集合后依次染色，后面染的跟前面不重复，因此是下降幂。
下降幂的转化：$i^{\underline{j}}={i \choose j}j!$
习题
CF1342E Placing Rooks
注意到一共仅有 $n$ 个车，那么当且仅当每行恰好有一个车或每列恰好有一个车。
不妨考虑每行有一个车的情况，行上显然没有可以互相攻击的车，那么考虑列的贡献。设最终有 $m$ 列存在车，那么首先先用 $m$ 个车填满这 $m$ 列，而后每增加一个车都恰好添加一对相互攻击的车，因此最终互相共计的车的对数为 $n-m=k$，解得 $m=n-k$。
那么最终的答案为：${n \choose n-k}{n \brace n-k}(n-k)!$，对于填列的情况恰好一一对应一种填行的情况，只需将答案乘 $2$ 即可。
P4609 [FJOI2016] 建筑师
题意转化：长度为 $n$ 的排列，前缀单调栈长度为 $A$ 且后缀单调栈长度为 $B$ 的排列数量。
由于 $n$ 一定在两边都能被看到，所以单调栈长度先减 $1$。
考虑单调栈中的每个数一定挡住了它后面的一些数，我们把每个单调栈中的数和它挡住的数一块考虑，当我们选定了这些数后，我们要把最大的数放在最前面，因此是一个置换环的形式，方案为第一类斯特林数。
最后答案即为 ${n-1 \brack A+B-2}{A+B-2 \choose A-1}$。
CF932E Team Work
推式子题。
$\sum\limits_{i=1}^n{n \choose i}\times i^k$ （首先拆 $i^k$ 为下降幂）
$=\sum\limits_{i=1}^n{n\choose i}\sum\limits_{j=0}^k{k \brace j}i^{\underline{j}}$（把 $i^{\underline{j}}$ 拆一下）
$=\sum\limits_{i=1}^n{n\choose i}\sum\limits_{j=0}^k{k \brace j}{i \choose j}j!$（换序求和）
$=\sum\limits_{j=0}^k{k \brace j}j!\sum\limits_{i=1}^n{n\choose i}{i \choose j}$（调整一下后面的组合数形式）
$=\sum\limits_{j=0}^k{k \brace j}j!\sum\limits_{i=j}^n{n\choose j}{n-j \choose i-j}$（观察到 $\sum\limits_{i=j}^n{n-j \choose i-j}=2^{n-j}$）
$=\sum\limits_{j=0}^k{k \brace j}j!{n\choose j}2^{n-j}$
$\mathcal{O}(k^2)$ 预处理第二类斯特林数，$\mathcal{O}(k)$ 组合数按列递推，$\mathcal{O}(k\log n)$ 求答案，总时间复杂度 $\mathcal{O(k^2+k\log n)}$。
CF1278F Cards
又是推式子题。
对于每次洗牌，有 $\dfrac{1}{m}$ 的概率第一张是王牌，有 $\dfrac{m-1}{m}$ 的概率第一张不是王牌，每次洗牌是独立的，枚举 $x$ 后则有：
$\sum\limits_{x=0}^n x^k{n\choose x}(\dfrac{1}{m})^x(\dfrac{m-1}{m})^{n-x}$
为方便起见，设 $\dfrac{1}{m}=p$。
$=\sum\limits_{x=0}^n x^k{n\choose x}p^x(1-p)^{n-x}$（拆 $x^k$）
$=\sum\limits_{x=0}^n\sum\limits_{j=0}^k {k \brace j}x^{\underline{j}}{n \choose x}p^x(1-p)^{n-x}$（拆 $x^{\underline{j}}$）
$=\sum\limits_{x=0}^n\sum\limits_{j=0}^k {k \brace j}{x \choose j}j!{n \choose x}p^x(1-p)^{n-x}$（换序求和 + 调整组合数形式）
$=\sum\limits_{j=0}^k {k\brace j}j!\sum\limits_{x=j}^n{n\choose j}{n-j \choose x-j}p^x(1-p)^{n-x}$
将 $p^x(1-p)^{n-x}$ 看作 $p^{x-j}(1-p)^{n-x}\cdot p^j$ 后，利用二项式定理化简：
$=\sum\limits_{j=0}^k {k \brace j}j!{n\choose j}p^j$
$=\sum\limits_{j=0}^k {k \brace j}n^{\underline{j}}p^j$
易知求解此式的复杂度为 $\mathcal{O}(k^2)$。
P6620 [省选联考 2020 A 卷] 组合数问题
双是推式子题。
我们不妨修改题面中式子的枚举变量 $k$ 为 $i$，以下均与 $i$ 为准。
首先把原式的 $f(i)$ 打开：
$=\sum\limits_{i=0}^n \sum\limits_{j=0}^m a_j i^j\times x^i\times {n \choose i}$
观察到又有形如 $i^j\times {n\choose i}$ 的美妙形式，因为上两题已经推导，这里我们直接得出：
$=\sum\limits_{i=0}^n\sum\limits_{j=0}^m a_j\times x^i\times \sum\limits_{k=0}^j {j \brace k}k!{n \choose k}{n-k \choose i-k}$（换序求和）
$=\sum\limits_{j=0}^m a_j\sum\limits_{k=0}^j {j \brace k}k!{n \choose k}\sum\limits_{i=k}^n{n-k \choose i-k}x^i$（二项式定理）
$=\sum\limits_{j=0}^m a_j\sum\limits_{k=0}^j {j \brace k}k!{n \choose k}x^k(x+1)^{n-k}$
$=\sum\limits_{j=0}^m a_j\sum\limits_{k=0}^j {j \brace k}n^{\underline{k}}x^k(x+1)^{n-k}$
然后我们在 $\mathcal{O}(m^2 \log m)$ 的时间复杂度解决问题即可。
U117299 染色（容斥+斯特林数）
考虑首先只满足 “不存在颜色相同的 $2$ 列” 这一条件。记 $f_i$ 表示染 $i$ 行，不存在颜色相同的 $2$ 列的方案数。
显然是从 $A^i$ 种方案中排列 $m$ 个，则 $f_i=(A^i)^{\underline{m}}$。
那么接下来我们想办法把行的限制也加进去，考虑将这些情况容斥掉，记 $g_i$ 表示染 $i$ 行，不存在颜色相同的 $2$ 行也不存在颜色相同的 $2$ 列。
我们可以通过枚举不同的行的数量来变成一个小规模子问题，假设不同的行有 $j$ 个，搞出 $j$ 行的方案数为 $g_j$，然后我们要做的问题就是 “将 $i$ 个不同的小球放入 $j$ 个集合，集合非空的方案数”，用第二类斯特林数，因此总转移方程为：$g_i=f_i-\sum\limits_{j=1}^{i-1}g_j{i \brace j}$。
时间复杂度 $\mathcal{O}(nm)$。
总结
对于斯特林数的相关题目，一般有如下标志/转化/思路：
出现次数很多 $(10^9)$ 的幂次项
$i^j\times {n\choose i}$
容斥 & 组合意义