幂前缀和的生成函数

问题描述：

对于给定的大数 \(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}\) 吗。

线性解法

待补。。。