第二類斯特林數

第二類斯特林數(Stirling Number of the 2nd Kind)，是用來計算一種問題：

將 $n$ 顆不同的小球放入 $k$ 個相同的箱子中，不允許空箱，有幾種方法數？

通常記做 $S(n, k)$ 或 $\begin{Bmatrix}n\\ k\end{Bmatrix}$。

如何計算

可以思考一下，現在有 $n$ 顆球， $k$ 個箱子：

1. $n - 1$ 顆球已經被放到了 $k - 1$個箱子中，現在要放入最後一顆球到最後一個空的箱子。
   方法數會是 $S(n - 1, k - 1)$。
2. $n - 1$ 顆球已經被放到了 $k$ 個箱子中，現在要放入最後一顆球到其中一個箱子。
   方法數會是 $C^n_1 \times S(n - 1, k)$ 。

因此可以寫出 $S(n, k)$ 的遞迴式：

而第二類斯特林數有以下性質：

1. $S(n, 0) = 0$
2. $S(n, 1) = 1$
3. $S(n, n) = 1$
4. $S(n, 2) = 2^{n-1} - 1$
5. $S(n, n - 1) = C^n_2$
6. $S(n, k) = S(n - 1, k - 1) + C^n_1 \times S(n - 1, k)$

通式

斯特林數的通式可以寫成：

或者

或者

證明：

1. 考慮將 $n$ 個有區別的球放入 $m$ 個有區別的盒中，且無一個盒是空的，命 $S_a(n, m)$ 為方案數目。
2. 考慮 $m$ 個有區別的盒中，最少存在 1 個盒是空的。因為在不考慮其他盒是否為空的，某一特定的盒不放入球，$n$ 個球每個球有 $(m − 1)$ 個選擇。$m$ 個盒中，任何 1 個皆可為空，所以其方案數目是 $\binom{m}{1}(m-1)^n$ 。
3. 考慮 $m$ 個有區別的盒中，最少存在 2 個盒是空的。因為在不考慮其他盒是否為空的，某一特定的盒不放入球，$n$ 個球每個球有 $(m − 2)$ 個選擇。$m$ 個盒中，任何 2 個皆可為空，所以其方案數目是 $\binom{m}{2}(m-2)^n$ 。
4. 如此這般…直到…
5. 考慮 $m$ 個有區別的盒中，最少存在 $m-1$ 個盒是空的。因為在不考慮其他盒是否為空的，某一特定的盒不放入球，$n$ 個球每個球有 $m - (m-1) = 1$ 個選擇。$m$ 個盒中，任何 $m-1$ 個皆可為空，所以其方案數目是 $\binom{m}{m-1}(1)^n$ 。
6. 計算 $S_a(n, m)$，可將「任意放入 m 個盒」的方案數目 $m^n$，減去「1 個、2 個、· · · 、$(m − 1)$個盒是空的」數目便可，由容斥原理可得：
   $$S_a(m, n) = m^n - \binom{m}{1}(m - 1)^n + \binom{m}{2}(m - 2)^n - \cdots + (-1)^{m-1}\binom{m}{m-1}$$
   $$=\sum^{m-1}_{k=0}(-1)^k\binom{m}{k}(m-k)^n$$
7. 因為 $S(n, m)$ 僅考慮相同盒子狀況，所以除掉 $m!$ 的盒子排序：
   $$S(n, m)=\frac{1}{m!}\sum^{m-1}_{k=0}(-1)^k\binom{m}{k}(m-k)^n$$

Sample Code

可以利用之前提到的 $O(n)$ 預處理組合數，時間複雜度是 $O(k \log n)$：

ll qpow(ll a, ll b) {
    ll res = 1;
    a %= MOD;
    while (b > 0) {
        if (b & 1) {
            res = res * a % MOD;
        }
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

ll inverse_mod(int a) {
    return qpow(a, MOD - 2);
}

ll fact[MAXN], inv_fact[MAXN];

void precompute_combination() {
    fact[0] = 1;
    inv_fact[0] = 1;

    for (int i = 1; i < MAXN; i++) {
        fact[i] = fact[i - 1] * i % MOD;
    }

    inv_fact[MAXN - 1] = inverse_mod(fact[MAXN - 1]);
    for (int i = MAXN - 2; i >= 1; i--) {
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;
    }
}

ll nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fact[n] * inv_fact[r] % MOD * inv_fact[n - r] % MOD;
}

ll stirling2(int n, int k) {
    ll res = 0;
    for (int i = 0; i <= k; i++) {
        ll term = nCr(k, i) * qpow(i, n) % MOD;
        if ((k - i) & 1) {
            res = (res - term + MOD) % MOD; // 注意負數取模
        } else {
            res = (res + term) % MOD;
        }
    }
    res = res * inv_fact[k] % MOD;
    return res;
}

Reference

第二類斯特林數(Stirling Number of the 2nd Kind)