【编程数论】第二类斯特林数s(n, k)教程

定义

性质

1. 边界条件

• $S(n,0)=\{\begin{array}{ll}1,& n=0\\ 0,& n>0\end{array}$：当 $n=0$ 时，只有一种划分方式，即空集；当 $n>0$ 时，无法划分成 0 个非空子集，所以方法数为 0 。
• $S(n,n)=1$：$n$ 个不同元素划分成 $n$ 个非空子集，只能是每个元素单独构成一个子集，只有 1 种划分方法。
• $S(n,1)=1$：$n$ 个不同元素划分成 1 个非空子集，也就是所有元素都在一个子集中，只有 1 种划分方式。
2. 递推关系
   $S(n,k)=kS(n-1,k)+S(n-1,k-1)$
   理解方式：考虑第 $n$ 个元素的放置情况。
• 若第 $n$ 个元素单独构成一个子集，那么剩下 $n-1$ 个元素要划分成 $k-1$ 个非空子集，方法数为 $S(n-1,k-1)$ 。
• 若第 $n$ 个元素不单独构成一个子集，那么它要放入已经划分好的 $k$ 个子集中的某一个，有 $k$ 种放法，而剩下 $n-1$ 个元素划分成 $k$ 个非空子集的方法数为 $S(n-1,k)$ ，所以这种情况下的方法数为 $kS(n-1,k)$ 。
• 两种情况相加，就得到了递推公式。

计算方法

1. 递推法
   根据递推关系 $S(n,k)=kS(n-1,k)+S(n-1,k-1)$ ，可以通过编写程序或者手动计算来求解。以计算 $S(5,3)$ 为例：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 5;
    int k = 3;
    
    // 初始化二维数组 dp
    vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
    
    // 设置边界条件 S(i, 0)
    for (int i = 0; i <= n; i++) {
        dp[i][0] = (i > 0) ? 0 : 1;
    }
    
    // 动态规划计算 S(n, k)
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= min(i, k); j++) {
            dp[i][j] = j * dp[i - 1][j] + dp[i - 1][j - 1];
        }
    }
    
    // 输出结果
    cout << dp[n][k] << endl;
    return 0;
}

2. 公式法
   $S(n,k)=\frac{1}{k!}{\sum }_{i=0}^k(-1{)}^i(\genfrac{}{}{0ex}{}{k}{i})(k-i{)}^n$
   其中 $\left(\genfrac{}{}{0ex}{}{k}{i}\right)$ 是组合数，表示从 $k$ 个元素中选取 $i$ 个元素的组合方式数。这个公式是通过容斥原理推导得出的。

   
   

应用

1. 集合划分问题
   在组合计数中，许多集合划分问题可以转化为计算第二类斯特林数。例如，将 $n$ 个不同的球放入 $k$ 个相同的盒子中，且每个盒子都不为空，方法数就是 $S(n,k)$ 。如果盒子是不同的，那么方法数为 $k!S(n,k)$ ，因为对于每种将球放入相同盒子的划分方式，都可以对 $k$ 个盒子进行全排列，得到不同的放入不同盒子的方式。
2. 多项式表示
   第二类斯特林数可以用于将幂函数 $x^n$ 表示为下降阶乘幂 $(x{)}_k=x(x-1)\cdots (x-k+1)$ 的线性组合，即 $x^n={\sum }_{k=0}^{n}S(n,k)(x{)}_k$ 。
3. 算法分析
   在一些涉及分组、分配等操作的算法中，可能会用到第二类斯特林数来分析算法的复杂度或者计算不同情况下的方案数。例如，在将任务分配给不同小组的场景中，可以利用第二类斯特林数来计算合理的分配方案数量。