斯特林数

第二类斯特林数

也可以记做 $S_{n,k}$，表示将 $n$ 个 两两不同 的元素，划分为 $k$ 个 互不区分 的 非空子集 的方案数。

递推式 $S_{n,k}=S_{n-1,k-1}+k*S_{n-1,k}$

边界 $S_{n,0}=0$

考虑组合意义证明。

• 将新元素单独放入一个子集，有 $S_{n-1,k-1}$ 种方案。
• 将新元素放入一个现有的非空子集，有 $k*S_{n-1,k}$ 种方案。

应用

• $n$ 个 不同 的球放入 $m$ 个 相同 的盒子，不允许 有空盒子。正是第二类斯特林数

第 $i$ 个球，单独放入第 $j$ 个或者，和前面 $i-1$ 个球放入前 $j$ 个里由于不同所有乘上了 $j$。

f[0][0] = 1;
for (int i = 1; i <= n; i++)
{
    for (int j = 1; j <= m; j++)
    {
        f[i][j] = f[i - 1][j - 1] + j * f[i - 1][j];
    }
}
cout << f[n][m];

• $n$ 个 不同 的球放入 $m$ 个 不同 的盒子，不允许 有空，答案是 $S_{n,m}*m!$

因为盒子也不同因此乘上盒子的阶乘。

ans = 1;
for (int i = 1; i <= m; i++) ans *= i;
f[0][0] = 1;
for (int i = 1; i <= n; i++)
{
    for (int j = 1; j <= m; j++)
    {
        f[i][j] = f[i - 1][j - 1] + j * f[i - 1][j];
    }
}
cout << ans * f[n][r];

• $n$ 个 不同 的球放入 $m$ 个 相同 的盒子，允许 盒子有空，答案是 $\sum_{i=1}^mS(n,i)$

也就是在 $i$ 个盒子的方案数的和

f[0][0] = 1;
for (int i = 1; i <= n; i++)
{
    for (int j = 1; j <= m; j++)
    {
        f[i][j] = f[i - 1][j - 1] + j * f[i - 1][j];
    }
}
ans = 1;
for (int i = 1; i <= m; i++) ans += f[n][i];

• $n$ 个 不同 的球放入 $m$ 个 不同 的盒子，允许 有空。每个球都有 $m$ 种选择，是 $m^n$

int ans = 1;
for (int i = 1; i <= n; i++) ans *= m;

• $n$ 个 相同 的球放入 $m$ 个 相同 的盒子， 允许 有空。

for (int i = 0; i <= m; i++) f[0][i] = f[1][i] = 1;
for (int i = 0; i <= n; i++) f[i][0] = f[i][1] = 1;
for (int i = 2; i <= n; i++)
{
    for (int j = 2; j <= m; j++)
    {
        if (j > i) f[i][j] = f[i][i];
        else f[i][j] = f[i][j - 1] + f[i - j][j];
    }
}

• $n$ 个 相同 的球放入 $m$ 个 相同 的盒子，不允许 有空。

for (int i = 1; i <= n; i++) f[i][1] = 1;
for (int i = 1; i <= n; i++)
{
    for (int j = 2; j <= m; j++)
    {
        if (i >= j) f[i][j] = f[i - 1][j - 1] + f[i - j][j];
    }
}
cout << f[n][m];

• $n$ 个 相同 的球放入 $m$ 个 不同 的盒子，允许 有空。

插板法：$C_{n-1}^{m-1}$

• $n$ 个 相同 的球放入 $m$ 个 不同 的盒子， 允许 有空。

给每个盒子一个球，然后插板。$C_{n+m-1}^{m-1}$

第一类斯特林数

也可以记做 $S_{n,k}$，表示将 $n$ 个两两不同的元素，划分为 $k$ 个互不区分的非空 轮换 的方案数。轮换就是环形排列

递推式 $S_{n,k}=S_{n-1,k-1}+(n-1)S_{n-1,k}$

边界 $S_{n,0}=0$

考虑组合意义证明。

• 将新元素单独放入一个子集，有 $S_{n-1,k-1}$ 种方案。
• 将新元素放入一个现有的非空子集，有 $k*S_{n-1,k}$ 种方案。