组合数学笔记(三)

组合数学

第6章 容斥原理及应用

6.1 容斥原理

定义

计数函数： ${\sigma }_x(A)$

$${\sigma }_x(A)=\{\begin{array}{c}1,x\in A\\ 0,x\notin A\end{array}$$

定理和推论

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

6.1.1

集合 $S$ 不具有性质 $P_1,P_2,\dots ,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,\dots ,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|$$

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

特别情况

若：

$$\begin{array}{rl}& {\alpha }_1=|A_1|=|A_2|=\dots =|A_m|(\mathrm{所}\mathrm{有}\mathrm{集}\mathrm{合}\mathrm{包}\mathrm{含}\mathrm{的}\mathrm{元}\mathrm{素}\mathrm{个}\mathrm{数}\mathrm{相}\mathrm{等})\\ & {\alpha }_2=|A_1\cap A_2|=\dots =|A_{m-1}\cap A_m|(\mathrm{任}\mathrm{意}\mathrm{两}\mathrm{个}\mathrm{集}\mathrm{合}\mathrm{的}\mathrm{交}\mathrm{包}\mathrm{含}\mathrm{相}\mathrm{等}\mathrm{个}\mathrm{数}\mathrm{的}\mathrm{元}\mathrm{素})\\ & {\alpha }_3=|A_1\cap A_2\cap A_3|=\dots =|A_{m-2}\cap A_{m-1}\cap A_m|(\mathrm{任}\mathrm{意}\mathrm{三}\mathrm{个}\mathrm{集}\mathrm{合}\mathrm{的}\mathrm{交}\mathrm{包}\mathrm{含}\mathrm{相}\mathrm{等}\mathrm{个}\mathrm{数}\mathrm{的}\mathrm{元}\mathrm{素}\mathrm{个}\mathrm{数}）)\\ & \dots \\ & {\alpha }_k=|A_1\cap \dots \cap A_k|=\dots =|A_{m-k+1}\cap \dots \cap A_m|\\ & \dots \\ & {\alpha }_m=|A_1\cap A_2\cap \dots \cap A_m|\end{array}$$

则，

$$\begin{array}{rl}& \overline{A_1}\cap ...\cap \overline{A_n}\\ & ={\alpha }_0-(\genfrac{}{}{0ex}{}{m}{1}){\alpha }_1+(\genfrac{}{}{0ex}{}{m}{2}){\alpha }_2-(\genfrac{}{}{0ex}{}{m}{3}){\alpha }_3+...+(-1{)}^k(\genfrac{}{}{0ex}{}{m}{k}){\alpha }_k+...+(-1{)}^m{\alpha }_m\end{array}$$

6.2 带重复的组合

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

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

多重集 $T=\{n_1\times a_1,n_2\times a_2,\dots ,n_k\times a_k\}$ 的 $r$ 组合数等于方程

$$\begin{gathered} x_1+x_2+\dots +x_k=r, \\ 0\le x_1\le n_1,0\le x_2\le n_2,\dots ,0\le xk\le n_k \end{gathered}$$

的整数解的个数。

6.3 错位排列

定义

1.

设 $X=\{1,2,\dots ,n\}$ , 它的排列用 $i_1{i}_2\dots i_n$ 表示。错位排列是使得 $i_1\ne 1,i_2\ne 2,\dots ,i_n\ne n$ 的排列。用 $D_n$ 表示错位排列个数

定理

6.3.1

对 $n\ge 1$ ，

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

性质

错位排列的递推关系

1

$$\begin{gathered} D_n=(n-1)(D_{n-2}+D_{n-1}),(n=3,4...) \\ {D}_2=1;D_1=0 \end{gathered}$$

2

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

6.4 带有禁止位置的排列

定义

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

令 $X_1,X_2,\dots ,X_n$ 是 $\{1,2,\dots ,n\}$ 的子集 (可以为空集)，用 $P(X_1,X_2,\dots ,X_n)$ 表示 $\{1,2,\dots ,n\}$ 的排列 $i_1{i}_2\dots i_n$ 的集合，使得： $i_1\notin X_1，i_2\notin X_2，\dots ，i_n\notin X_n$

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

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

令 $\{1,2,\dots ,n\}$ 的排列 $i_1{i}_2\dots i_n$ 对应于棋盘上以方格

$$(1,i_1),(2,i_2),\dots ,(n,i_n)$$

为坐标的n个车的位置

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

定理

6.4.1

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

$$n!-r_1(n-1)!+r_2(n-2)!-\dots +(-1{)}^k{r}_k(n-k)!+\dots +(-1{)}^n{r}_n$$

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

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

6.5 另一个禁止位置问题

定义

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

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

定理

6.5.1

对于 $n\ge 1$ ，

$$\begin{array}{rl}{Q}_n& =n!+{\mathrm{\Sigma }}_{k=1}^{n-1}(-1{)}^k(\genfrac{}{}{0ex}{}{n-1}{k})(n-k)!\\ & =n!-(\genfrac{}{}{0ex}{}{n-1}{1})(n-1)!+(\genfrac{}{}{0ex}{}{n-1}{2})(n-2)!+...+(-1{)}^{n-1}(\genfrac{}{}{0ex}{}{n-1}{n-1})1!\end{array}$$

例题

旋转木马问题

看ppt去

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

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

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

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

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

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

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

7.1 若干数列

定义

斐波那契数列

设有数列 $f_0,f_1,f_2,\dots ,f_n,\dots$ 。如果 $f_0=0,f_1=1$ , 且满足递推关系 $f_n=f_{n-1}+f_{n-2}，n\ge 2$
称该数列为斐波那契（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\ge 0$$

7.1.2

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

$$f_n=(\genfrac{}{}{0ex}{}{n-1}{0})+(\genfrac{}{}{0ex}{}{n-2}{1})+(\genfrac{}{}{0ex}{}{n-3}{2})+...+(\genfrac{}{}{0ex}{}{n-t}{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数列与黄金分割数

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

7.2 生成函数

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

*常见展开式

$$\begin{array}{rl}(1+x{)}^n& ={\mathrm{\Sigma }}_{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})x^k\\ (1-x{)}^n& ={\mathrm{\Sigma }}_{k=0}^n(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})x^k\end{array}$$

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

$$\begin{array}{rl}\frac{1}{(1+x{)}^n}& ={\mathrm{\Sigma }}_{k=0}^{\mathrm{\infty }}(-1{)}^k(\genfrac{}{}{0ex}{}{n+k-1}{k})x^k\\ \frac{1}{(1-x{)}^n}& ={\mathrm{\Sigma }}_{k=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{n+k-1}{k})x^k\end{array}$$

当$n=1$ 时，得：

$$\begin{array}{rl}\frac{1}{1+x}& ={\mathrm{\Sigma }}_{k=0}^{\mathrm{\infty }}(-1{)}^k{x}^k(|x|<1)\\ \frac{1}{1-x}& ={\mathrm{\Sigma }}_{k=0}^{\mathrm{\infty }}{x}^k(|x|<1)\end{array}$$

令 $x=y^m$ ，得：

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

生成函数的定义

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

$$\begin{array}{rl}g(x)& =h_0+h_{1}x+h_2{x}^2+\dots +h_n{x}^n+\dots \\ & ={\mathrm{\Sigma }}_{k=0}^{\mathrm{\infty }}{h}_k{x}^k\end{array}$$

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

适合多重集组合

生成函数——多重集组合

求生成函数

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

$$e_1+e_2+\dots +e_k=n$$

的非负整数解个数，

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

$$\begin{array}{rl}g(x)& ={\mathrm{\Sigma }}_{n=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{n+k-1}{n})x^n=\frac{1}{(1-x{)}^k}\\ & =({\mathrm{\Sigma }}_{e_1=0}^{\mathrm{\infty }}{x}^{e_1})({\mathrm{\Sigma }}_{e_2=0}^{\mathrm{\infty }}{x}^{e_2})...({\mathrm{\Sigma }}_{e_k=0}^{\mathrm{\infty }}{x}^{e_k})(2)\\ & ={\mathrm{\Sigma }}_{e_1+...+e_k=n=0}^{\mathrm{\infty }}{x}^{e_1}{x}^{e_2}...x^{e_k}\end{array}$$

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

求通项

把生成函数向根本形式： ${\mathrm{\Sigma }}_{k=0}^{\mathrm{\infty }}{h}_k{x}^k$ 化简

排列逆序

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

设 $h(n,t)$ 表示 $\{1,2,\dots ,n\}$ 的排列中有 $t$ 个逆序的排列的数目，则：

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

定理

7.2.1

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

$$g_n(x)=1(1+x)(1+x+x^2)\dots (1+x+\dots +x^{n-1})=\frac{{\mathrm{\Pi }}_{j=1}^n(1-x^j)}{(1-x{)}^n}(1)$$

7.3 指数生成函数

指数生成函数的定义

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

$$\begin{array}{rl}g(x)& =h_0+h_{1}x+h_2\frac{x^2}{2!}+...+h_n\frac{x^n}{n!}+...\\ & ={\mathrm{\Sigma }}_{k=0}^{\mathrm{\infty }}{h}_k\frac{x^k}{k!}\end{array}$$

例

$P(n,k)$

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

$$P(n,0),P(n,1),P(n,2),\dots ,P(n,n)$$

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

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

$e^x$

求数列 $1,1,1,\dots ,1,\dots$ 的指数生成函数

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

多重集排列

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

$$S=\{n_1\cdot a_1,n_2\cdot a_2,\dots ,n_k\cdot a_k\}$$

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

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

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

若 $r<n$

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

有限重数

已知 $S=\{n_1\cdot a_1,n_2\cdot a_2,n_3\cdot a_3\}$ 的 $r$ 排列数 $h_r$ ， $r=0,1,2,\dots ,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$ 前的系数为：

$$\begin{gathered} \sum _{\begin{array}{c}{e}_1+e_2+e_3=r\\ 0\le e_1\le n_1,0\le e_2\le n_2,0\le e_3\le n_3\end{array}}\frac{x^{e_1}{x}^{e_2}{x}^{e_3}}{e_1!e_2!e_3!} \\ =(\sum _{\begin{array}{c}{e}_1+e_2+e_3=r\\ 0\le e_1\le n_1,0\le e_2\le n_2,0\le e_3\le n_3\end{array}}\frac{r!}{e_1!e_2!e_3!})\frac{x^r}{r!} \end{gathered}$$

此处：

$$h_r=(\sum _{\begin{array}{c}{e}_1+e_2+e_3=r\\ 0\le e_1\le n_1,0\le e_2\le n_2,0\le e_3\le n_3\end{array}}\frac{r!}{e_1!e_2!e_3!})$$

故指数生成函数为：

$$\sum _{r=0}^{n_1+n_2+n_3}(\sum _{\begin{array}{c}{e}_1+e_2+e_3=r\\ 0\le e_1\le n_1,0\le e_2\le n_2,0\le e_3\le n_3\end{array}}\frac{r!}{e_1!e_2!e_3!})\frac{x^r}{r!}$$

定理

7.3.1

设 $S$ 是多重集 $\{n_1\cdot a_1,n_2\cdot a_2,\dots ,n_k\cdot a_k\}$ ，其中 $n_1,n_2,\dots ,n_k$ 是非负整数。设 $h_n$ 是 $S$ 的 $n$ 排列数，那么数列 $h_1,h_2,\dots ,h_k\dots$ 的指数生成函数 $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$ 是多重集 $\{\mathrm{\infty }\cdot a_1,\mathrm{\infty }\cdot a_2,\dots ,\mathrm{\infty }\cdot a_k\}$ 。设 $h_n$ 是 $S$ 的 $n$ 排列数，那么数列 $h_0,h_1,h_2,\dots ,h_k\dots$ 的指数生成函数 $g$ 为：

$$\begin{array}{rl}g(x)& =h_0+h_{1}x+h_2\frac{x^2}{2!}+...+h_n\frac{x^n}{n!}+...\\ & =f_{\mathrm{\infty }}(x)f_{\mathrm{\infty }}(x)...f_{\mathrm{\infty }}(x)(k\mathrm{个}\mathrm{因}\mathrm{子})\end{array}$$

其中：

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

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

*常用展开式

$$\begin{gathered} e^x={\mathrm{\Sigma }}_{n=0}^{\mathrm{\infty }}\frac{x^n}{n!}=1+x+\frac{x^2}{2!}+...+\frac{x^n}{n!}+... \\ {e}^{-x}={\mathrm{\Sigma }}_{n=0}^{\mathrm{\infty }}(-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)!}+... \end{gathered}$$

