鉴于未见有人整理组合学试题，做了一个期中回忆版

2025秋组合学期中考回忆版及部分解答.pdf

组合学到底在学习什么呢？各种工具和方法当然是组合学的血肉，但最主要的还是面对问题处理信息的能力，有人说上这门课只学会了做题，可是我觉得学会做题也就学会了组合学，近年很多重要工作的核心都是组合，因为计数，算两次，找表示的思想到底是普适的。我思考自己在什么时候入了组合学的门，想到许多年以前亲手算出来\(C_4\)-free图的边数上界而从此我便明白了算两次的道理。\(C_4\)-free只是一个小例子，但是想明白了它，半本组合学讲义不过是变换对象和语言的游戏。

这门课的内容主干是很少的，技术上有计数算两次、概率方法和代数方法，对象上有图和集族。但对象之间的关系是复杂的，从关系里剥离出有效信息和结论就是多数时候在做的事。除去读来令人作呕的第五章Design，课程的绝大部分内容不超出中学竞赛的范围，而技巧上弗如远甚，如果找来一本 Problems from the Book 会发现组合学及进阶讲义作业与之多有重合，代数方法可以参见其中Higher Algebra一章，多项式方法连同组合零点定理位于其最后一章正文及习题中。想更全面了解概率方法时，可能有人推荐Alon和Spencer400页的书或者赵宇飞200页的讲义，但实际上还有Spencer整理过的一本小册子Ten Lectures on the Probabilistic Method 覆盖了从概率论到组合学到进阶讲述的所有内容。

信息、关系、表示、对象这些词看起来没在讲义上出现过，我似乎也没有在老师口中听到过。我以为这样思考的方式才是组合学入门所该学习的。Sperner定理的算两次证明里两个从属的关系被表示成一个排序当中的先后顺序，而考虑所有的排序就编码出了充分的信息，于是我们能够通过考察它们的耦合作具体计算。同样的，Erdos-Ko-Rado定理用圆排列简单编码了集合相交的关系，多项式方法用多项式的零化编码了某些数量关系，概率方法用概率的语言表达整体与渐近，其中线性的期望给出一种算两次的自然框架（此处不得不抨击期末考试唯一使用概率方法的sum-free子集，直接使用算两次更加简明）。为了解决问题，了解这些还是不够的，探索特殊情况、寻找不变关系的能力，作不完全归纳的直觉只有跟问题搏斗才能培养，这在其它数学课中也能进行，但在组合问题里练习应当最为直接，可惜修读课程对此帮助不大，大三上课程堆叠如山更无所适从。

这门课的作业和讲义上的练习偶尔会出现不好处理的题目，查询的时候可以试试用Kimi联网搜索，但是自己给出一个非标准证明会更令人激动。今年的授课教师有变，具体表现是：到期中之后也许收到一些反映，作业变得非常简单。老师还为了照顾大多数同学，把期末考全部出成了背诵套用定理证明，但又为了不送分选出来两个硬性要求背诵关键点，很难短时间自行推导的题目: Even-odd town的证明和较大Sum-free子集的存在性。这导致对自己能力自信而没有仔细复习的同学会面临难堪的结果。相比之下期中考试则容易得多。将考试出成背诵无疑有悖这门课的灵魂，组合需要掌握的不是一两个特例而是处理问题的思想，要么就干脆完全地送分，会远远好过偏离导向的考察。

当然考试如此，上课小测不乏有老师希望同学提高参与度的原因。我在学期初决定一次课也不去，然后不久这个计划就被考勤制度终结了。根据我的观察上课无非是把既定的内容局部编排一下展现给大家，相比自行摸索对理解速度没有本质上的提升，而部分拥有良好基础的同学完全能够在几天之内完全掌握细枝末节以外的一切。另外这门课讲义的英语表达属实不敢恭维，同时很多证明写得远非必要地冗长却还偶有gap影响阅读，还有奇妙操作把Turan定理留作习题未予注明，也许可以期待后来的助教为之改进。

不知道这门初等数学课在干什么。组合学的特点似乎就是没有一个公认的知识顺序、没有一般意义上的工具。剩下可选的授课顺序—也就是目前的模式—也只有按照不同topic进行扁平化介绍了。

