My Vault

1 排列组合基础

23 min read

先纠正一个小笔误：是 plain text（纯文本），不是 “plan text”。下面用 LaTeX 把 Stage 1 重讲一遍。

Stage 1：计数基础与双射思想

在堆公式之前，先给你这一站的”内核”。Stage 1 看起来有十几个公式，但它们全是三条思想的产物。带着它们往下读，你会发现公式根本不用背——都能现推：

  1. 乘法原理是引擎：能把一个对象唯一地描述成”一步步做选择”，总数就是各步连乘。
  2. “先多数，再除以重复倍数”：直接数难、但”带上额外结构去数”容易时，就过度计数再除——组合、重复排列、圆排列全是它（但有个关键前提，下面会反复敲）。
  3. 双射是万能钥匙：难数的集合架一座桥到好数的集合；证”两类一样多”就造一个对应。前两条其实都是它的特例。

一、先分清三件事：计数、概率、枚举

  • 枚举 (enumeration)：把对象一个个列出来——回答”有哪些”。
  • 计数 (counting)：只问”有多少个”，不要求列出——回答”有多少”。
  • 概率 (probability)：等概率时就是计数的比值，。

竞赛组合的主战场是计数：在根本列不完的情况下算出数量。而正确的计数，几乎总是先依赖一个判断——哪些对象算”同一个”，哪些算”不同”。这个判断错了，公式再熟也白搭。

例： 字母 排成一排， 和 算不算同一个？排列问题里算不同（顺序重要）；但若问”从 里取一个两元素子集”， 和 就是同一个（顺序无关）。同样的字母，问法不同，答案就不同。所以动笔前第一件事永远是：问清楚”什么算同一个”。

二、记号：、、

  • 阶乘 ，约定 。直观上 是” 个不同东西排成一排”的方法数（§四会证）。为什么 ？因为” 个东西排成一排”恰有 种方式（空排列）——不是硬规定，是为了让公式自洽。
  • 求和 。
  • 连乘 。所以 。

三、两条基本原理（整站的引擎）

加法原理 (Addition Rule)

完成一件事若有几”类”互不相交的方法，总数 = 各类之和。关键词是互斥 (disjoint)：没有一种方法同时属于两类。

例： 书架上 本小说、 本漫画，选一本读： 种。（一本书不会既是小说又是漫画，互斥成立。）

陷阱与修正： 两类若有重叠，直接相加会重复算。修正它的最简形式就是容斥（Stage 3 的种子）：

例： 到 中能被 或被 整除的有几个？被 的有 个；被 的有 个；被 的（同时满足）有 个。故 个。若直接 ，就把 各算了两次。

乘法原理 (Multiplication Rule)

一件事若分若干”步”完成，且每一步可选的数目固定（不随前面具体怎么选而变），总数 = 各步数目之积。

例： 早餐 1 主食 1 饮料，主食 选、饮料 选： 种。 例： 车牌 2 字母 3 数字（可重复）： 种。

核心心法（你做 USACO 时其实天天在用）：把计数问题翻译成”一步步做选择的序列”。 只要能把一个对象唯一地写成”第一步选…，第二步选…”，总数就是各步连乘。这是大半计数题的起手式。

一个微妙但要命的点： 乘法原理要求”每步数目固定”。如果第二步能选几个取决于第一步选了什么（数目会变），就不能直接乘——要么分类讨论，要么换个描述方式。

例（合法地用）： 个不同的人坐 把不同的椅子。第一人 选 ，第二人从”剩下的”里 选 ，第三人 选 ：。这里”剩下谁”虽然在变，但”剩几个”是固定的（），所以能乘。——这正好引出排列。

四、排列 ：有序地选

从 个不同的东西里，有序地取 个排成一列：

推导（直接套乘法原理）： 第 个位置 选，第 个位置 选，……第 个位置 选，连乘即得，共 个因子。

特例 ：，这就是” 个不同东西排成一排 “的由来（回填了 §二的直观）。

例： 名选手争金、银、铜牌（有序）：。

为什么又写成 ？因为

约掉后半截就剩前半。这个”补全再约掉”的写法，是为了方便和组合公式对照。

五、组合 ：无序地选 —— 第一次”先多数再除”

从 个不同的东西里无序地取 个（只关心取了”哪些”，不关心顺序）：

透彻推导（Stage 1 的灵魂之一，务必吃透）： 直接数”无序的 元子集”不容易，但”有序地取 个”很容易，就是 。关键观察：每一个无序子集，在 里被数了恰好 次——因为这 个元素自己内部有 种排列顺序，对应的却是同一个子集。于是

