随便记点。
定义
第二类 Stirling Number。
latex：$\begin{Bmatrix}n\\m\end{Bmatrix}$ 或 n\brace m，大小渲染可能有差别。
我们定义 \(\begin{Bmatrix}n\\m\end{Bmatrix}\) 表示将 \(n\) 个不同的球放进 \(m\) 个相同非空盒子的方案数。
求法
考虑类似 DP 地求出 \(\begin{Bmatrix}n\\m\end{Bmatrix}\)。
\[\begin{Bmatrix}n\\m\end{Bmatrix}=\begin{Bmatrix}n-1\\m-1\end{Bmatrix}+m\cdot\begin{Bmatrix}n-1\\m\end{Bmatrix} \]即，分类第 \(n\) 个球单独放新盒子 / 放一个之前有的盒子。
边界条件 \(\begin{Bmatrix}n\\0\end{Bmatrix}=[n=0]\)。这很类似组合数，不是么？
有通项。还没看。
第二类斯特林数优化 K 次方幂和问题
给出关键公式
\[n^k=\sum\limits_{i=0}^k{k\brace i}\binom nii!=\sum_{i=0}^{n}\left\{\begin{array}{c}n \\i\end{array}\right\} \cdot n^{\underline{i}} \]利用组合意义简单证明：
- LHS：将 \(k\) 个球放入 \(n\) 个不同可空盒子的方案数。
- RHS：先钦定有值的 \(i\) 个盒子，再有值地往里面放 \(k\) 个球。
显然两者相同。
一个题
标签：第二类,begin,end,斯特林,Bmatrix,个球,小记 From： https://www.cnblogs.com/liangbowen/p/18595579\(n\) 个点的树，\(m\) 种颜色，对每个节点染色，定义一个方案是合法的，当且仅当所有相邻两点的 Color 不同。
给定一个点集 \(S\)，定义一个合法方案的贡献为 \(\{c_x|x\in S\}\) 集合的大小，即点集内不同颜色数。
对所有合法方案，求贡献的 \(K\) 次方之和。\(n,m\le10^5,K\le80\)。