组合数学：修订间差异

2026年9月20日 (日) 10:06的最新版本

组合数学（combinatorics）研究离散对象怎样选择、排列、分配和组织，以及满足条件的结果共有多少种。一次计数既要说明所数的对象，也要说明什么时候把两种描述看成同一个结果。

例如，从 5 人中选主席和秘书，与从 5 人中选两名不分职务的代表，答案就不同。甲任主席、乙任秘书，与乙任主席、甲任秘书是两套任职方案；作为两名代表，却是同一个二人组。

从分步选择到排列

先选主席，有 5 种选择；对每种主席选择，秘书都可从余下 4 人中选。因此共有 $5 \cdot 4 = 20$ 套方案。这里每套方案由前后两步唯一确定，这就是乘法原理。

同样，从 n 个不同对象中依次选 k 个，不重复使用对象，第一步有 n 种，第二步有 n−1 种，直到第 k 步有 n−k+1 种。带顺序的选取称为排列，数量为 $P (n, k) = n (n - 1) \dots (n - k + 1) = \frac{n!}{(n - k)!} .$ 这里 n、k 是整数， $0 \leq k \leq n$ ； $n! = n (n - 1) \dots 1$ 叫阶乘，约定 $0! = 1$ 。

乘法原理所要求的是每个阶段有确定的分支数。例如 3 件上衣与 2 条裤子，任意搭配都可用时有 6 套；若有一件上衣只能配其中一条裤子，就应分开计算为 $1 + 2 + 2 = 5$ 套。这里按上衣分成互不重叠的三类，再相加，是加法原理。

不计顺序时，为什么要除

仍从 5 人中选 2 人。前面的 20 套任职方案里，每个二人组都出现两次：两人交换职位得到另一种排列。因此不分职务的代表组只有 $20 / 2 = 10$ 个。

一般选出 k 人后，这 k 人可以排成 $k!$ 种次序。所有有序选取按“选中了哪些人”分成等大的组，每组恰有 k! 个结果。忽略顺序的选取称为组合，数量记为 $(\binom{n}{k}) = \frac{n!}{k! (n - k)!}, 0 \leq k \leq n .$ 例如 $(\binom{5}{2}) = 10$ 。选 0 个对象时只得到空集一种结果，选全部 n 个时也只有一种，故 $(\binom{n}{0}) = (\binom{n}{n}) = 1$ 。

取补集还给出一个对应：每种选 k 个的方案，恰好留下 n−k 个未选对象。因此 $(\binom{n}{k}) = (\binom{n}{n - k}) .$ 这条等式来自同一选择的两种描述。

委员会有条件时，怎样避免漏计和重计

现有 4 名甲组成员、3 名乙组成员，7 人各不相同。要选 3 人，且至少有一名乙组成员。

可以先数全部三人组，再去掉全部来自甲组的情况： $(\binom{7}{3}) - (\binom{4}{3}) = 35 - 4 = 31.$ 也可以按乙组人数分类。恰有 1 名乙组时，选法为 $(\binom{3}{1}) (\binom{4}{2}) = 18$ ；恰有 2 名时为 $(\binom{3}{2}) (\binom{4}{1}) = 12$ ；恰有 3 名时只有 1 种。三类不会重叠，总数为 $18 + 12 + 1 = 31$ 。

为什么不先选一名乙组成员，再从剩下 6 人选 2 人？这会算出 $3 (\binom{6}{2}) = 45$ 。含两名乙组的委员会，其中任何一位都能被当作“先选的人”，所以被算了两次；含三名乙组的被算了三次。重复次数不一样，便不能通过统一除以一个数恢复答案。

若题目还要求指定一位主席，每个合法委员会都恰有 3 种选择，结果为 $31 \cdot 3 = 93$ 。若主席必须来自乙组，则前面的三类分别有 1、2、3 种主席选择，总数变为 $18 \cdot 1 + 12 \cdot 2 + 1 \cdot 3 = 45.$ 这次 45 数的是“委员会加乙组主席”，每个结果确实包含一个被特别指定的乙组成员。

把选择画成格点路径

从 $(0, 0)$ 到 $(3, 2)$ ，每次只能向右或向上走一个单位。图中金色路线先右、右，再上、右、上，记录成 $R R U R U$ ；R 表示右移，U 表示上移。

