斯特林数

第一类斯特林数\(s_{n,m}\)

组合意义：

将\(n\)个不同数划分为\(m\)个圆排列的方案数

递推公式：

与阶乘关系：

意义就是一个圆排列可以看做一个置换，所有排列的方案就是\(n!\)

与上升幂的关系：

证明：数学归纳法

快速求法：

行：

\(O(n\log^2n)\)的做法

考虑构造第一类斯特林数的生成函数

分治\(NTT\)直接乘起来就好了，第\(m\)项系数就是\(s_{n,m}\)

列：

待填

第二类斯特林数\(S_{n,m}\)

组合意义：

将\(n\)个不同数划分为\(m\)个相同集合（集合非空，并且相同）的方案数

递推公式：

一个重要公式：

直接考虑组合意义，\(n^m\)表示将\(m\)个不同的数放入\(n\)个不同集合（可空）的方案数，直接枚举放入多少个不可空的集合即可

与下降幂的关系：

根据上面公式和\(\dbinom{n}{i}i!=n^{\underline{i}}\)可得

快速求法：

行：

考虑公式\(n^m=\sum _{i=0}^mS_{m,i}i!\dbinom{n}{i}\)，对其进行二项式反演得

展开二项式并移项得

列：

待填

反转公式

首先考虑两类斯特林数可将常幂，上升幂，下降幂联系起来

然后注意到上升幂和下降幂也有一定联系

我们将\((10)\)式中的两个式子两边都乘上一个\((-1)^n\)，就可以得到下面两个式子

如果将上面式子中\(x^{\bar{i}}\)和\(x^i\)分别用第一类斯特林数和第二类斯特林数展开，可以得到反转公式

一个经典问题

计算\(n\)个点\(m\)条边的无向连通图的方案数

\(O(n^6)\)的做法

考虑设\(f_{n,m}\)表示\(n\)个点\(m\)条边的无向连通图的方案数，转移拿所有的方案减去不合法的方案，考虑直接枚举\(1\)号点所在连通图的点数和边数，剩下的随便选，即

\(O(n^5)\)的做法

考虑一个比较套路的做法，我们设一个\(f_{k}\)表示\(n\)个点，随意划分成\(k\)个集合，满足只有在相同集合内的点有边，不同集合中不会有边，并且边数恰好为\(m\)的方案数

我们考虑一个有\(x\)的联通块的图会在一个\(f_k\)中被计算到\(S_{x,k}\)次，所以考虑使用上面的反转公式

所以如果我们求一个\(\sum_{i=1}^nf_{k}(k-1)!(-1)^{k-1}\)就可以得到所有\(n\)个点\(m\)条边的连通图的方案数

那么剩下的就是考虑怎么计算这个\(f_k\)了，考虑\(DP\)，设\(g_{n,c,e}\)表示\(n\)个点划分成了\(c\)个集合一共有\(e\)条边的方案数，这里我们在转移的时候强制每个集合都是连成完全图，最后假设有\(e\)条边，那么直接从中间选出\(m\)条边就好了，也就是直接乘一个组合数即可，转移同样也是枚举\(1\)号点所在集合转移即可

所以最后答案就是\(\sum_{i=1}^n\sum_{j=m}^{\binom{n}{2}}g_{n,i,j}(j-1)!(-1)^{j-1}\binom{j}{m}\)

\(O(n^4)\)的做法

考虑优化\(O(n^5)\)的做法，如果我们能让一个划分成\(k\)个集合的方案被计算到\((k-1)!\)次，那么我们就可以在\(DP\)的时候不用记录一个\(c\)了

要做到这个其实只需要在\(DP\)转移的时候不枚举\(1\)所在的联通块，而是枚举任意一个联通块就好了，那么对于一个划分成\(k\)个集合的方案就会被算到\(k!\)次了，那么如果是\((k-1)!\)次，只需要在最后枚举下\(1\)所在的联通块计数，那么一个联通块就会被计算\((k-1)!\)次了，对于\((-1)^{j-1}\)，可以直接在\(DP\)转移的时候乘一个\(-1\)的系数就好了，那么最后转移式就是

那么最后答案就是\(\sum_{i=1}^n\sum_{j=\binom{i}{2}}^{\binom{n}{2}}\binom{j}{m}\binom{n-1}{i-1}g_{n-i,j-\binom{i}{2}}\)

斯特林反演

咕咕咕

斯特林数

原文：https://www.cnblogs.com/roal-l/p/13097355.html