[TJOI 2016] 求和

题解

要先知道一件事情:
$$
\begin{Bmatrix}n\\m\end{Bmatrix}=\frac{1}{m!}\sum_{i=0}^m\binom{m}{i}(-1)^{m-i}i^n
$$
即第二类斯特林数通项公式。

下面开始推式子(为了方便,设$s_i=\sum_{j=0}^ni^j$):
$$
\begin{aligned}
\sum_{i=0}^n \sum_{j=0}^i \begin{Bmatrix} i \\ j \end{Bmatrix} 2^j j! &= \sum_{i=0}^n\sum_{j=0}^n\sum_{k=0}^j\binom{j}{k}(-1)^{j-k}k^i2^j\\
&=\sum_{j=0}^n\sum_{k=0}^j\binom{j}{k}(-1)^{j-k}2^j(\sum_{i=0}^nk^i)\\
&=\sum_{j=0}^n\sum_{k=0}^j\binom{j}{k}(-1)^{j-k}2^js_k\\
&=\sum_{j=0}^n\sum_{k=0}^j\frac{j!}{k!(j-k)!}(-1)^{j-k}2^js_k\\
&=\sum_{j=0}^nj!\cdot 2^j\sum_{k=0}^j(\frac{s_k}{k!})\cdot \frac{(-1)^{j-k}}{(j-k)!}
\end{aligned}
$$
很明显,后面那堆东西是一个卷积的形式。

代码

Tagged with:

发表评论