本文共 2499 字，大约阅读时间需要 8 分钟。

最近做题有时会碰到斯特林数（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连一条边的一副图），然后枚举轮换里环的数量就好了

应用

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

转载地址：https://blog.csdn.net/zhouyuheng2003/article/details/79026975 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！