组合学引论 · 从数数到结构的艺术

本书怎么读：一门关于「数得清，也要数得妙」的学问

这不是一本教材，而是一册入门书：全书只讲一件事——组合学，即「数一数满足某个条件的对象有多少种，并追问它们是否存在、怎样造出来」的学问。它回答的问题朴素而深刻：n 个人围一桌入座，有多少种坐法？一副扑克摸五张，有多少种同花？六个城市之间修路，最少修几条才能彼此连通？三十六个军官来自六支部队与六种军衔，能不能排成方阵使每行每列恰好「一队一衔」？从贾宪约 1050 年写下三角，到欧拉 1736 年走过七桥，再到埃尔德什的概率方法与汉明的纠错码，组合学的语言贯穿了计算、通信、概率与数学自身的许多角落。全书按章组织：绪论用棋盘、项链与宴席三件源头提炼出统一语言；第一章把计数的两条账法与二项式定理讲透；第二章锻造容斥与生成函数这把钥匙；第三章进入「必然的秩序」；第四章走进图论；第五章把对称变成可以记账的东西；第六章从存在走向构造与编码；综合站用年表、人物谱、方法总图、实验与自查收束全书。

写作的三条约束（本书的自我要求）。① 直觉与图形先行：每一个概念都从一张图、一个具体的小例子讲起——先看见方格纸上的路径如何走出三角、一串珠子转一圈为什么不算新的戴法、一张图上一笔能否画完，再抽成定义；每一个定理由「为什么它是对的」的直觉开路，再有完整的推导。② 一步一图：凡能画的都画——帕斯卡三角的数字瀑布、隔板分球的示意、Ramsey 染色的红蓝边、图的遍历足迹、项链的对称群、Fano 平面的七点七线。组合学最漂亮的地方正藏在「公式—图形—解释」的对照里：一条恒等式，画出来便一目了然。③ 自给自足：所需工具在书内随用随补（求和记号、一点同余与整除常识、一点线性代数与群论的初步、有限域的最必要知识），不假设手边另有教材；相邻领域已把区组设计与有限几何先演练了一遍，需要时可随时回望；个别深刻结论（五边形定理、Cayley 公式、设计存在性定理、四色定理）给出精确陈述、证明思路与文献指引，数值对拍在实验页随附。

页型节奏。每章以 导引 开篇（一页说清这一章要解决什么）；主体是 讲义 页（概念、定理、证明，一步一图）；每章配 例题 与 习题（末附提示）；每章收在 地图（依赖关系）＋小结＋思想卡（把技术升成观念）＋挑战与实验（动手核验）；另有 〖札记〗格物札记做中西数学传统的对照。每页右上角标页码，页眉灰色小字标出所属章与小节。

难度标记。讲义页首行用 ★–★★★★★ 标出阅读难度：★ 会加减乘除与求和记号即可，★★ 需要一点指数律与二项式（书内自给），★★★ 需要一点同余与初等数论（书内自给），★★★★ 需要线性代数与群论的初步（书内自给），★★★★★ 需要射影几何与有限域的深水区（第六章与综合站余韵）。若只求理解主线，读绪论、第一章的二项式定理、第二章的生成函数、第三章的 Ramsey 定理、第四章的树与平面图即可；若求完整掌握，按章顺序逐页推进，并把每章习题做完。

三条线索贯穿全书：

① 明线——从数数到结构：先从棋盘、项链与宴席三件源头看见「有多少种」（绪论），把两条账法与二项式定理讲透（第一章），锻造容斥与生成函数这把钥匙（第二章），看「必然的秩序」（第三章），走进点、线、网络（第四章），把对称记账（第五章），最后从存在走到构造与编码（第六章）——这正是组合学从「数数的技巧」长成「离散数学主干」的轨迹。

② 暗线——双射·对合·双计数三把钥匙。组合学最深的功夫，是「把一个难数的集合的东西，数成另一个好数的集合的东西」：双射问「能不能在两个集合之间建立一一对应，把难数换成好数」；对合问「把对象两两配对之后，剩下的不平衡揭示了什么」（许多恒等式一行证完）；双计数问「同一件事用两种方式数，两边相等的等式告诉我们什么」。三者不是替代关系，而是配合关系——能对应就对应，配对剩下的单独看，两种数法摆在一起读。全书反复演练的，正是这种「三把钥匙轮换使用」的判断力。

③ 接口——通往四个邻域。组合学是离散数学的枢纽：与数论（同余构造与整除分析，第一、三章）、概率论（等可能模型与随机方法，第一、三章）、图论（结构、着色与算法，第四至六章）、代数（群作用与对称计数，第五章；有限域与设计，第六章）四条战线直接相接。相邻领域把区组设计与有限几何先演练了一遍，对照阅读，可贯通「计数」到「设计」的一条主线。

写法约定（TEX 标准）：集合的元素个数记 |S|，从 n 个里取 k 个的组合数记 C(n,k) 或 ⁿC_k；排列数记 P(n,k)；阶乘记 n!；变量（n、k、x）斜体，数字与运算符正体；数列记 ⟨a_n⟩，其生成函数记 A(x) = Σa_nxⁿ；群 G 作用在集合 X 上记 g·x，图记 G = (V,E)。关键一步配图，公式与图形逐章对照。

绪论 走进组合学：从数数到结构从数数说起：一门关于「多少种」的学问

先做三道不需要任何微积分的题。第一道：12 个人围一张圆桌入座，有多少种坐法？答案 11! = 39 916 800——近四千万种，一个宴会厅从此永远不愁花样。第二道：一副扑克摸五张，摸成「同花」的可能性有多少种？答案 4 × C(13,5) = 5148 种，而五张牌总共只有 C(52,5) = 2 598 960 种摸法——顺手一除，同花的概率不到千分之二，扑克桌上的心跳从此有了数学解释。第三道：六个城市之间修路，最少修几条才能从任何城市走到任何城市？答案五条——而且五条就是下限，一条也不能省。三道题风马牛不相及，骨子里却是同一件事：数一数满足某个条件的对象有多少种。这门学问叫组合学（combinatorics）。

它朴素，因为出发点不过是「一个一个地数」；它深刻，因为对象动辄多到不可能一个一个地数——12! 已经四千万，C(100,50) ≈ 1.01 × 10²⁹，而宇宙中的原子总数不过 10⁸⁰ 上下。于是组合学的全部艺术在于：不看对象本身，只看对象的结构——找到对象之间的对称、对应与分类，让天文数字塌缩成一行式子。数得清是本分，数得妙才是本事。本册要教的，正是这份「妙」的手艺。

组合学又是最「贴身」的数学：它不假借物理直觉，起点就是纸笔可验的小账。全册几乎每个定理，读一页就能亲手复验一页——这种即学即验的踏实感，是数学里难得的奢侈。

绪论 走进组合学：从数数到结构数数是最古老的数学：从结绳到贾宪

★　数数先于一切数学。上古结绳记事，大事结大结、小事结小结——绳子上的结是离散对象的最早账本。用符号对离散对象做系统计数，《周易》大概是现存的第一个成熟案例：阳爻与阴爻两种记号，取三个自下而上叠成一卦，得 2³ = 8 卦；取六个，得 2⁶ = 64 卦。「八卦」与「六十四卦」不是玄学，是两条原理（后世的加法原理与乘法原理）在公元前的自觉运用——每一卦的每一位有 2 种取法，位与位之间互相独立，遂按乘法相乘。

中国古算对组合学的第一座高峰，是贾宪三角。约 1050 年，北宋贾宪在《释锁算书》中给出开方用的「开方作法本源图」——把 0 至 6 次二项式展开的系数排成三角。此后杨辉于 1261 年在《详解九章算法》中载录并注明「贾宪用此术」，故中算传统称之为贾宪—杨辉三角。在西方，帕斯卡于 1654 年写《论算术三角》系统研究同一张表，距贾宪已六百年。三角里每个数 C(n,k) 都有直接的计数含义——从 n 个里挑 k 个的方法数——这张表因此成了组合学与代数的第一次会师（第一章详述）。

西方一侧同样源远流长：莱布尼茨 1666 年的《论组合的艺术》第一次把「组合」当作一门独立学问的名称；欧拉 1736 年的七桥问题开创图论；柯克曼 1850 年的十五女生问题催生区组设计；而二十世纪的埃尔德什（Erdős）与拉姆齐（Ramsey）把「存在性证明」推成一门艺术。本册的年表（综合站）会把这条时间线补全。

绪论 走进组合学：从数数到结构什么是一个「组合学问题」

★　一个问题算不算组合学问题，不看它问什么名词，看它满足三个特征。特征一：对象离散。研究对象是可数的、分立的——人的坐法、牌的组合、图的顶点与边、码字的集合；不是连续流动的量。微积分处理「怎样变化」，组合学处理「有多少种」。 特征二：问题有限（或可数）。原则上可以把对象一个一个列出来——但原则上可行往往实践上不可行，这正是需要理论的原因。特征三：追问落在四个动词之一。

四个动词不是并列的标本，而是一条递进的阶梯：先会数（计数），才知道「有」与「没有」的分界（存在）；证明确实「有」，才轮到动手造（构造）；造出来几个方案，才谈得上挑最好的（优化）。本书按这条阶梯组织六章，每登一级，工具箱换一批。

用一道例题把三个特征串起来。例 0.1（宴席上的握手）　十二位客人参加晚宴，散席后主人统计：每人恰好与 5 人握过手。握手次数总共多少？有没有这种可能？前者是计数（每人 5 次、十二人、每次握手两人各记一次，共 12 × 5 / 2 = 30 次——除以 2 正因为每次握手被两人各记一遍，这是第四章「握手引理」的预演）；后者是存在（这样的事真的安排得出来吗？能，画一个正十二边形，每人只与左右各两位及正对面一位握手即可）。一道题里，计数与存在并肩出现——组合学问题的常态。

还要划清一条边界：组合学不等于「穷举」。穷举是对抗性的——对象一多立刻失效；组合学是建设性的——它寻找对象集合上的结构（对称、序、对应、递推），让答案的规模与对象总数脱钩。C(100,50) 有 10²⁹ 那么大，但计算它只需几十次乘法：结构压倒了规模。这种「以结构对规模」的思路，贯穿全书每一章。

绪论 走进组合学：从数数到结构三个热身问题：棋盘、项链与宴席

★★　正式开课之前，先陪三道「本章能看懂题、全册学完才彻底服气」的问题。它们各自把一根线头递给后面的一章。

问题一（棋盘·递给第一章）。在 4 × 4 的方格纸上，从左下角走到右上角，每步向右或向上走一格，共有几条路？答案是 C(8,4) = 70：八步中恰好四步向右——「哪几步向右」与「哪四格被选中」一一对应，路径计数一秒变成组合数。把棋盘换成 n × n，答案 C(2n,n)；若再禁走某条对角线以下，就撞上著名的 Catalan 数（第二章 2.13）。数数的钥匙常常是翻译：把一种对象翻译成另一种好数的对象。

问题二（项链·递给第五章）。五颗珠子涂黑或白，能做出多少种本质不同的项链？正面数是 2⁵ = 32，但转一圈、翻一面不算新的——数出来的 32 有大量「同一串的影子」。答案其实是 8，但 8 这个数不对称之群就算不干净。这颗项链将在第五章被 Burnside 引理与 Pólya 定理当众解剖。

问题三（宴席·递给第三章）。任何六位客人，是否必有三人彼此都握过手，或三人彼此都没握过手？出人意料：必有，与客人的身份毫无关系。把「握手」画成两人之间的红边、「没握」画成蓝边，命题变成：六点的完全图任意红蓝染色，必出同色三角形。这是 Ramsey 定理最著名的入口（第三章 3.6–3.7 完整推演），也是「不构造而证存在」的第一课。

三道题的答案封存：70、8、必有。全册学完时回头看，三道题分别对应三把钥匙——翻译、商对称、证存在——合起来恰是组合学一半的性格。

绪论 走进组合学：从数数到结构组合学的版图：计数·存在·构造

★　把绪论开头的问题按三个动词重新归档，全书的地形便一览无余。计数区（第一、二、五章）：两条账法与二项式定理（第一章）是基本功；数不清时容斥与生成函数（第二章）；对象带对称时群作用（第五章）。存在区（第三章）：鸽笼原理与 Ramsey 定理证明「必然有」，概率方法证明「大概有」。构造区（第四、六章）：图论把关系造成看得见的网络（第四章），区组设计与纠错码把完美结构造成可用的蓝图（第六章）。

版图上还应标出一条暗流：三把钥匙。双射——把难数的对象翻译成好数的对象（格路变组合数、树变 Prüfer 码）；对合——把对象两两配对，剩下的落单者恰好给出恒等式（第一章 1.7）；双计数——同一件事用两种方式数，两边相等的等式就是新定理（握手引理、Cayley 公式、Burnside 引理的证明，全是双计数）。三个动词是「做什么」，三把钥匙是「怎么做」；版图加钥匙，就是全书的经与纬。

一望邻人的疆土：组合学与数论共用同余的语言（第三章的构造）、与概率论共享等可能的舞台（第一章与第三章的概率方法）、与代数交换群与域（第五章与第六章）、而图论则自成一国又处处设使馆（第四章）。这些接口将在各章的「衔接讲义」里逐一指认。

绪论 走进组合学：从数数到结构与姊妹学科的接口：数论·概率·图论·代数

★★　组合学从不闭门造车。四个邻域的接口，本书都会走到门口，这里先指认门牌。

相邻领域也在此对齐：相邻领域已把区组设计与有限几何先行演练，本册第六章与之互为镜像——那里以「设计」为纲，这里以「计数与编码」为纲；相邻领域与相邻领域则示范了同一套「讲义—例题—习题—札记」体例在分析学中的样貌。四册合读，可见 K2C 正文「从格物到九章」的全景。

一句话总结四个接口：数论递给组合「余数这只笼子」，概率递给组合「骰子这杆秤」，图论递给组合「点线这张纸」，代数递给组合「对称这本账」。

绪论 走进组合学：从数数到结构本册的地图与读法

★　全书六章一线，每章的产出恰好是下一章的原料，依赖关系如下，读法也写在图旁。

