CV自skyh博客
第一类斯特林数
定义
(S_1(n,m))为(n)个数形成(m)个环的方案数
元素元素之间区分，环与环直接不区分
递推公式
(egin{bmatrix}n\mend{bmatrix}=egin{bmatrix}n-1\m-1end{bmatrix}+(n-1)*egin{bmatrix}n-1\mend{bmatrix})
考虑第(n)个数单独成环还是放进之前的环里就可以了
性质
- 第一类斯特林数第(n)行的和等于(n!)
(sum limits_{i=0}^negin{bmatrix}n\iend{bmatrix}=n!)
考虑(n)个元素的排列(p)，建立(i ightarrow p_i)的置换，发现会形成若干个环，这和第(n)行的第一类斯特林数的方案是一一对应的
- 可以用普通幂表示上升幂
(x^{overline n}=sum limits_{i=0}^n egin{bmatrix}n\iend{bmatrix}x^i)
证明可以通过数学归纳法：
(n=0)时原式显然成立
设原式在(n)时成立
则在(n+1)时，有
后面的式子将((x+n))乘出来，发现正好符合第一类斯特林数转移
- 用普通幂表示下降幂可以用类似的方法求出，这里给出一种更妙的求法
首先对于普通幂 显然有(x^n=(-x)^n*(-1)^n)
对于下降幂与上升幂同样有
(x^{overline n}=(-x)^{underline n}*(-1)^n)
(x^{underline n}=(-x)^{overline n}*(-1)^n)
将该式代入(x^{overline n}=sum limits_{i=0}^n egin{bmatrix}n\iend{bmatrix}x^i)
整理得到(x^{underline n}=sum limits_{i=0}^n egin{bmatrix}n\iend{bmatrix}(-1)^{n-i}x^i)
同一行第一类斯特林数
套用第二个性质可以分治(FFT)做到(nlog^2)
第二类斯特林数
定义
(S_2(n,m))表示(n)个数形成(m)个集合的方案数
其中元素与元素之间区分，集合与集合不区分
递推公式
(egin{Bmatrix}n\mend{Bmatrix}=egin{Bmatrix}n-1\m-1end{Bmatrix}+m*egin{Bmatrix}n-1\mend{Bmatrix})
还是按照实际含义去考虑第(n)个数单独作为一个集合还是放进之前的集合
性质
1.下降幂表示普通幂
(x^n=sum limits_{i=0}^n egin{Bmatrix}n\iend{Bmatrix}x^{underline i})
证明(1):类似第一类斯特林数，数学归纳法
证明(2):(x^n=sum_{i=0}^negin{Bmatrix}n\iend{Bmatrix}inom{x}{i} i!)
考虑(x^n)的实际含义，有(n)个元素，每次有(x)个集合可选择
所以即(x)个集合中选出(i)个集合然后将(n)个元素放入这(i)个集合，又因为第二类斯特林数中的集合是无差别的，所以要乘上(i!)
整理可得上面式子
2.同样代入负数形式，可以得到上升幂表示普通幂
(x^n=sum limits_{i=0}^n egin{Bmatrix}n\iend{Bmatrix}(-1)^{n-i}x^{overline i})
求法
求单点第二类斯特林数：
设将(n)个元素放入至少(x)个集合的方案数为(g_x)(也就是允许空集
将(n)个元素放入恰好(x)个集合的方案数为(f_x)(也就是不允许空集
(g_i = i^n)
(g_i = sum_{j=1}^{i} f_j inom{i}{j})
根据二项式反演得到
(f_i = sum_{j=1}^{i} g_j inom{i}{j} (-1)^{i-j})
(f_i = sum_{j=1}^{i} j^n inom{i}{j} (-1)^{i-j})
然后就可以(O(n))求单点第二类斯特林数的值了
设有(n)个不同的元素,(m)个不同集合
设(g_x)为恰好x个集合为空的方案数
(f_x)为至少x个集合为空的方案数
(f_x=inom{m}{x}(m-x)^n)
(f_x=sum limits_{i=x}^{m}inom{i}{x}g_i)
二项式反演得到:
(g_x=sum limits_{i=x}^{m}(-1)^{i-x}inom{i}{x}f_i)
代入(x=0)，得到
(egin{Bmatrix}n\mend{Bmatrix}=frac{1}{m!}*sum limits_{i=0}^{m}(-1)^iinom{m}{i}(m-i)^n)
发现是个卷积式，所以求一行第二类斯特林数可以(nlog_n)求