![离散数学及其应用]()
离散数学及其应用
导航
成绩构成
- 作业(10%)+小测(20%)+期末(70%)
高级计数技术
递推关系的应用
求解线性递推关系
- 前面的递推关系的推出，我们需要利用动态规划的思想得到，那么我们应该怎样得到求解呢？
- 这就涉及到线性递推关系的求解
求解定理1
- 设c1,c2为实数。假设$r^2-c_1r-c_2=0$有两个不相同的根r1,r2，那么序列{an}是递推关系$a_n=c_1a_{n-1}+c_2a_{n-2}$的解，当且仅当$a_n=a_1r_1^n+a_2r_2^n$
求解定理2（重根）
- 设c1,c2为实数。假设$r^2-c_1r-c_2=0$有两个相同的根r，那么序列{an}是递推关系$a_n=c_1a_{n-1}+c_2a_{n-2}$的解，当且仅当$a_n=a_1r^n+a_2r^n$
扩展到一般情况
- 设c1,c2,….ck为实数。假设$r^n-c_1r^{n-1}-c_2r^{n-2}-…-c_kr^0=0$有k个不相等的根，那么序列{an}是递推关系$a_n=c_1a_{n-1}+c_2a_{n-2}+…+cka_{n-k}$的解，当且仅当$a_n=a_1r_1^n+a_2r_2^n+…+a_kr_k^n$
扩展到一般情况(存在重根)
- 设c1,c2,….ck为实数。假设$r^n-c_1r^{n-1}-c_2r^{n-2}-…-c_kr^0=0$有t个不相等的根r1,r2….rt，其重数分别为m1,m2…mt,满足$\sum_{i=1}^t m_{i}=k$,那么序列{an}是递推关系$a_n=c_1a_{n-1}+c_2a_{n-2}+…+ck*a_{n-k}$的解，当且仅当$a_n=(\alpha {1,0}+\alpha{1,1}*n…\alpha_{1,m1-1}*n^{m1-1})*r_1^n+(\alpha {2,0}+\alpha{2,1}*n…\alpha_{2,m2-1}*n^{m2-1})*r_2^n+…$
求解常系数线性非齐次递推关系
- 对于常系数非齐次递推关系$a_{n}=c_1a_{n-1}+c_2a_{n-2}….+F(n)$,其中$a_{n}^{p}$为这个递推关系的一个特解，$a_{n}^{h}$为上述的相伴的齐次递推关系的解，则每一个解的形式是$a_{n}^{p}+a_{n}^{h}$
非齐次递推关系中的特解的求取
- 对于非齐次线性递推关系，$F(n)=(b_t*n^t+b_{t-1}n^{t-1}+…+b_1n+b_0)*s^n$.当s不是相伴的线性齐次递推关系的特征方程的根时，存在一个下列形
式的特解$(p_tn^t+p_{t-1}n^{t-1}+…+p_1n+p_0)*s^n$
生成函数
有用的生成函数
- $(1+x)^n=\sum_{k=0}^{n}C(n,k)x^k$
- $(1+a*x)^n=\sum_{k=0}^{n}C(n,k)a^kx^k$
- $\frac{1-x^{n+1}}{1-x}=\sum_{k=0}^{n}x^k$
- $\frac{1}{1-x}=\sum_{k=0}^{\infty}x^k$
- $\frac{1}{1-a*x}=\sum_{k=0}^{\infty}a^kx^k$
本文总阅读量次
