Home 数学 离散数学 离散数学基础

离散数学基础 - 整理: --- 排列与组合 --- 组合计数基本原理 --- 排列组合计数问题 --- 递推关系式 --- 关系 --- 集合与关系的运算 --- 函数 --- 代数系统

# 思维导图

递推关系式

# 递推关系式相关概念

# 定义

用序列中某些前面的项ai,0≤i<n表示第n项an的等式\text{用序列中某些前面的项}a_i,0\leq i\lt n\text{表示第}n\text{项}a_n\text{的等式}

# 解

序列{an}满足一个递推关系式，则{an}即为该递推关系式的一个解\text{序列}\{a_n\}\text{满足一个递推关系式，则}\{a_n\}\text{即为该递推关系式的一个解}

# 封闭公式解

序列{an}的第n项可以用不含序列中任何项的通项公式表达，则该通项公式称为该递推关系式的封闭公式解\begin{aligned} &\text{序列}\{a_n\}\text{的第n项可以用不含序列中任何项的通项公式表达，}\\ &\text{则该通项公式称为该递推关系式的封闭公式解} \end{aligned}

# 常系数线性递推关系式的一般形式

an=c1an−1+c2an−2+...+ckan−k+F(n)\begin{aligned} &a_n = c_1a_{n-1}+c_2a_{n-2}+...+c_ka_{n-k}+F(n) \end{aligned}

若F(n)=0则为齐次\text{若}F(n)=0\text{则为齐次}

若F(n)≠0则为非齐次\text{若}F(n)\neq 0\text{则为非齐次}

# 线性齐次递推关系式的解

# 特征方程

xn=c1xn−1+c2xn−2+...+ckxn−k+F(n)\begin{aligned} &x^n = c_1x^{n-1}+c_2x^{n-2}+...+c_kx^{n-k}+F(n) \end{aligned}

# 特征方程的根

r1,r2,...rt,重数分别为m1,m2,...m3,这门课没管复根情况咱就不背了捏\begin{aligned} r_1,r_2,...r_t,\text{重数分别为}m_1,m_2,...m_3,\text{这门课没管复根情况咱就不背了捏} \end{aligned}

# 解的形式

an=(β1,0+β1,1n+...+β1,m1−1nm1−1)r1n+(β2,0+β2,1n+...+β2,m2−1nm2−1)r2n+...+(βt,0+βt,1n+...+βt,mt−1nmt−1)rtn代入至少t个初始条件解出待定系数β1,β2,...βt即可得到解\begin{aligned} a_n &= (\beta_{1,0}+\beta_{1,1}n+...+\beta_{1,m_1-1}n^{m_1-1})r_1^{n} \\& +(\beta_{2,0}+\beta_{2,1}n+...+\beta_{2,m_2-1}n^{m_2-1})r_2^{n} \\& +...\\& +(\beta_{t,0}+\beta_{t,1}n+...+\beta_{t,m_t-1}n^{m_t-1})r_t^{n}\\& \text{代入至少t个初始条件解出待定系数}\beta_1,\beta_2,...\beta_t\text{即可得到解} \end{aligned}

# 线性非齐次递推关系式的解

# 伴随齐次递推关系式

令F(n)=0得到：\text{令}F(n)=0\text{得到：}

an=c1an−1+c2an−2+...+ckan−k\begin{aligned} &a_n = c_1a_{n-1}+c_2a_{n-2}+...+c_ka_{n-k} \end{aligned}

  • 按照线性齐次递推关系式求解得到：

    • 通解，即伴随齐次递推关系式的解

# F (n) 形式

F(n)=(btnt+bt−1nt−1+...+b1n+b0)sn\begin{aligned} F(n)=(b_tn^t+b_{t-1}n^{t-1}+...+b_1n+b_0)s^n \end{aligned}

这门课没管的别的情况咱就不背了捏

# 特解的形式

  • s 不是伴随线性齐次递推关系式的特征方程的根

an(p)=(ptnt+pt−1nt−1+...+p1n+p0)sn\begin{aligned} a_n^{(p)} = (p_tn^t+p_{t-1}n^{t-1}+...+p_1n+p_0)s^n \end{aligned}

  • s 是伴随线性齐次递推关系式的特征方程的 m 重根

an(p)=nm(ptnt+pt−1nt−1+...+p1n+p0)sn\begin{aligned} a_n^{(p)} = n^m(p_tn^t+p_{t-1}n^{t-1}+...+p_1n+p_0)s^n \end{aligned}

将特解代入递推关系式，对得到的关于n的多项式的等式两边比较系数，可以确定待定系数p0,p1,...pt\text{将特解代入递推关系式，对得到的关于n的多项式的等式两边比较系数，可以确定待定系数}p_0,p_1,...p_t

# 解的形式

an=通解+特解=通解+an(p)\begin{aligned} a_n = \text{通解}+\text{特解}=\text{通解}+a_n^{(p)} \end{aligned}

# 算法效率

分析主定理
（Master Therorem）

#

f(n)是实递增函数，且满足递推关系式f(n)=af(nb)+Cnd，则：f(n)是{O(nd)a<bdO(ndlogn)a=bdO(nlogba)a>bda,b∈Z,a≥1,b>1,C,d∈R,C>0,d≥0\begin{aligned} &f(n)\text{是实递增函数，且满足递推关系式}f(n)=af(\frac{n}{b})+Cn^d\text{，则：}\\& \begin{aligned} f(n)是\left\{\begin{aligned} &O(n^d) & a\lt b^d\\ &O(n^dlogn) & a= b^d\\ &O(n^{log_ba})& a\gt b^d \end{aligned}\right. &&&&&& \begin{aligned} &a,b\in\mathbb{Z},a\geq1,b\gt1,\\ &C,d\in\mathbb{R},C\gt0,d\geq0 \end{aligned} \end{aligned} \end{aligned}