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

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

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

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

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

counting · 乘法 / 加法原理

两条计数原理：分步相乘、分类相加

一件事若需依次完成若干步，总方案数是各步方案数的乘积（乘法原理）；若可归入互斥的若干类、每类独立完成，总方案数是各类方案数的和（加法原理）。用一棵选择树看「分步」如何把方案数逐层翻倍，再对照「分类」为何是相加。

排列 · 有序地取 k 个

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

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

排列 P(n, k)：有序地取 k 个

从 n 个不同元素里有序取 k 个：第一格有 n 种选法，选定后第二格剩 n-1 种，依次到第 k 格。这些方案数相乘即 P(n, k) = n·(n-1)···(n-k+1) = n! / (n-k)！。拖动 n、k，看空位方案数逐格收缩，并枚举出全部排列。

constrained · 插空法 / 捆绑法

带约束的排列：插空法与捆绑法

排列常带附加条件。不相邻用插空法：先排 k 个骨架(k!)，其间与两端得 k+1 个空隙，把 m 个受约束元素有序插入互不相同的空隙(P(k+1, m))，天然隔开。相邻用对偶的捆绑法：把 m 个捆成一个整体与其余一起排((k+1)!)，捆内再排 m!。两者都化归为全排列加一步选序。

组合 · 无序地取 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 个时不计次序，同一组元素的 k! 种排列都算作同一个组合。于是 C(n, k) = P(n, k) / k! = n! / (k!·(n-k)!)。demo 并排显示排列与组合的枚举，看 k! 倍的顺序如何被折叠，并验证对称性 C(n, k) = C(n, n-k)。

Pascal triangle · 二项式定理

Pascal 三角与二项式定理

把 C(n, k) 排成三角形，每个数等于它上方两数之和：C(n, k) = C(n-1, k-1) + C(n-1, k)。这条递推正是二项式定理 (a+b)ⁿ = Σ C(n, k)·aⁿ⁻ᵏ·bᵏ 的系数来源。点击任一格，看它由上一行哪两格相加、又对应展开式的哪一项。

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

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

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

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

multiset permutation · n! / ∏ nᵢ!

多重集排列：当源自带重复元素

源是多重集（如 {A, A, B, C}）时，朴素的 n! 会把「同值元素互换」的等价排法重复计数。除掉每组内部的 nᵢ！种互换，得可区分排列 n! / (n₁!·n₂!···n_r!)（多项式系数）。组合 C(n, k) 正是它「选中 / 没选」的两类特例。

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

可重复选取：取时放回

源仍是 n 个不同类型，但取后放回、可反复取同一个。有序取 k 个有 nᵏ 种（每格独立）；无序则用隔板法（stars and bars）数成 C(n+k-1, k)。这两格与排列、组合一起，凑成「有序 / 无序 × 放回 / 不放回」的四种取样模型。

它对应到代码里的什么

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

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

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

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

二项分布：(p+q)ⁿ 的每一项都是一个概率

抛 n 次成功概率为 p 的硬币，恰好成功 k 次的概率是 C(n, k)·pᵏ·qⁿ⁻ᵏ——正是 (p+q)ⁿ 展开式的第 k 项。系数 C(n, k) 数「哪 k 次成功」的位置，pᵏ·qⁿ⁻ᵏ 是单一结果的概率。拖动 n、p 看柱状图，所有柱高相加恒为 (p+q)ⁿ = 1。

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

近似计算：x 很小时 (1+x)ⁿ ≈ 1 + nx

(1+x)ⁿ = 1 + n·x + C(n, 2)·x² + …，x 很小时高次项迅速衰减，丢掉即得线性近似 (1+x)ⁿ ≈ 1 + n·x，误差主项是 C(n, 2)·x²。对照精确值、一阶与二阶近似的误差，看它随 x 平方收缩——这也是泰勒展开（binomial series）的雏形。

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

范德蒙德卷积：两行相乘配出第三行

从 m + n 个里选 k 个（C(m+n, k)），按「取自前 m 个的个数 j」分类：C(m, j)·C(n, k-j) 求和即得，这就是范德蒙德卷积 Σⱼ C(m, j)·C(n, k-j) = C(m+n, k)。它等价于把 (1+t)^m·(1+t)ⁿ = (1+t)^m+n 两边 tᵏ 的系数对齐。

相关链接

• 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)ⁿ 的展开与二项式系数。