斯特林数

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

组合意义：

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

递推公式：

[s_{i,j}=s_{i-1,j-1}+(i-1) imes s_{i-1,j} ]

与阶乘关系：

[sum_{i=0}^ns_{n,i}=n! ]

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

与上升幂的关系：

[m^{overline{n}}=sum_{i=0}^ns_{n,i} imes m^i ]

证明：数学归纳法

快速求法：

行：

(O(nlog^2n))的做法

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

[prod_{i=0}^{n-1}(x+i) ]

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

列：

待填

---

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

组合意义：

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

递推公式：

[S_{i,j}=S_{i-1,j-1}+j imes S_{i-1,j} ]

一个重要公式：

[n^m=sum _{i=0}^mS_{m,i}i!dbinom{n}{i} ]

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

与下降幂的关系：

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

[n^m=sum_{i=0}^mS_{m,i}n^{underline{i}} ]

快速求法：

行：

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

[S_{m,n}n!=sum_{i=0}^n(-1)^{n-i}i^mdbinom{n}{i} ]

展开二项式并移项得

[S_{m,n}=sum_{i=0}^nfrac{(-1)^{n-i}}{(n-i)!}frac{i^m}{i!} ]

列：

待填

---

反转公式

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

[egin{array}{l} x^{ar{n}}=sum_{i=0}^{n} s_{n, i} x^{i} \ x^{n}=sum_{i=0}^{n} S_{n, i} x^{underline{i}} end{array} ]

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

[(-x)^{underline{n}}=(-1)^{n} x^{ar{n}} ]

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

[egin{aligned} x^{n} &=sum_{i=0}^{n} S_{n, i}(-1)^{n-i} x^{ar{i}} \ x^{underline{n}} &=sum_{i=0}^{n} s_{n, i}(-1)^{n-i} x^{i} end{aligned} ]

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

[egin{array}{l} sum_{i=m}^{n} S_{n, i} s_{i, m}(-1)^{n-i}=[n=m] \ sum_{i=m}^{n} s_{n, i} S_{i, m}(-1)^{n-i}=[n=m] end{array} ]

一个经典问题

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

(O(n^6))的做法

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

[f_{n,m}=inom{inom{n}{2}}{m}-sum_{i=1}^nsum_{j=1}^mf_{i,j}inom{inom{n-i}{2}}{m}inom{n-1}{i-1} ]

(O(n^5))的做法

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

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

[sum_{i=1}^nS_{n,i}(i-1)!(-1)^{i-1}=[n=1] ]

所以如果我们求一个(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)号点所在集合转移即可

[g_{n,c,e}=sum_{i=1}^ninom{n-1}{i-1}g_{n-i,c-1,e-inom{i}{2}} ]

所以最后答案就是(sum_{i=1}^nsum_{j=m}^{inom{n}{2}}g_{n,i,j}(j-1)!(-1)^{j-1}inom{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)的系数就好了，那么最后转移式就是

[g_{n,e}=sum_{i=1}^n(-1) imesinom{n}{i}g_{n-i,e-inom{i}{2}} ]

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

斯特林反演

咕咕咕