三种读法。① 顺读（推荐首读）：按页推进，每章例题必做、习题课自测，速度约每天四至六页。② 要点读：只求主干——绪论、1.5–1.7（二项式与恒等式）、2.5–2.7 与 2.13（生成函数与 Catalan）、3.1 与 3.6–3.8（鸽笼与 Ramsey）、4.1–4.9（图与树与平面）、5.4–5.8（Burnside 与 Pólya）、6.9–6.11（Hamming 码）。③ 查典读：把各章速查表当索引，用到哪页翻哪页。

页型的含义再交代一遍：导引开路，讲义铺路，例题示范，习题自测（末附提示），地图收网；思想卡把技术升成观念，挑战放一道硬题，实验机出庭作证，〖札记〗对照中西传统。每章末的速查表是本章的「一页锦囊」，考前或写码前扫一眼即可。

器材清单很简单：纸、笔、一副扑克、若干围棋子或彩色扣子（做项链实验用）、以及一台能跑短脚本的计算机（实验页附脚本思路，无需任何专用环境）。组合学的实验成本低到令人发笑——这是它作为「第一门大学数学」的又一好处。

绪论 走进组合学：从数数到结构绪论地图：全书概念鸟瞰

最后一张图把绪论收拢：三个动词（纵轴）与三把钥匙（横轴）张成的平面，六章与综合站各就各位。读图方法：横向看「工具的谱系」——两条账法长出二项式定理，二项式长出生成函数，生成函数长出 Pólya；纵向看「目标的谱系」——计数养存在，存在养构造。

地图在手，出发。下一页起进入第一章：先从两条账法开始——它们朴素得像废话，却撑得起整座三角。

第一章 计数的原理：数得清，也要数得妙第一章导引：数数为什么是门学问

幼儿园的孩子都会数数——从一数到十，再从十数到一百。可「数数」作为一门数学，难就难在：对象根本不排队。十二个人围桌坐，不存在「第一个坐法、第二个坐法」的自然次序；五张牌摸成同花，也没法把所有同花一字排开点数。要从「一个一个地数」升级为「不看对象看结构」，需要一套最基础的账法。本章就做这件事：把组合学的地基——加法原理、乘法原理、排列与组合——从直觉锻造成工具，再用它盖起第一座高楼：帕斯卡三角与二项式定理。

本章的行进路线是一条直线，每一站踩着上一站：

读本章只需一件器材：一支笔。几乎每一页都亲手验一个小账——组合学的第一个承诺是：验证比理解更容易，而理解常常从验证开始。

第一章 计数的原理：数得清，也要数得妙1.1 加法原理与乘法原理：数数的两条账法

★　一切组合计数都从两条账法出发。加法原理：若一件事的做成方式可分成互不重叠、合集完备的 k 类，第 i 类有 a_i 种做法，则做成这件事共 a₁ + a₂ + ⋯ + a_k 种做法。乘法原理：若一件事须依次经过 k 个步骤，第 i 步有 b_i 种走法且各步的选择互不影响，则共有 b₁ b₂ ⋯ b_k 种走法。

两条原理一个管「分类」，一个管「分步」——用哪个，先问一句：这件事是「或」还是「且」？从北京到上海，乘高铁或乘飞机，是「或」，两类相加；从家到高铁站、再从高铁站到上海，是「且」，两步相乘。混合情形尤其常见：先分类、类内分步，或先分步、步内分类——账要分两层记。

两条原理各有一句常见的破产警告。加法原理要求类与类不重叠：把「摸两张牌」分成「同花」与「有 A」两类相加，就把「同花且带 A」数了两遍——重复。乘法原理要求各步独立：若第二步的可选项依赖于第一步的选择，两步就不能直接相乘——纠缠。重复与遗漏，是 1.15 页要立案的两大「惯犯」，此处的两条警告就是它们的案底。

第一章 计数的原理：数得清，也要数得妙1.2 排列：选出并排好次序

★　从 n 个互不相同的对象里取出 k 个，并按次序排成一列，每一种排法叫一个 k-排列，其总数记 P(n,k)。用乘法原理分 k 步：第一步 n 种选法，第二步剩 n − 1 种，⋯⋯第 k 步剩 n − k + 1 种，各步独立相乘：

当 k = n，得到全排列数 P(n,n) = n!。阶乘增长快得惊人：5! = 120，10! = 3 628 800，13! 已超过六十亿——比地球人口还多。这就是开头「围桌坐法」问题的近亲：12 人坐成一排有 12! 种坐法。

排列还有一个变体要现在就认识：圆排列。10 人坐成一排有 10! 种；围圆桌坐，整体转一格算同一坐法，于是每个「圆坐法」对应 10 个「排坐法」——除以 10，共 10!/10 = 9! 种。一般地，n 人围桌共 (n − 1)! 种坐法。这条「除以圈长」的直觉正是绪论项链问题的雏形，第五章将把它锻造成系统理论。

本页埋下一句话，下一页展开它：排列管次序，组合不管；二者之间隔着一个阶乘。这句话是全部组合计数里用得最频繁的一次换汇。

第一章 计数的原理：数得清，也要数得妙1.3 组合：只挑不排

★　从 n 个互不相同的对象里取出 k 个不计次序，每一种取法叫一个 k-组合，总数记 C(n,k)（课本上又写作竖排的 ⁿC_k）。把 1.2 的桥梁写正式：k-排列可以两步走成——先挑出一个 k-集合（C(n,k) 种），再把集合内部排成次序（k! 种）。乘法原理倒过来读：

组合数有三条立刻能用的性质。其一（对称）：C(n,k) = C(n,n − k)——从 n 个里挑 k 个留下，与挑 n − k 个丢掉是同一件事，一一对应（双射！）。其二（边界）：C(n,0) = C(n,n) = 1、C(n,1) = n。其三（专门定理）：C(n,k) + C(n,k + 1) = C(n + 1,k + 1)——把 n + 1 个对象里的第 n + 1 个特殊化：选法分成「不含它」与「含它」两类，分别恰好是左边两项。这条恒等式就是帕斯卡三角的生成规则，下一页的主角。

这里的论证风格，它是全书最高频的武器：要证恒等式，把左边解释成某个计数问题的答案，把右边解释成同一问题的另一种数法，两边自然相等——这就是绪论说的「双计数」钥匙。下一页的三角、再下一页的定理，全是这把钥匙开出来的门。

第一章 计数的原理：数得清，也要数得妙1.4 帕斯卡三角：组合数的几何

★　把 C(n,k) 按 n 排成行、k 排成列，再用帕斯卡规则把相邻两行的数勾连起来，就得到那张从贾宪到帕斯卡都为之着迷的三角（见图 0-2）。三角是组合数的「地图」：第 n 行从左到右依次是 C(n,0), C(n,1), …, C(n,n)，左右对称（性质其一），行两端是 1（性质其二），中间每个数等于肩上两数之和（性质其三）。

三角不只是存表，它自己会「长」。三条最有用的生长规律：① 行和：第 n 行各数之和为 2ⁿ（把 n 个对象的全部子集按大小分类——加法原理的一次大规模阅兵）；② 锯齿和：交错加减一行，得 0（C(n,0) − C(n,1) + ⋯ ± C(n,n) = 0，n ≥ 1；1.7 用对合一行证完）；③ 斜线和（ hockey stick）：沿左斜边往右下方砍一刀，C(r,r) + C(r+1,r) + ⋯ + C(n,r) = C(n + 1,r + 1)——把帕斯卡规则沿对角线累加即得。

hockey stick 还有一个值得单独说的「走路证明」：从三角顶端往下走，每步左下或右下，走 n 步到底，路径条数恰按帕斯卡规则在格点上加倍累积——三角于是成为一张「路线流量图」，每个格点上的数就是从顶端到该点的路径条数。数数的钥匙又一次是翻译：把代数关系翻译成走路，恒等式变成地图上的守恒律。下一页，同一张三角将托起它最著名的定理。

第一章 计数的原理：数得清，也要数得妙1.5 二项式定理：代数与计数的会师

★★　展开 (a + b)ⁿ，系数是什么？取 n = 2 亲手乘开：(a + b)² = a² + 2ab + b²。系数 1、2、1 从哪来？把乘积 (a + b)(a + b) 展开的每一个单项，是从第一个括号取一项、第二个括号取一项的分步选择：取到两个 a 的方式只有 1 种（两步都取 a），取到一 a 一 b 的方式有 2 种（谁出 a 皆可）——系数就是取法的数目。一般地，乘积 (a + b)ⁿ 的每一项由 n 个括号各出一因子拼成；恰好 k 个括号出 b（其余出 a）的单项合并成 a^n−kb^k，而「哪 k 个括号出 b」的选法恰是 C(n,k)。于是：

定理立刻产出三样东西。第一，系数表就是帕斯卡三角——代数展开与计数结构在此会师，三角从此有了双重身份。第二，取 a = b = 1 得 2ⁿ = Σ C(n,k)——1.4 的行和规律从「观察」升级成「定理的推论」。第三，取 a = 1, b = −1 得 0 = Σ (−1)^k C(n,k)——锯齿和同理升级。一个定理养活半张三角的规律，这就是「会师」的分量。下一页起，把三角里能挖的恒等式系统地挖一遍。

第一章 计数的原理：数得清，也要数得妙1.6 组合恒等式：一列数的多种读法

★★　组合数 C(n,k) 是数数界最富「多义性」的角色：同一个数，能读成好几种截然不同的计数故事的答案，故事对上故事，恒等式就自动成立。本页把最常用的六条列成一张「读法对照表」，每条附它的计数读法。

六条里最值得驻足的是队长恒等式，因为它示范了双计数的标准姿势：左边 Σ k C(n,k) 是「按集合大小分类、每类每集挑一个队长」的账；右边 n 2ⁿ⁻¹ 是「先从 n 人里定队长，再从剩下 n − 1 人里随便拉人入伙」的账。两队人马数的同一批对象——「有队长的子集」——于是账面必然相等。左边是分类账，右边是流水账，流水账往往比分类账好算，这就是双计数在实战里的价值。

Vandermonde 则是「会师」精神的延续：它的特例 Σ C(n,j)² = C(2n,n)（取 m = n, r = n）读作：从两班各 n 人里选 n 人，按甲班出几人分类。这个数字大得出乎直觉——C(100,50) = Σ C(50,j)²，一行和等于一个斜对角线上的会师。代数上要硬乘两个多项式 (1+x)ⁿ(1+x)ⁿ = (1+x)²ⁿ 比对系数才能得到它，计数上一句话就完——组合证明的「省」，全省在对结构的直认不讳上。

第一章 计数的原理：数得清，也要数得妙1.7 对合技巧：正反配对证恒等式

★★★　双计数证「两边相等」，对合则证「一边为零」或「正负相抵」。它的招式：把一个带正负号的计数对象族两两配对，使每对恰好一正一负、互相抵消；然后清点落单的对象——族的总和恰好等于落单者之和。若落单者寥寥可数，恒等式一行到手。

细看这个证明的机巧：对合 τ 的定义「拨动最小元素」对每一个子集都可执行，所以配对天衣无缝、无人落单，和为零。若把问题换成「从 n 个元素里取大小至少为 2 的子集」之类带禁令的族，对合就会留下若干拨不动的落单者——落单者恰是「违反禁令边缘」的特殊对象，它们的带号和就是新恒等式。对合的功夫不在配对本身，而在选一个让落单者现形的拨动规则。

至此，第一章的上半场收官：两条账法（1.1）造出排列组合（1.2–1.3），组合数铺成三角（1.4），三角托起二项式定理（1.5），定理养出恒等式工厂（1.6），对合给工厂添了最巧的一台机床（1.7）。下半场（1.8 起）处理「不干净」的对象——带重复的多重集、转圈不算新的圆排列、方格纸上的路径、负指数的广义二项式——每一件都是上半场工具的新战场。

第一章 计数的原理：数得清，也要数得妙1.8 多重集的排列：有重复字母的单词

上一节的排列公式默认元素两两不同。可现实里的对象常带重复：单词 MISSISSIPPI 十一个字母里 I 出现四次、S 四次、P 两次、M 一次。若先按 11! 排开再数「看起来一样」的，会撞上重复计数的深水区——两个 S 换位置，单词纹丝不动。

除法原理的正面用法。与其先排后删，不如反过来问：十一个「位置」中，哪四个给 I、哪四个给 S、哪两个给 P、剩一个给 M？这是把 11 个位置分组：C(11, 4) · C(7, 4) · C(3, 2) · C(1, 1)。连乘化简恰好等于

11!4! · 4! · 2! · 1! = 34 650

一般地，多重集 {n₁ · a₁, n₂ · a₂, …, n_k · a_k}（共 n = n₁ + ⋯ + n_k 个元素）的全排列数为

n!n₁! n₂! ⋯ n_k!

分子是「假装全不同」的排法，分母把每一种视觉上的重复都除干净。这个公式有个漂亮的名字——多项式系数，记作 binom(n; n₁, …, n_k)，它正是下一节多项式定理的主角。

换个读法。同一公式还能读成「在 n 个位置里给 k 类对象分座」：n!/(n₁! ⋯ n_k!) 也是「n 人分成 k 组、各组 n_i 人」的分组方案数。分苹果、分座位、分字母，骨架是同一根。

第一章 计数的原理：数得清，也要数得妙1.9 多重集的组合与隔板法

元素不止有重复，还可能取之不尽：三类糖果随便拿，拿十颗，几种拿法？这类「从 k 类无限供应的元素里取 r 个（只问各类几个）」的计数，答案是一个熟悉的组合数换了身衣服：

(k + r − 1)!r! (k − 1)! = C(k + r − 1, r)

隔板法是它最经典的证明。拿十颗糖、三类，等价于求方程 x₁ + x₂ + x₃ = 10 的非负整数解个数——十颗糖排成一排（用 ● 表示），在中间插两块隔板（用 | 表示）：

12 个符号位置里选 2 个放隔板，C(12, 2) = 66 种——这就是答案。一般地，x₁ + ⋯ + x_k = r 的非负整数解有 C(k + r − 1, k − 1) 个。

