概览

• Realtions(关系)
• Semigroups and Groups(群和半群)
• Groups and coding(群和码)

---

• Advanced Counting Techniques(高级计数技巧)

---

• Groups(图)
• Trees(树)

关系

• Relations and their properties(关系及关系性质)
• n-ary relations and their applicaitons(n元关系及应用)
• Representing realtions(关系的表示)
• Closures of relations(关系闭包)
• Equivalence relations(等价关系)
• Partial Ordings(偏序关系)

群和半群

• Binary operations revisited(二元关系)
• Semigroups(半群)
• Products and Quotients of Semigroups(乘积半群和商半群)
• Groups(群)
• Products and Quotients of Groups(乘积群和商群)

群和码

• Coding of Binary Information and Error Dection
• Decoding and Error Correction

高级计数技巧

• Recurrence Relation
• Solving Recurrence Relations
• Divide-and-Conquer Algorithms and Recurrence Relations(分治算法和递归关系)
• Generating Functions(生成函数)
• Inclusion-Exclusion(容斥)
• Applications of Inclusion-Exclusion(容斥原理的应用)

图

• Graphs and Graph Models
• Graph terminology and Special Types of Graphs
• Representing Graphs and Graphs Isomorphism(图的表示和同构)
• Connectivity(连通性)
• Euler and Hamilton Path(欧拉联通与哈密顿通路)
• Shortest-path Problem(最短通路问题)
• Planar Graphs(平片图)
• Graph Coloring(图着色)

树

• Introduction to trees(树的概述)
• Application of Trees
• Tree Traversal(树的遍历)
• Spanning Trees(生成树)
• Minimum Spanning Trees(最小生成树)

大致分为三个板块：
板块一：由关系引入，到群和半群，最后是偏应用的群和码
板块二：高级计数技巧
板块三：图和树

Advanced Counting Techniques

由于很多计数问题不能用第六章(counting)讲解的方法解决。我们在这里介绍一些更高级的方法。
一些问题可以表示为递推关系和初始条件构成的序列。由与这个序列有关的等式可以得到每一项的显示公式(explicit formula)(求解递推公式)。类似的技术可以解决很多不同的计数问题。
递推关系起到重要作用的两种算法范式：动态规划(dynamic)、分治(divide-and-conquer)。(二者区别在于子问题是否重叠，重叠的叫动态规划) 同时，我们可以用递推公式求解算法复杂度。
我们还可以利用形式幂级数(也叫生成函数)来求解许多计数问题。其中x的幂的系数代表我们感兴趣的序列的项。生成函数可以用来求解递推关系式和证明组合恒等式。
还有一种方法：通过计数集合并集中元素个数来解决问题。我们将开发一种叫做容斥原理(Inclusion-Exclusion)的算法。

我们研究用递推关系构造模型的计数问题

问题类型：

• 经典递推问题：斐波那契数列、汉诺塔
• 求满足特定要求的n长度序列个数(分治思想，枚举最后一(几)位，分成不重合的小规模问题)
• 卡塔兰数序列(Catalan)$$C_n=\sum _{k=0}^{n-1}{C}_k\ast C_{n-k-1}$$

算法与递推关系：递推关系在研究一些算法和算法复杂度方面起着重要作用

8.2 求解线性递推关系

有一类重要的递推关系可以用一种系统方法明确地求解。这种递推关系中，序列的项由它的前项的线性组合来表示。

定义：k阶线性齐次递推关系
$$a_n=c_1{a}_{n-1}+c_2{a}_{n-2}+...+c_k{a}_{n-k}$$
特定递推序列由这个递推关系和k个初始条件唯一确定

说明：

• 只要满足C_k不为零就可以称为k阶的
• 齐次是指没有常数部分。
• 线性是指a_k的表示都是一次的。

求解

通过解特征方程的特征根求解递推关系的显示表示

1. 把a_k替换成r^k==>原递推关系表示为特征方程
2. 求解特征根
   2.1. 有两个不同的解：$$a_n=u{r}_1^n+v{r}_2^n$$
   2.2. 有两个相同的解：$$a_n=u{r}_1^n+nv{r}_2^n$$
3. 根据初始条件求解u,v

成立性证明同样是递推形式的

接下来给出思想核心

递推方程的解是q ^ n代表，显示表示有解H(n) = q ^ n（通解）。注意，这里当初始态不确定时，解有很多种可能。
这里肯定了一个前提：q是特征方程的特征根<==>q^n是递推方程的解（这一步是可以直接通过化简得到的）
特征根h_1(n),h_2(n)各对应线性齐次方程的一个解。也就是说它们都是该递推方程的解。
使这两个解做线性组合，这个线性组合也是递推方程的解。$$u{h}_1(n)+v{h}_2(n)$$
至于两个特征根相同时的情况同样参考二阶常系数线性齐次微分方程的解的情况

这里给出思想并不是需要记住证明方法。只是希望将各个知识点关联起来，通过理解记忆方式对固定的解题方法进行高效学习。理解了就不需要死记硬背了。
理解后的记忆：
求解线性齐次递归关系<==>求解常系数线性齐次微分方程。
(解的对应关系a_n = q ^n（通解） <==> r = q)