stirling number

斯特林数。

感觉斯特林数从构造角度能更好理解吧。

未更新完毕，待更新。

part 0 上升幂，下降幂

\(x^{\overline n}=\prod_{i=x}^{x+n-1}i\)

\(x^{\underline n}=\prod_{i=x-n+1}^{x} i\)

为什么引入？

我们发现对于差分运算下降幂与微分运算对普通幂有着类似方面。

而上升幂的性质要比下降幂要简洁，所以引出上升幂。

简单结论 \(x^{\overline n}=(-1)^n(-x)^{\underline n}\),\(x^{\underline n}=(-1)^n(-x)^{\overline n}\)​。

很显然的是 \(x^{\overline n},x^{\underline n}\) 都是 \(n\) 次多项式。

part1 第一类斯特林数

斯特林数是为了将普通幂将下降幂/上升幂联系起来。

第一类斯特林数是用普通幂表示上升幂。

相比较组合意义，用构造的理解更加便捷。

定义满足以下的 \(\begin{bmatrix}n\\m\end{bmatrix}\) 称为第一类斯特林数。 \[ x^{\overline n}=\sum_{i=0}^{n}\begin{bmatrix}n\\i\end{bmatrix}x^i \] 那么他是如何具有像组合意义那样的递推式的呢？

考虑： \[ x^{\overline {n+1}}=(x+n)x^{\overline{n}}=(x+n)\sum_{i=0}^{n}\begin{bmatrix}n\\i\end{bmatrix}x^i=\sum_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}x^{i+1}+n\begin{bmatrix}n\\i\end{bmatrix}x^i \] \[ [x^i]x^{\overline {n+1}}=[x^i]\sum_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}x^{i+1}+n\begin{bmatrix}n\\i\end{bmatrix}x^i \] \[ \begin{bmatrix}n+1\\i\end{bmatrix}=\begin{bmatrix}n\\i-1\end{bmatrix}+n\begin{bmatrix}n\\i\end{bmatrix} \] \[ \begin{bmatrix}n\\m\end{bmatrix}=\begin{bmatrix}n-1\\m-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\m\end{bmatrix} \] 下降幂转普通幂也可以根据 \(x^{\overline n}=(-1)^n(-x)^{\underline n}\) 得到类似结论。

---

part 2 第二类斯特林数

第二类斯特林数是用下降幂表示普通幂。

定义满足以下的 \(\begin{Bmatrix}n\\m\end{Bmatrix}\) 称为地二类斯特林数。 \[ x^n=\sum_{i=0}^{n}\begin{Bmatrix}n\\i\end{Bmatrix}x^{\underline i} \] \[ x^{n+1}=x\cdot x^{n}=x\sum_{i=0}^{n}\begin{Bmatrix}n\\i\end{Bmatrix}x^{\underline i}=\sum_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}x^{\underline {i+1}}+i\begin{Bmatrix}n\\i\end{Bmatrix}x^{\underline i} \] \[ [x^i]x^{n+1}=[x^i]x\cdot x^{n} \] \[ \begin{Bmatrix}n+1\\i\end{Bmatrix}=\begin{Bmatrix}n\\i-1\end{Bmatrix}+i\begin{Bmatrix}n\\i\end{Bmatrix} \] \[ \begin{Bmatrix}n\\m\end{Bmatrix}=\begin{Bmatrix}n-1\\m-1\end{Bmatrix}+m\begin{Bmatrix}n-1\\m\end{Bmatrix} \]

未完待续

自然数幂？ \[ \begin{aligned} &\sum_{i=1}^{n}i^a\\ &\sum_{i=1}^n\sum_{j\leq n}\begin{Bmatrix}a\\j\end{Bmatrix}i^{\underline{j}}\\ &\sum_{j\leq n}\begin{Bmatrix}a\\j\end{Bmatrix}\sum_{i\leq n}i^{\underline{j}}=\sum_{j\leq n}\begin{Bmatrix}a\\j\end{Bmatrix}\frac{(n+1)^{\underline{j+1}}}{j+1}\\ &\sum_{j\leq n}\frac{\mathrm{s}_2(a,j)}{j+1}(-1)^{j+1}(-(n+1))^{\overline{j+1}}\\ &\sum_{j\leq n}\frac{(-1)^{j+1}\mathrm{s}_2(a,j)}{j+1}x^{\overline{j+1}},x=(-n-1)\\ &\sum_{j\leq n}\frac{(-1)^{j+1}\mathrm{s}_2(a,j)}{j+1}\sum_{i\leq j+1}\begin{bmatrix}j+1\\i\end{bmatrix}x^i\\\ \end{aligned} \] 这个结论是正确的，验证代码。

