Skip to main content

斯特林数

Summary

斯特林数分为两类，都是组合计数里的基础工具。第二类斯特林数表示把 n 个不同的元素划分成 m 个非空、彼此无序的集合的方案数，满足递推 S(n,m) 等于 S(n-1,m-1) 加上 m 乘 S(n-1,m)，对应新元素单独成集或并入已有集合两种情形。第一类斯特林数表示把 n 个元素排成 m 个非空圆排列的方案数。两类数分别刻画普通幂与下降幂之间的相互转换关系，在幂的展开、自然数幂求和以及多项式变换中经常用到。文末配有四道模板题，分别求两类斯特林数的一行或一列。

参考资料​

简介​

第二类斯特林数 {nm}\begin{Bmatrix}n\\m\end{Bmatrix} 表示把 nn 个不同元素划分成 mm 个非空、无序集合的方案数，递推为

{nm}={n−1m−1}+m{n−1m}\begin{Bmatrix}n\\m\end{Bmatrix}=\begin{Bmatrix}n-1\\m-1\end{Bmatrix}+m\begin{Bmatrix}n-1\\m\end{Bmatrix}

第一类斯特林数 [nm]\begin{bmatrix}n\\m\end{bmatrix} 表示把 nn 个元素排成 mm 个非空圆排列的方案数。两者在普通幂与下降幂之间相互转换，是组合计数的基础工具。

例题​

洛谷 P5395 第二类斯特林数·行

给定 nn，对所有整数 i∈[0,n]i\in[0,n]，求第二类斯特林数 {ni}\begin{Bmatrix}n\\i\end{Bmatrix} 对 167772161167772161 取模的值。

洛谷 P5396 第二类斯特林数·列

给定 n,kn,k，对所有整数 i∈[0,n]i\in[0,n]，求第二类斯特林数 {ik}\begin{Bmatrix}i\\k\end{Bmatrix} 对 167772161167772161 取模的值。

洛谷 P5408 第一类斯特林数·行

给定 nn，对所有整数 i∈[0,n]i\in[0,n]，求第一类斯特林数 [ni]\begin{bmatrix}n\\i\end{bmatrix} 对 167772161167772161 取模的值。

洛谷 P5409 第一类斯特林数·列

给定 n,kn,k，对所有整数 i∈[0,n]i\in[0,n]，求第一类斯特林数 [ik]\begin{bmatrix}i\\k\end{bmatrix} 对 167772161167772161 取模的值。