这么看组合学就是一门学不会的课，因为根本不知道要学多少东西、学到什么程度。顶多是了解了一些数学，对于不做相关研究的人没啥意义。（除了理论计算机，真不知道组合学出来能干啥，貌似没啥国内学校有组合学教职，不像其他纯数，多少听说过清北复浙这些学校的大佬。杰哥似乎真是“中国组合数学做的最好的”了。。）

除了第一节以外一次都没到过课，点名全空，每次只在写作业时对着去年答案和讲义定义抄一抄（对于这门课真是最高效的学习方式，抄会即学会）。因为个人原因申请只考期末，得分84总评85，估计出勤扣了点分。。

这学期因为华班培养方案要求，修读了组合学和组合学进阶这两门课程，可以说这两门课结合我现在做的一些工作，以及对近期一些工作的综合了解，深刻改变了我对组合学这个学科的看法。

首先说一下这门课的课程设置，这门课的前半学期首先介绍了一些概念和基本的技术（例如计数、算两次、图论常识），后面针对一些专题只进行了扁平化的一些介绍（SDR，design，intersecting family，Ramsey，Poset）等等，然后介绍了两个基本方法：概率方法和代数方法（线性代数方法 多项式方法等）。三个部分的讲解方法也截然不同，第一个部分主要是通过学技术算一些很基础的例子，第二部分只能扁平化介绍领域的基本概念和基本定理的证明（比如intersecting family那里唯一的非平凡定理可能也只有Erdos-Ko-Rado），第三部分个人比较喜欢，先介绍一些不平凡的方法，再看他解决不平凡的问题（这很大程度也依赖于第二部分对问题的扁平化介绍，所以在这里看起来第二部分是否也比较重要呢？）。如果细细这样看一下组合学这门课的设置，高潮其实还是在最后的两个方法上，但是前面的铺垫似乎又是必要的（提供大量例子？），虽然前面部分对组合学基础0的学生学起来真的很痛苦就是了😭

在这个学期之前，我对组合的印象似乎还停留在是一门纯粹的技巧学科，为了能躲避这门课，我甚至听说过往届同学采用“明修计数，暗逃组合”的策略，再加上关系很好的希望做组合方向的同学因为期末考试失利痛失国奖，再加上这门课在同学中的普遍口碑，这些都让我对组合这门课在还没有开始学习之前，就留下了不好的第一印象。但是这半年，越来越多的渠道让我充分认识到了组合的重要性：首先是近几年组合在数学各个领域大放异彩，从哲（xia）学（xiang）的角度来看这似乎也是历史的必然，毕竟离散结构似乎是一条看似平凡但非常本质的暗线，贯穿在所有学科的研究中，比如著名的Yu Deng关于Hilbert第六问题的工作，属于方程；以及去年Anantharaman-Monk关于随机双曲曲面与随机图谱的研究，属于几何等等，都展现出了似乎走向离散化的数学研究的重要意义（🔥老师曾经也谈起过这一点）；第二是个人学术品位的变化，让我不再对硬分析感兴趣（拜某门冯飞课程所赐），相反，这学期听到的很多讲座都在强调组合、概率在kinetic theory和mathematical physics中的重要性。上海交通大学的金石教授（曾任UW Madison数学系主任，现任上海交通大学自然科学研究院院长）就认为应用数学的研究者需要积极学习来自组合、物理（eg. quantum）、机器学习的各种技术，带着这样的观点和变化的taste让我重新审视这门课，似乎这门课没有那么“难堪”？当然，真正可能有趣的topic，是在组合学进阶上讲到 Szemeredi正则引理的时候，当我看到这个命题的时候我就意识到了这个可能和分析的关系，让我真正惊讶的是早在本世纪初Lovasz等人就已经以此为基础发展出了名为graphon的技术，这一技术在我做的工作中也扮演着十分重要的角色——这可能是让我真正惊叹组合的用处的时候。

当然，上述这些个人看法也只能说明组合这门学科本身潜在的重要性，也只能作为对这门课本身评价的一部分。这门课最大的不好之处可能还是在其考试的设置上，毕竟对于大三学生而言成绩还是比较重要的，而组合的考试恰恰是容易失手的，这可能也是绝大多数学生对此心生畏惧的原因吧。

