在组合数学中，有几个重要的 “递推数”，

而笔者今天要介绍的，

就是其中的 第二类斯特林数。

正题：

第二类斯特林数(即斯特林子集数)\(\begin{Bmatrix}n\\k\end{Bmatrix}\)，

也记作 \(S(n,k)\)，

它表示将 \(n\) 个 两两不同 的元素，划分为 \(k\) 个 互不区分 的 非空子集 的方案数。

每次加入一个新元素时，有两种方案：

• 单独放进 一个 新子集：\(\begin{Bmatrix}n-1\\k-1\end{Bmatrix}\)
• 放入一个现有的 非空子集：\(\begin{Bmatrix}n-1\\k\end{Bmatrix}\)

根据加法原理，即可得出递推式：

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

边界：\(\begin{Bmatrix}n\\1\end{Bmatrix}=1\)。

最终，我们能得出以下程序：

//第二类斯特林数模板
#include
using namespace std;
const int N=5e3+5,mod=1e9+7;
int n,Stirling[N][N];
int main()
{
	scanf("%d",&n);
	Stirling[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
			Stirling[i][j]=(Stirling[i-1][j-1]+j*Stirling[i-1][j]%mod)%mod; //递推式
	}
	return 0;
}

To be continued……