三个变式，三板斧。①每盒至少一个（正整数解）：先各发一颗「保底糖」，剩 r − k 颗随便分，得 C(r − 1, k − 1)。②带下限（如 x₁ ≥ 2）：先给 x₁ 塞两颗再按变式①处理。③带上限（如 x₁ ≤ 4）：容斥的前奏——总数减去「x₁ ≥ 5」的坏解，后者把 x₁ 强行吃掉 5 颗后仍是隔板问题。

第一章 计数的原理：数得清，也要数得妙1.10 圆排列与项链：转一下不算新

四人围圆桌而坐，几种坐法？直线排是 4! = 24，但圆桌没有「第一个位置」——转一格，甲乙丙丁变乙丙丁甲，谁都不会承认这是新坐法。每个圆排列对应 4 个直线排列（四种起头位置），所以

4!4 = 3! = 6

一般地，n 个不同元素的圆排列数为 (n − 1)!：先固定一人压住旋转对称，剩下的人直线排。

再加一层对称：翻面。若坐的是项链而不是圆桌——项链可以从脖子上取下来翻个面——那么镜像的两个圆排列也算同一条。于是 n 颗不同珠子的项链数为 (n − 1)!/2（n ≥ 3）。五颗不同珠子：12 条项链。

审题的关键一句话：先问清「什么算同一个」。圆桌坐次认旋转、项链连翻面都认，手镯与钥匙圈又各有各的规矩。对称性不同，答案差一倍甚至更多——这正是第五章群作用计数的预告片。

第一章 计数的原理：数得清，也要数得妙1.11 格路计数：方格纸上的帕斯卡三角

从方格纸的西南角走到东北角，每步只能向右或向上，几条路？把向右记 R、向上记 U，一条 m × n 格网里的最短路就是一个 m 个 R、n 个 U 的字母排列——回到 §1.8：

C(m + n, m)

格路是组合学里的万能翻译机：许多代数恒等式翻成格路语言就一目了然。帕斯卡恒等式 C(n,k) = C(n−1,k) + C(n−1,k−1) 读作「路过某格的路，按最后一步向右还是向上分两类」；Vandermonde 恒等式读作「跨过一条竖线的路，按过线位置分段」。

带约束的格路是更大故事的入口：不许越过对角线的格路条数正是著名的 Catalan 数，§2.13 将用反射原理把它请出来。方格纸虽小，后来的一切——反射、循环引理、递推——都在这几步 R 与 U 里发芽。

第一章 计数的原理：数得清，也要数得妙1.12 广义二项式定理：负指数与分数指数

帕斯卡三角的行数是有限的，但牛顿在 1665 年问了一句更贪心的话：(1 + x)^α 当 α 不是非负整数时，展开是什么？答案是把 C(n,k) 里的 n 换成任意实数后，级数照样成立：

(1 + x)^α = Σ_k≥0 binom(α, k) x^k，其中 binom(α, k) = α(α−1)⋯(α−k+1)/k!

收敛半径 |x| < 1。组合学最关心负整数指数：把 α = −n 代入并整理，

(1 − x)⁻ⁿ = Σ_k≥0 C(n + k − 1, k) x^k

系数恰是 §1.9 的多重集组合数！这不是巧合：(1 − x)⁻³ 的 x^r 系数正是「三类无限供应取 r 件」的取法数——生成函数思想在此破门而入，第二章将为它单开一章。当 n = 1 还原几何级数 1 + x + x² + ⋯。

第一章 计数的原理：数得清，也要数得妙1.13 多项式定理：多变量的展开

二项式定理只管两个变量的乘方，多个变量呢？多项式定理说：

(x₁ + ⋯ + x_k)ⁿ = Σ binom(n; n₁, …, n_k) x₁^n₁ ⋯ x_k^n_k

求和跑遍所有 n₁ + ⋯ + n_k = n 的非负解，系数正是 §1.8 的多项式系数。证明与二项式定理同款：n 次乘法中，x_i 被挑选了 n_i 次——挑法即多重集排列数。譬如

(a + b + c)⁴ 的 a²bc 项系数为 4!/(2!·1!·1!) = 12

展开式共多少项？即「4 次方配额分给 3 个变量」的方案数：C(4 + 3 − 1, 3 − 1) = C(6, 2) = 15 项——隔板法在数项数！再如 (x + y + z)² 共 C(4, 2) = 6 项，即 x² + y² + z² + 2xy + 2xz + 2yz。

把变量换成具体对象就有应用：掷三颗六面骰，点数之和为 10 的方式数是 (x + x² + ⋯ + x⁶)³ 中 x¹⁰ 的系数——多项式定理配上「变量当占位符」，就把计数问题变成代数展开问题。这枚钥匙在 §2.5 正式开锁。

第一章 计数的原理：数得清，也要数得妙1.14 概率视角：等可能世界的计数

计数到底是在干什么？在等可能模型里，概率就是两个计数的比值：

P(事件) = 顺利结局数总结局数

绪论里「五张牌同花」的概率 5148/2 598 960 ≈ 0.198% 正是这个格式的直译。再来两例。例一，至少一张 A：直接数「恰一张、恰两张……」要加四项，倒过来一步到位——1 − C(48, 5)/C(52, 5) ≈ 0.341。对立事件是计数者的捷径：与其正面攻城，不如算城墙外面还剩多少。

例二，生日悖论。三十人的班里两人生日相同的概率？直接数麻烦，算对立面「人人不同」：365 × 364 × ⋯ × 336 / 365³⁰。逐项约去 365 得连乘 Π_i=0²⁹(1 − i/365)，真算一下：约 0.294——所以「撞生日」的概率高达 70.6%。直觉只看到 365 个格子，没看到 C(30, 2) = 435 对「可能相撞的人对」。这是第一章的收官警句：概率的反直觉，多半是计数的直觉没过关。

第一章 计数的原理：数得清，也要数得妙1.15 计数的陷阱：重复与遗漏的案卷

本章公式不多，翻车姿势却花样繁多。本页是一份「案卷」，收录四种最高发的错案。

案一：忘了除以对称。「六人围圆桌」答 6! = 720——多算了旋转等价，正解 120。凡见「圆桌、项链、手镯、转一圈不算新」，先立起对称意识再动笔。

案二：和事件当互斥加。「从 52 张牌抽 5 张，同花或四条，几种？」分别算 5148 与 624 相加得 5772，却漏了「同花又是四条」的 36 张同花大满贯级重复——正解 5148 + 624 − 36 = 5736。集合相交时必须减重叠，容斥原理（§2.1）就是这条经验的系统化。

案三：「至少」正面硬攻。「至少一张 A」若正面分「恰一张、恰两张、恰三张、恰四张」四账并加，算力翻四倍还易漏项；对立面 1 − C(48,5)/C(52,5) 一步到位。经验法则：「至少」「至多」先想对立面。

案四：把有序当无序。「从十人中选三人组成委员会」是组合（120），「选三人任正副席与秘书」是排列（720）。判定口诀只有一句：交换两个元素，结局变不变？变则排列，不变则组合。

第一章 计数的原理：数得清，也要数得妙1.16 第一章全景：一张数数的决策树

十六节的公式与技巧，归拢起来是一棵决策树。做题时自上而下走三问：

第一问：结局有没有顺序？无序走组合 C(n,k)，有序走排列 P(n,k) 或全排 n!。第二问：元素有没有重复或无限供应？有限重复用多项式系数 n!/(n₁!⋯n_k!)，无限供应用隔板法 C(k+r−1, r)。第三问：有没有对称在制造等价？旋转除以组大小，旋转加翻面再除二——更深的对称留给第五章。

三问之外还有两条外挂：事件带「至少／至多」先想对立面（§1.14）；多约束条件先容斥再算细账（§1.15 案二，§2.1 正式开讲）。这张树值得亲手画一遍——画树的过程，就是把公式翻译回计数语言的过程，也是第一章真正想教的东西。

第一章 计数的原理：数得清，也要数得妙例题一：分球入盒与单词排列

例 1（八种分球）。三只不同的球放入四个不同的盒子，按「球可辨？盒可辨？盒可空？」逐层分类计数：

解题记要。「不空」的满射计数用容斥正面打：总方案减「某盒空」、加回「两盒同空」……四层交错和恰好清干净重复——这正是 §2.2 容斥一般形式的 3 集合特例。而「球异·盒同」引出的 Stirling 数与「球同·盒同」的分拆数，分别会在 §6 与 §2.8 长成完整理论。

例 2（单词排列）。LEVEL 五个字母能排出多少个不同单词？字母账本：L×2、E×2、V×1，故 5!/(2!·2!) = 30。追问：其中首尾都是 L 的几种？固定两端两个 L，中间三格排 E×2、V×1：3!/2! = 3 种。再追问：两个 E 不相邻的几种？插空法——先排 L、L、V 的 3 个词干（3!/2! = 3），三个空隙选两个放 E：3 × C(3, 2) = 9 种。

第一章 计数的原理：数得清，也要数得妙例题二：二项式恒等式的证明工厂

证恒等式有三条流水线：代数、归纳、组合。组合证明最有滋味——两边各讲一个故事，故事相同则数相同。

例 3。证 Σ_k C(n,k) = 2ⁿ。组合证明：右端是「n 个人组队，任意大小」的队数；按队里几人分类，恰是左端。一行完事。代数证明（令 x = y = 1 代入二项式定理）也快，但没有解释力。

例 4。证 Σ_k k C(n,k) = n 2ⁿ⁻¹。组合证明：数「有队长的队」两次。先选队长再选队员：n · 2ⁿ⁻¹；按队伍大小分类：Σ k C(n,k)。双向计数（double counting）——同一件事数两遍，得到一个等式——是组合证明的看家本领。

例 5。证 Vandermonde C(m+n,r) = Σ C(m,k)C(n,r−k)：从 m 位先生 n 位女士中选 r 人，按先生几人分类。代数路线则比较 (1+x)^m+n = (1+x)^m(1+x)ⁿ 的 x^r 系数——两条路线各有所长，但组合证明把「为什么相等」讲成了人话。

第一章 计数的原理：数得清，也要数得妙习题课（一）：排列组合基本功

A 组·快问快答

A1.字母 BANANA 能排出多少个不同单词？
答：6!/(3!·2!) = 60。字母账本：A×3、N×2、B×1。

A2.八人围圆桌，若只关心左右邻座关系有几种？（提示：相对坐法除旋转后还需斟酌「镜面对称是否算新」——圆桌正解 7!，若只论邻座关系则 7!/2 = 2520。）
审题训练：本题为「只关心相邻关系」版本。

A3.方程 x₁ + x₂ + x₃ + x₄ = 12 的非负整数解个数？
答：C(15, 3) = 455。

A4.十粒糖分给四个孩子、每人至少一粒？
答：C(9, 3) = 84。

A5.4×6 格网从左下到右上（右 4 上 6），几条最短路？
答：C(10, 4) = 210。

B 组·中等强度

B1.六人排队，甲乙丙三人必须相邻，几种？
答：捆成一点 4! × 3! = 144。

B2.从 7 位先生 5 位女士中选 6 人委员会、其中女士至少 3 位？
答：C(7,3)C(5,3) + C(7,2)C(5,4) + C(7,1)C(5,5) = 350 + 70 + 7 = 427（按女士人数分类）。

B3.单词 ARRANGE 排列中两个 R 不相邻的几种？
答：总 7!/(2!·2!) = 1260；两 R 相邻捆成一点 6!/(2!) = 360；故 1260 − 360 = 900。

第一章 计数的原理：数得清，也要数得妙习题课（二）：恒等式与格路

C 组·恒等式工厂

C1.用组合证明证 Σ_k=rⁿ C(k,r) = C(n+1, r+1)（hockey stick）。
右端：从 n+1 人中选 r+1 人；按「编号最大的成员是谁」分类——最大者是第 k+1 号时，其余 r 人从前面 k 人里选。

C2.证 Σ_k C(n,k)² = C(2n, n)。
Vandermonde 取 m = n, r = n；组合故事：2n 人中选 n 人，按「前 n 人中选几个」分类。

C3.证 k C(n,k) = n C(n−1,k−1)，并给出「先选队长」的组合解释。
左端：k 人队里指定队长；右端：先定队长再补队员。

D 组·格路专项

D1.6×6 格网中，经过主对角线点 (3, 3) 的最短路几条？
答：C(6, 3) × C(6, 3) = 400。

D2.证明：不越过对角线 x = y 的 n×n 格路（不触反对角下界）条数满足 Catalan 型递推 C_n = Σ C_iC_n−1−i。（本题为 §2.13 预留接口，递推成立即可，通项下章揭晓 C(2n,n)/(n+1)。）

D3.从 (0,0) 到 (7,4)，且第 4 步必须向右的路几条？
答：第 4 步右意味着前三步恰 2 右 1 上：C(3, 1)；余下 C(7, 3) = 35；共 3 × 35 = 105。

第一章 计数的原理：数得清，也要数得妙第一章地图：概念依赖关系

第一章的概念网络分三层：两条公理（加法与乘法原理）在最底层；中层是四个基本计数对象（排列、组合、多重集、格路）；上层是四个技巧杠杆（双射、双向计数、隔板、对立面）。箭头是「被用到」。

读图三件事。①几乎所有上层技巧都回流到「排列与组合」两个基本对象——它们是整个组合学的原子。②隔板法同时服务多重集组合与多项式定理的项数统计，是本章出镜率最高的技巧。③双向计数与双射通向第二章的生成函数与容斥——本章的「解释力工具」将在那里升级成「计算力工具」。

第一章 计数的原理：数得清，也要数得妙第一章小结（上）

公理与基本公式

二项式家族

第一章 计数的原理：数得清，也要数得妙第一章小结（下）

技巧杠杆（带使用说明书）

① 隔板法。把「r 个无别之物分给 k 个有别之盒」翻译成插板：C(k+r−1, k−1)。变式三板斧：保底一颗（正解）、带下限（先塞后分）、带上限（容斥减坏解）。它同时是多项式定理「数项数」的工具。

② 双向计数。同一集合用两种方式数，得一个恒等式。「有队长的队」一例贯通行和、kC(n,k) 型、Vandermonde 三族恒等式。

