求解\(\sum_{x=1}^nC(n,x)x^k,n\le 10^9,k\le 5000\)
第二类斯特林数 n个不同的小球放入k个相同的盒子的方案数\(S(n,k)\)，盒子非空
显然有\(S(n,k)=S(n-1,k-1)+k\cdot S(n-1,k)\)
注意边界\(S(n,0)=[n==0],S(n,1)=1\)
考虑到\(x^k\)可以利用第二类斯特林数化简\(x^k=\sum_{i=1}^{x}C(x,i)S(k,i)i!\)
这个式子的意义就是\(k\)个球放\(x\)个不同的盒子里的方案数=选出\(i\)个盒子有球此时需要非空且盒子得有序的方案数
考虑到\(i>k\)时\(S(k,i)=0\)，\(i>x\)时\(C(x,i)=0\)
原式亦可变为\(x^k=\sum_{i=1}^{k}C(x,i)S(k,i)i!\)
带入上式\(\sum_{x=1}^n\sum_{i=1}^{k}C(n,x)C(x,i)S(k,i)i!\)
\(LHS=\sum_{i=1}^{k}S(k,i)\sum_{x=i}^n\frac{n!}{(n-x)!(x-i)!}=\sum_{i=1}^{k}S(k,i)\sum_{x=i}^n\frac{n!(n-i)!}{(n-i)!(n-x)!(x-i)!}=\sum_{i=1}^{k}S(k,i)\frac{n!}{(n-i)!}\sum_{x=i}^nC(n-i,n-x)=\sum_{i=1}^{k}S(k,i)\frac{n!}{(n-i)!}\sum_{w=0}^{n-i}C(n-i,w)=\sum_{i=1}^{k}S(k,i)\frac{n!}{(n-i)!}2^{n-i}\)
由此可以\(k^2\)递推\(S(k,i)\)来解决这个题目。