组合数学笔记(四)

组合数学

第8章特殊计数序列

8.1 Catalan 数

定义

Catalan 数列是序列 $C_{0}, C_{1}, \dots, C_{n}, \dots,$ 其中

C_{n} = \frac{1}{n + 1} (\binom{2 n}{n}) ， n = 0, 1, 2, . . .

是第 $n$ 个 Catalan 数。

凸 $n + 1$ 边形被在其内部不相交的对角线划分成三角形区域的方法数为 $C_{n - 1}$

由 $C_{n - 1} = h_{n}$ 得递推为：

C_{n} = C_{0} C_{n - 1} + C_{1} C_{n - 2} + . . . + C_{n - 1} C_{0}

另一个递推：

C_{n} = \frac{4 n - 2}{n + 1} C_{n - 1} (n \geq 1), C_{0} = 1

应用

括号化问题
出栈次序问题
$n$ 个结点构成得二叉树数

定理

8.1.1

考虑由 $n$ 个 $+ 1$ 和 $n$ 个 $- 1$ 构成的 $2 n$ 项序列

a_{1}, a_{2}, . . ., a_{2 n},

其部分和总满足：

a_{1} + a_{2} + . . . + a_{k} \geq 0 (k = 1, 2, . . ., 2 n)

的序列的个数等于第 $n$ 个Catalan数

可解决的问题

买票找零问题
走方格问题

拟 Catalan 数

定义一个新数列：

C_{1}^{*}, C_{2}^{*}, . . ., C_{n}^{*}, . . . .

其中， $C_{n}^{*} = n! C_{n - 1}, n = 1, 2, . . ., n, . . .$

得到：

C_{n}^{*} = (n - 1)! (\binom{2 n - 2}{n - 1})

将 Catalan 数的递推关系代入得到拟 Catalan 数的递推
关系：

C_{n}^{*} = (4 n - 6) C_{n - 1}^{*} (n \geq 1)

初值为：

C_{1}^{*} = 1

8.2 差分序列

定义

设 $h_{0}, h_{1}, h_{2}, \dots, h_{n}, \dots$ 是一个序列。定义新序列：

Δ h_{0}, Δ h_{1}, Δ h_{2}, \dots, Δ h_{n}, \dots ，

称为 $h_{0}, h_{1}, h_{2}, \dots, h_{n}, \dots$ 的（一阶）差分序列，其中 $Δ h_{n} = h_{n + 1} － h_{n} (n \geq 0)$ ，是序列的相邻项的差。

递归定义

对 $0$ 阶差分序列： $h_{0}, h_{1}, h_{2}, \dots, h_{n}, \dots,$

对 $1$ 阶差分序列： $Δ^{1} h_{n} ＝ h_{n + 1} － h_{n} (n ＝ 0, 1, 2, \dots)$

对 $2$ 阶差分序列：

\begin{aligned} Δ^{2} h_{n} = Δ (Δ^{1} h_{n}) \\ = & Δ^{1} h_{n + 1} － Δ^{1} h_{n} = (h_{n + 2} － h_{n + 1}) － (h_{n + 1} － h_{n}) \\ = & h_{n + 2} － 2 h_{n + 1} + h_{n} (n \geq 0) \end{aligned}

对 $k$ 阶差分序列：

Δ^{k} h_{n} = Δ (Δ^{k - 1} h_{n}) = Δ^{k - 1} h_{n + 1} － Δ^{k - 1} h_{n} (n = 0, 1, 2, . . .)

差分表

设序列 $h_{n} (n = 0, 1, 2, . . .)$ ，最上面一行是第 $0$ 行！！！

h_{0} h_{1} h_{2} h_{3} h_{4} . . . Δ^{1} h_{0} Δ^{1} h_{1} Δ^{1} h_{2} Δ^{1} h_{3} . . . Δ^{2} h_{0} Δ^{2} h_{1} Δ^{2} h_{2} . . . Δ^{3} h_{0} Δ^{3} h_{1} . . . . . .

