组合数学笔记(四)

组合数学

第8章 特殊计数序列

8.1 Catalan 数

定义

Catalan 数列是序列 $C_0, C_1,…, C_n,…,$ 其中

$$C_n = \frac{1}{n+1}{{2n}\choose{n}}，\quad n=0,1,2,...$$

是第 $n$ 个 Catalan 数。

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

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

$$C_n=C_0C_{n-1}+C_1C_{n-2}+...+C_{n-1}C_0$$

另一个递推：

$$C_n=\frac{4n-2}{n+1}C_{n-1}\quad(n\geq1),C_0=1$$

应用

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

定理

8.1.1

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

$$a_1,a_2,...,a_{2n},$$

其部分和总满足：

$$a_1+a_2+...+a_k\geq0\quad (k=1,2,...,2n)$$

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

可解决的问题

• 买票找零问题
• 走方格问题

拟 Catalan 数

定义一个新数列：

$$C_1^*,C_2^*,...,C_n^*,....$$

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

得到：

$$C_n^*=(n-1)!{2n-2\choose n-1}$$

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

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

初值为：

$$C_1^*=1$$

8.2 差分序列

定义

设 $h_0, h_1, h_2, …, h_n, …$ 是一个序列。定义新序列：

$$\Delta h_0, \Delta h_1, \Delta h_2, …, \Delta h_n,…，$$

称为 $h_0, h_1, h_2, …, h_n, …$ 的（一阶）差分序列，其中 $\Delta h_n= h_{n+1}－h_n\quad(n≥0)$ ，是序列的相邻项的差。

递归定义

对 $0$ 阶差分序列： $h_0, h_1, h_2, …, h_n, …,$

对 $1$ 阶差分序列： $\Delta^1h_n＝h_{n+1}－h_n\quad(n＝0,1,2,…)$

对 $2$ 阶差分序列：

$$\begin{aligned} &\Delta^2h_n=\Delta(\Delta^1h_n)\\ =&\Delta^1h_{n+1}－\Delta^1h_n = (h_{n+2}－h_{n+1})－(h_{n+1}－h_n)\\ =&h_{n+2}－2h_{n+1}+ h_n\quad(n≥ 0) \end{aligned}$$

对 $k$ 阶差分序列：

$$\Delta^kh_n=\Delta(\Delta^{k-1}h_n) =\Delta^{k-1}h_{n+1}－\Delta^{k-1}h_n \quad (n=0,1,2,...)$$

差分表

设序列 $h_n\quad(n=0,1,2,...)$ ，最上面一行是第 $0$ 行！！！

$$h_0 \qquad h_1 \qquad h_2 \qquad h_3 \qquad h_4 \qquad ...\\ \Delta^1h_0 \quad \Delta^1h_1 \quad \Delta^1h_2 \quad \Delta^1h_3 \quad ...\\ \Delta^2h_0 \quad \Delta^2h_1 \quad \Delta^2h_2 \quad ...\\ \Delta^3h_0 \quad \Delta^3h_1 \quad ...\\ ...$$

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

定理

8.2.1

设序列的通项 $h_n$ 是 $n$ 的 $p$ 次多项式：

$$h_n= a_pn^p+a_{p-1}n^{p-1}+a_{p-2}n^{p-2}+……+a_1n+a_0,$$

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

8.2.2

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

$$c_0,c_1,c_2, …,c_p,0,0,0, …， 其中cp \neq 0$$

的序列的通项满足：

$$h_n=c_0{n\choose0}+c_1{n\choose1}+c_2{n\choose2}+...+c_p{n\choose p}$$

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

证明思路

线性性+简单差分表

8.2.3

假设序列 $h_0, h_1, …, h_n,…$ 的差分表的第 $0$ 条对角线等于

$$c_0, c_1, …, c_p, 0, 0,…$$

那么：

$$\Sigma^n_{k=0}h_k=c_0{n+1\choose1}+c_1{n+1\choose2}+...+c_p{n+1\choose p+1}$$

