组合数学

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

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

100687 组合数学

一、总述

1. 教材

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

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

2. 作业

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

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

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

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

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

3. 课堂

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

4. 考试

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

23 级：

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

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

一共六道大题，分别是：

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

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

做好心理准备，加油。

24 级：平时分以考核作业情况和报告情况为主，期末会下发文件让大家核对。

期末试卷包含45分的填空和55分的大题（好像是），填空多为定义挖空，比如第二类斯特林数的公式，比如错排定义

大题内容： 1. 二项式系数的介值定理证明（教材P31 定理2.6）； 2. 平面上有6个点，证明必存在某个三角形的最小边是另外一个三角形的最大边（我当时是考虑拉姆齐数）。 3. f（n）是0的个数为偶数的4进制数，假设这个数有长度为n，求f（n） PS：这个数是可以含前导0的； 4. 证明：e^-x/(1-x)= ∑D(n)x^n/n!（应该是课本-错排那个地方的一道课后习题）。 5. 用容斥原理证明欧拉函数；

总结：本课程从考核角度来看与其说是数学课，个人以为不如说是背书课，做卷子更像是在默写而没有那种灵光一闪突然做出来的感觉（虽然不妨碍我拿良）。

二、任课教师

13166 Liu

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