[具体数学]第六章·特殊的数（第一部分）

第六章·特殊的数分7节，包括斯特林数、欧拉数、调和数、调和求和法、伯努利数、斐波那契数和连项式的内容。这是笔记第一部分，包括斯特林数、欧拉数，它们可以构成类似杨辉三角的三角形。

$$$$

斯特林数

符号表示：

第一类斯特林数（斯特林轮换数）：$\left[\begin{array}{c}n\\ k\end{array}\right]$；

第二类斯特林数（斯特林子集数）：$\left\{\begin{array}{c}n\\ k\end{array}\right\}$.

注：自定义 $LATEX$ 运算符号，以上述两个斯特林数为例：

\newcommand{\stra}[2]{\begin{bmatrix}#1\\#2\end{bmatrix}}
\newcommand{\strb}[2]{\begin{Bmatrix}#1\\#2\end{Bmatrix}}
LATEX

\newcommand{运算符}[参数数量]{运算符长什么样}，其中 #1,#2 标注参数位置。

第二类斯特林数

我们先来考虑第二类斯特林数。$\left\{\begin{array}{c}n\\ k\end{array}\right\}$ 表示将一个有 $n$ 件物品的集合划分成 $k$ 个非空子集的方案数。

花括号也用来表示集合，这一雷同有助于让我们记住 $$ 的意义。

我们可以推导 $$ 的递归式：把 $$ 件物品分成 $$ 个部分，要么是最后一件物品单独一类，这一共有 $$ 种方案；要么是最后一件物品加入前 $$ 件物品划分出的 $$ 个部分之一去，共有 $$ 种方案。所以我们有： $$ （如果系数 $$ 是 $$ 就是二项式系数了）

基于此，我们可以生成第二类斯特林数的三角形：

第一类斯特林数

现在讨论第一类斯特林数。$$ 表示将 $$ 个元素排成 $$ 个轮换的方案数。这里，轮换是指环形排列，可以转动而相等，例如 $$，但是 $$.

先看几个特殊的值，$$ 个元素的 $$ 轮换有 $$ 种，所以 $$；当所有轮换都是单元素或者双元素时，轮换和子集没有差别，所以 $$.

我们也可以推导 $$ 的递归式：考虑最后一件物品，要么单独放在自己的轮换里，有 $$ 种方式；要么加入前 $$ 件物品分成的 $$ 个轮换中的一个，而方法有 $$ 种（插入任何一个轮换的任何一个位置都行）。所以我们有： $$

记忆是很方便的，第一类斯特林数是在二项式系数的递归式中乘上了上指标 $$ 作为系数，第二类斯特林数是乘上了下指标 $$ 作为系数。

基于此，我们也可以生成第一类斯特林数的三角形：

一些恒等式

我们知道，每一种排列都和一个轮换等价——例如 $$，从下标向数值连边，就构成了若干个环 $$，也即形成了一个轮换（这一点在竞赛中也经常使用）。所以，所有轮换方案加起来就是所有排列数，即： $$ 之前说过，普通的幂次和下降幂之间可以通过斯特林数建立起联系，我们观察前几个关系： $$ 会发现这系数不就是第二类斯特林数吗？也就是说，我们可以猜想： $$ 数学归纳法证明： $$ 证毕。

同样的，上升阶乘幂与普通的幂次之间也有类似关系： $$ 数学归纳法证明： $$ 证毕。

上面是用下降幂表示了普通幂，普通幂表示了上升幂。但如果我们想用普通幂表示下降幂，上升幂表示普通幂呢？只需要应用 $$，把 $$ 取相反值就得到： $$ 如果我们把普通幂表示上升幂的式子代入上升幂表示普通幂的式子，那么得到： $$ 由于这是一个恒等式，所以 $$ 对应系数相等，于是我们得到： $$

更多的实践总结出了一大堆斯特林数恒等式： $$

欧拉数

定义和递归式

$$ 表示 $$ 的有 $$ 个升高的排列 $$ 的个数。也即，有 $$ 个地方 $$.

推导欧拉数的递归式：尝试插入数 $$，如果它插在某个上升段的最后，那么升高数 $$，这样的位置有 $$ 个；如果它插在某个上升段的中间，升高数不变，这样的位置有 $$ 个。所以我们有： $$ 初始条件：$$，并假定 $$ 时 $$.

由此我们可以得到欧拉数的三角形：

性质和恒等式

从表中可以看出，欧拉数具有对称性： $$ 因为 $$ 有 $$ 个升高当且仅当 $$ 有 $$ 个升高。

$$ 恒等式： $$ 证明：数学归纳法。首先 $$ 时，$$ 成立；假设 $$ 均成立，则： $$ 证毕。（注：上述推导用了恒等式：$$. ）

还有一些其他性质： $$

（二阶欧拉数和斯特林多项式目前跳过）