特殊的数

发表于 2022-03-17 更新于 2022-11-09 分类于数学本文字数： 3487 阅读时长 ≈ 9 分钟

简介：卡特兰数，斯特林数，欧拉数，调和级数

卡特兰数(Catalan Numbers)

卡特兰数 (~~Català~~Catalan Numbers) 十分常用，序列的开头是 $1,1,2,5,14,42,\cdots$。

卡特兰数的主要应用是再括号序列上面，很多题目都可以转化成为括号序列的问题，就比如下面这个：

引入

有关卡特兰数的例题有很多，其中最经典的是下面这个：

我们有 $n$ 个元素和一个栈。这 $n$ 各元素是 $[1,n]$ 的所有整数，并且以升序排列。

现在我们将所有的元素放入栈中，并最终让所有元素都出栈。栈的pop()和push()的顺序由你自己来决定，问有多少种可能的出栈顺序。

分析

我们显然可以看出，我们不能对着一个空的栈疯狂pop()，也不能对着一个空的进栈序列疯狂push()。
所以，每一个pop()操作必定对应着之前的一个pop()操作，且所有pop()操作的次数与push()操作的次数相等。

我们尝试将push()和pop()抽象为前缀和的形式。
我们可以将push()转化为+1，pop()转化为-1。
那么，我们的要求就是：

该序列的每一个前缀和必定大于等于0，且整个序列的和必定为0。

这就需要我们使用卡特兰数。

求值

我们这里使用 $C_n$ 来代表第 $n$ 项卡特兰数。

我们通常使用的都是单个的卡特兰数（除非有多组测试数据），所以这里首先给出了通项公式。

卡特兰数的通项公式是这个样子的：

$$
C_n=\frac{C_{2n}^n}{n+1}
$$

如果需要生成卡特兰数数列，那么我们可以进行递推：

首先，$C_0=C_1=1$，这两个我们先自己手动输入进去。
之后我们可以根据这个递推公式来计算：

$$
C_n = C_{n-1} \frac{4n-2}{n+1}
$$

我们需要注意，在 $n \in [ 0,16 ] $ 的时候可以只开int；在 $n \in [ 17,35 ] $ 的时候就需要开long long了；而当 $n \geq 36$ 的时候就只能使用高精度或者用 Python 来求了。

递推代码示例：

Python：

ans = 1
n = int(input("项数："))
print("1:" + str(ans))
for i in range(2, n + 1):
    ans = ans * (4 * i - 2) // (i + 1)
    print(str(i) + ":" + str(ans))

例题 Luogu P1044 代码示例：

Python：

ans = 1
n = int(input(""))
for i in range(2, n + 1):
    ans = ans * (4 * i - 2) // (i + 1)
print(str(ans))

C++：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    scanf("%d", &n);
    long long ans = 1;
    for(int i = 1; i <= n; i++)
        ans = ans * (4 * i - 2) / (i + 1);
    printf("%lld\n", ans);
    return 0;
}

斯特林数(Stirling Numbers)

斯特林数 (Stirling Numbers) 分为第一类斯特林数和第二类斯特林数。

我们使用 $S_1(n,k)$ 来表示第一类斯特林数，使用 $S_2(n,k)$ 来表示第二类斯特林数。
通常的表达方式是这样的：
使用 $\begin{bmatrix} n \\ k \end{bmatrix}$ 来表示第一类斯特林数，使用 $\begin{Bmatrix} n \\ k \end{Bmatrix}$ 来表示第二类斯特林数。
但是因为这个样子在 $ \LaTeX $ 里面并不好打，所以我就索性换了个表达方式，以便我能够打出来。

第二类斯特林数

第二类斯特林数比第一类更加常用（其实是所有这些数里除了组合数外最常用的），所以我们先介绍第二类斯特林数。

定义

第二类斯特林数 $S_2(n,k)$ $(n \geq k)$ 表示讲一个有 $n$ 件互不相同的物品的集合划分为 $k$ 个非空子集的方法数。

例：

$S_2(4,2)$ 有下列几种情况：

$$
\begin{align}
\{ 1 , 2 , 3 \} & \cup \{ 4 \} \\
\{ 1 , 2 , 4 \} & \cup \{ 3 \} \\
\{ 1 , 3 , 4 \} & \cup \{ 2 \} \\
\{ 2 , 3 , 4 \} & \cup \{ 1 \} \\
\{ 1 , 2 \} & \cup \{ 3 , 4 \} \\
\{ 1 , 3 \} & \cup \{ 2 , 4 \} \\
\{ 1 , 4 \} & \cup \{ 2 , 3 \}
\end{align}
$$

所以 $S_2(4,2)=7$ 。

