定义:第二类斯特林数\(??(??,??)\)表示的是把\(n\)个不同的小球放在\(m\)个相同的盒子里方案数。
求法
递推式:\(S(n,m)=S(n-1,m-1)+S(n-1,m)*m\)
容斥原理:
\(S(n,m)=\frac{1}{m!}\sum_{k=0}^{m}(-1)^k(^m_k)(m-k)^n\)
根据定义,我们可以枚举空了多少个盒子,然后容斥.因为每一种方案被算了\(m!\)次(放了的小球使盒子不同)
所以要除去.
注意:这个式子是卷积的形式,所以可以\(O(nlogn)\)时间内求出\(S(n,i)\)
\(n^k=\sum_{i=0}^{n}S(k,i)*(^n_i)*i!\)
左边其实就是把\(k\)个数放进\(n\)个盒子的方案数(可以空盒子,并且盒子不同)
右边枚举空的盒子数,然后就算一下就行了
关于更加高深的东西以后再补..
参考:link
原文：https://www.cnblogs.com/zzy2005/p/12181338.html