斯特林数
第一类斯特林数
(n^2)递推式
[egin{bmatrix}n\kend{bmatrix}
]
表示(n)个不同的人做(k)张圆桌的方案数(相对位置的变化算不同),那么有以下的式子:
[egin{bmatrix}
n\k
end{bmatrix}
=egin{bmatrix}
n-1\k-1
end{bmatrix}+(n-1)
egin{bmatrix}
n-1\k
end{bmatrix}
]
每一张桌子都要有一个人
一个人的插入当且仅当有两种情况:
- 自己新开一张桌子,所以方案是(egin{bmatrix}n-1\k-1end{bmatrix})
- 和别人合并到一张桌子,此时这个人可以做到任何一个人的右手边,所以方案数是((n-1)egin{bmatrix}n-1\kend{bmatrix})
这个式子就解释清楚了.
第一类斯特林数的一些性质
[sum_{i=0}^negin{bmatrix}
n\
i
end{bmatrix}
=n!
]
[x^{underline n}=sum_{i=0}^negin{bmatrix}n\iend{bmatrix}-1^{n-i}x^i
]
[x^{overline n}=sum_{i=0}^negin{bmatrix}n\iend{bmatrix}x^i
]
证明可以用数学归纳法证明.戳这里看证明
快速求法
但是有的实际问题中我们并不需要用到所有的斯特林数,或者是题目钦定你求一行的第一类斯特林数,考虑生成函数.
我们知道(x)的(n)次上升幂是第一类斯特林数的生成函数,那么得到下面的式子:
[prod_{i=0}^{n-1}(x+i)=sum_{i=0}^negin{bmatrix}n\iend{bmatrix}x^i
]
然后这个东西显然可以分治(FFT)的对吧(其实一开始我是不知道为什么显然的.)
你考虑我们令(f_i)表示(egin{bmatrix}n\iend{bmatrix}),那么你把左右卷起来,显然得到的就是(l)到(r)区间的第一类斯特林数对吧.
然后初始你令(f_i=i),然后直接分治(FFT)就行了,注意要补(1)满足能够卷出来.
第二类斯特林数
(egin{Bmatrix}n\kend{Bmatrix})表示把(n)个不同的球放到(k)个黑暗的盒子里面的方案数(盒子里面的顺序不用管).
(n^2)递推式
那么根据这个定义可以写出来式子:
(egin{Bmatrix}n \ kend{Bmatrix}=egin{Bmatrix}n-1 \ k-1end{Bmatrix}+(k-1)egin{Bmatrix}n-1 \ kend{Bmatrix})
容斥式
[egin{Bmatrix}n\kend{Bmatrix}=frac{1}{k!}sum_{i=0}^n(-1)^iinom{k}{i}(k-i)^n
]
这就是考虑有(i)个空盒,剩下的随便放.
快速求法
你把容斥的式子拆开:
[egin{align}
egin{Bmatrix}n\kend{Bmatrix}&=frac{1}{k!}sum_{i=0}^n(-1)^iinom{k}{i}(k-i)^n\
&=sum_{i=0}^nfrac{(-1)^i}{i!}frac{(k-i)^n}{(k-i)!}
end{align}
]
这就是一个卷积的形式了,直接(NTT)即可.
一些性质
[n^m=sum_{i=0}^ni!inom{n}{i}egin{Bmatrix}m\iend{Bmatrix}
]
根据几何意义理解一下这个式子:
(n^m)表示把(m)个不同球放到(n)个盒子里面的方案数(盒子可以为空),那么我们枚举有多少个盒子不是空的,这个时候(inom{n}{i})就出来了,然后相当于是把(m)个球放到这(i)个盒子里面.因为球是不同的,所以要带一个(i!).
自然数幂和:
[egin{align}
sum_{i=1}^ni^k&=sum_{i=1}^nsum_{j=0}^ij!inom{i}{j}egin{Bmatrix}k\jend{Bmatrix}\
&=sum_{j=0}^ij!egin{Bmatrix}k\jend{Bmatrix}sum_{i=1}^ninom{i}{j}\
&=sum_{j=0}^ij!egin{Bmatrix}k\jend{Bmatrix}inom{n+1}{j+1}\
&=sum_{j=0}^ij!egin{Bmatrix}k\jend{Bmatrix}frac{(n+1)!}{(j+1)!(n-j)!}\
&=sum_{j=0}^iegin{Bmatrix}k\jend{Bmatrix}frac{(n+1)^{underline {j-1}}}{j+1}
end{align}
]
终于手推完了(QwQ).
题目
- [TJOI2016&HEOI2016]求和
- BZOJ5093 [Lydsy1711月赛]图的价值