斯特林数基础

高等的我不会

前置知识：

• 组合数学

• 容斥原理（证明第二类斯特林数的通项公式）

• 二项式反演（证明第二类斯特林数的通项公式）

• 圆排列相关（第一类斯特林数）

• 上升幂与下降幂（通过斯特林数转换普通幂）

• 数学归纳法（通过斯特林数转换普通幂）

定义：

百度百科

oi-wiki

斯特林数，多出现在组合枚举问题中。

• 第一类斯特林数 \(s(n,m)\)，也被记为 \(\begin{bmatrix}n\\m \end{bmatrix}\)，表示将 \(n\) 个不同元素构成 \(m\) 个圆排列的方案数。

• 第二类斯特林数 \(S(n,m)\)，也被记为 \(\begin{Bmatrix}n\\m \end{Bmatrix}\)，表示将 \(n\) 个不同元素分成 \(m\) 个集合的方案数。

由于第一类斯特林数与第二类斯特林数的 \(s\) 大小写难以区分，所以本文将采用另一种写法。

通常第二类斯特林数更加常用，因此首先描述第二类斯特林数。

第二类斯特林数

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

（互不区分：不考虑非空子集之间的排列）

递推式：

边界为 \(\begin{Bmatrix} n\\0 \end{Bmatrix}=[n=0]\)。

(\([n=0]\) 返回值是一个 bool 值）

证明：

• 这是一个递推式，我们每新加入一个新元素，将新元素单独开一个子集，有\(\begin{Bmatrix} n-1\\k-1 \end{Bmatrix}\) 种方案。

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

加法原理相加。

最后边界是 \(\begin{Bmatrix} n\\0 \end{Bmatrix}=[n=0]\)，毫无疑问如果 \(n\neq 0\) 是无意义的，否则方案数为 \(1\)。

于是有递推代码：

#define rg register int
#define il inline
il void pre(){
//递推求至S[n][m] 
	S[0][0]=1;
	for(rg i=1;i<=n;++i){
		for(rg j=1;j<=min(i,m);++j){
			S[i][j]=S[i-1][j-1]+j*S[i-1][j]%mod;
		}
	}
} 

通项公式

这个公式可以用容斥原理或二项式反演证明，这里使用二项式反演：

设 \(n\) 个互异元素，划分到 \(i\) 个互异集合（包括空集）的方案数是 \(g_i=i^n\)，而 \(n\) 个互异元素，划分至 \(i\) 个两两不同的非空集合（不包括空集）的方案书是 \(f_i\)。

根据二项式反演形式一：\(f_n=\sum^{n}_{i=0}\limits C_{n}^ig_i \Leftrightarrow g_n=\sum^{n}_{i=0}\limits(-1)^{n-i}C_{n}^if_i\)，易得：

而 \(f_i\) 与 \(\begin{Bmatrix} n\\i \end{Bmatrix}\) 的唯一不同点在于：\(\begin{Bmatrix} n\\i \end{Bmatrix}\) 不计算非空集合之间的排列，因此 \(f_i=i!\times \begin{Bmatrix} n\\i \end{Bmatrix}\)，得证：

至于同一行第二类斯特林数之类的计算我不会，长大再学（

第一类斯特林数

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

（互不区分：不考虑非空子集之间的排列）

（有关圆排列已经在前置知识解释）

递推式

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

(\([n=0]\) 返回值是一个 bool 值）

相似的证明：

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

• 新元素单独放入一个圆排列： \(\begin{bmatrix} n-1\\k-1 \end{bmatrix}\)。

• 新元素插入到任何一个现有的圆排列中：\((n-1)\times \begin{bmatrix} n-1\\k \end{bmatrix}\)。

加法原理易证。

对于 \(\begin{bmatrix} n\\0 \end{bmatrix}=[n=0]\) 边界，\(n\leq 0\) 无意义，否则方案为 \(1\)。

#define rg register int
#define il inline
il void pre(){
//递推求至s[n][m] 
	s[0][0]=1;
	for(rg i=1;i<=n;++i){
		for(rg j=1;j<=min(i,m);++j){
			s[i][j]=s[i-1][j-1]+(i-1)*s[i-1][j]%mod;
		}
	}
} 

同一行第一类斯特林数我不会，长大再学（

上升幂、下降幂与普通幂的转化

有恒等式：

如何证明？数学归纳法（前置知识有）。

首先假设我们认为：

显然本式在 \(n=0\) 时成立，故假设本式在 \(0-(n-1)\) 区间成立，证明 \(n\) 是否成立。

（我只会这么证明，不要问我先辈是如何找到这个式子的，我真不会）

因为 \(x^{\underline {k+1}}=x^{\underline k}\times (x-k)\)，所以 \(x\times x^{\underline k}=x^{\underline {k+1}}+kx^{\underline k}\)。（本式在下面第三行使用）

因此得到：

证毕。

其余同理。

例题：Team Work

Team Work

题目链接

题面翻译

给定 $ n,k $，求：

$ 1 \leq k \leq 5000,1 \leq n \leq 10^9 $

题目描述

You have a team of $ N $ people. For a particular task, you can pick any non-empty subset of people. The cost of having $ x $ people for the task is $ x^{k} $ .

Output the sum of costs over all non-empty subsets of people.

输入格式

Only line of input contains two integers $ N $ $ (1<=N<=10^{9}) $ representing total number of people and $ k $ $ (1<=k<=5000) $ .

输出格式

Output the sum of costs for all non empty subsets modulo $ 10^{9}+7 $ .

样例 #1

样例输入 #1

1 1

样例输出 #1

1

样例 #2

样例输入 #2

3 2

样例输出 #2

24

提示

In the first example, there is only one non-empty subset $ {1} $ with cost $ 1^{1}=1 $ .

In the second example, there are seven non-empty subsets.

- $ {1} $ with cost $ 1^{2}=1 $

- $ {2} $ with cost $ 1^{2}=1 $

- $ {1,2} $ with cost $ 2^{2}=4 $

- $ {3} $ with cost $ 1^{2}=1 $

- $ {1,3} $ with cost $ 2^{2}=4 $

- $ {2,3} $ with cost $ 2^{2}=4 $

- $ {1,2,3} $ with cost $ 3^{2}=9 $

The total cost is $ 1+1+4+1+4+4+9=24 $ .

解题：

题意就是给你 \(n\) 个元素，你可以选任意几个元素组成的非空子集，选 \(x\) 个元素的代价是 \(x^k\)。

要求输出所有非空子集的元素代价总和。

也就是要求输出答案 \(\sum_{i=1}^{n}\limits C_n^i\times i^k\)。

而 \(\sum_{i=1}^{n}\limits C_n^i\times i^k=\sum_{i=0}^{n}\limits C_n^i\times i^k\)。

对于 \(i^k\) 可以用第二类斯特林数展开：

推柿子：