第二类斯特林数

问题描述

有n个互不相同的球，放到k个互不相同的盒子里，每个盒子里至少要有一个球，求方案数

递推式方式：

(f[n][k]=k*f[n-1][k]+f[n-1][k-1])
(f[n][k]记为第二类斯特林数，记为S_2(n,k))
时间复杂度为(O(kn))

用容斥原理求第二类斯特林数

设(a_i)为第i个盒子没有球
(ans=N(prod_{i=1}^k(1-a_i))=sum_{i=0}^k (-1)^i {n choose i} N(prod_{j=1}^i a_j))
(:::::::\,=sum_{i=0}^k (-1)^i {n choose i} (k-i)^n)
此方案数是对盒子进行编号后的方案数，题目中的盒子并没有方案数，也就是集合是无序的，所以最后要消序
所以
(S_2(n,k)cdot k!=sum_{i=0}^k (-1)^i {n choose i} (k-i)^n)
(S_2(n,k)=frac{sum_{i=0}^k (-1)^i {n choose i}(k-i)^n}{k!})
时间复杂度(O(kcdot logn))

重要公式

(n^m=sum_{k=0}^m S_2(m,k)n^{underline{k}})
其实(n^m)就是有m个球放入n个盒子的方案数（可以有盒子没有球）
(n^m=sum_{k=0}^n {n choose k}S_2(m,k)k!=sum_{k=0}^m S_2(m,k)n^{underline{k}})