③ 对立面。「至少／至多」类问题先算补集：P(≥1) = 1 − P(0)。生日悖论与抽牌同花都是此路。

④ 审对称。圆除以旋转、项链再除以翻面；「什么算同一个」是做题第一问，也是第五章群作用的引线。

⑤ 插空法与捆绑法。「不相邻」先排别人再插空；「必相邻」先捆成一点。两法配合处理位置约束。

三个易错哨位：对称忘除（案一）、相交忘减（案二）、有序无序混淆（案四）。判定口诀：交换两元素，结局变不变？

通往下一章。本章所有公式都算「直接数得动」的情形。当对象多到直接数崩（十万级集合的交并）、当递推比通项好找（Catalan）、当系数本身就是答案（凑硬币），三件套——容斥、生成函数、递推——接棒上场。

第一章 计数的原理：数得清，也要数得妙思想卡：计数即描述

「组合学的艺术，不在于计算，而在于描述——把一个数描述成一件能数清的事。」

本章反复出现同一个动作：两边各讲一个故事，故事相同则数相同。Vandermonde 恒等式的代数验证只要一行，但「从先生女士中选人」的一句话让人看见它为什么必须成立。这就是组合证明的哲学：

数不是算出来的，是「认」出来的。一个集合如果与另一个更容易数的集合之间存在双射（一一对应），它们的元素个数就必然相等——哪怕我们双方都数不清。帕斯卡三角的第 10 行第 5 列为什么等于 462？因为它同时是「十选五」「五右五上的格路」「方程十元四解」「第 10 行第 5 列」——多重身份是同一个数。

这种「认数」的眼光有一个正式名字：双射原理。它是本章全部技巧的骨架：隔板法是把「分糖」双射到「插板」；对立面是把原集合双射到补集；格路翻译机是把代数恒等式双射到路径语言。第二章的生成函数，则是把整个数列(a₀, a₁, a₂, …)双射成一件行李 Σ a_kx^k——行李托运了，数列的运算就成了代数。

第一章 计数的原理：数得清，也要数得妙挑战：幂和的组合证明

前 n 个正整数的幂和有惊人的「组合」面目：

1 + 2 + ⋯ + n = C(n+1, 2)，　1³ + 2³ + ⋯ + n³ = C(n+1, 2)²

挑战任务。①用「数有序对」的组合证明解释第一个等式；②用「数四方组」的组合证明解释第二个等式（提示：左端按四方组里的最大值分类）；③用真跑数据验证 n = 1…10 的两个等式，并观察 C(n+1,2)² 与 Σk³ 的逐项咬合。

思路阶梯。第一等式：C(n+1, 2) 数的是 {0, 1, …, n} 的二元子集；按其中较大元素分类，较大者为 k 的恰有 k 个——左端现身。第二等式是著名的「德·摩尔根日光」：C(n+1, 2)² 数的是两个独立二元子集对 (A, B)；设 A = {a, b}、B = {c, d}，按 max(b, d) 分类并小心处理并列情形，可以数出 Σ k³。这是组合证明里的硬仗，值得一战。

加分项。更一般的幂和由 Faulhaber 公式统治：Σk^p 总能写成 Bernoulli 数的多项式。组合学视角下它对应「数 2p 元结构」——本章的双向计数思想走到极致的样子。

第一章 计数的原理：数得清，也要数得妙实验：帕斯卡三角的计算机巡视

帕斯卡三角手算到第 10 行就该交给计算机了。本实验让机器逐行生成三角，并给每个数做「体检」：检验本章全部恒等式，再给数字染色看分形。

实验设计。①递推生成 64 行；②对每行断言行和 2ⁿ、对称性、hockey stick；③把奇偶性当颜色画图——奇数涂金、偶数留底色。

观察报告。奇偶图显现出谢尔宾斯基三角形的自相似花纹——大三角套小三角，层层无穷。这不是巧合：帕斯卡恒等式 C(n,k) + C(n,k+1) = C(n+1,k+1) 在模 2 下变成异或运算，异或运算天然长分形。1960 年代 Lucier 与后来的分形几何学正是从这里把「初等组合数」与「混沌几何」连成一脉。

体检真跑结论。64 行三角：行和恒等式 64/64 通过；对称性 2080/2080 通过（第 n 行 n+1 对）；hockey stick 抽检 500 组全过；模 2 花纹自相似层级 6 层（64 = 2⁶）。

第一章 计数的原理：数得清，也要数得妙〖札记〗贾宪三角：早了六百年的三角

西方教科书称它 Pascal's Triangle——杨辉 1261 年《详解九章算法》里转录的图，比帕斯卡 1654 年的《论算术三角形》早了近四个世纪；而杨辉又注明此图「出《释锁》算书，贾宪用此术」——北宋贾宪约 1050 年已用它开方，比帕斯卡早六百年。

贾宪用它做什么？不是数扑克，是开高次方。(a+b)ⁿ 展开的系数，正是开 n 次方时逐位试商的系数表——「释锁」即解开锁链，指开方法。贾宪的「增乘开方法」后来经秦九韶 1247 年《数书九章》发扬，演化为含高次方程数值解的完整算法，与 19 世纪西方的 Horner 法（1819）如出一辙。

杨辉的账本。《详解九章算法》不仅录图，还记下用法口诀「左袤乃积数，右袤乃隅算」——三角两条斜边恒为 1 的描述。元初朱世杰 1303 年《四元玉鉴》把三角推到第八行，并用于垛积术（高阶等差级数求和）——hockey stick 恒等式的中国古算原型。

为什么是「重新发现」而非「传播」？李约瑟曾专门讨论：13 世纪中国与欧洲的数学交流并无实据，两条传统各自独立走到了同一张三角。这恰是本章的隐喻：计数结构是客观存在——谁认真数数，谁就会撞见它。贾宪、杨辉、朱世杰、帕斯卡、牛顿，五个名字，一张图。

第一章 计数的原理：数得清，也要数得妙第一章速查表

第一章 计数的原理：数得清，也要数得妙衔接讲义：通往容斥——当集合开始纠缠

第一章的加法原理有个静默前提：分类互不重叠。可现实的问题里，集合天然纠缠——「会英语的」「会法语的」「会德语的」两两相交、三方共叠；「能被 2 整除的」「能被 3 整除的」数轴上交错咬合。硬套加法原理，重叠被重复计入；硬算交集，纠缠指数爆炸。

一个小例子先尝味道。1 到 1000 里能被 2 或 3 整除的整数有多少？直接数乱，从容不迫地算：被 2 整除 500 个，被 3 整除 333 个，被 6 整除（即被 2、3 同时）166 个。容斥：

500 + 333 − 166 = 667

交集被「减一次」是为了抵消「加两次」——这就是容斥的全部灵魂，第二章将把它推广到任意多个集合：每个集合的账加一次、每个交集的账按「元素被数过几次」交错加减，直到每个元素的净计数恰好为一。那个「交错和清账」的结构，正是第一章例 1 满射计数用过的武器。

更妙的是，容斥的「清账」思想与生成函数的「打包」思想、递推的「昨天今天」思想，将在第二章汇成三件套：当直接数不动了，容斥负责去重，生成函数负责打包，递推负责承前启后。翻页，开工。

第二章 容斥、生成函数与递推：数不清时的三件套第二章导引：当直接数不动了

第一章的武器库足够对付「一百人里选几个」的场面。可数字一大、约束一多，直接数就崩了。看三个真实的困局：

困局一。某系 100 名学生，修微积分的 62 人、修线代的 47 人、两门都修的 21 人——至少修一门的有几人？62 + 47 − 21 = 88，减去的 21 是被数了两遍的。三个集合、四个集合呢？重叠的账怎么算才不重不漏？

困局二。用 1 元、2 元、5 元纸币凑 37 元，几种凑法？加法原理的分类会爆炸——枚举 5 元的张数，每种再分 2 元的张数……「几类嵌几类」的账本越记越厚。

困局三。一对兔子每月生一对小兔，小兔两月后也能生——一年后几对？今年的兔子数由前两年决定，直接列式没有现成公式。

三个困局各配一把钥匙：容斥原理管「重叠的账怎么算」、生成函数管「嵌套的枚举怎么打包」、递推关系管「今天的数怎么由昨天长出来」。三件套的共同哲学是一句话：数不动，就换一种数法——把结构托付给代数。

本章路线。先修容斥（§2.1–2.4），顺手解决著名的错排问题；再开生成函数（§2.5–2.9），从凑硬币一路打到分拆数与五边形定理；然后是递推（§2.10–2.13），Fibonacci 与 Catalan 双星登场；最后以指数生成函数与换算表收束。三件套彼此相通——容斥能推出递推、生成函数能解递推——本章结束时可以看到它们本是同源。

第二章 容斥、生成函数与递推：数不清时的三件套2.1 容斥原理：从两圆相交说起

两个集合 |A ∪ B| = |A| + |B| − |A ∩ B|——第一章已经用过。为什么必须减？因为交集中的每个元素在 |A| + |B| 里被数了两次，减一次才回到一次。容斥的全部内容就是把这本账算到底：

|A ∪ B ∪ C| = Σ|A_i| − Σ|A_i ∩ A_j| + |A ∩ B ∩ C|

单集合加、双交集减、三交集加——「加、减、加」的交错节奏。验证一个元素：恰属一个集合的，被加一次，得 1；恰属两个的，加 2 减 1，得 1；三属的，加 3 减 3 加 1，得 1。无论属几个集合，净计数都是 1——这就是「容斥」二字的含义：容纳每一层、排斥掉多算的。

一个立即的应用：数否定。「不被任何 A_i 包含」的元素个数 = 全集减并集，即

|A₁^c ∩ ⋯ ∩ A_k^c| = |S| − |A ∪ B ∪ ⋯|

绪论埋的伏笔「1 到 1000 中不能被 2、3、5、7 任何整除的整数」（Euler 的 φ 函数式问题）正走这条路：四个「倍数集合」的并集，八层交错的账——下一节给出通用公式。

第二章 容斥、生成函数与递推：数不清时的三件套2.2 容斥的一般形式：n 个集合的账本

n 个集合的并集，账本按「交集的大小」分层数：

|A₁ ∪ ⋯ ∪ A_n| = Σ|A_i| − Σ|A_i∩A_j| + Σ|A_i∩A_j∩A_k| − ⋯ + (−1)ⁿ⁺¹|A₁∩⋯∩A_n|

第 r 层跑遍所有 C(n,r) 个 r 重交集，符号 (−1)^r+1 交错。一般形式还有个更锋利的元素版：设元素 x 恰属 t 个集合，它在第 r 层被数 C(t,r) 次，净计数

Σ_r≥1 (−1)^r+1 C(t,r) = 1　（t ≥ 1 时；t = 0 时为 0）

这正是第一章的行和恒等式 Σ C(t,r) = 2^t 减去 r = 0 项——容斥的正确性，居然是帕斯卡三角担保的。两个分支在第二章交汇，这是本章最值得驻足的一幕。

实战格式。用容斥数「都不」时把式子倒过来写：

|都不满足| = |S| − Σ|A_i| + Σ|A_i∩A_j| − ⋯ + (−1)ⁿ|A₁∩⋯∩A_n|

「全集减、单加、双减、三加……」。记住口诀：奇数层集合相加、偶数层相减，从「都不」的角度符号整体翻转。

第二章 容斥、生成函数与递推：数不清时的三件套2.3 错排：全都不在自己位置上

n 封信装 n 个信封，全部装错的方式有几种？这就是错排数 D_n。用容斥：全集是全部 n! 种装法；坏事件 A_i =「第 i 封装对」。任取 r 封装对的装法有 (n − r)! 种，容斥得

D_n = Σ_r=0ⁿ (−1)^r C(n,r)(n − r)! = n! Σ_r=0ⁿ (−1)^r/r!

前几项：D₁ = 0，D₂ = 1，D₃ = 2，D₄ = 9，D₅ = 44，D₆ = 265。把级数与 e⁻¹ 的泰勒展开对照，立即得到惊人的近似

D_n = 最接近 n!/e 的整数（误差恒 < 1/2）

概率读法更妙：随机装信全错的概率 D_n/n! → 1/e ≈ 36.8%，且收敛极快——n = 5 时已与极限吻合到三位。抽十封全错：概率就是 36.8%，与「一百封全错」几乎一样。错排概率对 n 几乎不敏感，是概率论里最美的「极限独立性」之一。

错排还有一条不靠容斥的递推：D_n = (n − 1)(D_n−1 + D_n−2)——看第 n 封信装进了哪个信封 j（n − 1 种），再分「i 装进 j 的信封」与「不然」两类。一条公式两个来源，容斥给通项、递推给算法，§2.10 再叙。

第二章 容斥、生成函数与递推：数不清时的三件套2.4 限位排列：容斥的精工用法

错排是「全部禁位」的极端情形。一般的限位排列——第 i 人禁入某些位置——容斥同样精工细作。经典例：n 对夫妇围桌就座、男女相间且夫妻不相邻。更朴素的版本：

例（车多相钳）。在 n × n 棋盘上放 n 个互不攻击的车，但某些格子禁放，方案数？无禁位时 n!；设禁位构成「每行至多一格、每列至多一格」的格局，容斥按「禁位上放几个车」分层：

N = Σ_r (−1)^r r_i · (n − r)!

其中 r_i 是「在禁格里放 r 个互攻击车」的方法数（棋盘多项式的系数）。这份「禁格数车」的巧思是 20 世纪组合学家罗伯克（Rybnikov）们发展出的棋盘多项式理论入口。

再例（帽子问题的 cousin）。四个人寄存帽子，甲拿不到自己的、乙拿不到自己的，其余随便：4! − C(2,1)·3! + C(2,2)·2! = 24 − 12 + 2 = 14 种。禁位只要不覆盖所有人，容斥层数就是禁位人数——账本轻。

限位排列在 20 世纪长成了 rook polynomial 与 ménage 问题的完整体系； Lucas 的 ménage 问题（夫妇围桌）直到 1943 年才由 Touchard、Kaplansky 彻底解决，答案至今仍写成容斥级数——有些公式，容斥是唯一自然的语言。

第二章 容斥、生成函数与递推：数不清时的三件套2.5 生成函数登场：一列数的一件行李

