斯特林数,欧拉数

第一类斯科特数

第一类斯科特数 $c(n,k)$ 表示 将$n$个不同元素排列成恰好$k$个”循环”的排列数

对于循环,我们可以理解为$\{1,2,3\}$与$\{2,3,1\}$ 与$\{3,2,1\}$均为一类循环,因为将这些数无限写下去的形式上是一致的

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

例子

• $c(3,1)=2$,即所有$3!$排列都在一个大循环中,此时有两种方案{(1,2,3),(1,3,2)}
• $c(3,2)=3$,此时有 (1)(2,3) | (2)(1,3) | (3)(1,2) 这样的组合方式
• $c(3,3)=1$,此时每个元素各自组成一个循环

第一类斯科特数递推公式
$c(n,k)=c(n-1,k-1)+(n-1)\cdot c(n-1,k)$
其中递推的初始条件我们规定为

• $c(0,0)=1\text{ , }c(n,0)=0(n>0)\text{ , }c(0,k)=0(k>0)$

上面为无符号第一类斯科特数的递归方式 如果想获得有符号类的可以使用 $s(n,k)=(-1{)}^{n-k}c(n,k)$方式得到

应用:

• 在排列的循环结构或者有向图的环的计数中使用
• 在阶乘多项式展开中使用

$$x^{\underline{n}}=x(x-1)\cdots (x-n+1)=\sum _{k=0}^{n}s(n,k)s^k$$

• 其中 $s(n,k)$即有符号的第一类斯科特数

第二类斯科特数

第二类斯科特数 $S(n,k)$ 表示将 $n$ 个不同元素划分为恰好 $k$ 个非空无序集合的方案数

对与三个不同元素{1,2,3}划分

• $S(3,1)=1$ ,即所有元素处于一个集合中
• $S(3,2)=3$:
  • $\{\{1\},\{2,3\}\},\{\{2\},\{1,3\}\},\{\{3\},\{1,2\}\}$

对第二类斯特林数有递推公式

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

• 初始条件我们规定
  $S(0,0)=1\text{ , }S(n,0)=0(n>0)\text{ , }S(0,k)=0(k>0)$

对与第二类斯特林数,我们有显式公式:

$$S(n,k)=\frac{1}{k!}\sum _{i=0}^k(-1{)}^i(\genfrac{}{}{0ex}{}{k}{i})(k-i{)}^n$$

可以在$O(k)$复杂度下计算出其值,可以结合快速组合数与快速幂计算,在最后给出板子

第一类欧拉数

i64 ksm(i64 a, i64 b, i64 mod = MOD)
{
    i64 res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
 
struct Stirling
{
    vector<i64> fac, inv_fac;
    i64 MAX_N;
    Stirling(i64 MAXK)
    {
        MAX_N = MAXK;
        fac.resize(MAX_N);
        inv_fac.resize(MAX_N);
        init();
    }
    // 预处理 [0, MOD-1] 阶乘及逆元
    void init()
    {
        fac[0] = 1;
        for (i64 i = 1; i < MAX_N; i++) fac[i] = fac[i - 1] * i % MOD;
        inv_fac[MAX_N - 1] = ksm(fac[MAX_N - 1], MOD - 2);
        for (i64 i = MAX_N - 2; i >= 0; i--) inv_fac[i] = inv_fac[i + 1] * (i + 1) % MOD;
    }
    // 计算 C(n, k) mod MOD，要求 n, k < MOD
    inline i64 C_small(i64 n, i64 k)
    {
        if (k < 0 || k > n) return 0;
        return fac[n] * inv_fac[k] % MOD * inv_fac[n - k] % MOD;
    }
    // Lucas 定理递归求解大组合数
    i64 C(i64 n, i64 k)
    {
        if (k < 0 || k > n) return 0;
        if (n < MOD && k < MOD) return C_small(n, k);
        return C(n / MOD, k / MOD) * C_small(n % MOD, k % MOD) % MOD;
    }
    i64 A(int n, int k) const
    {
        if (k < 0 || k > n) return 0;
        return fac[n] * inv_fac[n - k];
    }
    // 第二类斯特林数的显式表示
    i64 get_Stirling(int n, int k)
    {
        if (k < 0 || k > n) return 0;
        i64 res = 0;
        for (int i = 0; i <= k; ++i) {
            i64 term = C(k, i) * ksm(k - i, n) % MOD;
            // 符号： (-1)^i，根据公式 S(n,k) = 1/k! * sum_{i=0..k} (-1)^i C(k,i) (k-i)^n
            if (i & 1)
                res = (res - term + MOD) % MOD;
            else
                res = (res + term) % MOD;
        }
        res = res * inv_fac[k] % MOD; // 除以 k!
        return res;
    }
    // 第二类欧拉数计算
    i64 sec_Eulr(int n, int k)
    {
        return (get_Stirling(n, k) * fac[k]) % MOD;
    }
};

其实就是在快速组合数上进行了添加