两类斯特林数的其中之一 还是要了解一下的。
一般形如(left[egin{matrix}n\mend{matrix} ight])写作(s(n,k))
组合意义:(s(n,k))表示把n个数分成k组 每组是一个环 求分成的方案数。
环的意思其实是类似于圆排列的东西。
递推式：(s(n+1,k)=s(n,k-1)+s(n,k)cdot n)
有边界 (s(0,0)=1).
性质：(s(n,1)=(n-1)!) 这个看起来挺显然不正了 当然可以相当于圆排列来理解。
(s(n,2)=(n-1)! imessum_{i=1}^{n-1}frac{1}{i})这个利用数学归纳法也很好证。
(sumlimits_{i=0}^ns(n,k)=n!)证明：求n个数的所有排列方案数n! 对于某种排列其中必然有k个置换 而置换就是我们上述所说的环的概念。
对于有k个置换的方案数 其为s(n,k)所以可以得到(sumlimits_{i=1}^ns(n,k)=n!)因为s(n,0)=0所以原式成立。
这里先规定一下上升幂和下降幂。
定义下降幂为(x^{underline{n}} = x(x-1)cdots (x-n+1).)
上升幂为(x^{overline{n}} = x(x+1)cdots (x+n-1).)
有等式 (sum_{i=0}^ns(n,i)x^i=x^{overline{n}})
上面那个还不够重要 再来一个(x^{underline{n}}=sum_{i=0}^{n}left[egin{matrix}n\iend{matrix} ight](-1)^{n-i} x^i)
证明 这个式子可以利用数学归纳法 上面那个也同理。
update 7.25:当年写的过于稚嫩。
其实关于 下降幂和第一类斯特林数的关系 可以利用 自然幂和第二类斯特林数的关系 进行斯特林反演得到。
不过这里直接列出等式进行数学归纳法证明了。详细步骤如下:
(x^{underline{n+1}})
(=x^{underline{n}} imes (x-n))
(=(x-n)sumlimits_{i=0}^{n}(-1)^{n-i}s(n,i)x^i)
(=sumlimits_{i=1}^{n+1}(-1)^{n+1-i}s(n,i-1)x^i+sumlimits_{i=0}^{n}(-1)^{n+1-i}ncdot s(n,i)x^i)
左边是枚举从1开始 然后进行变换。右边是乘以了(-n)进行变换。
因为 s(n,-1)=0,所以左式再做一个变换:
(sumlimits_{i=1}^{n+1}(-1)^{n+1-i}s(n,i-1)x^i=sumlimits_{i=0}^{n+1}(-1)^{n+1-i}s(n,i-1)x^i)
左式把第n+1项给提出来 和右边进行合并。即：
(=(-1)^0s(n,n)x^{n+1}+sumlimits_{i=0}^{n}(-1)^{n+1-i}(s(n,i-1)+ns(n,i))x^i)
接下来做的变换是 由于(s(n,i-1)+ns(n,i)=s(n+1,i),s(n,n)=s(n+1,n+1))
(=s(n+1,n+1)x^{n+1}+sumlimits_{i=0}^{n}(-1)^{n+1-i}s(n+1,i)x^i)
(=sumlimits_{i=0}^{n+1}(-1)^{n+1-i}s(n+1,i)x^i)
证毕.
注意 这里讨论的是无符号第一类斯特林数 (有符号了一般很少使用
这个证明也比较简单 可以发现斯特林数和下降幂有关 也就是说我们求出下降幂的生成函数 其对应的系数的绝对值就是某一行的斯特林数。
很简便吧 我们可以更快的求斯特林数了。
可以考虑分治FFT 这样的话长度是递增的 每次合并两个多项式可以发现log层 每层FFT nlogn 总复杂度nlog^2
为了避免-1系数的一些问题 可以利用上升幂来求斯特林数 上面的公式也有提到 证明就不证了 数归即可。
设(f(x)=x^{overline{n}},g(x)=(x+n)^{overline{n}}) 则有(f(x)g(x)=x^{overline{2n}})
(f(x)=sum_{i=0}^{n}a_ix^i,则g(x)=sum_{i=0}^na_i(x+n)^i=sum_{i=0}^n(sum_{j=i}^nC(j,i)n^{j-i}a_j)x^i)
倍增+NTT 可以做到nlogn.