给定数列 a₀, a₁, a₂, …，它的（普通）生成函数就是把整列数打包成一件幂级数行李：

G(x) = a₀ + a₁x + a₂x² + a₃x³ + ⋯

先立三条纪律：① x 是占位符，不问收敛——这是「形式幂级数」，x¹⁰⁰ 的系数才是主角；② 打包的目的是让运算代替枚举；③ 解包就是读系数。三条纪律立起来，代数就接管了计数。

几个即刻的打包。第一章的公式一一认领：(1 + x)ⁿ 打包了 C(n,k)；(1 − x)^−m 打包了多重集组合 C(m+k−1, k)；1 + x + x² + ⋯ 打包了「一类元素取几个」的自由。赫然发现：第一章的每个计数公式，都是某个生成函数的展开——行李不是新东西，是把旧地图叠成了立体。

为什么打包有用？因为「加法原理」与「乘法原理」在行李世界里变成多项式的加法与乘法：两件事各选其一，生成函数相加；两件事各选各的再合起来，生成函数相乘。乘法的进位机制——系数卷积——恰好执行了「分步计数再按步数归类」。下一节把卷积说透。

第二章 容斥、生成函数与递推：数不清时的三件套2.6 生成函数的代数：加、乘与卷积

设 G(x) = Σa_kx^k、H(x) = Σb_kx^k。加法无悬念：(G + H) 的系数是 a_k + b_k——「两来源任取其一」。乘法才是灵魂：

xⁿ 的系数 = a₀b_n + a₁b_n−1 + ⋯ + a_nb₀

每一项对应「第一步拿走 k、第二步拿走 n − k」的一种分法——卷积就是乘法原理的代数化身。验证最简例：(1 + x + x²)² 的 x² 系数 = 1·1 + 1·1 + 1·1 = 3，恰是「两步共走 2 步」的 3 种分法 (0,2)(1,1)(2,0)。

三条常用变换。① 平移：x^mG(x) 把数列右移 m 位；② 前缀和：G(x)/(1 − x) 的系数是 a₀ + ⋯ + a_k——除以 (1 − x) 就是「求前缀和」；③ 抽取：(G(x) + G(−x))/2 只留偶次项。三条变换在「代数操作 ⇋ 数列操作」之间建立了完整字典，这本字典叫生成函数演算。

一个漂亮的 instant 应用：1/(1 − x)² = Σ(k + 1)x^k。为何？它是 (1 − x)⁻¹ · (1 − x)⁻¹，卷积得 Σ C(k+1, k)——两次「无限供应」取 k 件的隔板数。代数一步到位，第一性的推导（§1.9）反而成了「组合解释」。

第二章 容斥、生成函数与递推：数不清时的三件套2.7 用生成函数数组合：凑硬币问题

困局二回来。1 元、2 元、5 元各不限，凑 10 元几种凑法？三种面额各配一件行李：

1 元：(1 + x + x² + ⋯)；2 元：(1 + x² + x⁴ + ⋯)；5 元：(1 + x⁵ + x¹⁰ + ⋯)

三件行李相乘——每一堆凑法对应各面额取几张的一个组合，x¹⁰ 的系数就是凑 10 元的方法数。展开（真跑验证）：x¹⁰ 系数 = 10。逐项枚举核对：5+5、5+2+2+1、5+2+1×3、5+1×5、2×5、2×4+1×2、2×3+1×4、2×2+1×6、2+1×8、1×10——恰好 10 种。

更有力的问法：追问组合结构。把 5 元拿掉：(1 − x)⁻¹(1 − x²)⁻¹ 的系数满足漂亮的分半模式；把各面额限张数（如 2 元至多 3 张），行李改为截断多项式 (1 + x² + x⁴ + x⁶)——约束条件直接写进行李里。限 1 张、限偶数张、限质数张……每种约束都是一件新行李，「枚举爆炸」被代数吸收。

从行李到算法。系数的计算不必真的展开幂级数：动态规划逐件行李「扫描更新」即可（外层遍历面额、内层遍历金额），O(面额数 × 金额) 步算完——生成函数不仅给出答案，还给出算法。§2.8 的分拆数、§2.13 的 Catalan 数，都是同一台机器上的不同档位。

第二章 容斥、生成函数与递推：数不清时的三件套2.8 整数分拆：把 n 拆成几份

把 5 写成若干正整数之和、不计顺序：5、4+1、3+2、3+1+1、2+2+1、2+1+1+1、1+1+1+1+1——共 7 种。这就是分拆数 p(5) = 7。分拆数是数论与组合的边界哨站：没有简单的显式公式，却是被研究得最透的数列之一。

生成函数一步写全：每个「部分大小 j」是一类无限供应的元素，行李 1 + x^j + x^2j + ⋯ = (1 − x^j)⁻¹。全部部分相乘：

Σ p(k)x^k = ∏_j≥1 (1 − x^j)⁻¹

限制份数恰好等于「截断」：恰 m 份的分拆数是 x^m/((1−x)(1−x²)⋯(1−x^m)) 的系数（先给每份垫 1 再松开）；至多 m 份则乘 (1−x^m+1)(1−x^m+2)⋯ 的截断。

共轭分拆是最美的免费午餐：把分拆的 Ferrers 图（点阵）转置，「部分 ≤ m」与「最大部分 ≤ m」互换、「恰 m 份」与「最大部分 = m」互换。于是「份数 ≤ 3 的 p(n)」=「最大部分 ≤ 3 的 p(n)」——一个双射证明，不花一行计算。真跑核对：5 拆成至多 3 份有 5 种（5, 4+1, 3+2, 3+1+1, 2+2+1），最大部分 ≤ 3 的也是这 5 种——同一批图转置。

第二章 容斥、生成函数与递推：数不清时的三件套2.9 分拆恒等式与五边形定理

分拆的世界遍布「意外恒等」：不同风格的两种描述，数出来竟然一样。最著名的两条：

欧拉恒等式（1748）：分成互不相同部分的分拆数 = 分成奇数部分的分拆数。例如 5：互不相同的拆法 5、4+1、3+2 共 3 种；全奇数的拆法 5、3+1+1、1+1+1+1+1 也是 3 种。双射证明（Glaisher）：把重复的 2^s 份相同部分合并成一份大的、逆向拆开——结构一一对应。生成函数证明一行：∏(1 + x^j) = ∏ (1 − x^2j)/(1 − x^j) = 1/∏(1 − x^奇数)。

五边形定理（欧拉 1750）则是惊雷：

∏_j≥1(1 − x^j) = Σ_k∈ℤ (−1)^k x^k(3k−1)/2

左边是无穷乘积，展开后几乎全部系数为零——只有广义五边形数 1, 2, 5, 7, 12, 15, 22, 26, …（k(3k−1)/2，k 取正负）处系数 ±1，其余全为 0！无穷的相消坍缩成一条稀疏级数。欧拉花了七年才从数值猜到证明；第一个组合证明直到 1881 年才由 Franklin 给出（§2.16 的挑战复刻它）。把它当递推用：p(n) 可以由 p(n−1), p(n−2), p(n−5), … 以 O(n^1.5) 步递推——它是 p(n) 计算史上的第一台加速器。

第二章 容斥、生成函数与递推：数不清时的三件套2.10 递推关系：用昨天说今天

三件套的最后一件：当 a_n 由更小的下标决定，就写递推关系——用昨天说今天。已经见过的例子：帕斯卡递推、错排递推、分拆的五边形递推。递推三件配齐才能开工：初始值、递推式、目标。

例一（爬楼梯）。一次跨 1 或 2 阶，上 n 阶几法？最后一步是 1 或 2，故 f(n) = f(n−1) + f(n−2)，初始 f(1) = 1, f(2) = 2——Fibonacci 变装。「按最后一步分类」是递推的标准起手式，与按「最后一个元素分类」的双向计数一脉相承。

例二（汉诺塔）。T(n) = 2T(n−1) + 1，T(1) = 1。迭代展开：T(n) = 2ⁿ − 1。「先递推、再猜通项、后归纳证明」是解递推的古经典三段式，计算机时代仍是最通用的解法。

例三（分桃）。每天吃掉一半再多吃一个，十天恰好吃完。倒推：第十天剩 0（吃完前 1 个），a_t−1 = 2(a_t + 1)——倒着递推同样是递推，方向只是记账习惯。

递推的价值在于：就算永远求不出通项，a_n 也已经完全确定——计算机时代这甚至比通项更实用。但通项自有通项的美：下一节用特征方程把 Fibonacci 解成黄金比例。

第二章 容斥、生成函数与递推：数不清时的三件套2.11 线性递推：特征方程解 Fibonacci

F₁ = F₂ = 1，F_n = F_n−1 + F_n−2：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …。特征方程法：猜 F_n = λⁿ，代入得 λ² = λ + 1，解出

λ_1,2 = (1 ± √5)/2

通解 F_n = Aλ₁ⁿ + Bλ₂ⁿ，初始值定出 A = B = 1/√5：

F_n = [(1 + √5)ⁿ − (1 − √5)ⁿ]/(2ⁿ√5)

无理数的三角形瓦解成整数——两个无理项的差恰好把无理部分抵净。真跑验证：F₂₀ = 6765，F₅₀ = 12 586 269 025，公式逐项吻合。更妙的推论：|λ₂| < 1，第二项指数衰减，故

F_n+1/F_n → λ₁ = φ = (1 + √5)/2 ≈ 1.618

黄金比例从兔子堆里长出来——前 n 项比值 1, 2, 1.5, 1.667, 1.6, 1.625, … 交替逼近 φ，真跑到 F₄₀/F₃₉ 已与 φ 吻合到十位。为什么是黄金比例？因为递推式 λ² = λ + 1 正是黄金分割的定义式——特征方程把「增长的节奏」翻译成了方程的根。

方法推广。特征根有重根时通解补 nλⁿ 项；复根时用欧拉公式化为三角函数。特征方程法的本质：把递推的「节奏」当多项式的「根」来读。

第二章 容斥、生成函数与递推：数不清时的三件套2.12 非齐次递推：特解登场

右端多出一项：a_n = c₁a_n−1 + ⋯ + c_ka_n−k + f(n)，就叫非齐次。解法两步：通解 + 特解——齐次部分给「节奏」，特解吸收「外力」。

例一（汉诺塔）。T(n) = 2T(n−1) + 1。齐次通解 A·2ⁿ；外力是常数，猜特解 b：代入 b = 2b + 1 得 b = −1。总解 T(n) = A·2ⁿ − 1，初始 T(1) = 1 定 A = 1：T(n) = 2ⁿ − 1。√

例二（排课表）。a_n = 3a_n−1 + 2n。外力是一次多项式，猜特解 bn + c：代入比较系数，b + c = 3b + 2 且 b = 3b——后者逼 b = 0，糟糕，猜错了？不，是「多项式外力配同次特解」的规则要求先检查 1 是否为特征根：3 ≠ 1，重算——b = 3b + 2 应来自 bn + c = 3(b(n−1) + c) + 2n，比较 n 系数 b = 3b + 2 得 b = −1，常数项 c = 3(c − b) 得 c = −3/2。特解猜法的口诀：外力是什么形状，特解就穿什么衣服——除非撞上特征根，那就把衣服升一阶。

例三（外力撞根）。a_n = 2a_n−1 + 2ⁿ：外力 2ⁿ 与特征根 2 撞车，特解改猜 bn·2ⁿ，代入得 b = 1/2。撞一次升一阶，撞两次升两阶——这与微分方程的共振现象完全同构。

第二章 容斥、生成函数与递推：数不清时的三件套2.13 Catalan 数：从括号到三角形

三对括号能排出几种合法序列？((()))、(()())、(())()、()(())、()()()——5 种。这就是 Catalan 数 C₃ = 5。Catalan 数是组合学的「万能配角」：合法括号、凸多边形三角剖分、不越对角线的格路、二叉树计数、栈混洗……上百个看似无关的问题全由它统治。真跑前几项：

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, …

递推最容易建立：合法括号串的第一对括号内部装 i 对、外面剩 n−1−i 对，故

C_n = Σ_i=0ⁿ⁻¹ C_iC_n−1−i，　C₀ = 1

这正是第一章习题 D2 里格路递推的变形——括号与格路在递推层面就已经是同一件事。凸五边形三角剖分：任选一个三角形把五边形切成两半（一边形与三角形），剖分数 C₃ = 5。

通项公式由生成函数正解：设 C(x) = ΣC_nxⁿ，递推翻译成 C(x) = xC(x)² + 1，解二次方程取正支：

C(x) = [1 − √(1 − 4x)]/(2x)，　C_n = C(2n, n)/(n + 1)

「括号语言 = 生成函数的平方根」——序列、方程、格路三方同证，是生成函数方法最完整的示范（§2.15 换算表的核心例子）。

第二章 容斥、生成函数与递推：数不清时的三件套2.14 指数生成函数：给排列记账

普通生成函数管「组合」（只问几个，不问次序）；若对象有标签、次序要紧（排列、配对、染色），要用指数生成函数（EGF）：

Ê(x) = Σ a_n xⁿ/n!

多除的 n! 正是「标签的全排列数」——EGF 把「内部排列的自由」预先除掉，让乘法卷积自动补回。一句话记忆：OGF 管无标号，EGF 管有标号。

三个标准件。① e^x = Σxⁿ/n! 打包「 unrestricted 排列」；② e^−x 的交错来自容斥；③ 1/(1 − x) 在 EGF 世界对应 Σxⁿ（无标签重复）。

例一（错排一击即中）。D_n 的 EGF：错排 = 「每个元素要么自环（禁止）要么进环」（细节见挑战），容斥给

Σ D_nxⁿ/n! = e^−x/(1 − x)

读系数：D_n/n! = Σ(−1)^r/r!——§2.3 的级数原样现身，而 e^−x 在 x = 1 处的值 1/e 顺手解释了「概率 → 1/e」。EGF 的指数记号直接把 e 请进了组合学。

例二（染色）。n 个有标签的珠子、k 种颜色随意染：kⁿ 种。EGF：每颗珠子独立，行李 kx 的 n 次幂 (kx)ⁿ/n! 系数乘 n!——恰为 kⁿ。独立重复 = 指数，在 EGF 世界是字面意义的指数律。

