首页 > 其他 > 详细

关于第二类斯特林数的一丢丢东西

时间:2018-02-17 23:09:51      阅读:106      评论:0      收藏:0      [点我收藏+]

标签:mat   得到   表示   重新   是我   isp   logs   spl   gpo   

关于第二类斯特林数的一丢丢东西

第二类斯特林数

S(n,m)表示有\(n\)个有区别小球,要放进\(m\)个相同盒子里,且每个盒子非空的方案数
考虑一个很容易的递推:
\[S(n,m)=S(n-1,m-1)+m*S(n-1,m)\]
考虑组合意义:
假设前面的\(n-1\)个球丢进了\(m-1\)个组,因为每个组非空,所以这个球只有一种选择——自己一组
如果前面的球已经分成了\(m\)组,那么,这个球就有\(m\)种放法
所以这个递推式就是这样来的


那么,只考虑组合意义可不可以算?
当然是可以的啦
写式子:
\[S(n,m)=\frac{1}{m!}\sum_{k=0}^{m}(-1)^kC(m,k)(m-k)^n\]
为啥呢?
假设盒子有区别,并且我们允许空盒的存在
显然的,\(m^n\)就是答案
但是我们当然就是不允许空盒存在啊
所以容斥一下
枚举我当前有几个空盒子存在
那么先把这几个盒子选出来,也就是\(C(m,k)\)
然后剩下\(m-k\)个盒子,\(n\)个球可以随便放,也就是\((m-k)^n\)
最后退出来,我们盒子是没有区别的,所以除以一个\(m!\)
这样就是直接考虑了


那么,我们来想想一个东西怎么算?
\(m^n\)怎么算?
考虑一下组合意义,把\(n\)个有区别的小球分给有区别的\(m\)个盒子里,允许空盒的方案数
挺好呀,第二类斯特林数是啥意思?
\(S(n,m)\)表示\(n\)个球丢进\(m\)个相同盒子里,不允许空盒
好吧,那我枚举一下有\(i\)个盒子不是空的
再把球丢进盒子不就是\(S(n,i)*i!\)
所以不就推出来啦?
\[m^n=\sum_{i=0}^{m}S(n,i)*i!*C(m,i)\]


回来回来,,
如果要算第二类斯特林数,除了\(n^2\)的递推有没有别的方法呢?
显然是有的
重新看看上面用容斥和组合意义得到的式子
\[S(n,m)=\frac{1}{m!}\sum_{k=0}^{m}(-1)^kC(m,k)(m-k)^n\]
整理一下
\[S(n,m)=\frac{1}{m!}\sum_{k=0}^{m}(-1)^k\frac{m!}{k!(m-k)!}(m-k)^n\]
\[S(n,m)=\frac{1}{m!}\sum_{k=0}^{m}m!\frac{(-1)^k}{k!}\frac{(m-k)^n}{(m-k)!}\]
\[S(n,m)=\sum_{k=0}^{m}\frac{(-1)^k}{k!}\frac{(m-k)^n}{(m-k)!}\]
这样的话,是不是想到了多项式的卷积啦?
于是乎,可以用多项式卷积求出\(S(n,X)\)
复杂度\(O(nlogn)\)

关于第二类斯特林数的一丢丢东西

标签:mat   得到   表示   重新   是我   isp   logs   spl   gpo   

原文:https://www.cnblogs.com/cjyyb/p/8452297.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号