第一类斯特林数学习记录

最近做题有时会碰到斯特林数（Stirling数），就觉得好好的学习一番，于是呢，写下这篇博客，来记录一些知识

简单介绍

第一类斯特林数表示表示将 n 个不同元素构成m个圆排列的数目。——百度百科

第一类斯特林数，可以表示为$s(n,m)$，注意这里是小写
，要与大写的第二类斯特林数区分开来，定义上面也讲到了，但是呢，其实那句话最好改成第一类斯特林数的绝对值，因为第一类斯特林数是分正负的，分为无符号斯特林数$s_u(n,m)$和有符号斯特林数$s_s(n,m)$

有无符号Stirling数分别表现为其升阶函数和降阶函数的各项系数[类似于二项式系数]，形式如下：
$$x^{n\downarrow }=x(x-1)(x-2)\cdot \cdot \cdot (x-n+1)=\sum _{k=0}^n{s}_s(n,k)x^k$$
$$x^{n\uparrow }=x(x+1)(x+2)\cdot \cdot \cdot (x+n-1)=\sum _{k=0}^n{s}_u(n,k)x^k$$

这是一个很烦的式子，但其实呢，有符号和无符号斯特林数之间的关系其实很简单$s_s(n,m)=(-1{)}^{n+m}{s}_u(n,m)$
另外，这个式子的推导可以见我的另一篇博客：第二类斯特林数学习记录

计算公式

第一类斯特林数有个递推式很好想
想一下对于$s_u(n,m)$
若$n=0$，$m=0$那么显然就一种方案
若$n̸=0$，$m=0$那么肯定分配不了，有0种方案
若$n̸=0$，$m̸=0$
那么考虑转移
倘若由$s_u(n-1,m-1)$转移而来，则说明新来的一个点自成一个环只有一倍的贡献
倘若由$s_u(n-1,m)$转移而来，则说明新来的一个点插入到m个环中的n-1个空格的任何一个位置，那么就有n-1倍的贡献，递推式为$s_u(n,m)=s_u(n-1,m-1)+(n-1)\ast s_u(n-1,m)$
有符号的第一类斯特林数的递推式为$s_s(n,m)=s_s(n-1,m-1)-(n-1)\ast s_s(n-1,m)$
证明是前面那个公式$$\sum _{k=0}^{n}s(n,k)x^k=x^{n\downarrow }=x^{n-1\downarrow }\ast (x-n+1)=\sum _{k=0}^{n-1}s(n-1,k)x^{k+1}-n\ast \sum _{k=0}^{n-1}s(n-1,k)x^k$$
依次把$x^m$在左右两边的系数提取出来得到
另外有这个式子：（证明在第二类斯特林数的博客里）
$$x^{n\downarrow }=\sum _{i=0}^n{\left[\begin{array}{c}n\\ i\end{array}\right]}_s{x}^i$$
我们可以通过这个公式在$\Theta (nlo{g}^{2}n)$的复杂度内用分治+FFT求出某个$n$对应的所有$s_u(n,m)$值

性质

除了一些比较容易想到的性质外，第一类斯特林数还有如下性质
$$s_u(n,2)=(n-1)!\ast \sum _{i=1}^{n-1}\frac{1}{i}$$
$$\sum _{k=0}^n{s}_u(n,k)=n!$$
容易发现，每一个排列都对应着一个轮换（相当于i到ai连一条边的一副图），然后枚举轮换里环的数量就好了

应用

第一类斯特林数是一种在组合方面比较有用的数，很多问题都可通过它来解决，熟悉它的性质，才能熟练的运用到公式推导的过程中去

总结

以上是生活随笔为你收集整理的第一类斯特林数学习记录的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。