Stirling数笔记
Updating....
这几个玩意儿要记的东西太多太乱所以写blog整理一下
虽然蒯的成分会比较多全部
我居然开始记得写blog了??
第一类
这里讨论的是无符号类型的。
OEIS编号A130534
表示方法
\(s(n,m)\)或者\(\begin{bmatrix}n \\ m\end{bmatrix}\)
注意前者是小写s
意义
\(n\)个元素的项目分作\(m\)个非空环排列的方法数目
求法
递归求解法
\[\begin{bmatrix}n\\m\end{bmatrix}=\begin{bmatrix}n-1\\m-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\m\end{bmatrix}\]
这个就是说新建一个环排列或者插入已有的环排列
可怕 这很\(O(n^2)\)
各种性质
\(\begin{bmatrix}n\\1\end{bmatrix}=(n-1)!\)
\(\begin{bmatrix}n\\2\end{bmatrix}=(n-1)!\times\sum_{i=1}^{n-1}\frac 1 i\)
\(\sum_{i=0}^n \begin{bmatrix}n\\i\end{bmatrix}=n!\)
\(\begin{bmatrix}n\\n-1\end{bmatrix}=\binom{n}{2}\)
这里就不给出证明了
别的地方都有
也挺好记好想的
maybe
第二类
OEIS编号A008277
表示方法
\(S(n,m)\)或者\(\left\{\begin{matrix}n \\ m\end{matrix}\right\}\)
当然这里是大写S
意义
\(n\)个元素的集定义\(m\)个等价类的方法数目
。。。wiki害人
就是从环排列变成集合划分了
当然也要保证非空
求法
递归求解法
\[\begin{Bmatrix}n\\m\end{Bmatrix}=\begin{Bmatrix}n-1\\m-1\end{Bmatrix}+m\begin{Bmatrix}n-1\\m\end{Bmatrix}\]
同样也可以解释,新建or插入已有的
再次\(O(n^2)\)??别啊
幸好这玩意儿能搞容斥,通项就有了
\[\begin{Bmatrix}n\\m\end{Bmatrix}=\frac{1}{m!}\sum\limits_{k=0}^{m}(-1)^k\binom{m}{k}(m-k)^n\]
\(O(n)\)求解不是梦
好吧只求一个用这个会快
最重要的是这个能卷,也好搞些别的???
稍微整理一下
\[\left\{\begin{matrix}n\\m\end{matrix}\right\}=\sum_{k=0}^m\frac{(-1)^k}{k!}\frac{(m-k)^n}{(m-k)!}\]
就很舒服
Stirling 反演
两个柿子挺好记
但我暂时还搞不清具体是干嘛的。。。
\[f(x) = \sum_{i=0}^x \begin{Bmatrix}x\\i\end{Bmatrix} g(i) \Leftrightarrow g(x) = \sum_{i=0}^x (-1) ^ {x - i}\begin{bmatrix}x\\i\end{bmatrix} f(i)\]
\[f(x) = \sum_{i=0}^x \begin{bmatrix}x\\i\end{bmatrix} g(i) \Leftrightarrow g(x) = \sum_{i=0}^x (-1) ^ {x - i}\begin{Bmatrix}x\\i\end{Bmatrix} f(i)\]
Bell数
OEIS编号A000110
就是把第二类stirling数的集合划分个数限制去掉了
只限制了基数
也就是
\[B_n=\sum_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}\]
当然也可以直接\(O(n)\)递推
\[B_{n+1}=\sum_{k=0}^n\binom{n}{k}B_{k}\]
参考
%%%
https://www.cnblogs.com/NaVi-Awson/p/9242645.html
https://www.cnblogs.com/ezoiLZH/p/9424911.html
https://www.cnblogs.com/owenyu/p/6724661.html
https://blog.csdn.net/winycg/article/details/70233717
最新文章
- Python之路第一课Day9--随堂笔记之一(堡垒机实例以及数据库操作)未完待续....
- CozyRSS开发记录4-抽屉效果订阅列表栏
- -- c语言数据类型总结 --
- Jsonp 解决跨域问题
- Ionic2 开发笔记(1)ionic2 +angular2搭建
- tcp入门(唐唐的故事)
- linux 的一些脑洞操作
- 利用AD采集获取外部温度传感器的值
- linux如何查看端口被谁占用
- POJ1743 Musical Theme [后缀自动机]
- zk日常运维管理
- WebRTC MCU( Multipoint Conferencing Unit)服务器调研
- Android远程桌面助手之性能监测篇
- 软件分享--EditPlus
- Sublime Text 2 2.0.2 序列号
- 餐饮ERP相关问题FAQ
- Nginx location配置详解
- django开发(一)
- ubuntu彻底删除apache2 再重装
- 实现数组(java)
热门文章
- python中argparse库的使用教程链接
- ajax 返回值问题
- 【Quartz.net】- Cron表达式
- Python2中编码错误---éç»äººè¡¨ç®çé¿å å­åè¶(æå­格式转化为UTF-8
- TScreen 类
- 【数据库】各种主流 SQLServer 迁移到 MySQL 工具对比
- 复杂类型的write写入功能 步骤解析
- 【bzoj1737】[Usaco2005 jan]Naptime 午睡时间 dp
- android应用打前需要准备些啥?
- poj 1719 Shooting Contest (二分匹配)