排列组合 · 从计数原理到 P(n,k) 与 C(n,k)

组合学 (combinatorics) 最朴素的问题只有一句：某种安排有多少种。本系列不急着背公式，而是从两条计数原理出发 —— 一件事分步完成时各步方案数相乘 (乘法原理)，分类完成时各类方案数相加 (加法原理) —— 把排列与组合都还原成这两条原理的直接推论。

接着区分两种「取 $k$ 个」：在意先后次序的是排列 $P(n, k)$，不计次序的是组合 $C(n, k)$，两者只差一个 $k!$。每页都可拖动 $n$ 与 $k$，即时看到填空位的方案数如何逐格收缩、枚举结果如何随之增减，以及 Pascal 三角上每个 $C(n, k)$ 如何由上一行两数相加得到。

越出中学范围的部分从加法原理的缺口接上：容斥与错排处理「分类不互斥」的情形，鸽巢原理给出计数之外的存在性下界，双射与双计数把恒等式还原成同一批对象数两遍；再往后是 Catalan 数、Stirling 数与整数分拆这三族经典序列，由十二重计数法收进一张球盒总表。末两组交给生成函数、Burnside 引理与 Stirling 渐近公式，以及把公式真正算出来时撞上的溢出、编号与抽样问题。

计数原理 · 分步相乘、分类相加

所有计数都建立在两条原理上：一件事分步做，总数是各步方案数的乘积；分类做，总数是各类方案数的和。分清分步还是分类，是列式的第一步。

counting · 乘法 / 加法原理

两条计数原理

分步完成的事，总方案数是各步之积（乘法原理）；可归入互斥若干类的事，总方案数是各类之和（加法原理）。分清分步还是分类，是列式的第一步。

inclusion–exclusion · 交错加减

容斥原理

加法原理要求各类互斥，一旦相交，直接相加就会重复计数。容斥原理用 $2^n-1$ 项交错加减把重叠扣干净，交错系数的抵消由二项式定理保证，满射计数与错排都是它的直接应用。

derangement · Dₙ ≈ n!/e

错排

$n$ 个人各交一顶帽子、随机发回，无人拿到自己那顶的发法数记 $D_n$。容斥把「有不动点」的重叠情形扣干净，给出求和式与两条递推，而比值 $D_n/n!$ 极快地收敛到 $1/e$。

排列 · 有序地取 k 个

从 $n$ 个不同元素里有序、不放回地取 $k$ 个，方案数记 $P(n, k)$。它是乘法原理的直接结果：第一格 $n$ 种、第二格 $n-1$ 种，逐格收缩相乘。

permutation · P(n, k) = n! / (n−k)!

排列 P(n, k)

从 n 个不同元素里有序取 k 个：逐格填，每填一格可选的元素少一个，各格方案数相乘即 $P(n,k) = n!/(n-k)!$。

constrained · 插空法 / 捆绑法

带约束的排列

不相邻用插空法，先排骨架再往空隙里有序插入；相邻用对偶的捆绑法，把受约束元素捆成一个整体参与排列、捆内再排。两者都化归为全排列加一步选序。

组合 · 无序地取 k 个

同样取 $k$ 个，但不计次序，方案数记 $C(n, k)$。把排列里 $k!$ 种同元素的不同顺序压成一种，就从 $P(n, k)$ 得到 $C(n, k)$；Pascal 三角与二项式定理则给出它的递推与展开。

combination · C(n, k) = P(n, k) / k!

组合 C(n, k)

取 k 个时不计次序，同一组元素的 $k!$ 种排列折叠成一个组合，于是 $C(n,k) = P(n,k)/k! = n!/(k!(n-k)!)$，并有对称性 $C(n,k) = C(n,n-k)$。

Pascal triangle · 二项式定理

Pascal 三角与二项式定理

把组合数排成三角形，每个内部数等于上方两数之和。这条递推既是三角的生成规则，也是二项式定理归纳证明里合并同类项的那一步。

到这里都在「从集合不放回地取」

前面的排列 P(n, k) 与组合 C(n, k) 都假设源是集合（元素互异）、且取后不放回。放松这两条假设，「重复」会从两个方向进来——见下面的重复的情形：源本身是多重集（自带相同元素），或取时放回（可反复取同一个）。后者的 nᵏ 与 C(n+k−1, k)，正好补齐「有序 / 无序 × 放回 / 不放回」四种取样模型里剩下的两格。

重复的情形 · 源自带重复 / 取时放回

前面都假设源是集合 (元素互异)、取后不放回。重复可以从两个方向进来，需要分开：源本身是多重集 (自带相同元素)，或取时放回 (可反复取同一个)。前者用「除掉同组互换」修正全排列，后者补齐取样模型里剩下的两格。