三列两行网格，金色箭头从原点依次右右上右上，到达三二 — 每条路径由五个步位组成，选择其中两个作为向上步，便确定整条路线。

到达终点总共需要 3 次右移、2 次上移。只要在 5 个位置中选出两个放 U，其余放 R，就唯一确定一条路径；任何允许的路径也都产生这样一组位置。因此路径数为 $(\binom{5}{2}) = 10.$ 一般从 $(0, 0)$ 到 $(m, n)$ 的同类路径，需要 m+n 步，其中选 n 步向上，故有 $(\binom{m + n}{n})$ 条。

这个对应还能处理障碍。若本例禁止经过 $(1, 1)$ ，先数经过该点的路线：到它需要一右一上，有 $(\binom{2}{1}) = 2$ 种；从它到终点需要两右一上，有 $(\binom{3}{1}) = 3$ 种。每条经过它的路线唯一分成这两段，故共有 6 条应被排除，留下 $10 - 6 = 4$ 条。

组合数之间为什么相加

从 n 人中选 k 人，固定某一人。每个组合要么不选此人，要么选此人。前一类从剩下 n−1 人选 k 人；后一类已选一人，还需从剩下的人选 k−1 人。因此 $(\binom{n}{k}) = (\binom{n - 1}{k}) + (\binom{n - 1}{k - 1}), 1 \leq k \leq n - 1.$ 加上两端的 1，就得到杨辉三角中“一个数等于上方相邻两数之和”的规则。

组合数也出现在二项式展开中。例如 $(x + y)^{3}$ 的每一项，都是从三个因子中各取 x 或 y 后相乘。要得到 $x^{2} y$ ，需选出一个因子提供 y，有 $(\binom{3}{1}) = 3$ 种，因此它的系数为 3。

一般在 n 个因子中选 k 个提供 y，其余提供 x，便有 $(x + y)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) x^{n - k} y^{k} .$ 这里的系数记录同一种乘积由多少次选择产生，称为二项式定理。

相同物品分到不同盒子

把 6 个相同球分到 3 个有标号的盒子，允许空盒。若三个盒子中的球数分别为 $x_{1}, x_{2}, x_{3}$ ，问题就是数出所有非负整数解 $x_{1} + x_{2} + x_{3} = 6.$ 用 6 个星号表示球、2 条隔板区分盒子。例如“★★｜｜★★★★”表示 $(2, 0, 4)$ 。隔板可以相邻，也可以位于两端，分别表示中间或端部的盒子为空。

每个分配恰对应一个由 6 个星号和 2 条隔板组成的串，反之亦然。只需从 8 个位置中选出 2 个放隔板，所以有 $(\binom{8}{2}) = 28$ 种分法。这叫隔板法。一般 n 个相同物品分到 $k \geq 1$ 个不同盒子，需要 n 个星号和 k−1 条隔板，结果为 $(\binom{n + k - 1}{k - 1})$ 。

如果球彼此可区分，每个球有 3 个盒子可选，结果是 $3^{6}$ ，不是 28。若盒子没有标号， $(2, 0, 4)$ 的不同排列又可能表示同一种分配；各类分配的重复次数不一致，也不能把 28 直接除以 $3!$ 。

加上下界和上界

若每盒至少一个，先给每盒放一个，剩下 3 个球自由分配。令 $y_{i} = x_{i} - 1$ ，就有 $y_{1} + y_{2} + y_{3} = 3$ ，各项非负，故分法为 $(\binom{5}{2}) = 10$ 。

下图上排展示 (2,0,4) 的编码，中间相邻的两条隔板表示第二个盒子为空。下排展示每盒先放一个球的做法：金色球是固定分配，剩余青色球才需要重新计数；(1,2,3) 因而对应剩余量 (0,1,2)。

上排六个球与两条相邻隔板表示二零四，下排三个金色预放球与三个剩余球表示一二三减下界后为零一二 — 隔板位置记录分配；扣除下界把至少一个转为允许空盒。

若允许空盒，但每盒至多 3 个，就从原来的 28 种中排除某盒至少 4 个的情况。固定这一个盒子先放 4 个，剩下 2 个任意分，有 $(\binom{4}{2}) = 6$ 种。共有 3 个盒子可以超限，而且 6 个球不可能同时使两盒各至少 4 个，所以这些坏情况不重叠。答案为 $28 - 3 \cdot 6 = 10$ 。