$Δ^{p} h_{n} = Δ^{p - 1} h_{n + 1} － Δ^{p - 1} h_{n}$
序列 $h_{n} (n ＝ 0, 1, 2, \dots)$ 的差分表由第 $0$ 行确定

定理

8.2.1

设序列的通项 $h_{n}$ 是 $n$ 的 $p$ 次多项式：

h_{n} = a_{p} n^{p} + a_{p - 1} n^{p - 1} + a_{p - 2} n^{p - 2} + \dots \dots + a_{1} n + a_{0},

则对于所有的 $n \geq 0$ ，必有： $∆^{p + 1} h_{n} = 0$ 。

8.2.2

差分表的第 $0$ 条对角线等于

c_{0}, c_{1}, c_{2}, \dots, c_{p}, 0, 0, 0, \dots ， 其 中 c p \neq 0

的序列的通项满足：

h_{n} = c_{0} (\binom{n}{0}) + c_{1} (\binom{n}{1}) + c_{2} (\binom{n}{2}) + . . . + c_{p} (\binom{n}{p})

的关于 $n$ 的 $p$ 次多项式。

证明思路

线性性+简单差分表

8.2.3

假设序列 $h_{0}, h_{1}, \dots, h_{n}, \dots$ 的差分表的第 $0$ 条对角线等于

c_{0}, c_{1}, \dots, c_{p}, 0, 0, \dots

那么：

Σ_{k = 0}^{n} h_{k} = c_{0} (\binom{n + 1}{1}) + c_{1} (\binom{n + 1}{2}) + . . . + c_{p} (\binom{n + 1}{p + 1})

（证明中间有一段： $Σ_{k = 0}^{n} (\binom{k}{p}) = (\binom{n + 1}{p + 1})$ ）

应用

一般项为多项式的序列的部分和

8.2.4

若 $1 \leq k \leq p - 1$ ，则：

S (p, k) = k S (p - 1, k) + S (p - 1, k - 1)

类比二项式公式中：

(\binom{n}{k}) = (\binom{n - 1}{k}) + (\binom{n - 1}{k - 1})

类 $P a s c a l$ 三角形：

直接上方的元素乘以 $k$ 再加上其左上方的元素

8.2.5

第二类 $S t i r l i n g$ 数 $S (p, k)$ 计数的是把 $p$ 元素集合划分到 $k$ 个不可区分的盒子且没有空盒子的划分的个数。

8.2.6

对每一个满足 $0 \leq k \leq p$ 的整数 $k$ ，都有

S^{♯} (p, k) = Σ_{t = 0}^{k} (- 1)^{t} (\binom{k}{t}) (k - t)^{p}

从而 $S (p, k) = \frac{1}{k!} Σ_{t = 0}^{k} (- 1)^{t} (\binom{k}{t}) (k - t)^{p}$

8.2.7

如果 $p \geq 1$ ，则：

B_{p} = (\binom{p - 1}{0}) B_{0} + (\binom{p - 1}{1}) B_{1} + (\binom{p - 1}{2}) B_{2} + . . . + (\binom{p - 1}{p - 1}) B_{p - 1}

8.2.8

若 $1 \leq k \leq p - 1$ ，则：

s (p, k) = (p - 1) s (p - 1, k) + s (p - 1, k - 1)

8.2.9

第一类 $S t i r l i n g$ 数 $S_{1} (p, k)$ 是将 $p$ 个物品排成 $k$ 个非空的循环排列的方法数

性质

差分表由第 $0$ 行上元素的值就能决定
差分表也可由第 $0$ 条对角线决定

例子

简单差分表1

若第 $0$ 条对角线全为 $0$

简单差分表1

第 $0$ 条对角线除一个 $1$ 外都是 $0$

首先 $1$ 在第 $p$ 行，前 $p$ 个元素就都为 $0$ ，从 $p + 1$ 行开始的所有行的元素都是 $0$

