第二类 Stirling 数

第二类 Stirling 数是计数组合中的计数结果. 对自然数 $1\le k\le n$, 第二类 Stirling 数 $S(n,k)$ 是将 $n$ 元集合写成 $k$ 个不交的非空子集之并的方法数. 例如, 我们有$$S(3,2)=3,$$因为 $\{1,2,3\}$ 可以写成 $\{1,2\}\cup \{3\}$, 或 $\{1,3\}\cup \{2\}$, 或 $\{2,3\}\cup \{1\}$.

所有第二类 Stirling 数可以排成一个三角形:$$\begin{array}{c}\text{1}\\ \text{1}\text{1}\\ \text{1}\text{3}\text{1}\\ \text{1}\text{7}\text{6}\text{1}\\ \text{1}\text{15}\text{25}\text{10}\text{1}\\ \text{1}\text{31}\text{90}\text{65}\text{15}\text{1}\\ \text{…}\text{…}\text{…}\text{…}\text{…}\text{…}\text{…}\end{array}$$其中, 第 $n$ 行的数字是 $S(n,1),$ $\dots ,$ $S(n,n)$. 每行的第 $k$ 个数都是其左上方的数加上其右上方的数的 $k$ 倍.

1定义

定义 1.1 (第二类 Stirling 数). 对自然数 $1\le k\le n$, 第二类 Stirling 数 $S(n,k)$ 定义为

$S(n,k)=\frac{1}{k!}\cdot \left|\right\{f:\{1,\dots ,n\}\to \{1,\dots ,k\}|f$ 是满射 $\left\}\right|.$

有时, 也将 $S(n,k)$ 记为 $\left\{\genfrac{}{}{0ex}{}{n}{k}\right\}$.

2性质

以下设 $1\le k\le n$ 为自然数.

•	有 $S(n,1)=S(n,n)=1$, 且当 $1<k<n$ 时, 有递推关系$$S(n,k)=S(n-1,k-1)+kS(n-1,k).$$

•	直接计算 $S(n,k)$ 的公式: $$S(n,k)=\frac{1}{k!}\sum _{i=0}^k(-1{)}^{k-i}(\genfrac{}{}{0ex}{}{k}{i})i^n.$$此公式可通过使用容斥原理计算定义中的计数而得.

•	第二类与第一类 Stirling 数可以视为彼此的逆矩阵: $$\begin{array}{rl}\sum _{j=k}^{n}s(n,j)S(j,k)& ={\delta }_{n,k},\\ \sum _{j=k}^{n}S(n,j)s(j,k)& ={\delta }_{n,k},\end{array}$$其中 ${\delta }_{n,k}$ 为 Kronecker $\delta$ 记号.

术语翻译

第二类 Stirling 数 • 英文 Stirling number of the second kind • 德文 Stirling-Zahl zweiter Art (f) • 法文 nombre de Stirling de deuxième espèce (m) • 日文 第 2 種 Stirling 数 • 韩文 제2종 Stirling 수