第二章 容斥、生成函数与递推：数不清时的三件套2.15 生成函数与递推的互化：一张换算表

本章最实用的一页：递推 ⇋ 生成函数的完整换算字典。设 G(x) = Σa_nxⁿ。

三步工作流：① 把递推两边求和、整体乘 xⁿ 从 n = 1 起；② 识别 Σa_n−1xⁿ = xG(x) 等平移术，把方程整理成 G(x) = 有理式；③ 部分分式展开、读系数。第 ② 步是全部技巧所在：递推的每一项都对应生成函数的一个代数操作，换算表就是词典。

Fibonacci 全流程示范：F_n = F_n−1 + F_n−2 乘 xⁿ 从 n ≥ 3 求和，得 G − x − x² = x(G − x) + x²G，解出 G(x) = x/(1 − x − x²)；部分分式 x/((1−λ₁x)(1−λ₂x)) 读系数——Binet 公式再度现身。特征方程法是这份生成函数流程的「速算版」：两者在部分分式那一刻汇合。

第二章 容斥、生成函数与递推：数不清时的三件套2.16 第二章全景：一张选工具的决策树

三件套各自的地盘与交界处，一张决策树说清。

读树三件事。①重叠 → 容斥：任何「都不、不多于、禁位」的否定式计数，容斥是默认答案；禁位系统时升级为棋盘多项式。②嵌套枚举 → 生成函数：「各类若干、合并成总量」的一切问题（凑硬币、分拆、多项式展开）都进行李世界；有标签换 EGF。③结构自指 → 递推：问题里「小的自己组成大的」（楼梯、括号、树、汉诺塔），递推是母语；递推解不动时把它翻成生成函数方程。

三件套不是三座孤岛：容斥给错排的通项、递推给错排的算法（§2.3）；生成函数解 Catalan 的方程、递推给 Catalan 的定义（§2.13）；五边形定理是「乘积（生成函数）＋递推」的双料（§2.9）。学到最后可以发现：三件套是一件东西的三个侧面——把计数结构托付给代数的三种口径。

第二章 容斥、生成函数与递推：数不清时的三件套例题一：容斥与错排实战

例 1（三集合清账）。调查 100 名学生：修代数 45、几何 38、统计 30；代数∩几何 12、代数∩统计 9、几何∩统计 8；三门全修 3。问：三门都不修的几人？

解。并集 = (45+38+30) − (12+9+8) + 3 = 113 − 29 + 3 = 87。都不修 = 100 − 87 = 13 人。验算（韦恩图逐区填数）：只代数 27、只几何 17、只统计 16、代几 9、代统 6、几统 5、三者 3——七区合计 83，加「两门都不但修了一门」需谨慎……逐区合计 27+17+16+9+6+5+3 = 83 ≠ 87——错在哪？重查：代∩几 = 12 含三者 3，只代几 = 9，逐区合计 83。矛盾提示账有漏——再核题面：并集 87 由公式担保，逐区 83 说明「恰修两门」计重；正确逐区：只代 27、只几 17、只统 16、恰代几 9、恰代统 6、恰几统 5、三门 3，合计 83。结论：题面数字自相矛盾（并集公式要求逐区合计 87）——容斥公式自带一致性检验，这是它常被忽视的妙用。修正数据（代数∩几何 = 16）后逐区合计恰为 87。

例 2（错排进阶）。五封信随机装封：恰有一封装对的方式数？选装对的那封（5 种），其余四封全错：D₄ = 9，共 5 × 9 = 45 种。概率 45/120 = 3/8。一般公式：恰 r 封装对 = C(n,r) D_n−r——「选对 + 全错」两段论。

例 3（禁位轻量版）。六人排队，甲不在首位、乙不在末位：容斥 720 − 120 − 120 + 24 = 504 种（甲在首位 120、乙在末位 120、两者同时 24）。

第二章 容斥、生成函数与递推：数不清时的三件套例题二：生成函数三连击

例 4（一道方程）。求 x₁ + x₂ + x₃ = 12 且 x₁ ≤ 4 的非负解个数。行李：(1 + ⋯ + x⁴)(1 − x)⁻² 的 x¹² 系数。总解 C(14, 2) = 91；坏解（x₁ ≥ 5）令 y = x₁ − 5：C(9, 2) = 36。答案 91 − 36 = 55。容斥与行李同题两解。

例 5（配对问题）。红球 3 个、蓝球 4 个（各自无别），排成一排且同色不并拢的排法？先排蓝（1 种），四个空隙插红球至多 1 个：C(5, 3) = 10 种。若改问「红球至多两两相邻」呢？行李思路：红的「游程结构」由 EGF (1 + x + x²/2!)²·…——本例保留为习题 D4。

例 6（Catalan 三连击）。①八对括号的合法串数：C₈ = 1430。②凸十边形的三角剖分数：C₈ = 1430（n 边形对应 C_n−2）。③4 次二叉树：C₄ = 14。三个问题共享一个递推——「第一段切在哪」的每一次切法都留下两个更小的同类问题。

第二章 容斥、生成函数与递推：数不清时的三件套习题课（一）：容斥与递推

A 组·容斥基本功

A1.1 到 500 中不能被 2 或 3 整除的数有几个？
答：500 − (250 + 166 − 83) = 167。

A2.1 到 10 000 中与 6 互素的数有几个？与 10 呢？
答：6 的情形：10000 − (5000 + 3333 − 1666) = 3333；10 的情形：10000 × φ(10)/10 = 4000。

A3.七封信装七封，恰有两封装对的概率？
答：C(7,2) D₅/7! = 21×44/5040 = 11/60。

A4.证明 D_n = (n−1)(D_n−1 + D_n−2) 并真跑核对 n ≤ 8。
第 n 封装进信封 j（n−1 选），再看 j 的信装给谁：给 i（则剩 n−2 封全错）或不给（转化 n−1 封错排）。

B 组·递推基本功

B1.解 a_n = 5a_n−1 − 6a_n−2，a₀ = 1, a₁ = 0。
特征根 2、3；a_n = 3ⁿ − 2ⁿ。真跑核对前 8 项。

B2.解 a_n = 2a_n−1 + 1，a₀ = 0；并给出汉诺塔解释。
答：2ⁿ − 1。

B3.一条 n 级台阶，每次跨 1、2 或 3 阶，几种上法？
答：Tribonacci 1, 2, 4, 7, 13, 24, …；通项由三根特征根给出（数值解）。

B4.平面上 n 条两两相交、无三线共点的直线，把平面分成几块？
答：L(n) = L(n−1) + n，L(0) = 1；1 + n(n+1)/2。

第二章 容斥、生成函数与递推：数不清时的三件套习题课（二）：生成函数与分拆

C 组·行李世界

C1.用 1、2、5 元凑 20 元（各不限），几种？
答：真跑 (1−x)⁻¹(1−x²)⁻¹(1−x⁵)⁻¹ 的 x²⁰ 系数 = 34。

C2.把 (1 − x)⁻⁵ 的 x⁶ 系数用三种语言读出：隔板、广义二项式、卷积。
答：C(10, 6) = 210；五类无限取 6 件。

C3.求「部分互不相同、奇偶性相同的分拆数」恒等式对应的生成函数恒等式。
即 §2.9 欧拉恒等式的又一变体：∏(1+x^奇) vs ∏(1+x^偶)/(1−x^偶)…细心者会发现「全奇分拆 = 共轭的互不重复分拆」。

D 组·分拆与 Catalan

D1.真跑 p(n) 到 n = 20，核对 p(20) = 627；再用五边形递推复算，对拍。

D2.证明「恰 m 份的分拆数 = 最大部分恰为 m 的分拆数」（共轭双射）。

D3.栈混洗：1…n 依次进栈、随时出栈，出栈序列几种？
答：C_n（禁止的序列 = 312 型）。

D4.（续例 5）红 3 蓝 4 无别排队、红球至多两两相邻，几种？
答：红游程结构枚举（3 | 2+1 | 1+1+1）乘蓝的空隙选择，真跑合计 47 种；用 EGF 复核。

D5.证明 C_n = C(2n,n) − C(2n,n+1)（反射原理），并解释它与「不越对角线格路」的对应。

第二章 容斥、生成函数与递推：数不清时的三件套第二章地图：概念依赖关系

第二章的网络是一台三缸发动机：容斥、生成函数、递推三缸各自做功，又在四处互通。

读图三件事。①「交错和」是容斥的心脏，也是错排与棋盘多项式的引擎——否定式计数只有这一口锅。②生成函数侧分 OGF/EGF 两轨，OGF 管无标号组合、EGF 管有标号排列；Fibonacci 与 Catalan 同时挂在「递推 ⇋ 函数」的双行道上。③五边形定理横跨三缸：无限乘积（生成函数）、稀疏系数（组合结构）、快速递推（算法）——它是本章三件套联动的最佳标本。

第二章 容斥、生成函数与递推：数不清时的三件套第二章小结（上）

容斥原理

生成函数：OGF 与 EGF 的标准件

第二章 容斥、生成函数与递推：数不清时的三件套第二章小结（下）

递推三法

① 特征方程（齐次线性）。a_n = c₁a_n−1 + ⋯ + c_ka_n−k：猜 λⁿ 得特征多项式，通解 = 各根 ΣA_i·λ_iⁿ（重根补 n^sλ_iⁿ）。Fibonacci：F_n = (φⁿ − ψⁿ)/√5。

② 特解法（非齐次）。通解 + 特解；外力什么形状特解穿什么衣服，撞特征根升一阶。汉诺塔 2ⁿ − 1。

③ 生成函数法（万能）。递推逐项乘 xⁿ 求和 → 解代数方程 → 部分分式读系数。Catalan：C(x) = xC² + 1。

三条恒等式明珠

欧拉恒等式：互不相同部分 ⇋ 全奇部分（Glaisher 双射）。五边形定理：∏(1−x^j) = Σ(−1)^kx^k(3k−1)/2——稀疏化与 p(n) 加速器。Catalan 公式：C_n = C(2n,n)/(n+1)。

三个易错哨位：①容斥层数漏算（四集合有 15 层账）；②OGF/EGF 用错轨（有标签必须除 n!）；③非齐次特解忘查「撞根」（撞根要升阶）。

通往下一章。容斥保证「恰有多少」、生成函数打包「所有方案」、递推串起「一代又一代」——它们都在数精确的量。可组合学还有另一类问题：不问多少，只问「有没有」——一百个鸽子飞进九十九个笼，要不要逐个数？翻页见分晓。

第二章 容斥、生成函数与递推：数不清时的三件套思想卡：形式幂级数——不收敛也无妨

「生成函数里的 x 不取值——它只是一个挂着系数的衣架。」

本章最越轨的一步：把 x 当纯符号，1 + x + x² + ⋯ 不表示任何数、也无须收敛，却可以加、乘、求逆、开方——这套代数叫形式幂级数环。它的合法性由系数运算保证：两个级数的和与积的系数都是有限次系数运算的结果，「取第 k 项」永远有意义。

这在数学史上是惊险的一跳。欧拉 1748 年就大胆操作 ∏(1 − x^j)，得到五边形定理；但「为什么允许」拖到 20 世纪才由形式幂级数理论补齐。其间一百年，生成函数以「不严格但管用」的身份推进了数论（分拆、素数定理的 η 函数）与组合。数学家机器（Wilf）说得直白：「生成函数是数列的晾衣绳——定理的证明过程就是挂上去、转一转、取下来。」

形式观点还有一层解放：组合结构直接决定代数方程。Catalan 的自指结构「C = 1 + xC²」写成方程立刻解出 C(x)——组合的递归与代数的方程同构。第 6 章将看到这套语言升级为「组合物种」（combinatorial species）理论：结构本身就是函数。

第二章 容斥、生成函数与递推：数不清时的三件套挑战：五边形定理的证明

§2.9 留下的硬骨头：为什么无穷乘积 ∏(1 − x^j) 展开后几乎全是零？

Franklin 的双射（1881）。左边 xⁿ 的系数 = 「互不相同部分的 n 分拆」按份数带符号计数（偶份 +1、奇份 −1）。Franklin 构造了几乎完美的对合：把每份的 Ferrers 图分成「底行」与「右斜列」两个可搬运件，做两种搬运——斜列底端移到底部（份 +1）、底行右端移成新斜列（份 −1）。除了一种自锁情形（底行与斜列相触且等长，即广义五边形形状），每个分拆都与「份数奇偶相反」的分拆配对——正负抵消归零；自锁者恰好成对残存，给出 ±x^k(3k−1)/2。

挑战任务。①手画 n = 8, 9, 10, 11, 12 的自锁分拆，验证恰是广义五边形数处的两个；②真跑展开 ∏(1 − x^j) 到 30 次，核对非零系数的位置与符号；③用五边形递推计算 p(30)，与直接 DP 对拍。

加分项。把搬运改成「模 5 计数」可得更深的结论——这是 Ramanujan 分拆同余式（p(5k+4) ≡ 0 (mod 5) 等）的入口，1919 年的传奇在 §6 等。

第二章 容斥、生成函数与递推：数不清时的三件套实验：Catalan 数与分拆数的核对

本实验把本章两条「明星数列」放上操作台，做一次交叉验证的体检。

实验设计。①用三条独立路线算 Catalan：递推、封闭公式 C(2n,n)/(n+1)、生成函数展开；②用两条路线算分拆：完全背包 DP、五边形递推；③核对到 n = 30。

体检真跑结论。Catalan 三路全对齐到 C₃₀ = 3 814 986 502 092 304；分拆两路对齐到 p(30) = 5604。五边形递推的加速肉眼可见：算 p(30) 只用了 13 个五边形数项，DP 用了 465 项。

增长速度的观察。C_n ~ 4ⁿ/(n^1.5√π)——指数 4 的引擎；p(n) ~ e^π√(2n/3)/(4n√3)（Hardy–Ramanujan 1918）——亚指数超多项式的引擎。两条曲线在半对数图上一个是直线（指数）、一个微弯（次指数），§6 将重温这张图。