multiset permutation · n! / ∏ nᵢ!

多重集排列

源自带重复元素时，朴素的 $n!$ 会把同值元素互换的等价排法重复计数。除掉每组内部的互换即得多项式系数，组合数是它的两类特例。

with replacement · nᵏ / C(n+k−1, k)

可重复选取

取后放回、可反复取同一个：有序取 k 个有 $n^k$ 种，无序则用隔板法数成 $C(n+k-1,k)$。两者补齐「有序或无序乘放回或不放回」的四种取样模型。

它对应到代码里的什么

嵌套循环 vs 并列分支：乘法原理是嵌套 for（每层 n 次，总 n^层），加法原理是并列的若干独立分支求和。 排列 / 组合枚举：回溯生成 P(n, k) 个排列或 C(n, k) 个子集，是搜索类算法的基本骨架（见 排列生成系列的字典序与回溯）。 复杂度估计：一个「枚举全部子集」的算法是 2ⁿ（即 Σ C(n, k)），「枚举全排列」是 n!——这些量级都出自本系列的计数。

应用 · 二项式定理用在哪里

Pascal 三角与二项式定理不止是恒等式：$(a+b)^n$ 的展开系数一头连着概率里的二项分布，一头给出 $(1+x)^n$ 的线性近似；而系数之间的乘积求和又浓缩成范德蒙德卷积这条恒等式。

binomial distribution · P(X=k) = C(n,k)·pᵏ·qⁿ⁻ᵏ

二项分布

抛 n 次成功概率为 p 的硬币，恰好成功 k 次的概率就是二项式展开的第 k 项：系数数位置，幂次给单一结果的概率，各项相加恒为 1。

linear approximation · (1+x)ⁿ ≈ 1 + nx

线性近似

二项式展开在 x 很小时高次项迅速衰减，丢掉即得 $(1+x)^n \approx 1 + nx$，误差主项随 x 平方收缩。这是泰勒展开的雏形。

Vandermonde · Σⱼ C(m,j)·C(n,k−j) = C(m+n,k)

范德蒙德卷积

从 m + n 个里选 k 个，按「取自前 m 个的个数」分类求和即得范德蒙德卷积。它等价于把两个二项式的乘积展开后对齐同次项的系数。

高中范围到这一组为止

前五组——计数原理、排列、组合、重复的情形、二项式定理的应用——覆盖人教 A 版选择性必修三「计数原理」一章的全部内容，读到范德蒙德卷积即可接上概率与统计（其中容斥原理与错排两页已越出课本，属该组的延伸例子）。其后五组是扩展：鸽巢原理与双计数是竞赛与离散数学的入门，Catalan 数、Stirling 数、整数分拆与十二重计数法是组合学自身的研究对象，生成函数与 Burnside 引理要用到多项式与群作用，末组讲这些量落到代码里的溢出、编号与均匀抽样。扩展五组彼此独立，也不是前五组的前置，按需取用。

存在性 · 数不出来时的下界

计数问的是有多少种，存在性问的是「一定会出现什么」。鸽巢原理只说一句「$n$ 件物品放进 $m$ 个抽屉，必有一屉不少于 $\lceil n/m \rceil$ 件」，却能推出许多按方案数硬算不出来的结论。

pigeonhole · ⌈n/m⌉

鸽巢原理

不算方案数，只断言「一定存在」：$n$ 件物品放进 $m$ 个抽屉，必有一屉不少于 $\lceil n/m \rceil$ 件，且均分即达到这个界。整除对、连续和与 Erdős–Szekeres 定理三个例子说明难点全在如何选巢。

恒等式 · 双射与双计数

组合恒等式有三种读法：代数展开、组合意义上的双计数、以及 Pascal 三角上的一条几何路径。双射把「两个集合一样大」落实成一一对应，双计数则把等式还原成同一批对象被数了两遍。

bijection · 格路 ↔ C(n, k)

双射证明与格路模型

要证两个计数相等，可以不各算一遍再比数值，改为在两类对象之间造一一对应。单调格路先对应到 R/U 串、再对应到位置子集，计数 $C(a+b, a)$ 就此读出。

hockey-stick · 双计数

组合恒等式与双计数

恒等式的代数读法把两边展开对齐，组合读法则让两边数同一批对象。本页取曲棍球棒恒等式、加权和 $\sum k C(n,k)$ 与平方和 $\sum C(n,k)^2$ 三条，每条各给出两种读法。

经典序列 · Catalan、Stirling 与分拆

