imicola 斯特林数,欧拉数
斯特林数,欧拉数

斯特林数,欧拉数

658 字 · 约 2 分钟

第一类斯科特数

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

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

{⋯ ,1,2,3,1,2,3,1,2,3,1,2,⋯ }\{\cdots,\textcolor{blue}{1,2,3},1,\textcolor{red}{2,3,1},2,\textcolor{green}{3,1,2},\cdots\}

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

第一类斯科特数递推公式

c(n,k)=c(n−1,k−1)+(n−1)⋅c(n−1,k)c(n,k) = c(n - 1,k -1 ) + (n - 1)\cdot c(n-1,k)

其中递推的初始条件我们规定为

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

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

应用:

  • 在排列的循环结构或者有向图的环的计数中使用
  • 在阶乘多项式展开中使用
    xn‾=x(x−1)⋯(x−n+1)=∑k=0ns(n,k)skx^{\underline{n}} = x(x-1)\cdots(x-n+1) = \sum\limits^{n}_{k=0}s(n,k)s^k
  • 其中 s(n,k)s(n,k)即有符号的第一类斯科特数

第二类斯科特数

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

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

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

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

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

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

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

S(n,k)=1k!∑i=0k(−1)i(ki)(k−i)nS(n,k) = \frac{1}{k!} \sum_{i=0}^{k} (-1)^i \binom{k}{i} (k-i)^n
可以在O(k)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;
    }
};
cpp

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

知识关联

0 反向链接 · 2 提及笔记
局部关系图谱 悬停高亮 · 点击跳转