首页 > 其他 > 详细

Stirling数笔记

时间:2018-09-24 22:48:00      阅读:161      评论:0      收藏:0      [点我收藏+]

这几个玩意儿要记的东西太多太乱所以写blog整理一下
虽然蒯的成分会比较多全部
我居然开始记得写blog了??

第一类

这里讨论的是无符号类型的。

表示方法

\(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

第二类

表示方法

\(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}\]
再次\(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)\)求解不是梦
好吧只求一个用这个会快
最重要的是这个能卷,也好搞些别的???

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数什么的可能也会搞到这里来
但是我暂时还没看

参考

%%%
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

Stirling数笔记

原文:https://www.cnblogs.com/backupnoob01/p/9696971.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!