若同时要求每盒至少 1 个、至多 3 个，先减去下界后，各 $y_{i}$ 在 0 到 2 之间，总和为 3。不设上界时有 10 种；超限只能是某项为 3、其余为 0，共 3 种。因此答案为 $10 - 3 = 7$ 。可以直接列出检查： $(2, 2, 2)$ 一种，加上 $(1, 2, 3)$ 的六种排列。

一般下界不必相同。若第 i 盒至少放 $ℓ_{i}$ 个，先扣去这些固定份额，再对剩余量使用隔板法；若还有限定上界，也须一并减去同样的份额。

用多项式记下每个盒子的选择

单盒允许放 1、2、3 个球，可以记成 $z + z^{2} + z^{3}$ 。z 的指数记录球数。三个不同盒子逐个选择，对应乘积 $(z + z^{2} + z^{3})^{3} .$ 相乘时指数相加，因此六次项的系数就是总共放 6 个球的分法数。只有指数 $(1, 2, 3)$ 的六种排列与 $(2, 2, 2)$ 能凑成 6，所以系数为 7。

这种把“大小”记在指数、“数量”记在系数中的方法叫生成函数。这里它只是一个有限多项式，乘法的每一次取项都对应一个实际分配，不涉及无穷级数的收敛问题。

有重叠的类别怎样相加：容斥

在 1 到 30 中，2 的倍数有 15 个，3 的倍数有 10 个。若直接相加，6 的倍数会被数两次；这样的数有 5 个。因此能被 2 或 3 整除的数共有 $15 + 10 - 5 = 20.$ 用集合记为 $| A \cup B | = | A | + | B | - | A \cap B | .$

三个集合时，先加各自大小，再减三组两两交集。属于三重交集的对象先被数三次，又被减三次，变成零次，因此要补回来： $\begin{matrix} | A \cup B \cup C | = & | A | + | B | + | C | \\ - | A \cap B | - | A \cap C | - | B \cap C | \\ + | A \cap B \cap C | . \end{matrix}$ 逐个检查属于一个、两个、三个集合的元素，都恰好保留一次。这就是容斥原理。

例如将三个不同字母重新放进三个有标号的位置，要求没有字母留在原位。全部排列有 6 个。令 A、B、C 分别表示各字母仍在原位的坏情况，每类有 2 个排列；固定任意两个字母会使第三个也固定，因此各两两交集及三重交集都只含原排列一个。坏排列共有 $6 - 3 + 1 = 4$ 个，合法排列便为 $6 - 4 = 2$ 个，恰是两种循环移位。

把大问题拆成较小问题

用长度为 1 或 2 的小砖铺满一行长度为 n 的木板，砖沿木板方向放置，不留空隙。记铺法数为 $a_{n}$ 。

观察最后一块砖：若长 1，前面剩下长度 n−1 的木板，有 $a_{n - 1}$ 种铺法；若长 2，前面剩下 n−2，有 $a_{n - 2}$ 种。两类互不重叠又覆盖全部铺法，因此 $a_{n} = a_{n - 1} + a_{n - 2} (n \geq 2) .$ 空木板有“不放砖”一种铺法，故 $a_{0} = 1$ ；长度 1 只有一块短砖，故 $a_{1} = 1$ 。依次得到 $a_{2} = 2$ 、 $a_{3} = 3$ 、 $a_{4} = 5$ 。初值和递推式合在一起，才确定整列答案。

限制位置也可以转成已经解决的分配问题。八位二进制串恰含三个 1，有 $(\binom{8}{3}) = 56$ 个。若 1 不能相邻，先在相邻两个 1 之间各放一个必需的 0；五个 0 已用掉两个，剩下三个可分到两端与两个内部间隙，共四个有标号的空隙。隔板法给出 $(\binom{6}{3}) = 20$ 种。把这些零重新放回各空隙，就唯一恢复原串。

只问必然存在，不必逐一数出

13 人分到 12 个出生月份，若每个月至多一人，总人数最多为 12，与 13 矛盾。因此至少有两人的出生月份相同。这个结论与月份是否等可能无关，称为抽屉原理。