7.4 求解线性齐次递推关系

定义

线性齐次递推关系

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

$$h_n=a_1{h}_{n-1}+a_2{h}_{n-2}+\dots +a_{k-1}{h}_{n-k+1}+a_k{h}_{n-k}+b_n(n\ge k)$$

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

解法

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

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

定理

7.4.1(特征方程法)

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

$$h_n=a_1{h}_{n-1}+a_2{h}_{n-2}+\dots +a_k{h}_{n-k}(a_k\ne 0,n\ge k)(1)$$

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

$$x^k-a_1{x}^{k-1}-a_2{x}^{k-2}-\dots -a_{k-1}x-a_k=0(2)$$

的一个根。（特征根）

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

$$h_n=c_1{q}_1^n+c_2{q}_2^n+\dots +c_k{q}_k^n(3)$$

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

7.4.2(通解)

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

$$h_n=a_1{h}_{n-1}+a_2{h}_{n-2}+\dots +a_k{h}_{n-k}(a_k\ne 0,n\ge k)(1)$$

的特征方程的互异的根。

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

$$H_n^{(i)}=c_1{q}_i^n+c_{2}n{q}_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,\dots ,h_n,\dots$ 为满足 $k$ 阶常系数线性齐次递推关系：

$$h_n+c_1{h}_{n-1}+\dots +c_k{h}_{n-k}=0(c_k\ne 0,n\ge k)(1)$$

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

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

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