总的来说这门课给我的体验还是逐渐提升的，学期刚开始的时候也许也觉得品位非常差，不过后来尤其是到概率方法开始，就觉得其实体验还是可以的了（（当然不得不谈的其实还有给分，今年似乎zxd老师试图调分，但是收到了优秀率限制的影响，成绩被jwc打回三次，所以可能因此加强了对平时分的梯度（？）😭总的来说，如果在完全不考虑考试和成绩的意义上，把这门课作为选修课，可能还会成为一门不错的课，但是加上必修、和考试的话，这门课的口碑可能也就只能维持现状了吧！

一直没有点评这门课，今天出分了，遂来点评一二。

对这门课的情感是很复杂的，一方面先验地获取了太多负面评价，到了冯虚御风而不知其所止的程度；而另一方面，我在日常的证明中也会写出一些基于组合的东西，毕竟有限的东西本质是算是一个数数问题，因此我也没有什么立场去批评这个学科，总不能端着碗骂娘吧🤣

当然，在这个学期我也不止一次想来评课社区拉一坨，尤其是前半学期。作业有一大半不会写，上课教室坐着难受，讲义的英文看着糟糕。期中考试那天，我大概是得了胃肠性感冒，考试的时候肚子里翻江倒海，沟槽的考试也无法做出，看到最后一题要背反例的时候直接安详地似了。凉值。

（这里还有一个难绷的事，那天晚上我顶着肚子的难受去参加数院期中座谈，并反映了班上同学关于取消基数必修组合学的意见，当时老师们对这个意见似乎并不反感，结果最后流传出来的那个座谈会记录Word里居然没有这一条，白瞎我又饿又痛地在那开了这么久的会，气晕了。）

不过期中之后，这课的善良人格上线了，作业十分简单，然后内容也相对简单了不少，主要是概率方法和代数方法，感觉比算两次这种东西好理解114514倍 ，学起来也轻松了不少。最后的考试也比较好做，基本是书上的定理改个问法，附加题比最后一次作业还简单一些。我交完卷后就回家摊稀了，结果后来同学问到才发现我漏了一题，这个凉值有点高。

感觉张老师还是有善良人格在的，比某成功人士更有温情一些。最后听说某些分段235后还直接上调了一把，这还说啥。不过这课似乎惯例就是严管平时分，所以给分有些微妙，前半学期我作业基本是MSE上抄的或者直接ChatGPT，后半学期发现这作业在VS上装个Copilot，直接tab几次就做完了，遂爽摆。感觉这课已经成为可速成的良心好课，不赖😋

实在是一门从任何意义上你都不应该考虑的数学课，甚至我觉得理应移出必修以停止拿这种东西糊弄学生.

这门课提到的所有知识单独都确实有一些东西，但组合在一起就有一种泛泛行过所有主题但什么都没有深究的浅尝辄止，很多方法也好技巧也好都是独立单行在这门课程里，前后找不到什么联系感.

至于张老师的水平我实在无法恭维，英文讲义美其名曰让大家提前适应英文文献，实际上即使是英文的阅读感也极其不适，更像是人为设置一些没有必要的卡在此. 不是说你丢几个1.5m的栏在那里别人就能学会跨栏的.

讲课的水平高情商讲叫有条有理，低情商叫a.e可以看教材处理，点名的处理让很多事情变得格外糟心. 更别说学期初有说“写英文作业或者LATEX可以优先调分”，但实际上的成绩和235一分不调没有什么区别.

综上所述，比起最后那个让GPA涨了0.01的课程总评，过程中无论是前半学期被题目折磨分心暑研，后半学期又会被计入点名名单，还是复习时候如坐针毡的面对苍白的讲义，都绝对说明了选课不值得.  如果想单独学习图论的内容我会更推荐刘西之老师的图论，至少内容上是系统的；至于其他的内容甚至可以科研必要时候自然学习，而不是在这门课提前获得碎片到科研需要时候早已忘掉.

如果你不幸还是要学这门课，复习的时候建议直接对着作业和讲义一遍遍看，组合完美验证了那句话：

“别做没有答案没有出处的题目.”

以上.

这给分何意味，总评比一分不调低了3分？给个95要老命了？

真红温了这次