[具体数学]第六章·特殊的数（第一部分）
第六章·特殊的数分7节，包括斯特林数、欧拉数、调和数、调和求和法、伯努利数、斐波那契数和连项式的内容。这是笔记第一部分，包括斯特林数、欧拉数，它们可以构成类似杨辉三角的三角形。
\[ \newcommand{\stra}[2]{\begin{bmatrix}#1\\#2\end{bmatrix}} \newcommand{\strb}[2]{\begin{Bmatrix}#1\\#2\end{Bmatrix}} \newcommand{\elr}[2]{\left\langle\begin{matrix}#1\\#2\end{matrix}\right\rangle} \newcommand{\elrdb}[2]{\left\langle\left\langle\begin{matrix}#1\\#2\end{matrix}\right\rangle\right\rangle} \]
斯特林数
符号表示：
第一类斯特林数（斯特林轮换数）：\(\stra{n}{k}\)；
第二类斯特林数（斯特林子集数）：\(\strb{n}{k}\).
注：自定义 \(\LaTeX\) 运算符号，以上述两个斯特林数为例：
2\newcommand{\stra}[2]{\begin{bmatrix}#1\\#2\end{bmatrix}}
\newcommand{\strb}[2]{\begin{Bmatrix}#1\\#2\end{Bmatrix}}
\newcommand{运算符}[参数数量]{运算符长什么样}，其中#1,#2标注参数位置。
第二类斯特林数
我们先来考虑第二类斯特林数。\(\strb{n}{k}\) 表示将一个有 \(n\) 件物品的集合划分成 \(k\) 个非空子集的方案数。
花括号也用来表示集合，这一雷同有助于让我们记住 \(\strb{n}{k}\) 的意义。
我们可以推导 \(\strb{n}{k}\) 的递归式：把 \(n\) 件物品分成 \(k\) 个部分，要么是最后一件物品单独一类，这一共有 \(\strb{n-1}{k-1}\) 种方案；要么是最后一件物品加入前 \(n-1\) 件物品划分出的 \(k\) 个部分之一去，共有 \(k\strb{n-1}{k}\) 种方案。所以我们有： \[ \color{purple}{\strb{n}{k}=k\strb{n-1}{k}+\strb{n-1}{k-1}} \] （如果系数 \(k\) 是 \(1\) 就是二项式系数了）
基于此，我们可以生成第二类斯特林数的三角形：
| \(n\) | \(\strb{n}{0}\) | \(\strb{n}{1}\) | \(\strb{n}{2}\) | \(\strb{n}{3}\) | \(\strb{n}{4}\) | \(\strb{n}{5}\) | \(\strb{n}{6}\) | \(\strb{n}{7}\) | \(\strb{n}{8}\) | \(\strb{n}{9}\) |
|---|---|---|---|---|---|---|---|---|---|---|
| \(0\) | \(1\) | |||||||||
| \(1\) | \(0\) | \(1\) | ||||||||
| \(2\) | \(0\) | \(1\) | \(1\) | |||||||
| \(3\) | \(0\) | \(1\) | \(3\) | \(1\) | ||||||
| \(4\) | \(0\) | \(1\) | \(7\) | \(6\) | \(1\) | |||||
| \(5\) | \(0\) | \(1\) | \(15\) | \(25\) | \(10\) | \(1\) | ||||
| \(6\) | \(0\) | \(1\) | \(31\) | \(90\) | \(65\) | \(15\) | \(1\) | |||
| \(7\) | \(0\) | \(1\) | \(63\) | \(301\) | \(350\) | \(140\) | \(21\) | \(1\) | ||
| \(8\) | \(0\) | \(1\) | \(127\) | \(966\) | \(1701\) | \(1050\) | \(266\) | \(28\) | \(1\) | |
| \(9\) | \(0\) | \(1\) | \(255\) | \(3025\) | \(7770\) | \(6951\) | \(2646\) | \(462\) | \(36\) | \(1\) |
第一类斯特林数
现在讨论第一类斯特林数。\(\stra{n}{k}\) 表示将 \(n\) 个元素排成 \(k\) 个轮换的方案数。这里，轮换是指环形排列，可以转动而相等，例如 \([A,B,C,D]=[B,C,D,A]=[C,D,A,B]=[D,A,B,C]\)，但是 \([A,B,C,D]\neq[A,B,D,C]\).
先看几个特殊的值，\(n\) 个元素的 \(n\) 轮换有 \(\frac{n!}{n}\) 种，所以 \(\stra{n}{1}=(n-1)!\)；当所有轮换都是单元素或者双元素时，轮换和子集没有差别，所以 \(\stra{n}{n}=\strb{n}{n}=1,\,\stra{n}{n-1}=\strb{n}{n-1}=\binom{n}{2}\).
我们也可以推导 \(\stra{n}{k}\) 的递归式：考虑最后一件物品，要么单独放在自己的轮换里，有 \(\stra{n-1}{k-1}\) 种方式；要么加入前 \(n-1\) 件物品分成的 \(\stra{n-1}{k}\) 个轮换中的一个，而方法有 \(n-1\) 种（插入任何一个轮换的任何一个位置都行）。所以我们有： \[ \color{purple}{\stra{n}{k}=(n-1)\stra{n-1}{k}+\stra{n-1}{k-1}} \]
记忆是很方便的，第一类斯特林数是在二项式系数的递归式中乘上了上指标 \(n-1\) 作为系数，第二类斯特林数是乘上了下指标 \(k\) 作为系数。
基于此，我们也可以生成第一类斯特林数的三角形：
| \(n\) | \(\stra{n}{0}\) | \(\stra{n}{1}\) | \(\stra{n}{2}\) | \(\stra{n}{3}\) | \(\stra{n}{4}\) | \(\stra{n}{5}\) | \(\stra{n}{6}\) | \(\stra{n}{7}\) | \(\stra{n}{8}\) | \(\stra{n}{9}\) |
|---|---|---|---|---|---|---|---|---|---|---|
| \(0\) | \(1\) | |||||||||
| \(1\) | \(0\) | \(1\) | ||||||||
| \(2\) | \(0\) | \(1\) | \(1\) | |||||||
| \(3\) | \(0\) | \(2\) | \(3\) | \(1\) | ||||||
| \(4\) | \(0\) | \(6\) | \(11\) | \(6\) | \(1\) | |||||
| \(5\) | \(0\) | \(24\) | \(50\) | \(35\) | \(10\) | \(1\) | ||||
| \(6\) | \(0\) | \(120\) | \(274\) | \(225\) | \(85\) | \(15\) | \(1\) | |||
| \(7\) | \(0\) | \(720\) | \(1764\) | \(1624\) | \(735\) | \(175\) | \(21\) | \(1\) | ||
| \(8\) | \(0\) | \(5040\) | \(13068\) | \(13132\) | \(6769\) | \(1960\) | \(322\) | \(28\) | \(1\) | |
| \(9\) | \(0\) | \(40320\) | \(\small{109584}\) | \(\small{118124}\) | \(67284\) | \(22449\) | \(4536\) | \(546\) | \(36\) | \(1\) |
一些恒等式
我们知道，每一种排列都和一个轮换等价——例如 \(15234\)，从下标向数值连边，就构成了若干个环 \([1][2543]\)，也即形成了一个轮换（这一点在竞赛中也经常使用）。所以，所有轮换方案加起来就是所有排列数，即： \[ \color{blue}{\sum_{k=0}^n\stra{n}{k}=n!\quad,整数\;n\geqslant 0} \] 之前说过，普通的幂次和下降幂之间可以通过斯特林数建立起联系，我们观察前几个关系： \[ \begin{align} &x^0=x^{\underline 0}\\ &x^1=x^{\underline 1}\\ &x^2=x^{\underline 2}+x^{\underline 1}\\ &x^3=x^{\underline 3}+3x^{\underline 2}+x^{\underline 1}\\ &x^4=x^{\underline 4}+6x^{\underline 3}+7x^{\underline 2}+x^{\underline 1} \end{align} \] 会发现这系数不就是第二类斯特林数吗？也就是说，我们可以猜想： \[ \color{blue}{x^n=\sum_k\strb{n}{k}x^{\underline k}} \] 数学归纳法证明： \[ \begin{align} x^n=x\cdot x^{n-1}&=x\sum_k\strb{n-1}{k}x^{\underline k}\\ &=\sum_k\strb{n-1}{k}x^{\underline {k+1}}+\sum_k\strb{n-1}{k}kx^{\underline k}&&x\cdot x^{\underline k}=x^{\underline{k+1}}+kx^{\underline k}\\ &=\sum_k\left(\strb{n-1}{k-1}+k\strb{n-1}{k}\right)x^{\underline k}\\ &=\sum_k\strb{n}{k}x^{\underline k} \end{align} \] 证毕。
同样的，上升阶乘幂与普通的幂次之间也有类似关系： \[ \color{blue}{x^{\overline n}=\sum_k\stra{n}{k}x^k} \] 数学归纳法证明： \[ \begin{align} x^{\overline n}=(x+n-1)x^{\overline {n-1}}&=(x+n-1)\sum_k\stra{n-1}{k}x^k\\ &=\sum_k\stra{n-1}{k}x^{k+1}+\sum_k\stra{n-1}{k}(n-1)x^k&&(x+n-1)x^k=x^{k+1}+(n-1)x^k\\ &=\sum_k\left(\stra{n-1}{k-1}+(n-1)\stra{n-1}{k}\right)x^k\\ &=\sum_k\stra{n}{k}x^k \end{align} \] 证毕。
上面是用下降幂表示了普通幂，普通幂表示了上升幂。但如果我们想用普通幂表示下降幂，上升幂表示普通幂呢？只需要应用 \(x^{\underline n}=(-1)^n(-x)^{\overline n}\)，把 \(x\) 取相反值就得到： \[
\color{blue}{\begin{align}
&x^{n}=\sum_k\strb{n}{k}(-1)^{n-k}x^{\overline k}\\
&x^{\underline n}=\sum_k\stra{n}{k}(-1)^{n-k}x^k
\end{align}}
\] 如果我们把普通幂表示上升幂的式子代入上升幂表示普通幂的式子，那么得到： \[
x^n=\sum_k\strb{n}{k}(-1)^{n-k}\sum_m\stra{k}{m}x^m=\sum_{k,m}(-1)^{n-k}\strb{n}{k}\stra{k}{m}x^m
\] 由于这是一个恒等式，所以 \(x\) 对应系数相等，于是我们得到： \[
\color{blue}{\sum_{k,m}(-1)^{n-k}\strb{n}{k}\stra{k}{m}=[m=n]}
\]
更多的实践总结出了一大堆斯特林数恒等式： \[ \begin{align} &\stra{n}{k}=(n-1)\stra{n-1}{k}+\stra{n-1}{k-1}&&递归式\\ &\strb{n}{k}=k\strb{n-1}{k}+\strb{n-1}{k-1}&&递归式\\ &x^{n}=\sum_k\strb{n}{k}x^{\underline k}=\sum_k\strb{n}{k}(-1)^{n-k}x^{\overline k}&&在幂之间转换\\ &x^{\overline n}=\sum_k\stra{n}{k}x^k&&在幂之间转换\\ &x^{\underline n}=\sum_k\stra{n}{k}(-1)^{n-k}x^k&&在幂之间转换\\ &\sum_k\stra{n}{k}\strb{k}{m}(-1)^{n-k}=[m=n]&&反转公式\\ &\sum_{k,m}\strb{n}{k}\stra{k}{m}(-1)^{n-k}=[m=n]&&反转公式\\ &\stra{n}{k}=\strb{-k}{-n}&&对偶性\\ \\ &\strb{n+1}{m+1}=\sum_k\binom{n}{k}\strb{k}{m}\\ &\stra{n+1}{m+1}=\sum_k\stra{n}{k}\binom{k}{m}\\ &\strb{n}{m}=\sum_k\binom{n}{k}\strb{k+1}{m+1}(-1)^{n-k}\\ &\stra{n}{m}=\sum_k\stra{n+1}{k+1}\binom{k}{m}(-1)^{m-k}\\ &m!\strb{n}{m}=\sum_k\binom{m}{k}k^n(-1)^{m-k}\\ &\strb{n+1}{m+1}=\sum_{k=0}^{n}\strb{k}{m}(m+1)^{n-k}\\ &\stra{n+1}{m+1}=\sum_{k=0}^n\stra{k}{m}n^{\underline{n-k}}=n!\sum_{k=0}^n\stra{k}{m}/k!\\ &\strb{m+n+1}{m}=\sum_{k=0}^mk\strb{n+k}{k}\\ &\stra{m+n+1}{m}=\sum_{k=0}^m(n+k)\stra{n+k}{k}\\ &\binom{n}{m}=\sum_k\strb{n+1}{k+1}\stra{k}{m}(-1)^{m-k}\\ &n^{\underline{n-m}}[n\geqslant m]=\sum_k\stra{n+1}{k+1}\strb{k}{m}(-1)^{m-k}\\ &\strb{n}{n-m}=\sum_k\binom{m-n}{m+k}\binom{m+n}{n+k}\stra{m+k}{k}\\ &\stra{n}{n-m}=\sum_k\binom{m-n}{m+k}\binom{m+n}{n+k}\strb{m+k}{k}\\ &\strb{n}{l+m}\binom{l+m}{l}=\sum_k\binom{k}{l}\strb{n-k}{m}\binom{n}{k}\\ &\stra{n}{l+m}\binom{l+m}{l}=\sum_k\stra{k}{l}\stra{n-k}{m}\binom{n}{k} \end{align} \]
欧拉数
定义和递归式
\(\elr{n}{k}\) 表示 \(\{1,2,\cdots,n\}\) 的有 \(k\) 个升高的排列 \(\pi_1\pi_2\cdots\pi_n\) 的个数。也即，有 \(k\) 个地方 \(\pi_j<\pi_{j+1}\).
推导欧拉数的递归式：尝试插入数 \(n\)，如果它插在某个上升段的最后，那么升高数 \(+1\)，这样的位置有 \(n-k\) 个；如果它插在某个上升段的中间，升高数不变，这样的位置有 \(k+1\) 个。所以我们有： \[ \color{purple}{\elr{n}{k}=(k+1)\elr{n-1}{k}+(n-k)\elr{n-1}{k-1}} \] 初始条件：\(\elr{0}{k}=[k=0]\)，并假定 \(k<0\) 时 \(\elr{n}{k}=0\).
由此我们可以得到欧拉数的三角形：
| \(n\) | \(\elr{n}{0}\) | \(\elr{n}{1}\) | \(\elr{n}{2}\) | \(\elr{n}{3}\) | \(\elr{n}{4}\) | \(\elr{n}{5}\) | \(\elr{n}{6}\) | \(\elr{n}{7}\) | \(\elr{n}{8}\) | \(\elr{n}{9}\) |
|---|---|---|---|---|---|---|---|---|---|---|
| \(0\) | \(1\) | |||||||||
| \(1\) | \(1\) | \(0\) | ||||||||
| \(2\) | \(1\) | \(1\) | \(0\) | |||||||
| \(3\) | \(1\) | \(4\) | \(1\) | \(0\) | ||||||
| \(4\) | \(1\) | \(11\) | \(11\) | \(1\) | \(0\) | |||||
| \(5\) | \(1\) | \(26\) | \(66\) | \(26\) | \(1\) | \(0\) | ||||
| \(6\) | \(1\) | \(57\) | \(302\) | \(302\) | \(57\) | \(1\) | \(0\) | |||
| \(7\) | \(1\) | \(120\) | \(1191\) | \(2416\) | \(1191\) | \(120\) | \(1\) | \(0\) | ||
| \(8\) | \(1\) | \(247\) | \(4293\) | \(15619\) | \(15619\) | \(4293\) | \(247\) | \(1\) | \(0\) | |
| \(9\) | \(1\) | \(502\) | \(14608\) | \(88234\) | \(\small{156190}\) | \(88234\) | \(14608\) | \(502\) | \(1\) | \(0\) |
性质和恒等式
从表中可以看出，欧拉数具有对称性： \[ \color{blue}{\elr{n}{k}=\elr{n}{n-1-k}} \] 因为 \(\pi_1\cdots\pi_n\) 有 \(k\) 个升高当且仅当 \(\pi_n\cdots\pi_1\) 有 \(n-1-k\) 个升高。
\(\textbf{Worpitzky}\) 恒等式： \[ \color{blue}{x^n=\sum_k\elr{n}{k}\binom{x+k}{n}} \] 证明：数学归纳法。首先 \(n=0\) 时，\(1=\sum\limits_k\langle\begin{smallmatrix}0\\k\end{smallmatrix}\rangle\binom{x+k}{0}=1\) 成立；假设 \(\leqslant n\) 均成立，则： \[ \begin{align} x^{n+1}&=x\cdot x^n\\ &=x\sum\limits _k\elr{n}{k}\binom{x+k}{n}\\ &=\sum_k\elr{n}{k}\left[(k+1)\binom{x+k}{n+1}+(n-k)\binom{x+k+1}{n+1}\right]\\ &=\sum_k\left(\elr{n+1}{k}-(n+1-k)\elr{n}{k-1}\right)\binom{x+k}{n+1}+\sum_k\elr{n}{k}(n-k)\binom{x+k+1}{n+1}\\ &=\sum_k\elr{n+1}{k}\binom{x+k}{n+1}+\sum_k\elr{n}{k}(n-k)\binom{x+k+1}{n+1}-\sum_k(n+1-k)\elr{n}{k-1}\binom{x+k}{n+1}\\ &=\sum_k\elr{n+1}{k}\binom{x+k}{n+1} \end{align} \] 证毕。（注：上述推导用了恒等式：\(x\binom{x+k}{n}=(k+1)\binom{x+k}{n+1}+(n-k)\binom{x+k+1}{n+1}\). ）
还有一些其他性质： \[ \begin{align} &\elr{n}{m}=\sum_{k=0}^m\binom{n+1}{k}(m+1-k)^n(-1)^k\\ &m!\strb{n}{m}=\sum_k\elr{n}{k}\binom{k}{n-m}\\ &\elr{n}{m}=\sum_k\strb{n}{k}\binom{n-k}{m}(-1)^{n-k-m}k! \end{align} \]
（二阶欧拉数和斯特林多项式目前跳过）