问题

求下面这个式子：
$sum_{i=0}^n i^k$
$n$ 的范围可以很大。

第二类Strling数

第二类Strling数记作 $S(n,m)$ 、 $S_n^m$ 。
定义：将 $n$ 个相同的球放在 $m$ 个不同的箱子里的方案数（其中的每一个箱子至少有一个球）。
很容易推出一个式子： $S_n^m=S_{n-1}^{m-1}+mS_{n-1}^m$ 。不解释。
有个通项公式，但是我不会推……不过在处理这个问题的时候用不着。

一个性质

$a^k=sum_{i=0}^kS_k^i i! C_a^i$
如果直接理性地证明可能不容易，所以在这里通过它的定义来推理一下：
对于等式左边，相当于 $k$ 个不同的球放在 $a$ 个不同的箱子里。
对于等式右边，先枚举非空箱子的个数， $S_k^i$ 表示 $k$ 个不同的球放在 $i$ 个相同的箱子里。乘上 $i!$ 相当于放在不同的箱子里，再乘上非空箱子的选法 $C_a^i$ 。
当然这条式子也可以化成：
$sum_{i=0}^kS_k^i prod_{j=a-i+1}^a j$

推理

先把结论放在前面：
$sum_{i=0}^n i^k=sum_{i=0}^kfrac{S_k^iprod_{j=n-i+1}^{n+1}j}{i+1}$
证明如下：
$sum_{i=0}^n i^k \ =sum_{a=0}^nsum_{i=0}^kS_k^i i! C_a^i \ =sum_{i=0}^kS_k^i i!sum_{a=0}^nC_a^i$
因为 $a<i$ 时 $C_a^i=0$ ，所以
$=sum_{i=0}^kS_k^i i!sum_{a=i}^nC_a^i$
由 $C_m^n =C_{m-1}^{n-1}+C_{m-1}^n$ 得
$sum_{a=i}^nC_a^i=C_i^i+C_{i+1}^i+cdots +C_n^i \ =C_i^{i+1}+C_i^i+C_{i+1}^i+cdots +C_n^i \ =C_{i+1}^{i+1}+C_{i+1}^i+cdots +C_n^i \ cdots \ =C_{n+1}^{i+1}$
所以原式又可以化成下面这样：
$=sum_{i=0}^kS_k^i i!C_{n+1}^{i+1} \ =sum_{i=0}^kfrac{S_k^iprod_{j=n-i+1}^{n+1}j}{i+1}$
这样式子就推完了。