#include<iostream>
#include<cstring>
using namespace std;
#define int long long
const int mod=998244353;
int str1[2000][2000],str2[2000][2000],c[2000][2000];
inline int qpow(int a,int b){
    int ret=1;
    while(b){
        if(b&1) ret=ret*a%mod;
        a=a*a%mod;b>>=1;
    }return ret;
}
int k;
int h[10000],b[10000],iv[2000];
inline int g(int n){
    int ans=0;
    for(int i=1;i<=n;i++) ans+=qpow(i,k);
    return ans%mod;
}
inline int f(int n){
    int tmp=1,ans=0;
    for(int i=0;i<=k+1;i++){
        ans+=tmp*h[i];ans%=mod;
        tmp=tmp*n%mod;
    }return (ans+mod)%mod;
}
int32_t main(){
    str1[1][1]=str2[1][1]=1;
    c[1][1]=c[1][0]=c[0][0]=1;
    for(int i=2;i<=1000;i++){
        c[i][0]=1;
        for(int j=1;j<=i;j++){
            str1[i][j]=(str1[i-1][j-1]+str1[i-1][j]*(i-1))%mod;
            str2[i][j]=(str2[i-1][j-1]+str2[i-1][j]*j)%mod;
            c[i][j]=(c[i-1][j-1]+c[i-1][j]);if(c[i][j]>=mod) c[i][j]-=mod;
        }
    }
    for(int i=1;i<=1000;i++) iv[i]=qpow(i,mod-2);
    cin>>k;
    for(int i=1;i<=k+1;i++){
        for(int j=i-1;j<=k;j++){
            int val=str1[j+1][i]*str2[k][j]%mod*iv[j+1];
            if(j&1) b[i]+=val,b[i]%-mod;
            else b[i]-=val,b[i]%=mod;
        }
        if(i&1) b[i]=-b[i];
    }
    for(int t=0;t<=k+1;t++){
        for(int i=t;i<=k+1;i++){
            h[t]+=c[i][t]*b[i];h[t]%=mod;
        }
    }
}

可以说常数巨大。

那么告诉我正确的是什么呢？

我们希望写出 \(s_k(n)\) 关于 \(k,n\) 的二元生成函数。

如我们只考虑 \(n\) 这一维，那么实际上我们什么也得不到。。。。

所

以应该关注 \(k\) 这一维。 \[ \begin{aligned} f_k&=s_{k}(n)x^k\\ \hat F(x)&=\sum_{k\geq 0}s_{k}(n)\frac{x^k}{k!}\\ \hat F(x)&=\sum_{k\geq 0}\sum_{i< n}i^k\frac{x^k}{k!}\\ \hat F(x)&=\sum_{i< n}\sum_{k\geq 0}i^k\frac{x^k}{k!}=\sum_{i< n}e^{ix}\\ \hat F(x)&=\frac{e^{nx}-1}{e^{x}-1} \end{aligned} \] 得到了对于任意 \(n\) 的关于 \(k\) 的生成函数。

\(e^x-1\) 没有逆，\([x^0](e^x-1)=0\)，所以我们要求 \(\frac{x}{e^x-1}\) 这样的，然后让他乘上 \(\frac{e^{nx}-1}{x}\)。 \[ \begin{aligned} \hat B(x)&=\frac{x}{e^x-1}\\ \hat B(x)=e^x\hat B(x)-x&\Longrightarrow b_n=\sum_{i\leq n}\binom{n}{i}b_i\\ \sum_{i\leq n-1}\binom{n}{i}b_i=[n=1]&\Longrightarrow b_{n-1}=[n=1]-\frac{1}{n}\sum_{i\leq n-2}\binom{n}{i}b_i\\ b_{n}=[n=0]&-\frac{1}{n+1}\sum_{i<n}\binom{n+1}{i}b_i\\ \end{aligned} \] 得到递推式，那么 \(b_0\) 应该是什么呢，根据洛必达不难发现 \(b_0=1\)。(也可以直接解n=1方程组)

如何求 \(s_k(n)\)。 \[ \begin{aligned} \hat H(x)=\frac{e^{nx}-1}{x}=\sum_{i\geq 1} \frac{n^i x^{i-1}}{i!}&=\sum_{i\geq 0}\frac{n^{(i+1)} x^{i}}{(i+1)!},\color{blueviolet}h_i=\frac{n^{i+1}}{i+1}\\ \hat S(x)=\frac{x}{1-e^x}\cdot \frac{1-e^{(n+1)x}}{x}&\Longrightarrow s_k=\sum_{i+j=k}\binom{k}{i}b_i\frac{n^{j+1}}{j+1} \end{aligned} \]

尽管我们算的是 \(\sum_{1\leq i\leq n-1}i^k\) 得到的却是 \(n^i\) 这样的多项式，但是你考虑一下是不是只需要把 \(n^k\) 这一项+1就好了。。。。。

完事了，注意带 hat 的函数表示是 egf 函数，我们提取系数后产生的原数列是不带 hat,但是加法卷积被变成了二项卷积。