什么是两类斯特林数

斯特林数是组合数学中用来描述“把元素组织成若干部分”的一类计数工具，常见的有两类：第一类斯特林数和第二类斯特林数。

它们名字相近，但数的对象完全不同：

• 第一类斯特林数：数的是排列可以分成多少个循环；
• 第二类斯特林数：数的是集合可以分成多少个非空子集。

第一类斯特林数

第一类斯特林数通常记作

$c(n,k)$

或者

$\left[{n \atop k}\right]$

表示：

将 $n$ 个不同元素排成一个排列，并且这个排列恰好分解成 $k$ 个循环的方案数。

这里的“循环”指的是排列的循环表示。

例如 $n=3$ 时，元素为 $1,2,3$。

恰好分成 $1$ 个循环的排列有：

$(1\ 2\ 3), (1\ 3\ 2)$

所以

$c(3,1)=2$

恰好分成 $2$ 个循环的排列有：

$(1)(2\ 3), (2)(1\ 3), (3)(1\ 2)$

所以

$c(3,2)=3$

恰好分成 $3$ 个循环的排列只有：

$(1)(2)(3)$

所以

$c(3,3)=1$

因此第一类斯特林数关注的是：

一个排列的循环结构。

它的递推式是：

$$c(n,k)=c(n-1,k-1)+(n-1)c(n-1,k)$$

解释如下：

考虑第 $n$ 个元素。

如果 $n$ 单独成为一个循环，那么前 $n-1$ 个元素需要形成 $k-1$ 个循环，贡献为 $c(n-1,k-1)$。

如果 $n$ 插入到已有循环中，那么前 $n-1$ 个元素已经形成 $k$ 个循环。一个排列的循环表示中，总共有 $n-1$ 个位置可以插入 $n$，所以贡献为 $(n-1)c(n-1,k)$。

初始条件为：

$$c(0,0)=1$$

并且当 $n>0$ 时：

$$c(n,0)=0$$

当 $k>n$ 时：

$$c(n,k)=0$$

需要注意的是，有些资料会使用带符号第一类斯特林数，记作 $s(n,k)$。它和无符号第一类斯特林数的关系是：

$$s(n,k)=(-1)^{n-k}c(n,k)$$

竞赛中如果只是计数排列循环，通常用的是无符号第一类斯特林数。

第二类斯特林数

第二类斯特林数通常记作

$S(n,k)$

或者

$\left\{{n \atop k}\right\}$

表示：

将 $n$ 个不同元素划分成 $k$ 个非空集合的方案数。

这里的 $k$ 个集合之间没有顺序。

例如 $n=3$ 时，元素为 $1,2,3$。

划分成 $1$ 个非空集合，只有：

$\{1,2,3\}$

所以

$S(3,1)=1$

划分成 $2$ 个非空集合，有：

$\{1\},\{2,3\}$

$\{2\},\{1,3\}$

$\{3\},\{1,2\}$

所以

$S(3,2)=3$

划分成 $3$ 个非空集合，只有：

$\{1\},\{2\},\{3\}$

所以

$S(3,3)=1$

因此第二类斯特林数关注的是：

把不同元素分成若干个没有顺序的非空组。

它的递推式是：

$$S(n,k)=S(n-1,k-1)+kS(n-1,k)$$

解释如下：

考虑第 $n$ 个元素。

如果 $n$ 单独组成一个新集合，那么前 $n-1$ 个元素需要分成 $k-1$ 个非空集合，贡献为 $S(n-1,k-1)$。

如果 $n$ 放入已有集合，那么前 $n-1$ 个元素已经分成 $k$ 个非空集合，$n$ 可以放进其中任意一个集合，所以贡献为 $kS(n-1,k)$。

初始条件为：

$$S(0,0)=1$$

并且当 $n>0$ 时：

$$S(n,0)=0$$

当 $k>n$ 时：

$$S(n,k)=0$$

两类斯特林数的区别

类型	常用记号	计数对象	关键词
第一类斯特林数	$c(n,k)$ 或 $\left[{n \atop k}\right]$	$n$ 个元素的排列分解成 $k$ 个循环	排列、循环
第二类斯特林数	$S(n,k)$ 或 $\left\{{n \atop k}\right\}$	$n$ 个元素划分成 $k$ 个非空集合	集合划分、分组

一个简单的记忆方式是：

• 第一类斯特林数和排列有关；
• 第二类斯特林数和集合划分有关。

和多项式的关系

两类斯特林数还可以看成普通幂和阶乘幂之间的转换系数。

第一类斯特林数和下降幂有关。

下降幂定义为：

$$x^{\underline n}=x(x-1)(x-2)\cdots(x-n+1)$$

它可以展开成：

$$x^{\underline n}=\sum_{k=0}^{n}s(n,k)x^k$$

这里的 $s(n,k)$ 是带符号第一类斯特林数。

第二类斯特林数则可以把普通幂展开成下降幂：

$$x^n=\sum_{k=0}^{n}S(n,k)x^{\underline k}$$

这说明第二类斯特林数可以理解为：

把 $n$ 个独立选择整理成若干个非空组的计数系数。

和满射的关系

第二类斯特林数还有一个常用解释。

把 $n$ 个不同元素分到 $k$ 个有编号的盒子里，并且要求每个盒子非空，这就是从 $n$ 个元素到 $k$ 个盒子的满射数量。

先把 $n$ 个元素分成 $k$ 个非空集合，有 $S(n,k)$ 种方法。

再把这 $k$ 个集合分配给 $k$ 个有编号的盒子，有 $k!$ 种方法。

所以满射数量为：

$$k!S(n,k)$$

因此：

$$S(n,k)=\frac{\text{从 } n \text{ 个元素到 } k \text{ 个元素的满射数}}{k!} $$

小例子对比

当 $n=3$ 时，两类斯特林数分别为：

第一类斯特林数：

$k$	$c(3,k)$
$1$	$2$
$2$	$3$
$3$	$1$

第二类斯特林数：

$k$	$S(3,k)$
$1$
$2$	$3$
$3$	$1$

虽然这里有些数看起来一样，但它们的含义完全不同。

$c(3,1)=2$ 数的是 $3$ 个元素构成一个循环的排列数量。

$S(3,1)=1$ 数的是 $3$ 个元素全部放进同一个集合的划分数量。

一句话总结

第一类斯特林数数的是：
$n$ 个不同元素的排列可以分解成 $k$ 个循环的方案数。

第二类斯特林数数的是：
$n$ 个不同元素可以划分成 $k$ 个非空无序集合的方案数。