斯特林数笔记小结

斯特林数笔记整理

斯特林数笔记整理

 最近快被数学折磨疯了，具体数学上得快内容也难，在此整理一下所学的内容

第一类斯特林数

 第一类斯特林数$\begin{bmatrix}
n\\
k
\end{bmatrix}$表示从$n$个元素中组成$k$个循环的方案数，此处的循环合起来构成一个与原排列对应的置换(参考置换群)。注意:循环的内部是圆周有序的，即$(a_1a_2a_3)$与$(a_2a_3a_1)$等价。

 从组合的意义可以得到$\begin{bmatrix}n\\k\end{bmatrix}$的递推式

$$\begin{bmatrix}n\\k\end{bmatrix}=(n-1)\begin{bmatrix}n-1\\k\end{bmatrix}+\begin{bmatrix}n-1\\k-1\end{bmatrix}$$

 即当前的状态可以由直接添加一个新集合与放在任意一个元素后面转移而来

 根据置换的性质，可以得到$\begin{bmatrix}n\\k\end{bmatrix}$与$n!$的关系

$$\Sigma_k\begin{bmatrix}n\\k\end{bmatrix}=n!$$

 由于任何一个置换都与一个排列一一对应，所以置换的总数与排列的总数相等

 第一类斯特林数还可以用与上升幂与下降幂的展开

$$X^{\overline{n}}=\Sigma\begin{bmatrix}n\\k\end{bmatrix}x^k\\ X^{\underline{n}}=\Sigma\begin{bmatrix}n\\k\end{bmatrix}(-1)^{n-k}x^k\\$$

 首先可以直观感性的理解一下,$X^{\underline{n}}<X^n<X^{\overline{n}}$,所以$X^n$转化成下降幂需要容斥，而上升幂则不用。这两个公式非常有用，直接将上升幂下降幂与自然幂联系在一起。形式上也较为简洁，类似于二项式反演。

 至于证明，懒得写了，这篇文章的大部分公式证明都可以利用数学归纳法，大概思路就是先对和式进行扰动，利用吸收公式化简式子，并提取出公因式，最后利用递推式直接导出结果。

第二类斯特林数

 相似的，第二类斯特林数$\begin{Bmatrix}n\\k\end{Bmatrix}$表示将$n$个元素划分为$k$个非空集合的方案数，可以读作”n子集k”。比起$\begin{bmatrix}n\\k\end{bmatrix}$,$\begin{Bmatrix}n\\k\end{Bmatrix}$由于其内部无序性，显然不会更大。由于组合意义更加简洁，它的出现也更为频繁。

 从组合的意义可以得到$\begin{Bmatrix}n\\k\end{Bmatrix}$的递推式

$$\begin{Bmatrix}n\\k\end{Bmatrix}=k\begin{Bmatrix}n-1\\k\end{Bmatrix}+\begin{Bmatrix}n-1\\k-1\end{Bmatrix}$$

 即当前的状态可以由直接添加一个新集合与插入任意一个已有集合转移而来

 第二类斯特林数由于其无序性，没有与阶乘有关的和式。但是它同样有关于上升幂下降幂与自然幂的展开式

$$X^n=\Sigma_k\begin{Bmatrix}n\\k\end{Bmatrix}x^{\underline{k}}\\ X^n=\Sigma_k\begin{Bmatrix}n\\k\end{Bmatrix}(-1)^{n-k}x^{\overline{k}}\\$$

 类比于上面的反演式，$-1$可以从容斥的角度来理解

 类似于组合数，斯特林数并不要求$n,k$均为正整数，关于有符号斯特林数也有一个优美的公式

$$\begin{bmatrix}n\\k\end{bmatrix}=\begin{Bmatrix}-k\\-n\end{Bmatrix}$$

 关于两类斯特林数还有许多关于组合数的求和公式，从组合意义的角度去理解比较好，证明的话除了数学归纳法其他的方式过于繁琐我太菜了不会，在此不赘述

斯特林反演

 就是将上面几个关于上升幂下降幂与自然幂的式子结合起来看

$$X^n=\Sigma_k\begin{Bmatrix}n\\k\end{Bmatrix}x^{\underline{k}}\\ X^n=\Sigma_k\begin{Bmatrix}n\\k\end{Bmatrix}(-1)^{n-k}x^{\overline{k}}\\ X^{\overline{n}}=\Sigma\begin{bmatrix}n\\k\end{bmatrix}x^k\\ X^{\underline{n}}=\Sigma\begin{bmatrix}n\\k\end{bmatrix}(-1)^{n-k}x^k\\$$

 得到

$$g(n)=\Sigma_k(-1)^{n-k}\begin{bmatrix}n\\k\end{bmatrix}f(k)\\ f(n)=\Sigma_k\begin{Bmatrix}n\\k\end{Bmatrix}g(k)\\$$

 证明的话把式子一层层剥开，直接交换顺序组合在一起就是了。

 目前并没有做过很多利用斯特林数性质的题，一题都不会做，基本也是和组合数中的求和式扯在一起。以后会慢慢收集一些题再归纳整理。