组合数学笔记(三)

组合数学

第6章 容斥原理及应用

6.1 容斥原理

定义

计数函数： $\sigma_x(A)$

$$\sigma _x(A)= \left\{\begin{matrix} 1,x\in A \\ 0,x\notin A \end{matrix}\right.$$

定理和推论

设集合 $A_i$ 是集合S中满足性质 $P_i$ 的所有物体的子集， $i =1, 2, …, m$ , 则

6.1.1

集合 $S$ 不具有性质 $P_1,P_2,…,P_m$ 的物体的个数：

$$|\overline{A_1}\cap...\cap \overline{A_m}| = |S|-\sum|A_i|+\sum|A_i\cap A_j| -\sum|A_i \cap A_j \cap A_k|+...+ (-1)^m|A_1\cap A_2\cap...\cap A_m|$$

6.1.2

集合 $S$ 至少具有性质 $P_1,P_2,…,P_m$ 之一的物体的个数：

$$|A_1\cup A_2...\cup A_m| = \sum|A_i|-\sum|A_i\cap A_j| +\sum|A_i \cap A_j \cap A_k|+...+ (-1)^{m+1}|A_1\cap A_2\cap...\cap A_m|$$

其中，第一个和对 $\lbrace 1, 2, …, m \rbrace$ 的所有的 1 子集 $\lbrace i\rbrace$ 进行, 第二个和对 $\lbrace 1, 2, …, m \rbrace$ 的所有的 2 集合 $\lbrace i,j\rbrace$ 进行, 依此类推

特别情况

若：

$$\begin{aligned} & \alpha_1=|A_1|=|A_2|=…=|A_m| (所有集合包含的元素个数相等)\\ & \alpha_2=|A_1∩A_2|=…=|A_{m-1}∩A_m| (任意两个集合的交包含相等个数的元素)\\ & \alpha_3=|A_1∩A_2∩A_3|=…=|A_{m-2}∩A_{m-1}∩A_m| (任意三个集合的交包含相等个数的元素个数）)\\ & … \\ & \alpha_k =|A_1∩ … ∩A_k|=…=|A_{m-k+1}∩…∩A_m|\\ & … \\ & \alpha_m=|A_1∩A_2∩ …∩A_m| \end{aligned}$$

则，

$$\begin{aligned} &\overline {A_1} \cap ... \cap \overline {A_n}\\ &= \alpha_0 - {m\choose1}\alpha_1 + {m\choose2}\alpha_2 -{m\choose3}\alpha_3 + ... + (-1)^k{m\choose k}\alpha_k+...+(-1)^m\alpha_m \end{aligned}$$

6.2 带重复的组合

多重集组合与方程整数解个数

6.2 带重复的组合
回顾一下2.5

多重集 $T=\lbrace n_1×a_1, n_2×a_2,…, n_k×a_k \rbrace$ 的 $r$ 组合数等于方程

$$x_1+x_2+ …+x_k=r,\\ 0\leq x_1\leq n_1, 0\leq x_2\leq n_2, …, 0\leq xk \leq n_k$$

的整数解的个数。

6.3 错位排列

定义

1.

设 $X=\lbrace 1, 2, …, n\rbrace$ , 它的排列用 $i_1i_2…i_n$ 表示。错位排列是使得 $i_1\neq1, i_2\neq2,…, i_n\neq n$ 的排列。用 $D_n$ 表示错位排列个数

定理

6.3.1

对 $n \geq 1$ ，

$$D_n = n!(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+...+(-1)^n\frac{1}{n!})$$

性质

错位排列的递推关系

1

$$D_n= (n-1)(D_{n-2}+D_{n-1}), (n=3,4 ...)\\ D_2=1 ; D_1=0$$

2

$$D_n=nD_{n-1}+(-1)^n$$

6.4 带有禁止位置的排列

定义

(1) 带有禁止位置的排列

令 $X_1 , X_2 , … , X_n$ 是 $\lbrace1, 2, …, n\rbrace$ 的子集 (可以为空集)，用 $P(X_1 , X_2 , … , X_n)$ 表示 $\lbrace1, 2, …, n\rbrace$ 的排列 $i_1i_2…i_n$ 的集合，使得： $i_1\notin X_1，i_2 \notin X_2，…， i_n \notin X_n$

记 $p(X_1 , X_2 , … , X_n)=|P(X_1 , X_2 , … , X_n)|$ ，表示 $P(X_1 , X_2 , … , X_n)$ 中排列的个数。

(2) 带禁止位置的“非攻击性车”

令 $\lbrace1, 2, …, n\rbrace$ 的排列 $i_1 i_2… i_n$ 对应于棋盘上以方格

$$(1, i_1), (2, i_2),…, (n, i_n)$$

为坐标的n个车的位置

满足第 $j$ 行的车不在 $X_j$ 中的列， $j=1, 2,…, n$ ，共有多少种放置非攻击型车的方法。

定理

6.4.1

将 $n$ 个非攻击型不可区分的车放到带有禁止位置的 $n×n$ 的棋盘中，放法总数等于：

$$n!-r_1(n-1)!+r_2(n-2)!-…+(-1)^kr_k(n-k)!+…+(-1)^nr_n$$

所以 $r_1, r_2,…, r_n$ 的计算依赖于具体的问题！

• 任意两个车不在同一行或同一列
• 所有的 $k$ 个车放置在其禁止位置上的放置方法数， $k=1, 2, …, n$
• $r_k$ 的计算不考虑剩下的 $n-k$ 个车的放置

6.5 另一个禁止位置问题

定义

相对禁止位置排列计数 $Q_n$

对 $Q_n$ ： $\lbrace1, 2,…, n\rbrace$ 的排列中没有 $12, 23, …, (n-1)n$ 这些 模式出现的排列的个数

定理

6.5.1

对于 $n\geq 1$ ，

$$\begin{aligned} Q_n &= n! + \Sigma^{n-1}_{k=1}(-1)^k{{n-1}\choose{k}}(n-k)!\\ &=n!-{n-1\choose1}(n-1)!+ {n-1\choose2}(n-2)!+...+ (-1)^{n-1}{n-1\choose n-1}1! \end{aligned}$$

例题

旋转木马问题

看ppt去

相对禁止 $Q_N$ 与错位排列 $D_n$ 的关系

$Q_n = D_n + D_{n-1}$

第7章 递推关系和生成函数

生成函数(也称母函数)核心思想：

• 把离散数列和幂级数一一对应起来，

  把离散数列间的相互结合关系对应成为幂级数间的运算关系

• 由幂级数形式来确定 离散数列 的构造

7.1 若干数列

定义

斐波那契数列

设有数列 $f_0, f_1, f_2,…, f_n, …$ 。如果 $f_0=0, f_1=1$ , 且满足递推关系 $f_n= f_{n-1}+f_{n-2}，n\geq2$
称该数列为斐波那契（Fibonacci）数列，这个数列的项称为斐波那契数

定理

7.1.1

斐波那契数 $f_n$ 满足公式

$$f_n=\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^n- \frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^n,n\geq0$$

7.1.2

沿 $Pascal$ 三角形从左下到右上的对角线上的二项式系数和是斐波那契数, 即

$$f_n={{n-1}\choose{0}}+ {{n-2}\choose{1}}+ {{n-3}\choose{2}}+...+ {{n-t}\choose{t-1}}$$

其中， t= $\lfloor{\frac{m+1}{2}}\rfloor$

性质

斐波那契数列

斐波那契数列的项的部分和

$$s_n=f_0+f_1+f_2+...+f_n=f_{n+2}-1$$

斐波那契数是偶数当且仅当n被3整除

斐波那契数能被3整除当且仅当n可被4整除

斐波那契数能被4整除当且仅当n可被6整除

Fibonacci数列与黄金分割数

$$\lim\limits_{x\rightarrow\infty}\frac{f_n}{f_{n+1}}=\frac{\sqrt{5}-1}{2} \approx 0.618$$

7.2 生成函数

涉及一个整数参数 $n$ 的某些计数问题的代数求解方法：生成函数（母函数）

*常见展开式

$$\begin{aligned} (1+x)^n&=\Sigma^n_{k=0}{n\choose k}x^k\\ (1-x)^n&=\Sigma^n_{k=0}(-1)^k{n\choose k}x^k \end{aligned}$$

对满足 $|x|<1$ 的任意 $x$ ，有：

$$\begin{aligned} \frac{1}{(1+x)^n}&=\Sigma^{\infty}_{k=0}(-1)^k{n+k-1\choose k}x^k\\ \frac{1}{(1-x)^n}&=\Sigma^{\infty}_{k=0}{n+k-1\choose k}x^k \end{aligned}$$

当$n=1$ 时，得：

$$\begin{aligned} \frac{1}{1+x}&=\Sigma^{\infty}_{k=0}(-1)^kx^k \quad (|x|<1)\\ \frac{1}{1-x}&=\Sigma^{\infty}_{k=0}x^k \quad (|x|<1) \end{aligned}$$

令 $x=y^m$ ，得：

$$\begin{aligned} \frac{1}{1+y^m}&=\Sigma^{\infty}_{k=0}(-1)^ky^{mk} \quad (|y|<1)\\ \frac{1}{1-y^m}&=\Sigma^{\infty}_{k=0}y^{mk} \quad (|y|<1) \end{aligned}$$

生成函数的定义

令 $h_0, h_1,…,h_n,…$ 为一无穷数列, 其生成函数 $g(x)$ 定义为：

$$\begin{aligned} g(x) &= h_0+ h_1 x + h_2 x^2 +…+ h_n x^n+…\\ &=\Sigma_{k=0}^\infty h_kx^k \end{aligned}$$

有限数列 $h_0, h_1,…,h_n$ 可以看作是无限数列 $h_0, h_1,…,h_n,0,...,0,...$

适合多重集组合

生成函数——多重集组合

求生成函数

设 $k$ 是正整数， $h_n$ 等于方程

$$e_1+e_2+…+e_k=n$$

的非负整数解个数，

即 $h_n$ 为多重集 $S=\lbrace∞\cdot a_1,∞\cdot a_2, …,∞\cdot a_k\rbrace$ 的 $n$ 组合个数， $e_i$ 表示在一个 $n$ 组合中 $a_i$ 出现的次数。

$$\begin{aligned} g(x)&=\Sigma^\infty_{n=0}{n+k-1\choose n}x^n=\frac{1}{(1-x)^k}\\ &=(\Sigma^\infty_{e_1=0}x^{e_1})(\Sigma^\infty_{e_2=0}x^{e_2})...(\Sigma^\infty_{e_k=0}x^{e_k}) \quad(2)\\ &=\Sigma^\infty_{e_1+...+e_k=n=0}x^{e_1}x^{e_2}...x^{e_k} \end{aligned}$$

当 $n$ 组合中 $a_i$ 的出现次数有约束时，将反映到 $(2)$ 式的第 $i$ 个因子中。

求通项

把生成函数向根本形式： $\Sigma_{k=0}^\infty h_kx^k$ 化简

排列逆序

记 $\pi$ 中的逆序的数目为 $inv(\pi)$

设 $h(n, t)$ 表示 $\lbrace1, 2, …, n\rbrace$ 的排列中有 $t$ 个逆序的排列的数目，则：

• 对于 $0 \leq t \leq n(n-1)/2$ ，有 $h(n,t)≥1$
• 对 $t >n(n-1)/2$ ，有 $h(n,t) =0$

定理

7.2.1

设 $n$ 是正整数，则数列 $h(n, 0), h(n,1),…, h(n, n(n-1)/2)$ 的生成函数为

$$g_n(x)=1(1+x)(1+x+x^2)…(1+x+…+x^{n-1}) = \frac{\Pi^n_{j=1}(1-x^j)}{(1-x)^n} \quad (1)$$

7.3 指数生成函数

指数生成函数的定义

数列 $h_0, h_1, h_2,…, h_n ,…$ 的指数生成函数定义为

$$\begin{aligned} g(x)&=h_0+h_1x+h_2\frac{x^2}{2!}+...+h_n\frac{x^n}{n!}+...\\ &=\Sigma_{k=0}^\infty h_k\frac{x^k}{k!} \end{aligned}$$

例

$P(n,k)$

设 $n$ 是正整数。确定下面数列的指数生成函数：

$$P(n, 0), P(n, 1), P(n, 2), …, P(n, n)$$

其中， $P(n,k)$ 表示 $n$ 元素集合的 $k$ 排列的数目，即

$$P(n,k)=\frac{n!}{(n-k)!}$$

$e^x$

求数列 $1, 1, 1, …, 1,…$ 的指数生成函数

$$g(x)=\Sigma^\infty_{n=0}\frac{x^n}{n!}=e^x\quad(泰勒级数)$$

多重集排列

考虑由n个元素组成的多重集

$$S=\lbrace n_1\cdot a_1, n_2\cdot a_2,…, n_k\cdot a_k \rbrace$$

其中 $n=n_1+n_2+…+n_k$ 。从中取 $r$ 排列。

若 $r=n$ ，则考虑 $n$ 个元素的全排列，不同的排列数为

$$\frac{n!}{n_1!n_2!...n_k!}$$

若 $r<n$

由组合生成排列——即先选后全排列

有限重数

已知 $S =\lbrace n_1\cdot a_1, n_2\cdot a_2,n_3\cdot a_3\rbrace$ 的 $r$ 排列数 $h_r$ ， $r = 0, 1, 2, …, n_1+n_2+n_3$

则 $h_0,h_1,h_2,...,h_{n_1+n_2+n_3}$ 的指数生成函数：

$$(1+\frac{x}{1!}+\frac{x^2}{2!}+...++\frac{x^{n_1}}{n_1!}) (1+\frac{x}{1!}+\frac{x^2}{2!}+...++\frac{x^{n_2}}{n_2!}) (1+\frac{x}{1!}+\frac{x^2}{2!}+...++\frac{x^{n_3}}{n_3!})$$

展开后 $x^r$ 前的系数为：

$$\sum_{\substack{ e_1+e_2+e_3=r\\ 0\leq e_1 \leq n_1,0\leq e_2 \leq n_2,0\leq e_3 \leq n_3 }} \frac{x^{e_1}x^{e_2}x^{e_3}}{e_1!e_2!e_3!}\\ =(\sum_{\substack{ e_1+e_2+e_3=r\\ 0\leq e_1 \leq n_1,0\leq e_2 \leq n_2,0\leq e_3 \leq n_3 }}\frac{r!}{e_1!e_2!e_3!})\frac{x^r}{r!}$$

此处：

$$h_r=(\sum_{\substack{ e_1+e_2+e_3=r\\ 0\leq e_1 \leq n_1,0\leq e_2 \leq n_2,0\leq e_3 \leq n_3 }}\frac{r!}{e_1!e_2!e_3!})$$

故指数生成函数为：

$$\sum_{r=0}^{n_1+n_2+n_3}(\sum_{\substack{ e_1+e_2+e_3=r\\ 0\leq e_1 \leq n_1,0\leq e_2 \leq n_2,0\leq e_3 \leq n_3 }}\frac{r!}{e_1!e_2!e_3!})\frac{x^r}{r!}$$

定理

7.3.1

设 $S$ 是多重集 $\lbrace n_1\cdot a_1, n_2\cdot a_2,…, n_k\cdot a_k \rbrace$ ，其中 $n_1,n_2, …,n_k$ 是非负整数。设 $h_n$ 是 $S$ 的 $n$ 排列数，那么数列 $h_1, h_2,…,h_k…$ 的指数生成函数 $g$ 为：

$$g=f_{n_1}(x)f_{n_2}(x) ...f_{n_k}(x)$$

其中，对于 $i=1,2,..,k$ ，有

$$f_{n_i}(x)=1+x+\frac{x^2}{2!}+...+\frac{x^{n_i}}{n_i!}$$

推广到无穷重数

设 $S$ 是多重集 $\lbrace \infty\cdot a_1, \infty\cdot a_2,…, \infty\cdot a_k \rbrace$ 。设 $h_n$ 是 $S$ 的 $n$ 排列数，那么数列 $h_0,h_1, h_2,…,h_k…$ 的指数生成函数 $g$ 为：

$$\begin{aligned} g(x)&=h_0+h_1x+h_2\frac{x^2}{2!}+...+h_n\frac{x^n}{n!}+...\\ &=f_\infty(x)f_\infty(x)...f_\infty(x)\qquad(k个因子) \end{aligned}$$

其中：

$$f_\infty(x)=1+x+\frac{x^2}{2!}+...+\frac{x^n}{n!}+...=e^x$$

当 $n$ 排列中 $a_i$ 的出现有约束时，将反映到第 $i$ 个因子中

*常用展开式

$$e^x=\Sigma^\infty_{n=0}\frac{x^n}{n!}=1+x+\frac{x^2}{2!}+...+\frac{x^n}{n!}+...\\ e^{-x}=\Sigma^\infty_{n=0}(-1)^n\frac{x^n}{n!}=1-x+\frac{x^2}{2!}+...+(-1)^n\frac{x^n}{n!}+...\\ \frac{1}{2}(e^x+e^{-x})=1+\frac{x^2}{2!}+\frac{x^4}{4!}+...+\frac{x^{2n}}{2n!}+...\\ \frac{1}{2}(e^x-e^{-x})=x+\frac{x^3}{3!}+\frac{x^5}{5!}+...+\frac{x^{2n+1}}{(2n+1)!}+...\\$$

7.4 求解线性齐次递推关系

定义

线性齐次递推关系

令 $h_0, h_1, h_2,…, h_n,…$ 是一个数列。若存在量 $a_1, a_2, …, a_k (a_k≠0)$ 和量 $b_n$ （每个量是常数或依赖于 $n$ 的数）使得:

$$h_n=a_1h_{n-1}+a_2h_{n-2} +…+ a_{k-1}h_{n-k+1}+a_kh_{n-k}+ b_n \quad (n\geq k)$$

则称该数列满足 $k$ 阶线性递推关系。
若 $b_n= 0$ ，则称该数列是 $k$ 阶线性齐次递推关系。
若 $a_1, a_2, …, a_k$ 都为常数，则称该数列是 $k$ 阶常系数线性递推关系。

解法

本节重点讨论 $k$ 阶常系数线性齐次递推关系

• 特征方程法
• 生成函数法

定理

7.4.1(特征方程法)

令 $q$ 为一个非零数, 则 $h_n= q^n$ 是常系数线性齐次递推关系

$$h_n =a_1h_{n-1}+a_2h_{n-2}+…+a_kh_{n-k}\quad(a_k≠0, n≥k) (1)$$

的解当且仅当 $q$ 是多项式方程（特征方程）

$$x^k - a_1x^{k-1} - a_2x^{k-2}-…-a_{k-1}x - a_k=0\quad(2)$$

的一个根。（特征根）

若多项式方程 $(2)$ 有 k个不同的根 $q_1, q_2,…, q_k$ ，则

$$h_n=c_1q_1^n+c_2q_2^n+…+c_kq_k^n\quad(3)$$

是下述意义下 $(1)$ 的通解：任意给定初始值 $h_0, h_1, …,h_{k-1}$ ， 都存在 $c_1, c_2,…, c_k$ 使得 $(3)$ 式是满足 $ (1)$ 式和初始条件的唯一的数列。

7.4.2(通解)

令 $q_1,q_2,...,q_t$ 为常系数线性齐次递推关系：

$$h_n =a_1h_{n-1}+a_2h_{n-2}+…+a_kh_{n-k}\quad(a_k≠0, n≥k) (1)$$

的特征方程的互异的根。

如果 $q_i$ 是 $(1)$ 的特征方程的 $s_i$ 重根，那么该递推关系的通解中对应于 $q_i$ 的部分为：

$$H_n^{(i)}=c_1q_i^n+c_2nq_i^n+...+c_{s_i}n^{s_i-1}q_i^n$$

且该递推关系的通解为：

$$h_n=H_n^{(1)}+H_n^{(2)}+...+H_n^{(t)}$$

7.4.3

令 $h_0, h_1, h_2,…,h_n,…$ 为满足 $k$ 阶常系数线性齐次递推关系：

$$h_n+c_1h_{n-1}+…+c_kh_{n-k}=0 \quad(c_k≠0, n≥k) (1)$$

的数列, 则它的生成函数 $g(x)$ 形如：

$$g(x)=p(x)/q(x)\quad(2)$$

其中，
若 $q(x)$ 是具有非零常数项的 $k$ 次多项式，
且 $p(x)$ 是小于 $k$ 次的多项式。
反之, 给定这样的多项式 $p(x)$ 和 $q(x)$ ， 则存在序列 $h_0,h_1,…,h_n,…$ 满足 $(1)$ 式的 $k$ 阶常系数线性齐次递推关系, 其生成函数由 $(2)$ 式给出.

方法

特征方程法

详见定理7.4.1、7.4.2

特征方程有重根

定理7.4.1不适用于特征方程有重根的情况

生成函数法

（1）利用递推关系求出序列的生成函数： $\frac{p(x)}{q(x)}$ ，其中， $p(x) `$ 是次数小于 `$ k$ 的多项式，而 $q(x)$ 是常数项等于 1 的 $k$ 阶多项式；
（2）用部分分式法，把 $\frac{p(x)}{q(x)}$ 表示为如下代数分式的和： $\frac{c}{(1-rx)^t}$
（3）利用牛顿二项式展开 $\frac{c}{(1-rx)^t}$ ，并把所有项求和，得到生成函数的幂级数。

• 如何得到生成函数：

• • 先设出生成函数的通项
  • 利用递推关系加减消除法到只剩初始项
    • 加减消除法的系数为递推关系的系数！！！
    • 最终是含 $x$ 项系数尽量为 $0$

• 牛顿二项式：

• • 如果 $n$ 是正整数，而 $r$ 是非零实数， $|rx|<1$ 时，则有

  • $$\begin{aligned} (1-rx)^{-n}&=\Sigma^\infty_{k=0}{-n\choose k}(-rx)^k\\ &=\Sigma^\infty_{k=0}(-1)^k{-n\choose k}(rx)^k\\ &=\Sigma^\infty_{k=0}{n+k-1\choose k}(rx)^k\\ \end{aligned}$$

联系

设特征方程为 $r(x)$ ，生成函数 $g(x)=\frac{p(x)}{q(x)}$

设相应特征方程 $r(x)=0$ ，其中 $q(x)=x^kr(\frac{1}{x})$

…

不想写了，详见PPT~~~

小结

利用特征方程求解常系数线性齐次递推关系：

• 写出相应的特征方程
• 求解特征方程
• • 如果没有重根，则直接给出通解（定理7.4.1）
  • 如果有重根，根据重根求出通解（定理7.4.2）
• 将初始条件代入通解，得到满足初始条件的解

利用生成函数求解：使得 $x^j (j ≥ k)$ 前的系数为 $0$

7.5 非齐次递推关系

定义：

对于常系数线性递推关系

$$h_n=a_1h_{n-1}+a_2h_{n-2}+...+a_kh_{n-k}+b_n\quad(a_k \neq 0,n\geq k)$$

若 $b_n \neq0$ ，则称该递推关系为常系数线性非齐次递推关系。

汉诺塔问题

递推关系

$$\begin{aligned} h_n&=2h_{n-1}+1\quad(n\geq1)\\ h_0&=0\\ h_1&=1\\ h_2&=3 \end{aligned}$$

迭代求解

就嗯迭代

但是迭代完了一定要数学归纳法证明结果的正确性

通解

生成函数法

不一定可行，若 $b_n$ 为带 $n$ 的多项式则可能出问题。

特征方程法

假设有非齐次递推关系

$$h_n=a_1h_{n-1}+a_2h_{n-2}+...+a_kh_{n-k}+b_n\quad(1)$$

若 $f_n$ 是对应齐次递推关系

$$h_n^{'}=h_n-b_n=a_1h_{n-1}+a_2h_{n-2}+...+a_kh_{n-k}\quad(2)$$

的通解, 而 $c_n$ 是原非齐次递推关系（1）的一个特解,
那么： $h_n=cf_n+c_n$ 是原非齐次递推关系（1）的通解。

小结

1. 求对应的齐次递推关系的通解；
2. 求该非齐次递推关系的一个特解；
3. 将一般解和特解结合得到该非齐次递推关系的
   通解；
4. 通过初始条件确定通解中出现的常系数值.

难点：

• 特征方程求解
• 找出一个特解

尝试特解的方法：

根据非齐次项 $b_n$ 来尝试某些类型的特解（不绝对）：

• 如果 $b_n$ 是 $n$ 的 $k$ 次多项式，尝试 $h_n$ 也是 $n$ 的 $k$ 次多项式

  • 若 $b_n=d (常数)$ , 尝试 $h_n=r (常数)$
  • 若 $b_n=d_n+c (d, c是常数)$ , 尝试 $h_n= rn+s (r,s是常数)$
  • 若 $bn= an^2+dn+c (a,d,c是常数)$ , 尝试 $ hn = rn^2+sn+t (r, s, t是常数) $

• 若 $b_n=d^n (d是常数)$ 是指数形式，尝试 $h^n= pd^n (p是常数)$ 也是指数形式。

如：

若 $h_n=p3^n$ 不对，则可以尝试 $h_n=pn3^n$

7.6 一个几何例子

定义

定义1

设有平面或空间中的点集 $K$ , 若 $K$ 中任意两点 $p$ 和 $q$ 的连线上的所有点都在 $K$ 内,称 $K$ 是凸集

定理

定理7.6.1

设 $h_n$ 表示用下面方法把凸多边形区域分成三角形区域的方法数：
在有 $n+1$ 条边的凸多边形区域内通过插入不相交的对角线，而把它分成三角形区域。
定义 $h_1=1$ 。
则 $h_n$ 满足如下递推关系:

$$h_n=h_1h_{n-1}+h_2h_{n-2}+...+h_{n-1}h_1=\Sigma^{n-1}_{k-1}h_kh_{n-k}(n\geq2)$$

该递推关系解为： $h_n=\frac{1}{n}{{2n-2}\choose{n-1}}\quad(n=1,2,3...)$

其中： $\frac{1}{n}{{2n-2}\choose{n-1}}$ 为 Catalan数 $C_{n-1}$