（证明中间有一段： $\Sigma^n_{k=0}{k\choose p}={n+1\choose p+1}$ ）

应用

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

8.2.4

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

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

类比二项式公式中：

$${n\choose k}={n-1\choose k}+{n-1\choose k-1}$$

类 $Pascal$ 三角形：

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

8.2.5

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

8.2.6

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

$$S^{\sharp}(p,k)=\Sigma^k_{t=0}(-1)^t{k\choose t}(k-t)^p$$

从而 $S(p,k)=\frac 1{k!}\Sigma^k_{t=0}(-1)^t{k\choose t}(k-t)^p$

8.2.7

如果 $p\geq1$ ，则：

$$B_p={p-1\choose0}B_0+ {p-1\choose1}B_1+ {p-1\choose2}B_2+ ... +{p-1\choose 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

第一类 $Stirling$ 数 $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!}={n\choose p}$$

差分表的线性性

设 $g_n$ 和 $f_n$ 分别是两个序列的通项，若 $h_n = g_n +f_n$

• 一般的： $\Delta^ph_n=\Delta^pg_n+ \Delta^pf_n\quad,\quad p\geq 0$
• 更一般的，对于任何常数 $c, d$ 来说， $$\Delta^p(cg_n+df_n)= c\Delta^pg_n+d\Delta^pf_n\quad(p≥ 0, n≥ 0)$$

差分表的第0条

组合意义

(由定理8.2.2)

对于序列 $h_n= n^p$ ，设其差分表中第 $0$ 条对角线上的元素为 $c_0, c_1, …, c_p, 0, 0,…，$ 引入标记：

$$c(p, 0) =c_0, c(p, 1) = c_1, …, c(p, p) =c_p, 0, 0, ...$$

则有：

$$\begin{aligned} h_n=n^p&=c_0{n\choose0}+c_1{n\choose1}+...+c_p{n\choose p}\\ &=c(p,0){n\choose0}+c(p,1){n\choose1}+...+c(p,p){n\choose 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\geq1\\ 1, &k=0 \end{cases}$$

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

递推关系：

$$[n]_k=(n-k)[n]_k$$

且：

$$[n]_k=k!{n\choose 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^p_{k=0}c(p,k){\frac{[n]_k}{k!}}\\ &=\sum^p_{k=0}\frac{c(p,k)}{k!}[n]_k \end{aligned}$$

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

所以 $h_n=n^p$ 的展开式变为： $h_n=n^p=\sum^p_{k=0}S(p,k)[n]_k$

第二类 $Srirling$ 数

特殊值：

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

递推公式：

定理8.2.4

组合解释：

投球入盒

定理8.2.5

$Bell$ 数

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

$$S^{\sharp}(p,k) = k!S(p,k)$$

公式：定理 8.2.6

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

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

定义

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

$$B_p=S(p,0)+S(p,1)+...+S(p,p)$$

是第二类 $Stirling$ 数三角形的一行的元素和

递推

定理 8.2.7

第一类 $Srirling$ 数

对比

第二类 $Srirling$ 数 $S(n,p)$

• 指出如何用 $[n]_0,[n]_1,[n]_2,...,[n]_p$ 写出 $n^p$
• 把 $p$ 个元素的集合划分到 $k$ 个不可区分的盒子且没有空盒的划分的个数

第一类 $Srirling$ 数 $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^p_nn^p -a^{p-1}_nn^{p-1} +......+ +(-1)^{p-1}a^{1}_nn^{1}+ (-1)^{p}a^{0}_nn^{0}$$ $$n_k $$ 前的系数 $$ a_n^k $$ 称为第一类 $$ Stirling $$ 数，记为 $$ s(p, k)$$

特殊值

$$s(p, 0) = 0 \quad(p\geq1)\\s(p, p) =1 \quad(p\geq0)$$

递推式

定理 8.2.8

组合意义

定理 8.2.9

小结

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