组合数学

2 学分，给大数据（含国豪大数据）和计拔开的课。

虽然只有 2 学分，但是课程的难度很大，有一些（开学 82 人 -> 期末 65 人）同学选择了期中退课，来年再见。

100687 组合数学

一、总述

1. 教材

24251 学期以前用的是中科大的那本组合数学引论，但因为老师的新教材出版了，所以现在用的是：

组合数学及应用 刘关俊 科学出版社 ISBN: 9787030801210

2. 作业

每章讲完后会在课后题中选几道，有些是研究级别的题目（原话），确实需要花很大心力来思考。

大作业是，在每章后的应用小节选择一个内容，编程实现，写一份报告。

应用小节一共有这些内容，并不是所有的都可以编程来实现：

• 进程互斥建模与死锁分析（Petri 网，老师的科研方向）
• 决策树学习
• 多索引哈希
• 香农容量
• 概率分布的期望与方差
• 快速排序
• 非对称旅行商问题
• 门电路等价类问题

虽然并不一定每道题都能做出来，报告也不一定写的很出色，但是老师在作业上会捞的，狠狠地捞。所以，尽力完成就好。

3. 课堂

按照课本的顺序，每章都讲。老师会用课本的内容截图作为 ppt，并做板书。讲的很仔细，但是需要课下花一些时间才能理解。

4. 考试

大家一定要珍惜这次机会，因为我们有 40 分（平时分与作业分）白送给大家的。想及格的话，卷面达到 33 分就能及格。要是补考的话，就只能按卷面分录入了。

23 级：

卷子包含选择题和大题，都是以教材为主线。

30 分的选择题，是一些定义、定理的挖空。比如多集的排列数，鸽巢原理的某一种定理表达方式，斯特林数 or 卡特兰数的递归关系式，轮换的定义等等，几乎都是课本原文。

一共六道大题，分别是：

1. 二项式系数的介值定理证明（教材P31 定理2.6）；
2. 扇形等分为 N 个扇形，用 K 个颜色来染色，用递归方程求解染色方法数。
3. 拉姆齐数的证明，R(3, 3, 3) = 17（教材P65 定理4.9）；
4. 2n 个字母的集合，两个 a1，两个 a2，两个 a3，...，两个 an，用容斥原理求得任意两个字母不相邻的排列的个数。
5. 生成函数的卷积；
6. 莫比乌斯反演（教材P133 性质7.1，P134 定理7.5）。

共 75 分左右是课内的内容（填空 30 + 大题 45），剩下是比较灵活的题。

做好心理准备，加油。

二、任课教师

13166 Liu

老师年纪并不是很大，但是浑厚的嗓音让人觉得是一位老先生。课程讲的比较清晰，就算当时听不懂，看回放的时候也能 get 到要点，可能一部分原因是因为用的是自己写的教材吧，比较得心应手。有时候剩十几分钟就把当堂的课程讲完了，会和同学们谈谈人生，不过，大家可能是忙于 oj，oop，和一些大作业们，从而没有回应呢。