幂前缀和的生成函数

问题描述：

对于给定的大数$m$，求$\displaystyle k\in[1,n],F_k=\sum _{i=1}^m i^k$

$F_k=\sum _{i=1}^m i^k$，每一项的组合意义即：为$k$个元素每个染上$i$种颜色中的一个

带入第二类斯特林数的组合意义，得到

$\displaystyle F_k=\sum_{i=1}^m \sum_{j=0}^{\infty} \binom{i} {j}\begin{Bmatrix}k\\ j\end{Bmatrix}j!$

合并外层循环的组合数前缀和

$\displaystyle F_k=\sum_{i=0}^{\infty} \binom{m+1} {i+1}\begin{Bmatrix}k\\ i\end{Bmatrix}i!$

我们知道第二类斯特林数的$\text{EGF}$

$\displaystyle S(x)=\sum \begin{Bmatrix}i\\m \end{Bmatrix}\frac{x^i} {i!}=\frac{1} {m!}(e^x-1)^m$

其意义是合并每一种颜色的元素的$\text{EGF}$，要求每种颜色个数$\ge 1$，同时颜色之间无序，最后除掉

带入$F_k$的式子，得到$F_k$的$\text{EGF}$

$\displaystyle F(x)=\sum \binom{m+1} {i+1}(e^x-1)^i$

带入二项展开

$\displaystyle F(x)=\frac{e^{(m+1)x}-1} {e^x-1}$

停停停

这个东西不是直接根据$[x^n]e^{ax}=\cfrac{a^n} {n!}$

就会发现是$\displaystyle \sum_{i=0}^m e^{ix}=\frac{e^{(m+1)x}-1} {e^x-1}$吗

待补。。。

orangejuice's blog