组合数学：修订间差异

2026年9月20日 (日) 00:33的版本

组合数学研究离散对象的计数、排列、选择与结构。其核心不只是套用公式，而是确定什么算同一个对象、是否允许重复、顺序是否重要，以及怎样保证每个对象恰好被计数一次。

加法与乘法原则

若对象被分成互不重叠的几类，总数等于各类数量之和。若一个构造过程有多个阶段，而且对前面每种选择，下一阶段总有固定数量的选择，则总数为各阶段选择数的乘积。

例如从 3 件上衣和 2 条裤子中各选一件，若任意搭配都允许，共有 $3 \times 2 = 6$ 种搭配。若某些搭配被禁止，应重新划分类别或扣除禁例，不能仍机械地相乘。

排列与组合的差别

从 $n$ 个不同对象中不重复地选取 $k$ 个并排序，有 $P (n, k) = n (n - 1) \dots (n - k + 1) = \frac{n!}{(n - k)!} .$ 若不关心顺序，每个选择被上述过程按 $k!$ 种次序重复计算，因此 $(\binom{n}{k}) = \frac{n!}{k! (n - k)!}, 0 \leq k \leq n .$ 这里约定 $0! = 1$ 。例如从 5 人中选主席和秘书，有 20 种结果；只选 2 名不分职务的代表，则有 10 种。是否区分职位直接决定答案。

格点路径把抽象选择画出来

从 $(0, 0)$ 走到 $(3, 2)$ ，每次只能向右或向上走一个单位。每条路径都含 3 次向右、2 次向上；在 5 个步位中选出 2 个放“向上”，路径便唯一确定。

三列两行格点网格，从原点到三二的一条右右上右上路径被标出 — 路径与含三个 R、两个 U 的长度 5 序列一一对应，数量为 C(5,2)=10。

因此路径总数为 $(\binom{5}{2}) = 10$ 。一般从 $(0, 0)$ 到 $(m, n)$ 的这类路径有 $(\binom{m + n}{n})$ 条。若设置障碍点，上述无障碍计数就需要调整。

同一个数量的两种计数

考虑从 $n$ 人中选 $k$ 人，固定其中一人为“指定人”。每个选择要么不包含此人，要么包含此人，所以 $(\binom{n}{k}) = (\binom{n - 1}{k}) + (\binom{n - 1}{k - 1}) .$ 上式取 $1 \leq k \leq n - 1$ ，两端边界值为 $(\binom{n}{0}) = (\binom{n}{n}) = 1$ 。这解释了帕斯卡三角形的递推规则。二项式定理也有类似解释：在 $(x + y)^{n}$ 的 $n$ 个因子中，选 $k$ 个提供 $y$ ，其余提供 $x$ ，于是 $(x + y)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) x^{n - k} y^{k} .$ 系数来自选择次数，不必靠逐项展开猜测。

重复计数、容斥与抽屉原理

两个集合的并集满足 $| A \cup B | = | A | + | B | - | A \cap B |$ 。例如 1 到 30 中能被 2 或 3 整除的整数有 $15 + 10 - 5 = 20$ 个，减去的 5 个是能被 6 整除、此前被算了两次的数。

抽屉原理则说明：把 $N$ 个对象放进 $k$ 个盒子，至少一个盒子有 $⌈ N / k ⌉$ 个对象。例如 13 人中至少两人的出生月份相同，无需假设每个月等可能。它给出必然存在性，通常不告诉究竟是哪两人。

使用计数结果计算概率

只有基本结果等可能时，才能用“有利结果数除以总结果数”计算概率。从重复对象中选择、允许放回抽样或区分顺序，都会改变样本空间。先说清对象与规则，再选计数方法，是避免错用阶乘与组合数的关键。

延伸阅读

Oscar Levin，《Discrete Mathematics: An Open Introduction》第 1 章：加乘原则、二项式系数与组合证明。
概率 · 图论 · 逻辑

