 求法)
众所周知，第二类斯特林数通过二项式反演可以得到通项公式。
应用它可以得到线性计算 bell 与 fubini numbers 的方法。
先来看贝尔数。
\[\begin{aligned}
Bell(n)&=\sum_{k=0}^n{n\brace k}\\
&=\sum_{k=0}^n\sum_{j=0}^k\frac{(-1)^{k-j}j^n}{j!(k-j)!}\\
&=\sum_{j=0}^n\frac{j^n}{j!}\sum_{k=0}^{n-j}\frac{(-1)^k}{k!}
\end{aligned}
\]
显然和式的后部分可以前缀和，幂次可以通过线性筛递推。
再来看 fubini numbers。
\[\begin{aligned}
Fubini(n)&=\sum_{k=0}^nk!{n\brace k}\\
&=\sum_{k=0}^n\sum_{j=0}^k{k\choose j}(-1)^{k-j}j^n\\
&=\sum_{j=0}^n{j^n}\sum_{k=j}^n{k\choose j}(-1)^{k-j}
\end{aligned}
\]
设 \(S(j)=\sum_{k=j}^n(-1)^{k-j}{k\choose j}\)
\[Fubini(n)=\sum_{j=0}^nj^nS(j)
\]
\[\begin{aligned}
S(j)&=\sum_{k=j}^n{k-1\choose j-1}(-1)^{k-j}+{k-1\choose j}(-1)^{k-j}\\
&=S(j-1)-{n\choose j-1}(-1)^{n-(j-1)}-(S(j)-{n\choose j}(-1)^{n-j})\\
&=S(j-1)-S(j)+(-1)^{n-j}\left[{n\choose j}+{n\choose j-1}\right]\\
&=S(j-1)-S(j)+(-1)^{n-j}{n+1\choose j}
\end{aligned}
\]
因此有：
\[S(j-1)=2S(j)+(-1)^{n+1-j}{n+1\choose j}
\]
\(S(n)=1\)，故有：
\[S(j)=\sum_{k=j}^n{n+1\choose k+1}(-1)^{n-k}2^{k-j}
\]
带入原式有：
\[Fubini(n)=\sum_{j=0}^n\left(\frac{j}{2}\right)^n\sum_{k=j}^n{n+1\choose k+1}(-1)^{n-k}2^k
\]