【学习笔记】【数学】斯特林数-526互联

斯特林数

点击查看目录

前置知识：
定义：
第二类斯特林数
- 递推式：
- 通项公式
例题：Team Work
- 解题：

前置知识：

组合数学
容斥原理（证明第二类斯特林数的通项公式）
二项式反演（证明第二类斯特林数的通项公式）
圆排列相关（第一类斯特林数）：

循环排列，又称圆排列，环排列。

指 $m$ 个数中选 $n$ 个不同的元素排列成一个无头无尾的环形，两个圆排列相同当且仅当索取元素个数相同，取法一致，环上排列顺序相同。

如：$abcde,bcdea,cdeab,deabc eabcd$ 是五个元素的一种圆排列。

而 $acbde$ 则又是另一种圆排列，这是圆排列与直线排列的主要区别。

而根据刚刚我们知道，一种圆排列可以拆成五种不同的直线排列，而五个元素的直线排列有 $5!$ 种，设圆排列个数为 $x$，易得：

\[ \begin{aligned} x=\frac{5!}{5}=(5-1)!=4! \end{aligned} \]

即，对于 $n$ 个不同的元素，其圆排列个数为 $(n-1)!$。

而我们知道，$m$ 个相异元素里，选出 $n$ 个数的方案数是 $C_m^n$。

因此，从 $m$ 个相异元素选出 $n$ 个可以组成圆排列个数：

\[ \begin{aligned} x=C_m^n\times (n-1)!=\frac{A_m^n}{n} \end{aligned} \]

定义：

百度百科

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{aligned} \begin{Bmatrix}n\\k \end{Bmatrix}=\begin{Bmatrix} n-1\\k-1 \end{Bmatrix}+k\times\begin{Bmatrix} n-1\\k \end{Bmatrix} \end{aligned} \]

边界为 $\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;
		}
	}
}

通项公式

\[ \begin{aligned} \begin{Bmatrix} n\\m \end{Bmatrix}=\sum_{i=0}^{m}\limits\frac{(-1)^{m-i}\times i^n}{i!(m-i)!} \end{aligned} \]

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

设 $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$，易得：

\[ \begin{aligned} g_i&=\sum_{j=0}^{i}\limits C_i^j \times f_j\\ f_i&=\sum_{j=0}^{i}\limits (-1)^{i-j}\times C_i^j \times g_j\\ &=\sum_{j=0}^{i} (-1)^{i-j}\times C_i^j \times j^n\\ &=\sum_{j=0}^{i}\limits \frac{i!\times (-1)^{i-j}\times j^n}{j!\times (i-j)!} \end{aligned} \]

而 $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{aligned} \begin{Bmatrix} n\\m \end{Bmatrix}=\frac{f_m}{m!}=\sum_{i=0}^{m}\limits \frac{(-1)^{m-i}\times i^n}{i!\times (m-i)!} \end{aligned} \]

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

例题：Team Work

Team Work

题目链接

题面翻译

给定 $ n,k $，求：

\[\sum_{i=1}^n\binom n i \times i^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