其次 $h_{p} = 1$ ， $h_{0} = 0, h_{1} = 0, . . ., h_{p - 1} = 0$ ，故 $h_{n}$ 有因子 $n (n - 1) . . . (n - (p - 1))$ ，再代入 $h_{p} = 1$ ，得到：

h_{n} = \frac{n (n - 1) . . . (n - (p - 1))}{p!} = (\binom{n}{p})

差分表的线性性

设 $g_{n}$ 和 $f_{n}$ 分别是两个序列的通项，若 $h_{n} = g_{n} + f_{n}$

一般的： $Δ^{p} h_{n} = Δ^{p} g_{n} + Δ^{p} f_{n}, p \geq 0$
更一般的，对于任何常数 $c, d$ 来说， $Δ^{p} (c g_{n} + d f_{n}) = c Δ^{p} g_{n} + d Δ^{p} f_{n} (p \geq 0, n \geq 0)$

差分表的第0条

组合意义

(由定理8.2.2)

对于序列 $h_{n} = n^{p}$ ，设其差分表中第 $0$ 条对角线上的元素为 $c_{0}, c_{1}, \dots, c_{p}, 0, 0, \dots ，$ 引入标记：

c (p, 0) = c_{0}, c (p, 1) = c_{1}, \dots, c (p, p) = c_{p}, 0, 0, . . .

则有：

\begin{aligned} h_{n} = n^{p} & = c_{0} (\binom{n}{0}) + c_{1} (\binom{n}{1}) + . . . + c_{p} (\binom{n}{p}) \\ = c (p, 0) (\binom{n}{0}) + c (p, 1) (\binom{n}{1}) + . . . + c (p, p) (\binom{n}{p}) \end{aligned}

特殊值1： $c (p, 0)$