一般把 N 个对象放入正整数 k 个盒子，至少一盒的数量不小于 $⌈ N / k ⌉$ ，其中符号表示向上取整。若每盒数量都少于这个整数，总和便小于 N。

计数用于概率时则要多一个条件：只有基本结果等可能，才能直接用“有利结果数除以全部结果数”。例如选委员会时，若所有三人组等可能，上面至少含一名乙组的概率才是 $31 / 35$ 。指定某人必选，会改变选择机制和样本空间。

历史

二项式系数表在不同数学传统中出现过。杨辉 1261 年《详解九章算法》记述了相关数表，并引用贾宪的方法；贾宪的相关原著已经散佚，部分内容由杨辉的记述保存。MacTutor：杨辉介绍了这些文献关系。

今天常用“杨辉三角”或“Pascal 三角”称呼这一数表。它把多项式展开、组合选择和格点路径联系到一起：同样的数字可以来自不同问题，而一一对应或分类计数解释了它们为何相同。

从“数出多少”到“必有一个”

抽屉原理用总数证明某一类必有重复。它不要求列出全部对象：例如 n 个整数的 n+1 个前缀和只有 n 种余数，因此存在非空连续一段，其和能被 n 整除。该条目逐步说明如何把“连续段”转成两个前缀的差，以及如何选择分类规则。

参考资料

Oscar Levin：二项式系数。
Oscar Levin，Discrete Mathematics: An Open Introduction：计数、递推关系及生成函数。
MacTutor：杨辉。
相关条目：集合、概率、图论、逻辑。

