定义
第一类斯特林数： \({n \brack k}\)，指将 \(n\) 个数放入 \(k\) 个环中（环无区分）的方案数。
第二类斯特林数： \({n \brace k}\)，指将 \(n\) 个数放入 \(k\) 个盒子（盒子无区分）的方案数。
递推式：
\[{n \brack k}=(n-1){n-1 \brack k}+{n - 1 \brack k - 1} \]说明：
我们考虑最后一个数的位置，独立成环则为后一项，否则我们可以加到 \(n-1\) 个数中的某个数后面去，得到这个递推式。
\[{n \brace k}=k{n-1 \brace k}+{n - 1 \brace k - 1} \]说明：
我们考虑最后一个数的位置，自己一个盒子则为后一项，否则我们可以加到 \(k\) 个盒子中的某个盒子中。
常见应用
第一类斯特林数与阶乘：
\[\sum_{k=0}^n {n \brack k}=n! \]证明：
double counting，考虑计算有多少个 \(1 \sim n\) 的置换，显然有 \(n!\) 个。如果我们枚举置换中环的个数，就是 \(\sum_{k=0}^n {n \brack k}\)，所以二者相等。
第二类斯特林数通项公式：
\[{n \brace k}=\frac{1}{k!}\sum_{t=0}^k(-1)^k\binom{k}{t}(t-k)^n \]证明：
见容斥原理学习笔记。
上下阶乘幂与普通数幂的关系：
\[x^n = \sum_{k=1}^n {n \brace k}x^{\underline{k}} \]\[x^n = \sum_{k=1}^n(-1)^{n-k}{n \brace k}x^{\overline{k}} \]\[x^{\underline{n}} = \sum_{k=1}^n (-1)^{n-k} {n \brack k}x^k \]\[x^{\overline{n}} = \sum_{k=1}^n{n \brack k}x^k \]证明：
先证第一个，double counting，将 \(n\) 个数放入 \(x\) 个盒子中（盒子有区别），显然可以是 \(x^n\)，枚举哪些盒子非空，再用算这些盒子的情况，答案是 \(\sum_{k=1}^n {n \brace k}x^{\underline{k}}\)。
剩下的三个式子可以由 \(x^{\overline{k}}=(-1)^{k}(-x)^{\underline{k}}\) 推出。
题目
例1： \(n \le 10^9, k \le 5000\)，计算
\[\sum_{i=1}^n\binom{n}{i}i^k \]思路：
\[\begin{aligned} \sum_{i=1}^n\binom{n}{i}i^k &= \sum_{i=1}^n\binom{n}{i}\sum_{j=1}^k{k \brace j}i^{\underline{j}}\\ &= \sum_{i=1}^n\binom{n}{i}\sum_{j=1}^{\min\{k,i\}}{k \brace j}i^{\underline{j}}\\ &= \sum_{i=1}^n\binom{n}{i}\sum_{j=1}^{\min\{k,i\}}{k \brace j}\binom{i}{j}j!\\ &= \sum_{j=1}^{\min\{k,n\}}j!{k \brace j}\sum_{i=j}^n\binom{n}{i}\binom{i}{j}\\ &= \sum_{j=1}^{\min\{k,n\}}j!{k \brace j}\sum_{i=j}^n\binom{n}{j}\binom{n-j}{i-j}\\ &= \sum_{j=1}^{\min\{k,n\}}j!{k \brace j}\binom{n}{j}\sum_{i=j}^n\binom{n-j}{i-j}\\ &= \sum_{j=1}^{\min\{k,n\}}j!{k \brace j}\binom{n}{j}\sum_{i=0}^{n-j}\binom{n-j}{i}\\ &= \sum_{j=1}^{\min\{k,n\}}j!{k \brace j}\binom{n}{j}2^{n-j}\\ \end{aligned} \]再结合第二类斯特林数递推式便能计算。
标签：盒子,min,斯特林,sum,brack,相关,binom,brace From： https://www.cnblogs.com/rlc202204/p/17976478