当前位置：首页 > news >正文

学习笔记：第二类斯特林数

news 2026/5/12 10:46:58

代数推导天地灭，组合意义保平安。——@xzy_sf

0x01 概念

第二类斯特林数 \(\genfrac{\{}{\}}{0pt}{}{n}{k} \)，亦可记作 \(S(n,k)\)，表示将 \(n\) 个有标号的元素划分为 \(k\) 个无标号的非空子集的方案数。

由组合意义，\(n<k\) 时 \(\genfrac{\{}{\}}{0pt}{}{n}{k}=0\)，\(n=k\) 时 \(\genfrac{\{}{\}}{0pt}{}{n}{k}=1\)，\(k=0\) 时 \(\genfrac{\{}{\}}{0pt}{}{n}{k}=[n=0]\).

0x02 求法

递推求法

有如下递推式：

\[ \genfrac{\{}{\}}{0pt}{}{n}{k}=\genfrac{\{}{\}}{0pt}{}{n-1}{k-1}+k\cdot\genfrac{\{}{\}}{0pt}{}{n-1}{k}\\\genfrac{\{}{\}}{0pt}{}{n}{0}=[n=0]\]

由此可以 \(O(n^2)\) 预处理，且对模数没有要求。

考虑从组合意义证明这个递推式。

加入现在已经放好了 \(n-1\) 个元素，现在加入第 \(n\) 个；加入后共有 \(k\) 个非空子集。那么这个新元素有两种选择：独自作为一个新的子集，或者加入已有的某一子集。

先考虑前者。这种情况下，新加入元素的状态是确定的，我们不用管；而对于已有的 \(n-1\) 个元素，我们要把它们分进 \(k-1\) 个非空子集（剩下一个子集是新产生的）。因此这一情况有 \(\genfrac{\{}{\}}{0pt}{}{n-1}{k-1}\) 种方案。

再考虑后者。新加入的元素要加入某一子集，则有 \(k\) 种方案；我们还需要将已有的 \(n-1\) 个元素分进 \(k\) 个非空子集，则有 \(\genfrac{\{}{\}}{0pt}{}{n-1}{k}\) 种方案。两者相乘，则这一情况共有 \(k\cdot\genfrac{\{}{\}}{0pt}{}{n-1}{k}\) 种方案。

综上，递推式得证。

同行斯特林数求法

如何求同行第二类斯特林数的前几项（P5395）？

可以构造两个多项式：

\[A_i=\frac{i^n}{i!}\\ B_i=\frac{(-1)^i}{i!} \]

用 NTT 求出 \(C=A\ast B\)，那么 \(C_0\sim C_n\) 就是 \(\genfrac{\{}{\}}{0pt}{}{n}{0}\sim\genfrac{\{}{\}}{0pt}{}{n}{n}\).

为什么可以这样构造？

首先考虑一个问题：在允许存在空集的情况下，将 \(n\) 个有标号元素分为 \(k\) 个有标号子集，有几种方案？此时每个元素可以自由选择进入 \(k\) 个子集中的哪一个，因此答案为 \(k^n\).

然后考虑容斥掉空集后的方案数。钦定 \(i\) 个集合为空集，其余子集随意安排，那么选空集有 \(k\choose i\) 种方案；每个元素可以自由选择进入剩余的 \(k-i\) 个非空子集，那么选非空子集有 \((k-i)^n\) 种方案；两者相乘，总方案数即为 \({k\choose i}\cdot (k-i)^n\).

于是开始枚举 \(i\)，由容斥原理，我们得到如下和式：

\[f(k)=\sum\limits_{i=0}^k(-1)^i{k\choose i}\cdot (k-i)^n \]

其中 \(f(k)\) 表示将 \(n\) 个有标号元素分为 \(k\) 个有标号子集的方案数。由于第二类斯特林数的定义是无标号的，我们还需要除以一个全排列数，也即：

