『学习笔记』第二类斯特林数（部分）
第二类斯特林数
定义
定义 \(\begin{Bmatrix} n \\ m \end{Bmatrix}\) 表示 \(n\) 个互不相同的元素放入 \(m\) 个没有区分的集合并使这 \(m\) 个集合非空的方案数。
其中 \(\begin{Bmatrix} n \\ m \end{Bmatrix}\) 可读作“\(n\) 子集 \(k\)”。
递推式
\[\begin{Bmatrix} n \\ m \end{Bmatrix} = m \times \begin{Bmatrix} n - 1 \\ m \end{Bmatrix} + \begin{Bmatrix} n - 1 \\ m - 1 \end{Bmatrix}
\]
其中
\(\begin{Bmatrix} n \\ m \end{Bmatrix}\) 解释参见定义。
\(m \times \begin{Bmatrix} n - 1 \\ m \end{Bmatrix}\) 表示在原来某一个集合里新加了一个元素，一共有 \(m\) 种情况。
\(\begin{Bmatrix} n - 1 \\ m - 1 \end{Bmatrix}\) 表示将新加的元素单独放进新的集合里。
打表
参见其他博客或书籍。
下降幂
定义
定义下降幂为 \(x^ \underline n = \cfrac{x!}{(x-n)!}=\prod_{k=0}^{n-1} (x-k)\)。
根据打表可知，\(x^n = \sum_{k = 0}^n \times \begin{Bmatrix} n \\ k \end{Bmatrix} \times x^ \underline k\) 。
证明略，感性理解。