特殊计数序列——第二类斯特林(stirling)数
2024-10-13 03:59:54
计算式
\[
S(n,m)=S(n-1,m-1)+mS(n,m)
\]
\(S(0,0)=1,S(i,0)=0(i>0)\)
组合意义
将\(n\)个不可分辨的小球放入\(m\)个不可分辨的盒子中,且每个盒子非空
那么上面的式子就类似与\(dp\)的转移了
性质
1、\(S(n,m)=\frac{1}{m!}\sum_{i=0}^m(-1)^i\dbinom{m}{i}(m-i)^n\)
证明:考虑组合意义
先将盒子变成有序,最后除以\(m!\)即可
第二类斯特林数保障每个盒子非空,故考虑容斥,每次钦定\(i\)个盒子必须为空,选法有\(\dbinom{m}{i}\)种,\(n\)个小球放入剩下的\((m-i)\)个盒子中共有\((m-i)^n\)种放法
2、\(n^m=\sum_{i=0}^nS(m,i)*i!*\dbinom{n}{i}\)
证明:依然是考虑组合意义,左边是\(m\)个小球随意的放入\(n\)个盒子的方案数,并且考虑顺序
右边是枚举非空的盒子一共有\(i\)个,球放入的方案数为\(S(m,i)\),有顺序的选\(i\)个盒子有\(i!*\dbinom{n}{i}\)种方案
关于这个式子还有一个小技巧:为了使\(S(m,i)\)和\(\dbinom{n}{i}\)的值均大于\(0\),一定有\(i\leq min(n,m)\),所以我们枚举的sigma上界是可以根据我们的需求进行变化的
求解第二类斯特林数
求\(S(n,m)\)的值
普通求解是\(O(n^2)\)的递推,考虑其他的方法
由性质1的式子变形可以得到
\[
S(n,m)=\frac{1}{m!}\sum_{i=0}^m(-1)^i\frac{m!}{k!(m-k)!}(m-k)^n
\]
\[
S(n,m)=\sum_{i=0}^n\frac{(-1)^k}{k!}\frac{(m-k)^n}{(m-k)!}
\]
直接FFT即可,时间复杂度\(O(nlogn)\)
最新文章
- ASP.NET Aries 入门开发教程9:业务表单的开发
- 【SQLServer】“无法对数据库'XXX' 执行删除,因为它正用于复制”的解决方法
- js动态加载以及确定加载完成的代码
- Redis-cluster集群【第一篇】:redis安装及redis数据类型
- 分模块创建maven项目(二)
- UIActionSheet的使用
- IOS开发UI基础UIImagePickerController的属性
- Lintcode: Recover Rotated Sorted Array
- 黑马程序员——【Java基础】——面向对象(二)异常机制、包(Package)
- PE文件结构详解(二)可执行文件头
- Pox组件
- poj 3469 Dual Core CPU【求最小割容量】
- POJ1502
- Blacksmith test
- adb连接夜神模拟器执行命令
- 112A
- 根据时间段获取时间段内所有时间点(js)
- Oracle导入的常见语句
- Java中线程池,你真的会用吗?
- python之模块colorsys颜色转换模块 暂不了解