CF 932 E. Team Work 第二类斯特林数总结

求解\(\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)\)来解决这个题目。