c (p, 0) = {\begin{cases} 1 & p = 0 \\ 0 & p \geq 1 \end{cases}

特殊值2：

由 $n^{p}$ 项系数相等，得： $1 = \frac{c (p, p)}{p!}$

c (p, p) = p!

特殊值3：

令 [n]_{k} = {\begin{cases} n (n - 1) . . . (n - k + 1), & k \geq 1 \\ 1, & k = 0 \end{cases}

则， $[n]_{k}$ = $n$ 个不同元素中取 $k$ 个元素的排列数 $P (n, k)$

递推关系：

[n]_{k} = (n - k) [n]_{k}

且：

[n]_{k} = k! (\binom{n}{k})

故：

\begin{aligned} h_{n} = n^{p} & = c (p, 0) \frac{[n]_{0}}{0!} + c (p, 1) \frac{[n]_{1}}{1!} + . . . + c (p, p) \frac{[n]_{p}}{p!} \\ = \sum_{k = 0}^{p} c (p, k) \frac{[n]_{k}}{k!} \\ = \sum_{k = 0}^{p} \frac{c (p, k)}{k!} [n]_{k} \end{aligned}

令 $S (p, k) = \frac{c (p, k)}{k!}$ $(0 \leq k \leq p)$ ，成为第二类 $S r i r l i n g$ 数

所以 $h_{n} = n^{p}$ 的展开式变为： $h_{n} = n^{p} = \sum_{k = 0}^{p} S (p, k) [n]_{k}$

第二类 $S r i r l i n g$ 数

特殊值：

S (p, 0) = c (p, 0) = {\begin{cases} 1 & p = 0 \\ 0 & p \geq 1 \end{cases}

S (p, p) = 1 (p \geq 1)

递推公式：

定理8.2.4

组合解释：

投球入盒

定理8.2.5

$B e l l$ 数

令 $S^{♯} (p, k) = k! S (p, k)$ 表示把 ${1, 2, \dots, p}$ 分到 $k$ 个非空且可区分的
盒子的划分个数，则

S^{♯} (p, k) = k! S (p, k)

公式：定理 8.2.6

所以 $S^{♯} (p, k)$ ：把 ${1, 2, \dots, p}$ 分到 $k$ 个非空且可区分的盒子的划分个数。

$p$ 个物品	$k$ 个盒子	空盒
有区别	无区别	没有	$S (p, k)$
有区别	有区别	没有	$S^{♯} (p, k)$

定义

定义 $B e l l$ 数是将 $p$ 个元素的集合划分到非空、不可区分的盒子（盒子数 $\leq p$ ）的划分数，记为 $B_{p}$ ，则：

B_{p} = S (p, 0) + S (p, 1) + . . . + S (p, p)

是第二类 $S t i r l i n g$ 数三角形的一行的元素和

递推

定理 8.2.7

第一类 $S r i r l i n g$ 数

对比

第二类 $S r i r l i n g$ 数 $S (n, p)$

指出如何用 $[n]_{0}, [n]_{1}, [n]_{2}, . . ., [n]_{p}$ 写出 $n^{p}$
把 $p$ 个元素的集合划分到 $k$ 个不可区分的盒子且没有空盒的划分的个数

第一类 $S r i r l i n g$ 数 $s (n, p)$

如何用 $n^{0}, n^{1}, n^{2}, . . ., n^{p}$ 写出 $[n]_{p}$
将 $p$ 个物品排成 $k$ 个非空的循环排列方法数

定义

一般地， $[n]_{p}$ 展开式有 $p$ 个因子
乘开后得到 $n$ 的幂多项式， $n^{p}, n^{p - 1}, . . ., n^{1}, n^{0}$
其系数的符号正负相间。故：

[n]_{p} = a_{n}^{p} n^{p} - a_{n}^{p - 1} n^{p - 1} + . . . . . . + + (- 1)^{p - 1} a_{n}^{1} n^{1} + (- 1)^{p} a_{n}^{0} n^{0}

n_{k} $ $ 前 的 系 数 $ $ a_{n}^{k} $ $ 称 为 第 一 类 $ $ S t i r l i n g $ $ 数 ， 记 为 $ $ s (p, k)

特殊值

s (p, 0) = 0 (p \geq 1) s (p, p) = 1 (p \geq 0)

递推式

定理 8.2.8

组合意义

定理 8.2.9

小结

$p$ 个球	$k$ 个盒	是否为空	方案个数
有区别	有区别	有空盒	$k^{p}$
有区别	无区别	无空盒	$S (p, k)$	$S_{2} (p, k)$
有区别	有区别	无空盒	$k! S (p, k)$	$S^{♯} (p, k)$
有区别	无区别	有空盒	$S (p, 1) + S (p, 2) + . . . S (p, k) ， p \geq k$	$B e l l$ 数
有区别	无区别	有空盒	$S (p, 1) + S (p, 2) + . . . S (p, p) ， p \leq k$	$B e l l$ 数
有区别	$k$ 个循环序列	非空	$s (p, k)$	$S_{1} (p, k)$

组合数学

第8章 特殊计数序列

8.1 Catalan 数

定义

应用

定理

8.1.1

拟 Catalan 数

8.2 差分序列

定义

递归定义

差分表

定理

8.2.1

8.2.2

证明思路

8.2.3

应用

8.2.4

8.2.5

8.2.6

8.2.7

8.2.8

8.2.9

性质

例子

简单差分表1

简单差分表1

差分表的线性性

差分表的第0条

组合意义

特殊值1： c(p,0)

特殊值2：

特殊值3：

第二类 Srirling 数

特殊值：

递推公式：

组合解释：

Bell 数

定义

递推

第一类 Srirling 数

对比

定义

特殊值

递推式

组合意义

小结

微信扫一扫：分享

第8章特殊计数序列

特殊值1： $c (p, 0)$

第二类 $S r i r l i n g$ 数

$B e l l$ 数

第一类 $S r i r l i n g$ 数