例： 名选手选 人组成委员会（无序）：先有序数 ，每个委员会被 种点名顺序重复算，故 。

这里藏着会贯穿全书的大思想——“除以重复倍数”： 直接数难、但”带上某种额外结构（这里是顺序）去数”容易时，先过度计数，再除以”每个真正对象被重复算的次数”。

但有一个致命前提：每个对象必须被重复了相同的次数（这里每个子集都恰好被算 次），否则不能简单地除。 这个”均匀重复”的前提，到圆排列、再到 Burnside 引理会一次次回来。现在记牢一句话：

几个要熟到条件反射的恒等式（双射证明留到 §十一）：

  • 对称：（选 个”要的” 选 个”不要的”）。
  • 边界：。
  • 总子集数：。

六、多重集排列（重复排列）：除以重复倍数，再来一次

要排的东西里有”相同的”（不可区分）时，排法变少。把 个东西排一排，其中第 种有 个相同（）：

推导（又是”先多数再除”）： 先假装 个东西全不同，排法 。但同一种里的 个其实不可区分，它们内部的 种顺序对应同一个排列，所以每个真排列被重复算了 次，除掉即得。

例： 重排。 个字母：。

例： 。 个字母：。

注意一个漂亮的回扣： 其实就是多重集排列。 把”选 个”看成”给 个位置贴标签： 个’选中’、 个’没选’“，这就是一个有 种、个数为 和 的多重集排列：，和组合公式一字不差。这说明组合和重复排列本质是同一个”除以重复倍数”的思想，只是换了件外衣。

七、可重复组合 / 隔板法 (Stars and Bars)：双射的第一次主角戏

问题： 把 个完全相同的球放进 个不同的盒子（允许空盒）有几种？等价说法：方程

的非负整数解个数（ 是第 盒的球数）。

答案：

透彻推导——构造一个双射（Stage 1 必须吃透的范例）： 把每个解编码成一串符号： 个星 代表球， 个竖线 代表盒子之间的隔板。竖线把一排星分成 段，第 段的星数就是 。

以 盒、 球为例：

每个”放球方案”对应唯一一串” 个 个 “；反过来每串符号也对应唯一一个方案。这是一一对应（双射），所以两边数量相等。而""共 个位置，排法 从 个位置里挑 个放竖线 。一般地就是 。

例（落地）： 颗相同糖果分给 个小孩，允许有人分到 ：

极常考的变式——每盒至少 个（）： 先给每盒垫 个球（用掉 个），剩下 个再随便放（允许空），于是

例： 颗糖分给 个小孩、每人至少 颗： 种。这个”换元消掉下界”的招，配合隔板法的双射，是处理”带约束整数解计数”的标准套路。

八、圆排列与项链：又一次”除以重复倍数”，但要小心前提

圆排列： 个不同的人围一张圆桌，只看相邻关系（整体转圈算同一种）：。 推导（先多数再除）： 先当成一排数， 种；但圆桌能旋转——同一个圆排列转 个位置会得到 种不同的线性排列，它们其实是同一个圆排列。每个圆排列恰好被重复算 次（均匀，前提满足），故

例： 人围圆桌： 种。

项链（可翻转）： 颗不同珠子串项链，除旋转外还能翻面（镜像也算同一种）， 时：

推导： 在圆排列 基础上，再把”一个排列和它的镜像”配成一对算同一个，故再除以 。 例： 颗不同珠子的项链： 种。

这里有个 USAMO 级别的警告： “除以对称数”只在”每个对象被重复了相同次数”时才成立。圆排列里恰好每个被转出 个不同线性排列、项链里恰好被翻/转出 个——这全靠珠子各不相同。一旦珠子有相同的、或 很小，旋转/翻转可能把某个排列映到它自己（产生”少于 次”的重复），简单除法就崩了。 处理这种”重复次数不均匀”的情形，正是 Burnside 引理（Stage 6）存在的理由。你现在要带走的认知是：除法计数是有前提的特例，Burnside 是它的完全体。

九、补集计数 (Complementary Counting)：正难则反

当”满足条件”的情形零碎、要分很多类，而”不满足”的情形很整齐时，算补集更省事：

触发信号： 题里出现”至少一个""不全是""存在”时，反面往往是”一个都没有""全都是”，干净得多。

例： 掷两颗骰子，至少出现一个 的情形数？总情形 ；一个 都没有 ；故至少一个 种。

例： 位数（–）中至少含一个偶数数字的有几个？总数 ；每位都是奇数的：首位奇（） 选，其余三位各 选，；故 个。

十、系统化分类讨论 (Casework)：把大问题切成互斥的小块