@@ 第1行： / 第1行： @@
-组合数学研究离散对象的计数、安排与存在性。排列、组合与递推关系是其中常见的工具。
+组合数学研究离散对象的计数、排列、选择与结构。其核心不只是套用公式，而是确定什么算同一个对象、是否允许重复、顺序是否重要，以及怎样保证每个对象恰好被计数一次。
-== 核心表达 ==
+== 加法与乘法原则 ==
-{{定义|内容=<math display="block">\binom{n}{k}=\frac{n!}{k!(n-k)!}</math>}}
+若对象被分成互不重叠的几类，总数等于各类数量之和。若一个构造过程有多个阶段，而且对前面每种选择，下一阶段总有固定数量的选择，则总数为各阶段选择数的乘积。
-== 直觉与例子 ==
+例如从 3 件上衣和 2 条裤子中各选一件，若任意搭配都允许，共有 <math>3\times2=6</math> 种搭配。若某些搭配被禁止，应重新划分类别或扣除禁例，不能仍机械地相乘。
-从 n 个不同元素中无序选出 k 个元素的选法数为上式，其中 0≤k≤n。例如从 5 人中选出 2 人，共有 10 种选法。
-== 继续阅读 ==
+== 排列与组合的差别 ==
-* [[图论]]
+从 <math>n</math> 个不同对象中不重复地选取 <math>k</math> 个并排序，有
-* [[概率]]
+<math display="block">P(n,k)=n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}.</math>
+若不关心顺序，每个选择被上述过程按 <math>k!</math> 种次序重复计算，因此
+<math display="block">\binom nk=\frac{n!}{k!(n-k)!},\qquad0\le k\le n.</math>
+这里约定 <math>0!=1</math>。例如从 5 人中选主席和秘书，有 20 种结果；只选 2 名不分职务的代表，则有 10 种。是否区分职位直接决定答案。
+== 格点路径把抽象选择画出来 ==
+从 <math>(0,0)</math> 走到 <math>(3,2)</math>，每次只能向右或向上走一个单位。每条路径都含 3 次向右、2 次向上；在 5 个步位中选出 2 个放“向上”，路径便唯一确定。
+[[File:Gezhi-combination-paths.svg|frame|center|alt=三列两行格点网格，从原点到三二的一条右右上右上路径被标出|路径与含三个 R、两个 U 的长度 5 序列一一对应，数量为 C(5,2)=10。]]
+因此路径总数为 <math>\binom52=10</math>。一般从 <math>(0,0)</math> 到 <math>(m,n)</math> 的这类路径有 <math>\binom{m+n}{n}</math> 条。若设置障碍点，上述无障碍计数就需要调整。
+== 同一个数量的两种计数 ==
+考虑从 <math>n</math> 人中选 <math>k</math> 人，固定其中一人为“指定人”。每个选择要么不包含此人，要么包含此人，所以
+<math display="block">\binom nk=\binom{n-1}k+\binom{n-1}{k-1}.</math>
+上式取 <math>1\le k\le n-1</math>，两端边界值为 <math>\binom n0=\binom nn=1</math>。这解释了帕斯卡三角形的递推规则。二项式定理也有类似解释：在 <math>(x+y)^n</math> 的 <math>n</math> 个因子中，选 <math>k</math> 个提供 <math>y</math>，其余提供 <math>x</math>，于是
+<math display="block">(x+y)^n=\sum_{k=0}^n\binom nkx^{n-k}y^k.</math>
+系数来自选择次数，不必靠逐项展开猜测。
+== 重复计数、容斥与抽屉原理 ==
+两个集合的并集满足 <math>|A\cup B|=|A|+|B|-|A\cap B|</math>。例如 1 到 30 中能被 2 或 3 整除的整数有 <math>15+10-5=20</math> 个，减去的 5 个是能被 6 整除、此前被算了两次的数。
+抽屉原理则说明：把 <math>N</math> 个对象放进 <math>k</math> 个盒子，至少一个盒子有 <math>\lceil N/k\rceil</math> 个对象。例如 13 人中至少两人的出生月份相同，无需假设每个月等可能。它给出必然存在性，通常不告诉究竟是哪两人。
+== 使用计数结果计算概率 ==
+只有基本结果等可能时，才能用“有利结果数除以总结果数”计算概率。从重复对象中选择、允许放回抽样或区分顺序，都会改变样本空间。先说清对象与规则，再选计数方法，是避免错用阶乘与组合数的关键。
+== 延伸阅读 ==
+* [https://discrete.openmathbooks.org/dmoi3.html Oscar Levin，《Discrete Mathematics: An Open Introduction》第 1 章]：加乘原则、二项式系数与组合证明。
+* [[概率]] · [[图论]] · [[逻辑]]
 [[分类:离散数学]]