斯特林数

第一类斯特林数（Stirling Number）

第一类斯特林数 （斯特林轮换数） \begin{bmatrix}n\\ k\end{bmatrix} 表示将 n 个两两不同的元素，划分为 k 个非空圆排列的方案数。

递推式

\begin{bmatrix}n\\ k\end{bmatrix}=\begin{bmatrix}n-1\\ k-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\ k\end{bmatrix}

边界是 \begin{bmatrix}n\\ 0\end{bmatrix}=[n=0] 。

该递推式的证明可以考虑其组合意义。

我们插入一个新元素时，有两种方案：

  • 将该新元素置于一个单独的圆排列中，共有 \begin{bmatrix}n-1\\ k-1\end{bmatrix} 种方案；
  • 将该元素插入到任何一个现有的圆排列中，共有 (n-1)\begin{bmatrix}n-1\\ k\end{bmatrix} 种方案。

根据加法原理，将两式相加即可得到递推式。

第二类斯特林数（Stirling Number）

第二类斯特林数 （斯特林子集数） \begin{Bmatrix}n\\ k\end{Bmatrix} 表示将 n 个两两不同的元素，划分为 k 个非空子集的方案数。

递推式

\begin{Bmatrix}n\\ k\end{Bmatrix}=\begin{Bmatrix}n-1\\ k-1\end{Bmatrix}+k\begin{Bmatrix}n-1\\ k\end{Bmatrix}

边界是 \begin{Bmatrix}n\\ 0\end{Bmatrix}=[n=0] 。

还是考虑组合意义来证明。

我们插入一个新元素时，有两种方案：

  • 将新元素单独放入一个子集，有 \begin{Bmatrix}n-1\\ k-1\end{Bmatrix} 种方案；
  • 将新元素放入一个现有的非空子集，有 k\begin{Bmatrix}n-1\\ k\end{Bmatrix} 种方案。

根据加法原理，将两式相加即可得到递推式。

应用

上升幂与普通幂的相互转化

我们记上升阶乘幂 x^{\overline{n}}=\prod_{k=0}^{n-1} (x+k) 。

则可以利用下面的恒等式将上升幂转化为普通幂：

x^{\overline{n}}=\sum_{k} \begin{bmatrix}n\\ k\end{bmatrix} x^k

如果将普通幂转化为上升幂，则有下面的恒等式：

x^n=\sum_{k} \begin{Bmatrix}n\\ k\end{Bmatrix} (-1)^{n-k} x^{\overline{k}}

下降幂与普通幂的相互转化

我们记下降阶乘幂 x^{\underline{n}}=\dfrac{x!}{(x-n)!}=\prod_{k=0}^n-1 (x-k) 。

则可以利用下面的恒等式将普通幂转化为下降幂：

x^n=\sum_{k} \begin{Bmatrix}n\\ k\end{Bmatrix} x^{\underline{k}}

如果将下降幂转化为普通幂，则有下面的恒等式：

x^{\underline{n}}=\sum_{k} \begin{bmatrix}n\\ k\end{bmatrix} (-1)^{n-k} x^k

习题

HDU3625 Examining the Rooms

参考资料与注释

  1. Stirling Number of the First Kind - Wolfram MathWorld
  2. Stirling Number of the Second Kind - Wolfram MathWorld
build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论