没有单一公式可套时，把所有情形划成互不重叠又覆盖全部的几类（这正是加法原理），分别数再相加。要诀是选一个”好的分类变量”，让每类内部变简单，且各类绝不重叠（MECE：互斥且穷尽）。

例： 用 元、 元硬币（每种无限多、不计顺序）凑 元有几种？按 元硬币的枚数分类：

  • 枚 元 枚 元
  • 枚 元 枚 元
  • 枚 元 枚 元

（ 枚 元 元，超了，停。）共 种。

分类的两大常见错误：两类悄悄重叠（重复计数）、或漏掉边界情形（少算）。养成习惯：分完先自检——“会不会有一个对象同时落进两类？有没有谁哪类都不属于？“

十一、★ 双射原理 (Bijection)：Stage 1 的皇冠

前面”除以重复倍数”其实只是双射思想的一个特例。现在正面讲这把 USAMO 组合最锋利的刀。

原理： 若两个有限集 之间存在一一对应 （既单射又满射，每个 中元素配一个 中元素，不重不漏），则 。

为什么强大： 它让你”换一个集合来数”。 难数、 好数时，只要架一座桥 ，难题就变简单。隔板法就是典型——把难数的整数解双射到好数的星杠串。

双射证明 vs 代数证明： 很多组合恒等式可以硬算（阶乘公式约分），但双射证明更深刻——它告诉你”为什么相等”，因为两边在数同一类东西。USAMO 偏爱这种”给出对应关系”的证明。

例 1（对称恒等式的双射证明）： 证 。 构造映射：每个 元子集 对应它的补集 （剩下 个元素）。取补这个操作不重不漏（不同 给不同 ，每个 元子集都是某个 的补），是双射。故 元子集与 元子集一样多。——一行话，不碰阶乘。

例 2（子集总数）： 证 的子集共 个。 构造双射：每个子集 一个长度 的 串（第 位为 表示 在子集里）。子集与 串一一对应，而 串由乘法原理有 个（每位 选）。故子集数 。

例 3（真正展示威力的 USAMO 味例子）： 证明 中”偶数元子集”和”奇数元子集”一样多（），从而各为 个。 代数版要算 ，挺抽象。双射版极漂亮： 定义操作 ——对任意子集 ，看元素 在不在里面：在就拿掉它，不在就加进去（即 与 取对称差 ）。

  • 把偶数元子集变成奇数元子集，反之亦然（大小恰好 ，奇偶翻转）。
  • 做两次回到原样（拿掉又加回 / 加进又拿掉），所以 是它自己的逆——这种”自己是自己逆”的映射叫对合 (involution)，天然是双射。

于是偶子集与奇子集被 完美配对，数量相等；两者合起来是全部 个，故各 个。 验证 ： 共 个子集；偶数元（含 元）：—— 个；奇数元：—— 个。各 ，吻合。

带走的方法论： 看到”两类东西一样多”，先别硬算——想能不能造一个对应，尤其是”做两次还原”的对合，最好用。这是 Stage 1 留给你后面所有 Stage 的最重要肌肉记忆。

这一站的统一主线（请务必内化）

把 Stage 1 拧成三句话，后面每一站都在它们之上生长：

  1. 乘法原理是引擎：能把对象唯一描述成”一步步选择”，就连乘。
  2. 除以重复倍数 ：组合、重复排列、圆排列、项链全是它——但前提是每个对象被重复的次数相同，否则要上 Burnside。
  3. 双射是万能钥匙： 难数就架桥到好数的 ；证”一样多”就造对应（对合优先）。前两条都是它的特例。

公式不必背——都能从这三条现推。真正要练的是”这个对象该怎么唯一描述 / 该和谁配对”。

我的观点： Stage 1 里，多数人”会用 、 公式”就以为过关，其实真正决定你 USAMO 上限的是 §五的”先多数再除（及其均匀前提）“和 §十一的”双射 / 对合”。这两个不是计算技巧，是思维方式。 把它们练到看题就条件反射，后面的不变量、容斥、Burnside 才学得动。建议你现在就用 §十一例 3 的对合思想，自己把 和”子集数 “重证一遍，体会”造对应”的手感——这比多做十道套公式的题有用。

置信度：约 。 内容与推导我很有把握。两点提醒：（1）隔板法只适用于”球相同、盒不同”；“球不同”或”盒相同”是另外的模型（盒相同会用到 Stage 4 的分拆 / Stirling 数，到时再讲），别套错。（2）圆排列 / 项链的除法公式默认”对象各不相同且 不太小”，小情形或有重复元素时务必回到 §八那个警告，别盲目除。

Graph View

Backlinks