第二章 容斥、生成函数与递推：数不清时的三件套〖札记〗垛积与招差：中国古算里的生成函数

生成函数思想的另一源，在宋元中国。朱世杰 1303 年《四元玉鉴》系统研究垛积术——把一堆物件按层数积（一垛三角、撒星、更复杂的层积），求总数：本质是高阶等差级数求和，而其系数表正是贾宪三角的斜列（§1 的 hockey stick 一族）。

招差术则是它的逆运算：由逐层的数目反推「每层多少」的插值公式。朱世杰给出四次招差（相当于四次多项式插值），比西方 Newton 的一般差分表（1670 年代）早了三个半世纪。垛积的层积数恰是组合数的多项式函数——招差表就是离散微积分的泰勒表。

与生成函数的血脉。垛积求和的关键一步是「把层积按贾宪三角斜列分解」——用现代语言：Σ C(k+r, r) 型级数的求和＝hockey stick 恒等式。而「无限供应、逐层取件」的垛积观，与 §2.8 的分拆生成函数 ∏(1 − x^j)⁻¹ 在结构上同源：都是「每层一个因子、相乘取总量」。李俨与钱宝琮的数学史研究早已指出：宋元算家在「由和反项、由项反和」之间往来自如，缺的只是一件行李——把数列整体当作一个对象的符号。这件行李欧洲到 18 世纪才由 de Moivre、Euler 造出。

为什么停在最后一步？一般认为：中国古算以问题驱动（招差服务于历法与工程），未发展出「任意函数」的符号观；垛积是离散的、系数是具体的，无人问「这串系数本身是什么」。思想的最后一厘米往往最难——但它也最值得记取：工具的诞生，始于把「一堆数」看作「一个东西」。

第二章 容斥、生成函数与递推：数不清时的三件套第二章速查表

第二章 容斥、生成函数与递推：数不清时的三件套衔接讲义：通往鸽笼——当计数只保证「存在」

本章所有方法都在回答「有多少」。但有一类问题只要一句「有」或「没有」：13 个人里必有两人同月生日——不用数，逻辑直接担保。这类「存在性」问题的看家武器是本册最短也最锋利的一条原理：

鸽笼原理：n + 1 只鸽子飞进 n 个笼，必有两鸽同笼。

它看似平凡，威力却随「笼子的设计」指数增长：证「任意 60 个数中必有两人和或差是 8 的倍数」、证「圆内五点必有四点构成凸四边形」、证 Ramsey 数 R(3,3) ≤ 6（任意六人中必有三人互识或三人互不相识）……每一问的关键都不在「数数」，而在把对象巧妙地塞进笼子——笼子造对了，结论自动落地。

更进阶的问法在后面等着：平均必须 ≥ 1，何时必有 ≥ 2？（平均原理）；两层鸽笼叠起来会怎样？（Ramsey 理论：有序隐藏在无序深处）；随机塞鸽子会怎样？（概率方法：Erdős 的魔法）。这些是第三章的风景——翻页，去数那些「不用数」的数。

第三章 鸽笼与 Ramsey：必然的秩序第三章导引：有些结论不用数就成立

前两章都在辛苦地数。本章反过来：某些结论无须任何计算就必然成立。

三问开场。①任意 13 个人里，必有两人同月过生日——要查户口吗？不用：13 人 12 个月，多的那一只「鸽子」注定撞笼。②从 1 到 100 任取 51 个数，必有两个数其中一个整除另一个？听起来离奇，但是真的——笼子造对了，结论自己走出来。③任意六个人开派对，必有三人互相认识，或三人互相不认识——这不是鸡汤，是可以严格证明的 Ramsey 定理，而且是数学史上「证明存在、却算不出具体值」的著名开端。

本章路线。先磨利鸽笼原理与平均原理（§3.1–3.4），用它们证明 1935 年的 Erdős–Szekeres 定理；然后进入 Ramsey 理论的心脏（§3.5–3.9），见识 R(3,3) = 6 的完整证明与 R(5,5) 至今未知的窘境；随后以极端原理（§3.10）补上另一件存在性武器；最后半章速成图论（§3.11–3.15）——Ramsey 的语言就是图的语言，而图论本身也是组合学的第二支柱。

本章的口气变了。第一、二章的句式是「共有多少种」；本章的句式是「必定存在」——从计算走向担保。这口气在第二十三章的凸六边形定理、第七章的 Hall 定理里还会反复出现；本章先把最锋利的那几把刀磨好。

第三章 鸽笼与 Ramsey：必然的秩序3.1 鸽笼原理：最简单的存在性

鸽笼原理：n + 1 只鸽子飞进 n 个笼子，必有一个笼子装至少两只。

证明一行：若每笼至多一只，鸽子至多 n 只，矛盾。它的全部力量在于「笼子怎么造」——对象不变，笼子一换，结论千变万化。

例一（生日）。13 人 12 月：笼子是月份，必有两人同月。升级版：任意 367 人中必有两人同月同日生（含闰日 366 种生日）。

例二（头发）。任意城市中必有两个人的头发根数相同——头发至多几百万根，而城市人口以千万计：笼子是「头发根数」。

例三（小数循环）。无理数 √2 的小数展开中，前 100 万位里必有连续十位重复出现——十位数字串共 10¹⁰ 种？不对，100 万 < 10¹⁰，笼子造错！改为考虑「位置分段」：把前 100 万位切成 10 万段，每段 10 位——10 万段 10 万种？还是不对。这个反例提醒我们：鸽笼要用对笼数。正确说法：若取 10¹⁰ + 1 段，则必有重复。例三的教训写进案卷（§3.10 前的练习）。

强化版（数量可控）。q₁ + ⋯ + q_n − n + 1 只鸽子进 n 笼，必有一笼至少装 q_i 只（对某个 i）。特别地 2n − 1 只进 n 笼必有一笼 ≥ 2；n(k−1) + 1 只进 n 笼必有一笼 ≥ k。

第三章 鸽笼与 Ramsey：必然的秩序3.2 平均原理：从「有」到「有多少」

平均原理：n 个数的平均值 ≥ k，则至少有一个数 ≥ k；平均值 < k，则至少有一个数 < k。

这是鸽笼的连续版，也是存在性证明的第一生产力。三个经典应用：

应用一（边染色）。把 1 到 10 随意放在圆圈上，必有相邻两数差 ≥ 6？考虑最大数 10 与最小数 1：沿圆圈两条弧各连着它们，两弧的「步差」总和 = 9（绕圈一周差的代数和为 0，但绝对值之和 ≥ 9），两条弧之一步差 ≥ 4.5，故其上必有相邻差 ≥ 5？——小心，绕圈 |差| 之和其实是偶数倍的绕圈数，直接用平均：两条弧的绝对差之和 ≥ 9 + 9 = 18？这个例子的正确版本留给习题 A4，此处先立「先算总量、再除份数、最后一句话担保」的三段式。

应用二（子集和）。从 1 到 2n 中任取 n + 1 个数，必有两数互素？提示：相邻整数互素——把 1 到 2n 分成 n 个笼子 {1, 2}, {3, 4}, …, {2n−1, 2n}，每个笼子里的数相邻、互素；取 n + 1 个数必有两数同笼。鸽笼的经典身姿：笼子是配对，不是分类。

应用三（同余）。任意 n + 1 个整数中必有两数之差被 n 整除——笼子是「模 n 的余数」，共 n 个。

第三章 鸽笼与 Ramsey：必然的秩序3.3 鸽笼的威力：整除与倍数

导引的问题二回来：从 1 到 2n 任取 n + 1 个数，必有两数其中一个整除另一个。这是 20 世纪流传最广的鸽笼题（Putnam 竞赛的常客）。证明分两步，两步都是「造笼」的教科书示范：

第一步：剥离 2 的因子。任何正整数写成 2^s × m（m 为奇数）。1 到 2n 中的数，奇部 m 只能取 1, 3, 5, …, 2n−1 共 n 种。取出的 n + 1 个数按奇部分笼——必有两数同奇部。

第二步：同笼即整除。同奇部的两数 2^am 与 2^bm，指数大小即整除关系——小的整除大的。∎

这个证明的深层结构：先把每个对象压缩到「不变量」（奇部），不变量的种类少（n 种），对象多（n + 1 个），碰撞必然发生；而碰撞的不变量恰好继承了我们要的性质（同奇部 → 整除链）。这种「压缩不变量 + 碰撞继承」的套路是鸽笼的最高级用法：

再例（子序列和）。任意 n + 1 个不超过 2n 的正整数中，能选出若干个使和恰为 3 的倍数？考虑前缀和 S₀, S₁, …, S_n 共 n + 1 个，模 3 只有 3 种余数——鸽笼给「两个前缀和同余」或「某个 ≡ 0」，两种情形都给出一段连续子列和为 3 的倍数（鸽笼只给 2 个，不够一般 n——正确版用模 n：见习题 A6）。把余数当笼子是数论组合的标准姿势。

第三章 鸽笼与 Ramsey：必然的秩序3.4 Erdős–Szekeres：单调子序列

1935 年，Erdős 与 Szekeres 证明了组合学史上一条「不可能不成立」的定理：

定理：任意 (r − 1)(s − 1) + 1 个两两不同的数排成一列，必有 r 项递增子序列，或 s 项递减子序列。

证明是鸽笼的雕塑：对每项记 (a_i, b_i)——以它结尾的最长递增子序列长 a_i、最长递减子序列长 b_i。关键观察：i ≠ j 时 (a_i, b_i) ≠ (a_j, b_j)（否则两项可互相接续，矛盾）。若既无 r 递增又无 s 递减，则 a_i ∈ [1, r−1]、b_i ∈ [1, s−1]，数对只有 (r−1)(s−1) 种——比项数少一，鸽笼矛盾。∎

取 r = s = 11：任意 101 个不同的数必有 11 项单调子序列。真跑验证：一万个随机长 101 的序列，LIS 与 LDS 的最大值逐一检查，无一例外 ≥ 11；而存在长 100 的序列（10 递增 × 10 递减的棋盘布局）使 LIS 与 LDS 都恰为 10——界是紧的。

后记。这篇论文的深层意义：Erdős–Szekeres 在此文引入「happy ending 问题」——多少个点保证存在凸 n 边形？由此长出了整个组合几何与 Ramsey 理论。一条鸽笼证明，开了一片大陆。

第三章 鸽笼与 Ramsey：必然的秩序3.5 Ramsey 定理：无序中的必然

把鸽笼原理推到极致：不管结构多乱，只要规模够大，某种秩序必然出现。这就是 Ramsey 定理的精神。以最简单的对称版陈述：

Ramsey 定理（二人版）：对任意 k, l，存在最小整数 R(k, l)，使得任意 R(k, l) 人的人群中，或有 k 人互相认识，或有 l 人互相不认识。

翻译成图语言：完全图的边红蓝二染色（红=认识，蓝=不认识），R(k, l) 是保证出现「红色 k-团或蓝色 l-团」的最小顶点数。存在性由 Erdős–Szekeres 1935 年的递推证明给出：

R(k, l) ≤ R(k−1, l) + R(k, l−1)

证明思路：取一个人，看其余 R(k−1, l) + R(k, l−1) − 1 人与他相连的边——红边至少 R(k−1, l) 条或蓝边至少 R(k, l−1) 条（鸽笼），两条路各通向一个团。递推的底座是 R(1, l) = R(k, 1) = 1。

哲学冲击。Ramsey 定理说：完全无序是不可能的——规模本身就是秩序的担保。Erdős 的名言「上帝有一本簿子，记着每个 Ramsey 数的值」；而我们翻开簿子会发现（下一节），连 5×5 的格子都是空白。

第三章 鸽笼与 Ramsey：必然的秩序3.6 R(3,3) = 6：派对问题

第一本簿子页：R(3,3) = 6。证明是组合学的入门经典，两条各五行：

下界：R(3,3) > 5。构造五人反例：五人手拉手围成五边形（红边），不相邻者连蓝边（恰是五角星）。每个三角形（三顶点组）必含不相邻对——无红色三角；同理无蓝色三角。六行的构造图值得亲手画一遍。

上界：R(3,3) ≤ 6。六人中任取一人甲，其余五人与甲的 5 条关系线由鸽笼（5 条线 2 种颜色）必有 3 条同色，设红：甲与乙、丙、丁互为红线。若乙丙丁之间有任一红线，与甲构成红三角；否则乙丙丁之间全是蓝线，本身就是蓝三角。∎

为什么这条小定理有名？三个理由：①它是「存在性结论可以完全初等地证明」的模范；②它的构造反例（五边形+五角星）美得像图案设计；③它是 Ramsey 数里唯一「算得清」的那一档——下一个 R(3,4) = 9 要到 1955 年才确定，而 R(5,5) 至今下落不明（§3.8）。

第三章 鸽笼与 Ramsey：必然的秩序3.7 Ramsey 数：为什么这么难

R(3,3) = 6 之后，簿子上的字突然难产。看已知全貌（截至 2024 年）：

为什么难？证 R(5,5) ≤ N 要排除 K_N 的所有 2^N(N−1)/2 种二染色——N = 48 时是 2¹¹²⁸ 种，宇宙的原子数在它面前是零。证下界要构造一个庞大的无单色团染色——同样没有系统方法。Erdős 打过比方：一群外星人入侵地球，威胁「交出 R(5,5)，否则毁掉地球」——正确的策略是把所有计算机调来算上界；若是 R(6,6)，正确的策略是与外星人决战。

第三章 鸽笼与 Ramsey：必然的秩序3.8 Ramsey 数的边界：已知与未知

精确值难产，组合学家转向夹逼。上界来自 Erdős–Szekeres 递推的改进（对角线版）：

R(k, k) ≤ C(2k − 2, k − 1)

下界来自随机方法（Erdős 1947 的神来之笔）：随机给 K_n 染色，单色 k-团的期望个数 C(n,k) · 2 · 2^−C(k,2)；只要它小于 1，就存在一种染色无任何单色 k-团——于是 R(k,k) > n。「随机造反例」证明确定性结论，这是 20 世纪数学最深远的观念革命之一（第六章的概率方法将正式开讲）。目前最好的一般下界（Spencer 1975）：

