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

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打回三次，所以可能因此加强了对平时分的梯度（？）😭总的来说，如果在完全不考虑考试和成绩的意义上，把这门课作为选修课，可能还会成为一门不错的课，但是加上必修、和考试的话，这门课的口碑可能也就只能维持现状了吧！

主要按照 Extremal Combinatorics with Applications in Computer Science 这本书讲，授课内容大致如下。

上半学期：

Basic counting, Binomial theorem, Inclusion-Exclusion principle, Generating function, Möbius inversion, Pólya theorem

下半学期：

System of distinct representatives, Pigeonhole principle, Extremal set theory(chains and anti chains, intersecting family, designs), The linear algebra method(basic method, polynomial method, codes), The probabilistic method(union bound, linearity of expectation, deletion method, Lovász sieve).

平时作业一周一次，最少3题，最多8题，英文答题。一般要花一个下午一个晚上(毕竟我比较菜。。。某次可能做了一天+QAQ)，题目是老师从课本或是其他参考资料上找的，确实有挑战。

应该是张老师第一次在科大带课，她应该是主要研究组合设计和编码的，所以这一块讲的比较多，但期末并没考emmmmm。对比某老师上了两个半月的极值图论，张老师讲的更全面一点，可以作为组合入门。扣1分的原因主要是，有点拘泥于课本了，例子讲的有点死(好像也不能怪老师啥，组合这课本来就，严格依赖智商)。然后有的时候某些同学没听懂，提出一些问题，老师也没有及时反应过来，不过课后都会通过QQ群告诉大家，这点还挺好。

组合还是很有趣的，虽然真的好难。

调分调的很狠啊反正，这一点没啥好说的。大二的同学还是要慎重选，毕竟这门课用到了一些些近代、概率论，作业负担也有点大，大佬们随意。

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

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

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

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

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

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

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

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

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

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

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

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

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

以上.

       课程主要内容前面那位大佬已经写得相当详尽了，感觉涉及的面很广（偷偷下了马组合的讲义发现讲的内容确实比马老师的组合多多了…）自己虽然很菜但是还是在学习过程中产生了相当的兴趣23333

       作业确实有些题很难，组合真是对智商要求很高啊qwq经常一个题想做半天想不出来最后全靠一起选课的大佬carry，或者靠wiki爸爸生存qwq

       然后我是大二选的这门课，Pólya定理会涉及到一丢丢群论，后面概率方法会涉及到最简单的一点概率论。其实都没有什么大问题，张老师超善良的www上课的时候问大二同学有没有学过，然后补讲23333（记得Pólya那里花了一节课的时间补讲群论的东西www）

       最后给分其实不太清楚，自我感觉一般但是总评比较凉qwq我也没去查分…不过看调分标准真的是在疯狂上调啊，作业分实打实的计入成绩反正蛮好的（督促平时认真学习组合hhh）

本垃圾写这段点评，是为了向大家更全面地说一下这门课。不能只有一些大佬的点评，还要有一些渣渣的评论。

首先，这课确实非常难。而且定理非常多，期中考试之后我几乎记了一本笔记本。而且考试过程中就体现出来一点，不会的题，你想破天都想不出来。

其次，老师上课讲得很好，但是我觉得可以不要用英文。我觉得除了用英文可以更好地阐释一些概念的来源以外，对于英文不好的同学，还是中文会更舒服吧。

第三，给分真的杀。今年和去年截然相反。我大概算了一下，优秀率只有百分之15到20。虽然调分并不是老师的义务，但是这样的给分确实有些让人难以接受。

另外，这课确实有些奇怪的地方。。本来以为组合会比较偏应用，结果全是非常靠近理论的东西。可能每次得出一个新理论后便计算一下R（s，t）是一个应用吧hhhh

内容的话和往届差不多，前半学期都是一些组合计数理论，后半学期难度提高，会讲一些不同的专题。总的来说内容还是比较丰富的。老师的讲义也写的不错，考试前一定要仔细梳理一遍。

作业的话每周大概6道题左右，助教以pdf形式放出，总体难度不大，都是上课题一些拓展，但还是有些题挺难的。

考试的话期中期末都不是很难，掌握课上讲的内容的原理就都还好，不过一定不要粗心大意，有些题里面会有坑容易错（本人就是期中粗心跪了），然后一般会有一题特别难的，这种就随缘了基本很难有人做出来。

给分个人觉得不错，本人期中跪了（没上平均分+没及格），靠期末考的好硬是拉上了3.7。

  张老师全英文板书讲义授课,助教每周都有习题课,认真听课应该就不会有太大问题.

  老师上课的时候偶尔会卡壳,但是讲得很详细,举的例子都比较典型基础.讲的内容也挺全面的,后面还讲了一堆设计什么的,总的来说内容很杂.

  这门课是我那个学期唯一没翘过的课,这门课每周两次都是早课我都没翘,可见这门课是多么有趣.

这门课张老师讲的是非常清晰的，各个方面都有涉及，对我之前没有什么了解的学科有了一个大体的认识，作业虽然难（对我而言）但是量不多，比较适中，如果有大佬Carry＋互帮互助（当然不是指copy而是请教讨论）的话写起来不算很困难，很需要智商的一门课吧，还有就是我们这一级期中期末考试试卷每一题分值都比较大，强烈建议大家能写多少是多少，因为是会有过程分的（还不少），自己就没有想到这一点比较亏

我们这一级是严格按老师第一节课讲的比例算的（这应该是老师第二次教这个课），期中平均分没有及格，期末在60附近？所以有些考在前面的同学被卡绩...

本来听师兄师姐说老师给分挺好的Orz，猜测是嫌我们学的不够认真刻苦？sad...

除了最后给分这门课认真学下来还是有收获的，建议试听一两节课再决定要不要选（当然，应数没得选，但是可以换专业嘛hhhh）

惊闻今年60以上的同学完全不调分，看到上面一堆都是说调分狠啥的，觉得有必要来给后面同学提个醒。

关于给分，今年老师严格按照3:3:4比例算分，没有调分。除了50到60的同学给了及格。期中期末平均分都是58，59的样子。按照助教在群里公布的分数表估算了一下感觉优秀率可能是不到百分之二十的。

关于课程内容，组合真的挺有趣的，虽然很考验智商。

关于讲课，觉得老师上课很熟练，条理清晰，两位助教也很认真负责，讲义更新迅速，有错误也会及时修改。

关于作业，按照今年的政策，请不要迟于一周补交作业，否则没迟交一次，你的总评下降会超过1分。

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

真红温了这次