性质

显而易见的，$S_2(n,1)=1$ ，$S_2(n,n)=1$ 。
特别的，我们规定 $S_2(0,0)=1$ ，$S_2(n,0)=0$ 。

求值

我们从较小的 $k$ 来入手。

当 $k \leq 1$ 时比较好办，我们可以通过上面两个显而易见的性质推出来。

而当 $k=2$ 时，我们可以这样想：
一个物品不是放在一个篮子里面就是放在另一个篮子里面，所以 $n$ 个物品一共有 $n^2$ 中不同的划分方式。
而因为两个篮子不区分，且有着非空的要求，所以最终的划分方式就只有 $2^{n-1}-1$ 种了。
所以，

$$
S_2(n,k) = 2^{n-1}-1 \quad (n>0)
$$

或者使用更难打出来但更眼熟的方式：

$$
\begin{Bmatrix}
n \\ 2
\end{Bmatrix}
= 2^{n-1}-1
$$

再来看 $k>2$ 的情况。

我们仍然对每一个物品进行分析，只不过我们这次是倒序分析的。

对于最后的一个物品，我们可以将其单独分成一堆，也可以将其放入之前的 $n-1$ 个物品组成的 $k$ 堆中的一堆中。

对于前一个选择，我们有 $S_2(n-1,k-1)$ 中排列的方法；而对于后一种，我们有 $S_2(n-1,k)$ 中方法，最后还需乘以我们可以做出的选择数 $k$。

递推式

所以总结一一下，我们有以下递推式：

$$
S_2(n,k) = k · S_2(n-1,k) + S_2(n-1,k-1)
$$

或者使用更难打出来但更眼熟的表达方式：

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

通项式

还有一种直接求的通项公式，是这个样子的：

$$
S_2(n,m)=\sum_{i=0}^m \frac{(-1)^{m-i} i^n}{i! (m-i)!}
$$

第一类斯特林数

定义

第一类斯特林数 $S_1(n,k) (n \geq k)$ 也是一种描述将 $n$ 个互不相同的物品划分为 $k$ 个不同的轮换的方案。

所谓轮换，就是指像项链一样的环形排列，可以类比成把所有的元素像珠子一样穿到项链上。

比如说一个轮换 $[A,B,C,D]$，它有4种异构体：

$$
[A,B,C,D]=[B,C,D,A]=[C,D,A,B]=[D,A,B,C]
$$

所以说对于 $S_1(4,2)$，有下列几种情况：

$$
\begin{align}
[ 1,2,3 ] [ 4 ] \quad [ 1,3,2 ] [ 4 ] \\
[ 1,2,4 ] [ 3 ] \quad [ 1,4,2 ] [ 3 ] \\
[ 1,3,4 ] [ 2 ] \quad [ 1,4,3 ] [ 2 ] \\
[ 2,3,4 ] [ 1 ] \quad [ 2,4,3 ] [ 1 ]
\end{align}
$$
$$
[ 1,2 ] [ 3,4 ] \quad
[ 1,3 ] [ 2,4 ] \quad
[ 1,4 ] [ 2,3 ]
$$

一共11种。

所以， $S_1(4,2)=11$。

我们不难看出，$S_1(n,k) \geq S_2(n,k)$。

求值

我们仍然从较小的 $k$ 开始。

当 $k=1$ 时，我们对于每一个空位考虑。第 $i$ 个空位可以随意选择 $n-i+1$ 个物品，总体就是 $\displaystyle \prod_{i=1}^n (n-i+1)$，显而易见是 $(n-1)!$。
所以：

$$
S_1(n,1)=(n-1)!
$$

当所有的轮换都至多含两个物品的时候，我们就会发现，此时的轮换与子集是等价的。
这种情况只能在 $k=n-1$ 的时候成立，也就是说，
$$
\begin{align}
S_1(n,n) &= S_2(n,n) = 1 \\
S_1(n,n-1) &= S_2(n,n-1) = C^2_n
\end{align}
$$

递推式

我们考虑一般的情况。

还是类似之前考虑 $S_2$ 时的方法，我们还是考虑最后一个元素。

对于这个元素，我们可以将其单独成堆，也可以将其放在之前的任意一个轮换里面。

显然，对于前者，我们有 $S_1(n-1,k-1)$ 种方案；对于后者，我们有 $S_1(n-1,k)$ 种方案，而这个物品有 $n-1$ 种放置的位置（指插在任意一个元素的后面），所以总共是这样的式子：

$$
S_1(n,k) = (n-1) · S_1(n-1,k) + S_1(n-1,k-1)
$$

或者使用更难打出来但更眼熟的表达方式：

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

第一类斯特林数没有实用的通项公式。