卧薪尝胆,厚积薄发。
斯特林数与贝尔数
Date: Sat Dec 29 21:01:49 CST 2018
In Category:
总结
第一类斯特林数(斯特林轮换数)
定义:
记为
$\begin{bmatrix}n\\ m\end{bmatrix}$
或
$S_1(n,m)$
,计算将
$n$
个元素排成
$m$
个轮换的方案数。
性质:
递推公式:
$$
S_1(n,m)=S_1(n-1,m-1)+(n-1)S_1(n-1,m)
$$
也可以说成是恰好包含
$m$
个轮换的
$n$
个元素的排列个数,故:
$$
\sum_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}=n!
$$
第一类斯特林数的生成函数为:
$$
\sum_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}x^i=\prod_{i=0}^{n-1}(x+i)
$$
考虑乘上一个
$(x+n)$
时整个函数每一项的变化就可以得到这个式子。
一个特殊值:
$$
\begin{bmatrix}n\\2\end{bmatrix}=(n-1)!H_{n-1}
$$
$H$
是调和数:
$$
H_n=\sum_{i=1}^n\frac 1 i
$$
证明大概就是枚举第一个元素所在轮换的大小:
$$
\begin{align}
\begin{bmatrix}n\\2\end{bmatrix}&=\sum_{x=1}^{n-1}\binom{n-1}{x-1}(x-1)!(n-x-1)!\\
&=\sum_{x=1}^{n-1}\frac{(n-1)!}{(x-1)!(n-x)!}(x-1)!(n-x-1)!\\
&=(n-1)!H_{n-1}
\end{align}
$$
预处理方法:
由上面那个式子有一个直接的
$O(n\log^2n)$
的分治
$+FFT$
的做法,就是分治到区间
$[l,r]$
时计算
$\begin{align}\prod_{i=l}^r(x+i)\end{align}$
的值,然后每次把两边用
$FFT$
卷积起来。
还有一种
$O(n\log n)$
的倍增方法。
还是利用生成函数,加入我们现在已经知道了
$S_n$
的生成函数,我们想求
$S_{2n}$
的生成函数。考虑求出:
$$
\prod_{i=n}^{2n-1}(x+i)
$$
然后再乘起来就行了。
$$
\begin{align}
&\prod_{i=n}^{2n-1}(x+i)\\
=&\prod_{i=0}^{n-1}(x+i+n)\\
\end{align}
$$
因此我们可以把
$x=x+n$
代入
$S_n(x)$
,也就是:
$$
\begin{align}
&\sum_{i=0}^nf_i(x+n)^i\\
=&\sum_{i=0}^nf_i\sum_{j=0}^i\binom ijx^jn^{i-j}\\
=&\sum_{j=0}^n\sum_{i=j}^nf_i\frac{i!}{j!(i-j)!}x^jn^in^{-j}\\
=&\sum_{j=0}^n\frac1{n^jj!}\bigg(\sum_{i=j}^n\frac{f_ii!n^i}{(i-j)!}\bigg)x^j\\
=&\sum_{j=0}^n\frac1{n^jj!}\bigg(\sum_{i=j}^n\frac{f_ii!n^i}{(i-j)!}\bigg)x^j\\
\end{align}
$$
设
$r[i]=f_{n-i}(n-i)!n^{n-i}$
,那么:
$$
\sum_{i=j}^n\frac{r[n-i]}{(i-j)!}=\sum_{i=0}^{n-j}\frac{r[n-j-i]}{i!}
$$
是一个卷积,可以
$FFT$
求,时间复杂度
$O(n\log n)$
。
第二类斯特林数(斯特林子集数)
定义:
记为
$\begin{Bmatrix}n\\ m\end{Bmatrix}$
或
$S_2(n,m)$
,计算将
$n$
个元素排成
$m$
个集合的方案数。
性质:
递推公式:
$$
\begin{Bmatrix}n\\ m\end{Bmatrix}=\begin{Bmatrix}{n-1}\\ {m-1}\end{Bmatrix}+m\times \begin{Bmatrix}{n-1}\\ m\end{Bmatrix}
$$
第二类斯特林数的前缀和就是贝尔数(集合划分数):
$$
\sum_{i=0}^n\begin{Bmatrix}n\\ i\end{Bmatrix}=Bell(n)
$$
展开式:
$$
\begin{Bmatrix}n\\ m\end{Bmatrix}=\frac 1{m!}\sum_{i=0}^mC^m_i(-1)^i(m-i)^n
$$
思路就是枚举有几个集合一定是空的,然后把它们容斥掉。
$$
x^k=\sum_{i=0}^k\begin{Bmatrix}k\\ i\end{Bmatrix}P^x_i=\sum_{i=0}^k\begin{Bmatrix}k\\ i\end{Bmatrix}C^x_ii!
$$
预处理方法:
$$
\begin{align}
\begin{Bmatrix}n\\ m\end{Bmatrix}&=\frac 1{m!}\sum_{i=0}^mC^m_i(-1)^i(m-i)^n\\
&=\sum_{i=0}^m\frac{(-1)^i}{i!}\frac{(m-i)^n}{(m-i)!}
\end{align}
$$
显然是一个卷积,预处理阶乘的逆元然后
$NTT$
就可以
$O(n\log n)$
预处理了。
经典应用:
求:
$$
\sum_{i=0}^nC_i^ni^k
$$
$n=10^9,k=10^6$
把原式展开可得:
$$
\sum_{d=0}^n\sum_{i=0}^k\begin{Bmatrix}k\\ i\end{Bmatrix}C^d_ii!C^n_d
$$
交换求和号,会发现最后是一个:
$$
\sum_{d=0}^nC^d_iC^n_d
$$
的形式,然后会发现:
$$
\sum_{d=0}^nC^d_iC^n_d=C^n_i\sum_{d=0}^nC^{n-i}_{d-i}=C^n_i\sum_{d=0}^{n-i}C^{n-i}_d=C^n_i2^{n-i}
$$
然后只要预处理第二类斯特林数就可以
$O(k\log k)$
求解了。
上升幂与下降幂:
$$
x^{\overline i}=x(x+1)\cdots (x+i-1)\\
x^{\underline i}=x(x-1)\cdots(x-i+1)
$$
性质:
$$
x^{\underline i}=(-1)^i(-x)^{\overline i}\\
x^{\overline i}=(-1)^i(-x)^{\underline i}
$$
斯特林数与上升下降幂的关系:
斯特林数的本质是上升下降幂的表示系数和展开系数:
下降幂转通常幂:
$$
x^n=\sum_{k=0}^n\begin{Bmatrix}n\\ m\end{Bmatrix}x^{\underline k}
$$
上升幂转通常幂:
$$
x^n=\sum_{k=0}^n(-1)^{n-k}\begin{Bmatrix}n\\ m\end{Bmatrix}x^{\overline k}
$$
通常幂转上升幂:
$$
x^{\overline n}=\sum_{k=0}^n\begin{bmatrix}n\\ k\end{bmatrix}x^k
$$
通常幂转下降幂:
$$
x^{\underline n}=\sum_{k=0}^n(-1)^{n-k}\begin{bmatrix}n\\ k\end{bmatrix}x^k
$$
斯特林数法求自然数幂和:
第一类斯特林数法:
$$
x^{\underline n}=\sum_{k=0}^n(-1)^{n-k}\begin{bmatrix}n\\ k\end{bmatrix}x^k\Longrightarrow x^k=\frac{x!}{(x-n)!}-\sum_{k=0}^{n-1}(-1)^{n-k}\begin{bmatrix}n\\ k\end{bmatrix}x^k
$$
$$
\begin{align}
F_n(k)&=\sum_{x=1}^nx^k\\
&=\sum_{x=1}^n\biggl(\frac{x!}{(x-n)!}-\sum_{k=0}^{n-1}(-1)^{n-k}\begin{bmatrix}n\\ k\end{bmatrix}x^k\biggr)\\
\end{align}
$$
两类斯特林数之间的关系、反转公式和斯特林反演:
斯特林反演公式:
$$
f[i]=\sum_{j=0}^i\begin{Bmatrix}i\\j\end{Bmatrix}g[j]\Longleftrightarrow g[i]=\sum_{j=0}^i(-1)^{i-j}\begin{bmatrix}i\\j\end{bmatrix}f[j]
$$
贝尔数
In tag:
Copyright © 2020
wjh15101051
ღゝ◡╹)ノ♡