斯特林数
第一类斯特林数(Stirling Number)¶
第一类斯特林数 (斯特林轮换数)
递推式¶
边界是
该递推式的证明可以考虑其组合意义。
我们插入一个新元素时,有两种方案:
- 将该新元素置于一个单独的圆排列中,共有
\begin{bmatrix}n-1\\ k-1\end{bmatrix} - 将该元素插入到任何一个现有的圆排列中,共有
(n-1)\begin{bmatrix}n-1\\ k\end{bmatrix}
根据加法原理,将两式相加即可得到递推式。
第二类斯特林数(Stirling Number)¶
第二类斯特林数 (斯特林子集数)
递推式¶
边界是
还是考虑组合意义来证明。
我们插入一个新元素时,有两种方案:
- 将新元素单独放入一个子集,有
\begin{Bmatrix}n-1\\ k-1\end{Bmatrix} - 将新元素放入一个现有的非空子集,有
k\begin{Bmatrix}n-1\\ k\end{Bmatrix}
根据加法原理,将两式相加即可得到递推式。
应用¶
上升幂与普通幂的相互转化¶
我们记上升阶乘幂
则可以利用下面的恒等式将上升幂转化为普通幂:
如果将普通幂转化为上升幂,则有下面的恒等式:
下降幂与普通幂的相互转化¶
我们记下降阶乘幂
则可以利用下面的恒等式将普通幂转化为下降幂:
如果将下降幂转化为普通幂,则有下面的恒等式:
习题¶
参考资料与注释¶
- Stirling Number of the First Kind - Wolfram MathWorld
- Stirling Number of the Second Kind - Wolfram MathWorld
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用