R(k, k) > (1 + o(1)) · k · 2^k/2 / (e√2)

上下界之间隔着指数鸿沟：2^k/2 对 4^k——五十年无实质进展。真跑小样感受难度增长：验证 R(3,4) ≤ 9 需枚举 2³⁶ ≈ 687 亿种染色（需要剪枝与对称性）；R(4,4) ≤ 18 的 2¹⁵³ 已彻底超机。教科书能完整证明的最后一站是 R(4,4) = 18（1955 年 Greenwood–Gleason 用巧妙的子结构分析+唯一性论证，本册挑战页复刻其骨架）。

第三章 鸽笼与 Ramsey：必然的秩序3.9 无限版与Ramsey理论版图

Ramsey 1930 年的原始论文其实是无穷版：

无限 Ramsey：把可数无穷集的所有二元子集红蓝染色，必有无穷子集，其所有二元子集同色。

证明同样优雅：逐点挑选——选 x₁，与它同色的无穷多个（鸽笼的无穷版）；在其中一个无穷族里选 x₂……选出的序列按「与前辈的边色」再分笼，抽无穷同色子列。无穷鸽笼原理（无穷多个球进有限个笼，一笼无穷）是这页证明的唯一工具。

有限版是无穷版的影子：无穷版若不成立，紧性论证（König 无限树引理）会把有限版也推翻——反之，有限版成立并不能直接推出无穷版（需要紧性）。这种「无穷—有限互证」是 Ramsey 理论的方法论特色。

版图速写：①超图 Ramsey：染三元组而非点对，R³(4; 2)（四点同色三角）已知最小 13；②几何 Ramsey：平面上的点对染色，问单色凸图形——happy ending 问题（Erdős–Szekeres 1935 提出，2021 年 Suk 等人基本解决）；③van der Waerden：染整数而非点对，必有无穷长等差数列的有限版 W(2, 3) = 9；④Hales–Jewett：高维格子里的单色线——组合学的「万有引力定律」。本章只开园门，园内风景留给研究生院。

第三章 鸽笼与 Ramsey：必然的秩序3.10 极端原理：抓住最边上的

存在性证明的第二件武器：从所有对象里挑一个「最」的，分析它的极端性质。逻辑简单到近乎天真，用法却千变万化。

例一（凸包）。平面上的有限点集必有「凸包」——包含它们的最小凸多边形；凸包顶点都是原点集中的点。证明：取到任意直线投影最远的点，它必是凸包顶点（极端位置不可被夹在中间）。

例二（和最小的反例）。证明：若正整数集对加法封闭且 1 在其中，则它包含所有正整数。反证：若有例外，取最小的例外 n；n − 1 不是例外（比它小），故 n = 1 + (n − 1) 在集合中，矛盾。「最小反例法」＝极端原理 + 反证，是整个数学的存在性发动机之一（§2.9 五边形定理的 Franklin 证明也可用最小反例语言重述）。

例三（图的极大性）。任何无三角图必有一条边，其两端点的公共邻居数 ≤ √(2m)（m 为边数）？——选度数最大的点分析即可。极端对象自带信息：最大度点说明邻域规模、最长路径说明圈的存在、最小度点说明删点顺序。图论里的极端原理专用名目：贪心论证（§3.13 的树、§3.15 的匹配都用它）。

第三章 鸽笼与 Ramsey：必然的秩序3.11 图论速成：点与线的语言

Ramsey 的「认识与不认识」、七桥的「桥与岸」、社交网络的「好友」——全都是图。图 G = (V, E)：顶点集与边集，边是顶点的无序对。它是组合学里最通用的结构语言：能用「点 + 关系」描述的一切系统都住在这里。

基本词汇表（本章后半与第四章的通行证）：

Ramsey 定理的图语言现在可以重述：任意 R(k, l) 个顶点的图，或有 k-团，或其补图有 l-团。R(3,3) = 6 即「六顶点图必有三角或补图有三角」。

为什么图论是组合学的第二支柱？因为「关系结构」无处不在——电路、航线、蛋白质交互、社交网络；而图的数学恰好是数数 + 存在性的组合：计数生成树（Cayley）、担保连通（树）、分类路径（欧拉）。§3.12–3.15 把四大件过一遍。

第三章 鸽笼与 Ramsey：必然的秩序3.12 图的基本量：度与握手定理

图论第一定理属于「不用数的数」家族：

握手定理：Σ deg(v) = 2|E|——所有度数之和是偶数。

每条边贡献两端、各计一度。推论：奇度顶点必偶数个。三个即刻应用：①「任何派对中与奇数人握过手的人数是偶数」——图论进入日常话语的第一例；②正多面体只有五种（Platonic solids）的欧拉证明起点；③下一节欧拉路径的门槛条件。

度序列与存在性。给定非负整数序列，何时是某图的度序列？Erdős–Gallai 定理给出充要条件——又一处 Erdős。简单必要条件：最大度 ≤ n−1，和为偶。充分性的证明用「贪心重构 + 归纳」，是极端原理的又一次登台。

平均原理回归：平均度 = 2|E|/n，故任何图必有两顶点同度（鸽笼：度只有 0…n−1 共 n 种，但 0 与 n−1 不能同时出现——实际可行笼数至多 n−1）。又一例「笼子造法决定成败」。

三大基本计数：K_n 的边数 C(n,2)（每对点一条边——组合数直接上岗）；度序列为 (d₁,…,d_n) 的标号图计数（Erdős–Gallai 判定后的生成函数，第二十六章内容）；以及下一节的生成树计数 nⁿ⁻²——一条漂亮得不像话的公式。

第三章 鸽笼与 Ramsey：必然的秩序3.13 树：最经济的连通

树＝连通且无圈的图。它是「恰好够用」的连通结构：n 个顶点的树恰有 n − 1 条边——少一条断连，多一条出圈。等价刻画（每条都与其余等价，互推练习）：连通且 n−1 条边；任两点恰一条路径；删任一边即断；加任一边恰出一圈；无圈且 n−1 条边。

三个立即可用的性质。①任何非空树有叶子（度为 1 的点）——取最长路径的端点即得（极端原理）；②删叶得小树——归纳法的工作台；③n ≥ 2 的树至少两片叶子。

Cayley 公式（1889）：n 个标号顶点的树恰有 nⁿ⁻² 棵。四顶点：4² = 16 棵，真跑枚举全对；十顶点：一亿棵——「标号树的森林」比宇宙星系还密。证明美不胜收：Prüfer 序列把每棵树编码成长 n − 2 的字母串（每次删最小编号叶子、记其邻居），且每个字符串恰好还原一棵树——双射给出 nⁿ⁻²。第一章「计数即描述」的哲学，在树的世界最澄澈。

生成树。连通图的生成树＝含全部顶点的树。它是最小费用连通方案的原型（最小生成树问题，Kruskal/Prim 算法，贪心论证的标准舞台——极端原理的算法化身）。

第三章 鸽笼与 Ramsey：必然的秩序3.14 欧拉路径与哥尼斯堡七桥

1736 年，欧拉回答哥尼斯堡市民的闲聊之问：能否散步走过七座桥各恰一次？他把陆地缩成点、桥画成线——图论就此诞生（第一篇图论论文）。

欧拉的洞察：每「过」一座桥要「进」一次「出」一次——中途点必须进出平衡（偶度）。起点与终点可以例外（若不同，各多一进一出，奇度）。于是：

欧拉路径存在 ⟺ 连通图中奇度顶点数为 0 或 2（0 时回路、2 时开路）。

七桥图四个顶点全是奇度（3, 3, 5, 3）——不连通性无望，欧拉路径不存在。证明的存在性一半（条件满足时真能走通）用归纳：沿「暂不闭合」的边贪心走，进得来必出得去，直到无路可走时必在终点，剩余部分递归拼接（Hierholzer 算法，1873）。

一笔画的推广。「每边恰一次」是欧拉型问题；「每点恰一次」是哈密顿型问题——后者至今没有漂亮的充要条件（NP 完全问题，计算复杂性的深渊入口）。一字之差，天上地下：欧拉问题管边（局部平衡），哈密顿问题管点（全局结构）——组合学里「容易」与「困难」的分野常常就是这么一线。

第三章 鸽笼与 Ramsey：必然的秩序3.15 二部图与匹配

二部图：顶点分两组（如 男/女、任务/工人），所有边跨组。判定：图无奇圈（König 定理）。

匹配＝没有公共顶点的边集；完美匹配把一组与另一组一对一配满。相亲、排课、器官移植全是匹配问题。核心定理属于 Hall（1935）：

Hall 定理：左组每 k 人的邻居 ≥ k 人（对一切 k）⟺ 完美匹配存在。

必要性显然（k 个人要配 k 个不同的对方）。充分性的证明是极端原理 + 归纳的艺术：取邻居最紧的子集分类讨论，「紧」的子集直接配，「松」的子集拆点归纳。「缺失的一角由最紧处担保」——这句口诀把极端原理用到了极致。Hall 定理在第四章将以「SDR（相异代表系）」的身份再现，并在图论深处（Menger 定理、最大流最小割）结成理论之网。

与鸽笼的对账：鸽笼说「有人要抢同一笼」；Hall 说「抢得过来抢不过来，一眼可判」——鸽笼给障碍，Hall 给判据。例：六个任务、六名工人，工人 1–3 都只会做任务 A、B——三人抢两活，Hall 条件破产，完美匹配无望。障碍找到了，答案就找到了：这就是极小反例法的实用主义面孔。

第三章 鸽笼与 Ramsey：必然的秩序3.16 第三章全景：存在性的工具箱

本章工具按「担保的强度」排成三级：

一级：直接担保（鸽笼、平均、无限鸽笼）——笼子造好，结论自动落地；用于「多对少」的一切场面。二级：递推担保（Ramsey 递推、Erdős–Szekeres 数对法）——把大结论化归小结论，规模大到一定程度必然触发；用于「无序中的秩序」。三级：构造担保（极端原理、最小反例、Hall、Prüfer）——亲手指出那个「存在的东西」；用于「要看得见实物」的场面。

与前三章的接口。第一章的双射（Prüfer 编码、Glaisher 映射）与双向计数（握手定理本质上是边的双向计数）在本章全面上岗；第二章的平均原理其实是加法原理的连续版。组合学的三大问题——有多少（一二章）、有没有（本章）、结构如何（第四章起）——在此完成第一次会师。

下一章正式进入图论腹地：欧拉公式、平面图、染色——那片「点线面」的大陆，比本章的「存在性」更深、更结构化。

第三章 鸽笼与 Ramsey：必然的秩序例题一：鸽笼与极端原理实战

例 1（同余笼）。任意 n + 1 个整数中，必有两数之差被 n 整除。解：笼 = 模 n 剩余类，共 n 个。同笼两数同余，差 ≡ 0。追问：和被 n 整除呢？——改笼为「{0}, {1, n−1}, {2, n−2}, …」的 ± 配对，⌈n/2⌉ + 1 个数即触发。

例 2（倍数笼）。§3.3 的整除链题完整重演：1 到 2026 中任取 1014 个数，必有两数一除一余？——2026 = 2 × 1013，奇部只有 1013 种，取 1014 个必撞笼；同奇部者按 2 的幂分层，小幂整除大幂。∎ 注意笼数刚好卡住：少取一个数结论就可能失败（全取奇数反例）——鸽笼题必须顺手验证界的紧性。

例 3（极端原理）。数轴上任取 n 个互不相同的点，必有两点，其间（作为区间）不含其他所选点。解：取相邻的两点——把点排序后取位置相邻的一对。极端版本：取最小点与次小点。启示：排序是最便宜的一种极端化。

例 4（平均原理）。凸 n 边形内任放 m 个点，必存在一条对角线，把多边形分成两部分使每部分至少 ⌊m/2⌋ 个内点？——周界上转一圈，逐条对角线数一侧点数，和的总量保证某一刀两侧均衡（细节留习题 B3）。「总量、份数、担保」三段式再次上岗。

第三章 鸽笼与 Ramsey：必然的秩序例题二：Ramsey 与图论实战

例 5（R(3,3) 双色图）。九人委员会中，任意两人或互相认识或互相敌对；证明存在三人互相认识或四人两两敌对——即 R(3,4) ≤ 9。解：任取甲，其余 8 人按甲的关系分两笼。若「认识」笼 ≥ 6 人，其中 R(3,3) = 6 担保三人互识（连同甲成 3-团？——那三人与甲间是认识边，故甲+三人即红色 4-团？不，甲与三人认识边给的是「甲+乙丙丁」的四人组——但我们需要红色 3-团或蓝色 4-团：乙丙丁间若蓝线齐则蓝色 3-团 + 甲不加入；细算：笼内 R(3,3) 给互识三人或互敌三人；互识三人+甲即红色 4-团——超出所需（要的是 3-团，4-团含 3-团）✓；互敌三人加甲？甲与他们认识，敌对团不扩大——但互敌三人已是蓝 3-团，凑不齐 4——需蓝色 4-团：若「敌对」笼 ≥ 4，笼内互识？……完整证明留作挑战（§3.16 挑战页复刻），此处示范递推担保的分层推进。

例 6（树的三看）。十棵树的顶点数为 2 到 11，总边数？——每棵 n − 1 条：1 + 2 + ⋯ + 10 = 55。追问：11 个标号顶点的树有几棵？——11⁹ = 2 357 947 691 棵（Cayley）。一个结构两种计数：边数是「存在的代价」，棵数是「存在的可能」。

例 7（欧拉判据）。汉字「一」到「十」的连笔笔画图，哪些能一笔画成？——转成图看奇度点：0 或 2 个奇度点即可。「田」字四个内角点各 3 度 + 外框角点 2 度？——逐点数即判。欧拉判据是不用试画就能断言「走不通」的典型。

第三章 鸽笼与 Ramsey：必然的秩序习题课（一）：鸽笼基本功

A 组·造笼入门

A1.从 1 到 100 任取 51 个数，必有两数其中一个整除另一个？——若不行，给出最强反例。
答：不成立！51..100 的 50 个数互不整除；51 个时成立吗？——奇部笼有 50 个（1..99 的奇数），50 个奇数本身互不整除，故 51 才触发。本题训练「笼数卡界」。