Catalan 数数括号与格路，Stirling 数数集合划分，分拆数数把整数拆成无序几堆的方式。三者又由球盒模型串在一起：十二重计数法把球与盒是否可辨、映射是否单射或满射交叉成十二格，本系列前面的取样模型只占其中四格。

Catalan · C(2n,n)/(n+1)

Catalan 数

合法括号串、Dyck 路径、二叉树形状与凸多边形三角剖分数出同一列数。反射法把越界格路一一折成短一格的格路，给出闭式 $C_n = C(2n,n)/(n+1)$；按首个括号在哪里闭合分类，则给出卷积递推。

S(n,k) · Bell Bₙ

Stirling 第二类数与 Bell 数

$S(n, k)$ 数的是把 n 个可辨元素分成恰 k 个非空无标号块的方式数，对块数求和即得 Bell 数 $B_n$。它的递推与 Pascal 三角同构，只多出一个系数 k；给块贴上标号又通向满射计数。

partition · p(n) 与共轭

整数分拆与 Ferrers 图

把整数 n 写成若干正整数之和且不计次序，方案数是分拆数 p(n)。Ferrers 图的转置给出共轭分拆这一对合双射，由此得到「恰有 k 个部分」与「最大部分为 k」等势。p(n) 无初等闭式，按最大部分设限的递推与完全背包同形。

twelvefold way · 球盒总表

十二重计数法

$n$ 个球放进 $m$ 个盒，按球可辨与否、盒可辨与否、映射任意或单射或满射交叉出十二格。本系列此前的取样模型、Stirling 数与整数分拆各占其中若干格。

进阶 · 生成函数、对称与渐近

把序列装进多项式，乘法就成了卷积；把对称性交给群作用，「转一圈算同一种」就有了平均不动点的公式；把阶乘交给 Stirling 公式，组合数的量级才看得出来。

OGF · 乘积即卷积

生成函数：把序列装进多项式

把数列装进形式幂级数 $\sum a_k x^k$ 之后，数列的运算变成多项式的运算：乘积对应卷积，递推对应有理式，面额集合的连乘直接给出换钱方案数。

Burnside · 平均不动点数

Burnside 引理与本质不同的染色

项链转一圈能重合的染色算同一种时，$k^n$ 不再是答案。Burnside 引理把等价类个数写成各置换不动点数的平均，$n$ 珠 $k$ 色的项链据此得到 $\frac{1}{n}\sum_{d \mid n} \varphi(n/d) k^d$。

Stirling 公式 · 4ⁿ/√(πn)

阶乘与中心系数的渐近

Stirling 公式 $n! \sim \sqrt{2\pi n}(n/e)^n$ 的相对误差贴着 $1/(12n)$ 下降，代进 $C(2n, n)$ 得 $4^n/\sqrt{\pi n}$。渐近式给出组合数的量级，也给出大 $n$ 下改走对数的理由。

落到代码 · 算得出、编得上号、抽得均匀

公式落到代码会撞上三件事：$C(n, k)$ 按阶乘定义直算会溢出，组合对象与整数编号之间需要双向转换，以及在指数多的方案里等概率取一个。

迭代式 · BigInt · Lucas

组合数的计算与溢出

按 $n!/(k!(n-k)!)$ 直算，中间的阶乘比答案大出几十个数量级。乘除交替的迭代式、只用加法的 Pascal 递推、以及配合 Lucas 定理的模素数计算，给出精确、可控与可扩展的三条求值路线。

rank / unrank · O(k)

组合数系统：给每个组合一个编号

在 $C(n,k)$ 个 $k$ 元子集与 $0$ 到 $C(n,k)-1$ 的整数之间建立双向映射。字典序 rank 按首元素分段累加，组合数系统给出唯一的递减表示，unrank 是一次贪心。

Fisher–Yates · reservoir

均匀随机抽样：洗牌与蓄水池

计数问的是有多少种，抽样问的是怎样在这些方案里等概率取一个。Fisher–Yates 洗牌的均匀性来自选择序列与排列之间的双射；每步与全体交换的写法因 $n^n$ 除不尽 $n!$ 而必然偏斜。数据流长度未知时改用蓄水池抽样。

相关链接

• Combinatorics — Wikipedia en.wikipedia.org 组合学的范围与分支总览。
• Permutation — Wikipedia en.wikipedia.org 排列与 P(n, k) 的定义、记号与推导。
• Combination — Wikipedia en.wikipedia.org 组合、二项式系数 C(n, k) 与其恒等式。
• Pascal's triangle — Wikipedia en.wikipedia.org Pascal 三角的递推、对称性与二项式定理。
• Binomial theorem — Wikipedia en.wikipedia.org (a+b)ⁿ 的展开与二项式系数。