方法

特征方程法

详见定理7.4.1、7.4.2

特征方程有重根

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

生成函数法

（1）利用递推关系求出序列的生成函数： $\frac{p(x)}{q(x)}$ ，其中， $p(x)‘\$\mathrm{是}\mathrm{次}\mathrm{数}\mathrm{小}\mathrm{于}‘\$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{array}{rl}(1-rx{)}^{-n}& ={\mathrm{\Sigma }}_{k=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{-n}{k})(-rx{)}^k\\ & ={\mathrm{\Sigma }}_{k=0}^{\mathrm{\infty }}(-1{)}^k(\genfrac{}{}{0ex}{}{-n}{k})(rx{)}^k\\ & ={\mathrm{\Sigma }}_{k=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{n+k-1}{k})(rx{)}^k\end{array}$$

联系

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

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

…

不想写了，详见PPT~~~

小结

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

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

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

7.5 非齐次递推关系

定义：

对于常系数线性递推关系

$$h_n=a_1{h}_{n-1}+a_2{h}_{n-2}+...+a_k{h}_{n-k}+b_n(a_k\ne 0,n\ge k)$$

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

汉诺塔问题

递推关系

$$\begin{array}{rl}{h}_n& =2h_{n-1}+1(n\ge 1)\\ h_0& =0\\ h_1& =1\\ h_2& =3\end{array}$$

迭代求解

就嗯迭代

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

通解

生成函数法

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

特征方程法

假设有非齐次递推关系

$$h_n=a_1{h}_{n-1}+a_2{h}_{n-2}+...+a_k{h}_{n-k}+b_n(1)$$

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

$$h_n^{{}^{\prime }}=h_n-b_n=a_1{h}_{n-1}+a_2{h}_{n-2}+...+a_k{h}_{n-k}(2)$$

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

小结

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

难点：

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

尝试特解的方法：

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

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

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

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

如：

若 $h_n=p{3}^n$ 不对，则可以尝试 $h_n=pn{3}^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_1{h}_{n-1}+h_2{h}_{n-2}+...+h_{n-1}{h}_1={\mathrm{\Sigma }}_{k-1}^{n-1}{h}_k{h}_{n-k}(n\ge 2)$$

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

其中： $\frac{1}{n}(\genfrac{}{}{0ex}{}{2n-2}{n-1})$ 为 Catalan数 $C_{n-1}$