@@ 第1行： / 第1行： @@
-组合数学研究离散对象的计数、安排与存在性。排列、组合与递推关系是其中常见的工具。
+'''组合数学'''（combinatorics）研究离散对象怎样选择、排列、分配和组织，以及满足条件的结果共有多少种。一次计数既要说明所数的对象，也要说明什么时候把两种描述看成同一个结果。
-== 核心表达 ==
+例如，从 5 人中选主席和秘书，与从 5 人中选两名不分职务的代表，答案就不同。甲任主席、乙任秘书，与乙任主席、甲任秘书是两套任职方案；作为两名代表，却是同一个二人组。
-{{定义|内容=<math display="block">\binom{n}{k}=\frac{n!}{k!(n-k)!}</math>}}
-== 直觉与例子 ==
+== 从分步选择到排列 ==
-从 n 个不同元素中无序选出 k 个元素的选法数为上式，其中 0≤k≤n。例如从 5 人中选出 2 人，共有 10 种选法。
+先选主席，有 5 种选择；对每种主席选择，秘书都可从余下 4 人中选。因此共有 <math>5\cdot4=20</math> 套方案。这里每套方案由前后两步唯一确定，这就是'''乘法原理'''。
-== 继续阅读 ==
+同样，从 n 个不同对象中依次选 k 个，不重复使用对象，第一步有 n 种，第二步有 n−1 种，直到第 k 步有 n−k+1 种。带顺序的选取称为'''排列'''，数量为
-* [[图论]]
+<math display="block">P(n,k)=n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}.</math>
-* [[概率]]
+这里 n、k 是整数，<math>0\le k\le n</math>；<math>n!=n(n-1)\cdots1</math> 叫阶乘，约定 <math>0!=1</math>。
+乘法原理所要求的是每个阶段有确定的分支数。例如 3 件上衣与 2 条裤子，任意搭配都可用时有 6 套；若有一件上衣只能配其中一条裤子，就应分开计算为 <math>1+2+2=5</math> 套。这里按上衣分成互不重叠的三类，再相加，是'''加法原理'''。
+== 不计顺序时，为什么要除 ==
+仍从 5 人中选 2 人。前面的 20 套任职方案里，每个二人组都出现两次：两人交换职位得到另一种排列。因此不分职务的代表组只有 <math>20/2=10</math> 个。
+一般选出 k 人后，这 k 人可以排成 <math>k!</math> 种次序。所有有序选取按“选中了哪些人”分成等大的组，每组恰有 k! 个结果。忽略顺序的选取称为'''组合'''，数量记为
+<math display="block">\binom nk=\frac{n!}{k!(n-k)!},\qquad0\le k\le n.</math>
+例如 <math>\binom52=10</math>。选 0 个对象时只得到空集一种结果，选全部 n 个时也只有一种，故 <math>\binom n0=\binom nn=1</math>。
+取补集还给出一个对应：每种选 k 个的方案，恰好留下 n−k 个未选对象。因此
+<math display="block">\binom nk=\binom n{n-k}.</math>
+这条等式来自同一选择的两种描述。
+== 委员会有条件时，怎样避免漏计和重计 ==
+现有 4 名甲组成员、3 名乙组成员，7 人各不相同。要选 3 人，且至少有一名乙组成员。
+可以先数全部三人组，再去掉全部来自甲组的情况：
+<math display="block">\binom73-\binom43=35-4=31.</math>
+也可以按乙组人数分类。恰有 1 名乙组时，选法为 <math>\binom31\binom42=18</math>；恰有 2 名时为 <math>\binom32\binom41=12</math>；恰有 3 名时只有 1 种。三类不会重叠，总数为 <math>18+12+1=31</math>。
+为什么不先选一名乙组成员，再从剩下 6 人选 2 人？这会算出 <math>3\binom62=45</math>。含两名乙组的委员会，其中任何一位都能被当作“先选的人”，所以被算了两次；含三名乙组的被算了三次。重复次数不一样，便不能通过统一除以一个数恢复答案。
+若题目还要求指定一位主席，每个合法委员会都恰有 3 种选择，结果为 <math>31\cdot3=93</math>。若主席必须来自乙组，则前面的三类分别有 1、2、3 种主席选择，总数变为
+<math display="block">18\cdot1+12\cdot2+1\cdot3=45.</math>
+这次 45 数的是“委员会加乙组主席”，每个结果确实包含一个被特别指定的乙组成员。
+== 把选择画成格点路径 ==
+从 <math>(0,0)</math> 到 <math>(3,2)</math>，每次只能向右或向上走一个单位。图中金色路线先右、右，再上、右、上，记录成 <math>RRURU</math>；R 表示右移，U 表示上移。
+[[File:Gezhi-combination-paths-theme.svg|frame|center|alt=三列两行网格，金色箭头从原点依次右右上右上，到达三二|每条路径由五个步位组成，选择其中两个作为向上步，便确定整条路线。]]
+到达终点总共需要 3 次右移、2 次上移。只要在 5 个位置中选出两个放 U，其余放 R，就唯一确定一条路径；任何允许的路径也都产生这样一组位置。因此路径数为
+<math display="block">\binom52=10.</math>
+一般从 <math>(0,0)</math> 到 <math>(m,n)</math> 的同类路径，需要 m+n 步，其中选 n 步向上，故有 <math>\binom{m+n}{n}</math> 条。
+这个对应还能处理障碍。若本例禁止经过 <math>(1,1)</math>，先数经过该点的路线：到它需要一右一上，有 <math>\binom21=2</math> 种；从它到终点需要两右一上，有 <math>\binom31=3</math> 种。每条经过它的路线唯一分成这两段，故共有 6 条应被排除，留下 <math>10-6=4</math> 条。
+== 组合数之间为什么相加 ==
+从 n 人中选 k 人，固定某一人。每个组合要么不选此人，要么选此人。前一类从剩下 n−1 人选 k 人；后一类已选一人，还需从剩下的人选 k−1 人。因此
+<math display="block">\binom nk=\binom{n-1}k+\binom{n-1}{k-1},
+\qquad1\le k\le n-1.</math>
+加上两端的 1，就得到杨辉三角中“一个数等于上方相邻两数之和”的规则。
+组合数也出现在二项式展开中。例如 <math>(x+y)^3</math> 的每一项，都是从三个因子中各取 x 或 y 后相乘。要得到 <math>x^2y</math>，需选出一个因子提供 y，有 <math>\binom31=3</math> 种，因此它的系数为 3。
+一般在 n 个因子中选 k 个提供 y，其余提供 x，便有
+<math display="block">(x+y)^n=\sum_{k=0}^n\binom nkx^{n-k}y^k.</math>
+这里的系数记录同一种乘积由多少次选择产生，称为'''二项式定理'''。
+== 相同物品分到不同盒子 ==
+把 6 个相同球分到 3 个有标号的盒子，允许空盒。若三个盒子中的球数分别为 <math>x_1,x_2,x_3</math>，问题就是数出所有非负整数解
+<math display="block">x_1+x_2+x_3=6.</math>
+用 6 个星号表示球、2 条隔板区分盒子。例如“★★｜｜★★★★”表示 <math>(2,0,4)</math>。隔板可以相邻，也可以位于两端，分别表示中间或端部的盒子为空。
+每个分配恰对应一个由 6 个星号和 2 条隔板组成的串，反之亦然。只需从 8 个位置中选出 2 个放隔板，所以有
+<math display="block">\binom82=28</math>
+种分法。这叫'''隔板法'''。一般 n 个相同物品分到 <math>k\ge1</math> 个不同盒子，需要 n 个星号和 k−1 条隔板，结果为 <math>\binom{n+k-1}{k-1}</math>。
+如果球彼此可区分，每个球有 3 个盒子可选，结果是 <math>3^6</math>，不是 28。若盒子没有标号，<math>(2,0,4)</math> 的不同排列又可能表示同一种分配；各类分配的重复次数不一致，也不能把 28 直接除以 <math>3!</math>。
+=== 加上下界和上界 ===
+若每盒至少一个，先给每盒放一个，剩下 3 个球自由分配。令 <math>y_i=x_i-1</math>，就有 <math>y_1+y_2+y_3=3</math>，各项非负，故分法为 <math>\binom52=10</math>。
+下图上排展示 (2,0,4) 的编码，中间相邻的两条隔板表示第二个盒子为空。下排展示每盒先放一个球的做法：金色球是固定分配，剩余青色球才需要重新计数；(1,2,3) 因而对应剩余量 (0,1,2)。
+[[File:Gezhi-teaching-foundation-combinatorics-bars.svg|frame|center|alt=上排六个球与两条相邻隔板表示二零四，下排三个金色预放球与三个剩余球表示一二三减下界后为零一二|隔板位置记录分配；扣除下界把至少一个转为允许空盒。]]
+若允许空盒，但每盒至多 3 个，就从原来的 28 种中排除某盒至少 4 个的情况。固定这一个盒子先放 4 个，剩下 2 个任意分，有 <math>\binom42=6</math> 种。共有 3 个盒子可以超限，而且 6 个球不可能同时使两盒各至少 4 个，所以这些坏情况不重叠。答案为 <math>28-3\cdot6=10</math>。
+若同时要求每盒至少 1 个、至多 3 个，先减去下界后，各 <math>y_i</math> 在 0 到 2 之间，总和为 3。不设上界时有 10 种；超限只能是某项为 3、其余为 0，共 3 种。因此答案为 <math>10-3=7</math>。可以直接列出检查：<math>(2,2,2)</math> 一种，加上 <math>(1,2,3)</math> 的六种排列。
+一般下界不必相同。若第 i 盒至少放 <math>\ell_i</math> 个，先扣去这些固定份额，再对剩余量使用隔板法；若还有限定上界，也须一并减去同样的份额。
+=== 用多项式记下每个盒子的选择 ===
+单盒允许放 1、2、3 个球，可以记成 <math>z+z^2+z^3</math>。z 的指数记录球数。三个不同盒子逐个选择，对应乘积
+<math display="block">(z+z^2+z^3)^3.</math>
+相乘时指数相加，因此六次项的系数就是总共放 6 个球的分法数。只有指数 <math>(1,2,3)</math> 的六种排列与 <math>(2,2,2)</math> 能凑成 6，所以系数为 7。
+这种把“大小”记在指数、“数量”记在系数中的方法叫'''生成函数'''。这里它只是一个有限多项式，乘法的每一次取项都对应一个实际分配，不涉及无穷级数的收敛问题。
+== 有重叠的类别怎样相加：容斥 ==
+在 1 到 30 中，2 的倍数有 15 个，3 的倍数有 10 个。若直接相加，6 的倍数会被数两次；这样的数有 5 个。因此能被 2 或 3 整除的数共有
+<math display="block">15+10-5=20.</math>
+用集合记为
+<math display="block">|A\cup B|=|A|+|B|-|A\cap B|.</math>
+三个集合时，先加各自大小，再减三组两两交集。属于三重交集的对象先被数三次，又被减三次，变成零次，因此要补回来：
+<math display="block">\begin{aligned}
+|A\cup B\cup C|={}&|A|+|B|+|C|\\
+&-|A\cap B|-|A\cap C|-|B\cap C|\\
+&+|A\cap B\cap C|.
+\end{aligned}</math>
+逐个检查属于一个、两个、三个集合的元素，都恰好保留一次。这就是'''容斥原理'''。
+例如将三个不同字母重新放进三个有标号的位置，要求没有字母留在原位。全部排列有 6 个。令 A、B、C 分别表示各字母仍在原位的坏情况，每类有 2 个排列；固定任意两个字母会使第三个也固定，因此各两两交集及三重交集都只含原排列一个。坏排列共有 <math>6-3+1=4</math> 个，合法排列便为 <math>6-4=2</math> 个，恰是两种循环移位。
+== 把大问题拆成较小问题 ==
+用长度为 1 或 2 的小砖铺满一行长度为 n 的木板，砖沿木板方向放置，不留空隙。记铺法数为 <math>a_n</math>。
+观察最后一块砖：若长 1，前面剩下长度 n−1 的木板，有 <math>a_{n-1}</math> 种铺法；若长 2，前面剩下 n−2，有 <math>a_{n-2}</math> 种。两类互不重叠又覆盖全部铺法，因此
+<math display="block">a_n=a_{n-1}+a_{n-2}\qquad(n\ge2).</math>
+空木板有“不放砖”一种铺法，故 <math>a_0=1</math>；长度 1 只有一块短砖，故 <math>a_1=1</math>。依次得到 <math>a_2=2</math>、<math>a_3=3</math>、<math>a_4=5</math>。初值和递推式合在一起，才确定整列答案。
+限制位置也可以转成已经解决的分配问题。八位二进制串恰含三个 1，有 <math>\binom83=56</math> 个。若 1 不能相邻，先在相邻两个 1 之间各放一个必需的 0；五个 0 已用掉两个，剩下三个可分到两端与两个内部间隙，共四个有标号的空隙。隔板法给出 <math>\binom63=20</math> 种。把这些零重新放回各空隙，就唯一恢复原串。
+== 只问必然存在，不必逐一数出 ==
+人分到 12 个出生月份，若每个月至多一人，总人数最多为 12，与 13 矛盾。因此至少有两人的出生月份相同。这个结论与月份是否等可能无关，称为'''抽屉原理'''。
+一般把 N 个对象放入正整数 k 个盒子，至少一盒的数量不小于 <math>\lceil N/k\rceil</math>，其中符号表示向上取整。若每盒数量都少于这个整数，总和便小于 N。
+计数用于[[概率]]时则要多一个条件：只有基本结果等可能，才能直接用“有利结果数除以全部结果数”。例如选委员会时，若所有三人组等可能，上面至少含一名乙组的概率才是 <math>31/35</math>。指定某人必选，会改变选择机制和样本空间。
+== 历史 ==
+二项式系数表在不同数学传统中出现过。杨辉 1261 年《详解九章算法》记述了相关数表，并引用贾宪的方法；贾宪的相关原著已经散佚，部分内容由杨辉的记述保存。[https://mathshistory.st-andrews.ac.uk/Biographies/Yang_Hui/ MacTutor：杨辉]介绍了这些文献关系。
+今天常用“杨辉三角”或“Pascal 三角”称呼这一数表。它把多项式展开、组合选择和格点路径联系到一起：同样的数字可以来自不同问题，而一一对应或分类计数解释了它们为何相同。
+== 从“数出多少”到“必有一个” ==
+[[抽屉原理]]用总数证明某一类必有重复。它不要求列出全部对象：例如 n 个整数的 n+1 个前缀和只有 n 种余数，因此存在非空连续一段，其和能被 n 整除。该条目逐步说明如何把“连续段”转成两个前缀的差，以及如何选择分类规则。
+== 参考资料 ==
+* [https://discrete.openmathbooks.org/dmoi3/sec_counting-binom.html Oscar Levin：二项式系数]。
+* [https://discrete.openmathbooks.org/dmoi3.html Oscar Levin，Discrete Mathematics: An Open Introduction]：计数、递推关系及生成函数。
+* [https://mathshistory.st-andrews.ac.uk/Biographies/Yang_Hui/ MacTutor：杨辉]。
+* 相关条目：[[集合]]、[[概率]]、[[图论]]、[[逻辑]]。
 [[分类:离散数学]]