# 5 斯特林数

斯特林数分为两类，分别用于解决不同类型的组合划分问题。

---

## 5.1 第一类斯特林数（无符号）

第一类斯特林数 $ s(n, k) $（通常记作 $ \left[ {n \atop k} \right] $，这里指**无符号第一类斯特林数**）表示将 $ n $ 个**不同的元素**排成 $ k $ 个**非空的圆排列**（即循环排列）的方案数。

> 圆排列：旋转视为相同，例如 $(a,b,c)$、$(b,c,a)$、$(c,a,b)$ 视为同一个圆排列。

### 组合意义
- 将 $ n $ 个不同小球分成 $ k $ 个非空的环（每个环至少一个球），不考虑环之间的顺序，但环内是循环有序的。

### 递推公式

$
s(n, k) = (n - 1) \cdot s(n - 1, k) + s(n - 1, k - 1)
$

### 递推解释：
- **第 $ n $ 个元素插入到已有的某个圆排列中**：  
  对于任意一个已有的圆排列（共 $ k $ 个），有 $ n - 1 $ 个“间隙”可以插入（因为一个长度为 $ m $ 的圆排列有 $ m $ 个插入位置，所有已有元素总数为 $ n - 1 $，所以总共有 $ n - 1 $ 个位置），因此贡献为 $ (n - 1) \cdot s(n - 1, k) $。
- **第 $ n $ 个元素单独构成一个新的圆排列**：  
  此时前 $ n - 1 $ 个元素需组成 $ k - 1 $ 个圆排列，贡献为 $ s(n - 1, k - 1) $。

### 边界条件

- $ s(0, 0) = 1 $
- $ s(n, 0) = 0 $（当 $ n > 0 $）
- $ s(0, k) = 0 $（当 $ k > 0 $）
- $ s(n, k) = 0 $（当 $ k > n $）
- $ s(n, 1) = (n - 1)! $：$ n $ 个元素构成一个圆排列的方案数
- $ s(n, n) = 1 $：每个元素自成一个环

#### 问题：
将 3 个不同的小球（标号为 A、B、C）排成 2 个非空的圆排列，有多少种方案？

##### 即求：s(3,2)=?
##### 步骤 1：列出所有可能的划分方式
我们要把 {A, B, C} 分成 2 个非空的环。由于环内顺序是循环的（旋转等价），且环之间无序（盒子相同），我们只关心集合的划分和每个子集的圆排列结构。

可能的集合划分（分成两个非空子集）有：

{A}, {B, C}
{B}, {A, C}
{C}, {A, B}
共 3 种划分方式（这其实是第二类斯特林数 S(3,2)=3）。

### 动态规划实现（伪代码）

```python
dp = [[0] * (k+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(1, n+1):
    for j in range(1, min(i, k)+1):
        dp[i][j] = (i - 1) * dp[i-1][j] + dp[i-1][j-1]
```

# 5.2 第二类斯特林数

第二类斯特林数 $ S(n, k) $（也记作 $ \left\{ {n \atop k} \right\} $）表示将 $ n $ 个**不同**的物体划分为 $ k $ 个**非空、无序**集合的方案数。

等价地，可以理解为：  
将 $ n $ 个**不同的小球**放入 $ k $ 个**相同的盒子**中，且**每个盒子非空**的方案数。

## 递推公式

第二类斯特林数满足如下递推关系：

$
S(n, k) = k \cdot S(n-1, k) + S(n-1, k-1)
$

### 递推解释：
- **第 $ n $ 个球放入已有的 $ k $ 个盒子之一**：有 $ k $ 种选择，对应 $ k \cdot S(n-1, k) $；
- **第 $ n $ 个球单独构成一个新的盒子**：此时前 $ n-1 $ 个球需分成 $ k-1 $ 个非空集合，对应 $ S(n-1, k-1) $。

## 边界条件

- $ S(0, 0) = 1 $：0 个元素分成 0 个集合，有一种方式（空划分）；
- $ S(n, 0) = 0 $（当 $ n > 0 $）：非空元素无法分成 0 个非空集合；
- $ S(0, k) = 0 $（当 $ k > 0 $）：没有元素却要分成正数个非空集合，不可能；
- $ S(n, k) = 0 $（当 $ k > n $）：集合数不能超过元素数；
- $ S(n, 1) = 1 $：所有元素放在一个集合中；
- $ S(n, n) = 1 $：每个元素各自成一个集合。

## 动态规划实现（伪代码）

