斯特林数

第二类斯特林数

定义

$\left\{\begin{array}{c}n\\ k\end{array}\right\}$ 表示将 $n$ 个两两不同的元素，划分为 $k$ 个互不区分的非空子集的方案数。

递推式

$$\left\{\begin{array}{c}n\\ k\end{array}\right\}=\left\{\begin{array}{c}n-1\\ k-1\end{array}\right\}+k\left\{\begin{array}{c}n-1\\ k\end{array}\right\}.$$

边界是 $\left\{\begin{array}{c}n\\ 0\end{array}\right\}=[n=0]$。

通项公式

$$\left\{\begin{array}{c}n\\ m\end{array}\right\}=\sum _{i=0}^m\frac{(-1{)}^{m-i}{i}^n}{i!(m-i)!}.$$

贝尔数

定义

$B_n$ 表示将 $n$ 个两两不同的元素，划分为任意个非空集合的方案数。特别地，$B_0=1$。

递推式

$$B_{n+1}=\sum _{i=0}^n\left(\genfrac{}{}{0ex}{}{n}{i}\right)B_i.$$

通项公式

$$B_n=\sum _{i=0}^n\left\{\begin{array}{c}n\\ i\end{array}\right\}.$$