\[\begin{align*} \genfrac{\{}{\}}{0pt}{}{n}{k}&=\frac{1}{k!}f(k)\\ &=\frac{1}{k!}\sum\limits_{i=0}^k(-1)^i{k\choose i}\cdot (k-i)^n\\ &=\frac{1}{k!}\sum\limits_{i=0}^k(-1)^i\frac{k!}{i!(k-i)!}\cdot (k-i)^n\tag{1}\\ &=\sum\limits_{i=0}^k(-1)^i\frac{1}{i!(k-i)!}\cdot (k-i)^n\\ &=\sum\limits_{i=0}^k\frac{(k-i)^n}{(k-i)!}\cdot \frac{(-1)^i}{i!} \end{align*} \]

其中 \((1)\) 式即为第二类斯特林数的通项式。

注意到 \(\sum\) 后面的两个分式分别为 \(A_{k-i}\) 和 \(B_i\)，也即：

\[\begin{align*} \genfrac{\{}{\}}{0pt}{}{n}{k}&=\sum\limits_{i=0}^k A_{k-i}B_i\\ &=(A\ast B)_k \end{align*} \]

于是我们的做法是对的。~~瞪眼法万岁！~~

由于我们主要通过代数推导而非组合意义完成证明，所以 \(A\) 和 \(B\) 并没有什么特别直观的组合意义。~~一定要安一个的话确实也有，但不直观。~~

0x03 性质

性质 1

可以利用如下性质实现由普通幂到下降幂的转化：

\[x^n=\sum\limits_k\genfrac{\{}{\}}{0pt}{}{n}{k}x^{\underline k} \]

通过组合意义证明。左式表示将 \(n\) 个有标号元素放进 \(x\) 个有标号集合中的方案数；考虑右式的意义。

\(\genfrac{\{}{\}}{0pt}{}{n}{k}\) 表示将 \(n\) 个有标号元素分进 \(k\) 个无标号非空子集的方案数。在此基础上，将 \(x^{\underline k}\) 看做排列数 \(A_{x}^k\)，则右式表示：先将 \(n\) 个有标号元素放进 \(k\) 个无标号集合，再将 \(k\) 个无标号集合放进 \(x\) 个有标号组别，且不同集合在不同组别的方案数。

有点绕，但可以发现左右两边的组合意义是等价的，因此等式成立。

0x04 例题

例 1：P5395 第二类斯特林数·行

上面已经讲过了。

::::info[Code]

signed main(){cin>>n;init();for(int i=0;i<=n;++i)A[i]=mul(qpow(i,n),inv(jc(i))),B[i]=(i&1?p-inv(jc(i)):inv(jc(i)));polymul(A,B,n,n,f);for(int i=0;i<=n;++i)printf("%d ",f[i]);return printf("\n"),void();
}

::::

例 2：P6620 [省选联考 2020 A 卷] 组合数问题

咕咕咕

::::info[Code]

signed main(){n=read(),x=read(),p=read(),m=read();for(int i=0;i<=m;++i)a[i]=read();s[0][0]=1;for(int i=1;i<N;++i)s[i][1]=1;for(int i=2;i<N;++i)for(int j=1;j<N&&j<=i;++j)s[i][j]=(s[i-1][j-1]+mul(s[i-1][j],j))%p;for(int i=0;i<=m;++i){int res=0;for(int j=i;j<=m;++j)(res+=mul(s[j][i],a[j]))%=p;b[i]=res;}int res=0;for(int i=0;i<=m;++i)(res+=mul(b[i],mul(dmi(i),mul(qpow(x,i),qpow(x+1,n-i)))))%=p;return cout<<res<<"\n",0;
}

::::

例 3：P2791 幼儿园篮球题

咕咕咕

::::info[Code]

signed main(){n=read(),m=read(),s=read(),L=read();NTT::pre();//求同行第二类斯特林数，此时 A[i] 即为 S(L,i)while(s--){int ni=read(),mi=read(),ki=read();int inv_c=qpow(C(ni,ki),p-2);int res=0;for(int i=0;i<=min({ki,mi,L});++i)(((res+=mul(NTT::A[i],mul(C(mi,i),mul(C(ni-i,ki-i),jc[i]))))%=p)+=p)%=p;printf("%d\n",mul(res,inv_c));}return 0;
}

::::