```python
dp = [[0] * (k+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(1, n+1):
    for j in range(1, min(i, k)+1):
        dp[i][j] = j * dp[i-1][j] + dp[i-1][j-1]
```

5 斯特林数

斯特林数分为两类，分别用于解决不同类型的组合划分问题。

5.1 第一类斯特林数（无符号）

第一类斯特林数 $ s(n, k) $（通常记作 $ \left[ {n \atop k} \right] $，这里指无符号第一类斯特林数）表示将 $ n $ 个不同的元素排成 $ k $ 个非空的圆排列（即循环排列）的方案数。

圆排列：旋转视为相同，例如 $(a,b,c)$、$(b,c,a)$、$(c,a,b)$ 视为同一个圆排列。

组合意义

将 $ n $ 个不同小球分成 $ k $ 个非空的环（每个环至少一个球），不考虑环之间的顺序，但环内是循环有序的。

递推公式

$ s(n, k) = (n - 1) \cdot s(n - 1, k) + s(n - 1, k - 1) $

递推解释：

第 $ n $ 个元素插入到已有的某个圆排列中：
对于任意一个已有的圆排列（共 $ k $ 个），有 $ n - 1 $ 个“间隙”可以插入（因为一个长度为 $ m $ 的圆排列有 $ m $ 个插入位置，所有已有元素总数为 $ n - 1 $，所以总共有 $ n - 1 $ 个位置），因此贡献为 $ (n - 1) \cdot s(n - 1, k) $。
第 $ n $ 个元素单独构成一个新的圆排列：
此时前 $ n - 1 $ 个元素需组成 $ k - 1 $ 个圆排列，贡献为 $ s(n - 1, k - 1) $。

边界条件

$ s(0, 0) = 1 $
$ s(n, 0) = 0 $（当 $ n > 0 $）
$ s(0, k) = 0 $（当 $ k > 0 $）
$ s(n, k) = 0 $（当 $ k > n $）
$ s(n, 1) = (n - 1)! $：$ n $ 个元素构成一个圆排列的方案数
$ s(n, n) = 1 $：每个元素自成一个环

问题：

将 3 个不同的小球（标号为 A、B、C）排成 2 个非空的圆排列，有多少种方案？

即求：s(3,2)=?

步骤 1：列出所有可能的划分方式

我们要把 {A, B, C} 分成 2 个非空的环。由于环内顺序是循环的（旋转等价），且环之间无序（盒子相同），我们只关心集合的划分和每个子集的圆排列结构。

可能的集合划分（分成两个非空子集）有：

{A}, {B, C} {B}, {A, C} {C}, {A, B} 共 3 种划分方式（这其实是第二类斯特林数 S(3,2)=3）。

动态规划实现（伪代码）

dp = [[0] * (k+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(1, n+1):
    for j in range(1, min(i, k)+1):
        dp[i][j] = (i - 1) * dp[i-1][j] + dp[i-1][j-1]

5.2 第二类斯特林数

第二类斯特林数 $ S(n, k) $（也记作 $ \left{ {n \atop k} \right} $）表示将 $ n $ 个不同的物体划分为 $ k $ 个非空、无序集合的方案数。

等价地，可以理解为：
将 $ n $ 个不同的小球放入 $ k $ 个相同的盒子中，且每个盒子非空的方案数。

递推公式

第二类斯特林数满足如下递推关系：

$ S(n, k) = k \cdot S(n-1, k) + S(n-1, k-1) $

递推解释：

第 $ n $ 个球放入已有的 $ k $ 个盒子之一：有 $ k $ 种选择，对应 $ k \cdot S(n-1, k) $；
第 $ n $ 个球单独构成一个新的盒子：此时前 $ n-1 $ 个球需分成 $ k-1 $ 个非空集合，对应 $ S(n-1, k-1) $。

边界条件

$ S(0, 0) = 1 $：0 个元素分成 0 个集合，有一种方式（空划分）；
$ S(n, 0) = 0 $（当 $ n > 0 $）：非空元素无法分成 0 个非空集合；
$ S(0, k) = 0 $（当 $ k > 0 $）：没有元素却要分成正数个非空集合，不可能；
$ S(n, k) = 0 $（当 $ k > n $）：集合数不能超过元素数；
$ S(n, 1) = 1 $：所有元素放在一个集合中；
$ S(n, n) = 1 $：每个元素各自成一个集合。

动态规划实现（伪代码）

dp = [[0] * (k+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(1, n+1):
    for j in range(1, min(i, k)+1):
        dp[i][j] = j * dp[i-1][j] + dp[i-1][j-1]

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com