组合数学：修订间差异

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）研究离散对象怎样选择、排列、分配和组织，以及满足条件的结果共有多少种。一次计数既要说明所数的对象，也要说明什么时候把两种描述看成同一个结果。
-英文名称：Combinatorics。
+例如，从 5 人中选主席和秘书，与从 5 人中选两名不分职务的代表，答案就不同。甲任主席、乙任秘书，与乙任主席、甲任秘书是两套任职方案；作为两名代表，却是同一个二人组。
-== English overview ==
+== 从分步选择到排列 ==
-<div lang="en" class="math-english-summary">
+先选主席，有 5 种选择；对每种主席选择，秘书都可从余下 4 人中选。因此共有 <math>5\cdot4=20</math> 套方案。这里每套方案由前后两步唯一确定，这就是'''乘法原理'''。
-Combinatorics studies discrete arrangements, selections, and structures. A counting problem is not solved merely by recognizing a familiar formula: one must specify the objects, decide whether order and repetition matter, and explain why each valid outcome is counted exactly once. Addition and multiplication provide basic constructions; bijections and double counting explain identities by comparing descriptions of the same collection.
-This article develops permutations, combinations, the binomial theorem, inclusion–exclusion, and the pigeonhole principle through complete examples. It derives the formula for choosing a subset by counting ordered selections and then removing the repeated descriptions. Further examples cover distributing identical objects into distinct boxes, counting selections with restrictions, and building recurrences. Generating functions encode counts as coefficients, but the variables in such expressions may be formal bookkeeping devices rather than measured quantities. Historical discussion distinguishes the broad development of counting methods from the naming of particular arrays and formulas. In applications, combinatorial counts can support probability calculations only when the underlying sample outcomes and their weights are specified. Large counts also do not by themselves establish computational difficulty; an algorithm may reason about an entire family without enumerating every member.
+同样，从 n 个不同对象中依次选 k 个，不重复使用对象，第一步有 n 种，第二步有 n−1 种，直到第 k 步有 n−k+1 种。带顺序的选取称为'''排列'''，数量为
-</div>
+<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> 套。这里按上衣分成互不重叠的三类，再相加，是'''加法原理'''。
-若对象被分成互不重叠的几类，总数等于各类数量之和。若一个构造过程有多个阶段，而且对前面每种选择，下一阶段总有固定数量的选择，则总数为各阶段选择数的乘积。
-例如从 3 件上衣和 2 条裤子中各选一件，若任意搭配都允许，共有 <math>3\times2=6</math> 种搭配。若某些搭配被禁止，应重新划分类别或扣除禁例，不能仍机械地相乘。
+== 不计顺序时，为什么要除 ==
+仍从 5 人中选 2 人。前面的 20 套任职方案里，每个二人组都出现两次：两人交换职位得到另一种排列。因此不分职务的代表组只有 <math>20/2=10</math> 个。
-== 排列与组合的差别 ==
+一般选出 k 人后，这 k 人可以排成 <math>k!</math> 种次序。所有有序选取按“选中了哪些人”分成等大的组，每组恰有 k! 个结果。忽略顺序的选取称为'''组合'''，数量记为
-从 <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>\binom52=10</math>。选 0 个对象时只得到空集一种结果，选全部 n 个时也只有一种，故 <math>\binom n0=\binom nn=1</math>。
-== 格点路径把抽象选择画出来 ==
+取补集还给出一个对应：每种选 k 个的方案，恰好留下 n−k 个未选对象。因此
-从 <math>(0,0)</math> 走到 <math>(3,2)</math>，每次只能向右或向上走一个单位。每条路径都含 3 次向右、2 次向上；在 5 个步位中选出 2 个放“向上”，路径便唯一确定。
+<math display="block">\binom nk=\binom n{n-k}.</math>
+这条等式来自同一选择的两种描述。
-[[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> 条。若设置障碍点，上述无障碍计数就需要调整。
+现有 4 名甲组成员、3 名乙组成员，7 人各不相同。要选 3 人，且至少有一名乙组成员。
-== 同一个数量的两种计数 ==
+可以先数全部三人组，再去掉全部来自甲组的情况：
-考虑从 <math>n</math> 人中选 <math>k</math> 人，固定其中一人为“指定人”。每个选择要么不包含此人，要么包含此人，所以
+<math display="block">\binom73-\binom43=35-4=31.</math>
-<math display="block">\binom nk=\binom{n-1}k+\binom{n-1}{k-1}.</math>
+也可以按乙组人数分类。恰有 1 名乙组时，选法为 <math>\binom31\binom42=18</math>；恰有 2 名时为 <math>\binom32\binom41=12</math>；恰有 3 名时只有 1 种。三类不会重叠，总数为 <math>18+12+1=31</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>
+为什么不先选一名乙组成员，再从剩下 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> 条。
-两个集合的并集满足 <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 人中至少两人的出生月份相同，无需假设每个月等可能。它给出必然存在性，通常不告诉究竟是哪两人。
+== 组合数之间为什么相加 ==
+从 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>
+这里的系数记录同一种乘积由多少次选择产生，称为'''二项式定理'''。
-最稳妥的检查方法是先用很小的规模手工列举。例如从 A、B、C 中选两本，不计顺序只有 AB、AC、BC 三种；计顺序则有 AB、BA、AC、CA、BC、CB 六种。这个差二倍的结果来自每个无序选择有两种排列。一般情况下必须证明每个对象恰好被重复计了同样次数，才能统一除以某个数。若重复次数不一样，简单相除就是错的。
+== 相同物品分到不同盒子 ==
+把 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 个放隔板，所以有
-从 n 个不同对象中依次选 k 个、不允许重复，第一步有 n 种，第二步有 n−1 种，直到第 k 步有 n−k+1 种，得到
+<math display="block">\binom82=28</math>
-<math display="block">n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}.</math>
+种分法。这叫'''隔板法'''。一般 n 个相同物品分到 <math>k\ge1</math> 个不同盒子，需要 n 个星号和 k−1 条隔板，结果为 <math>\binom{n+k-1}{k-1}</math>。
-对任意固定的 k 元子集，将其中元素排列都有恰好 k! 种有序结果。所有有序选取按其底层子集分成等大的组，因此
-<math display="block">\binom nk=\frac{n!}{k!(n-k)!},\qquad 0\le k\le n.</math>
-端点 k=0 对应只选出空集这一种结果，所以约定 0!=1 与组合解释一致。k 大于 n 时通常把组合数定义为零，以方便统一写递推式；这不是对原来阶乘公式直接代入负整数。
-取补集给出一个双射：每个 k 元子集对应唯一的 n−k 元未选集合，所以 <math>\binom nk=\binom n{n-k}</math>。固定其中某一个对象，按“选它”与“不选它”把 k 元子集分成两类，则
+如果球彼此可区分，每个球有 3 个盒子可选，结果是 <math>3^6</math>，不是 28。若盒子没有标号，<math>(2,0,4)</math> 的不同排列又可能表示同一种分配；各类分配的重复次数不一致，也不能把 28 直接除以 <math>3!</math>。
-<math display="block">\binom nk=\binom{n-1}{k-1}+\binom{n-1}k.</math>
-两个证明都不需要繁琐约分，原因是等式两端本就在数同一批对象。理解这种分类方式后，三角形里相邻数相加的规则才不只是一张需要背诵的图表。
-== 完整算例：带限制的委员会 ==
+=== 加上下界和上界 ===
-现有四名甲组成员、三名乙组成员，七人均不同，要选三人且至少包含一名乙组成员。第一种方法先数所有三人组，再减去全来自甲组的情况，得到 <math>\binom73-\binom43=35-4=31</math>。第二种方法按乙组人数分类：一名乙组有 <math>\binom31\binom42=18</math> 种，两名乙组有 <math>\binom32\binom41=12</math> 种，三名乙组有 <math>\binom33\binom40=1</math> 种，总数同为 31。
+若每盒至少一个，先给每盒放一个，剩下 3 个球自由分配。令 <math>y_i=x_i-1</math>，就有 <math>y_1+y_2+y_3=3</math>，各项非负，故分法为 <math>\binom52=10</math>。
-这两种解法提供相互核对，还暴露一种常见错误：先选一名乙组成员，再从剩下六人选两人，会得到 <math>3\binom62=45</math>。其中含两名乙组成员的委员会被算两次，含三名乙组成员的被算三次，不能靠统一除以二或三修复。错误不在乘法原理，而在构造步骤给同一个最终对象提供了不同数量的描述。
+下图上排展示 (2,0,4) 的编码，中间相邻的两条隔板表示第二个盒子为空。下排展示每盒先放一个球的做法：金色球是固定分配，剩余青色球才需要重新计数；(1,2,3) 因而对应剩余量 (0,1,2)。
-若还要从三名委员中指定一位主席，最后才乘以三，结果是 93，因为每个合法委员会恰有三种主席选择。若主席必须来自乙组，则应按前面的三类分别乘以一、二、三，结果为 <math>18+24+3=45</math>。这次数字 45 是正确答案，但回答的是另一个问题；数值巧合不能代替对象定义。
+[[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>。
-把六个相同球放入三个有标号的盒子，允许空盒，等价于求非负整数解 <math>x_1+x_2+x_3=6</math>。用六个星号与两个分隔符表示，例如“★★｜｜★★★★”对应 (2,0,4)。每个分配都对应唯一这样的字符串，反之亦然，故结果为 <math>\binom82=28</math>。两个隔板可以相邻，也可以放在两端，恰好表示空盒。
-若每盒至少一个球，先给每盒一个，把 <math>y_i=x_i-1\ge0</math> 代入，得到和为三的非负整数解，计数为 <math>\binom52=10</math>。另回到允许空盒的情形，只限制每盒至多三个，则在原来的 28 个分配中，减去某盒至少四个的情形：固定某盒先放四个，剩下两个分到三盒有 <math>\binom42=6</math> 种；三个盒子合计 18，且不可能同时有两盒至少四个，所以最后为 10。
+若同时要求每盒至少 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> 的六种排列。
-“盒子无标号”会让若干排列代表同一个分配，但含重复份额与不含重复份额的重复次数不同，不能把 28 直接除以 3!。同样，若球可区分，问题变成每个球选择盒子，有 <math>3^6</math> 种。隔板法的前提必须同时包括：物品相同、盒子不同、总量固定以及相应的上下界。
+一般下界不必相同。若第 i 盒至少放 <math>\ell_i</math> 个，先扣去这些固定份额，再对剩余量使用隔板法；若还有限定上界，也须一并减去同样的份额。
-== 从递推关系到生成函数 ==
+=== 用多项式记下每个盒子的选择 ===
-用长度一和长度二的小砖铺满长度 n 的单行木板，砖方向固定，不留空隙。记铺法数为 <math>a_n</math>。最后一块若长一，前面有 <math>a_{n-1}</math> 种；若长二，前面有 <math>a_{n-2}</math> 种。两类互斥且覆盖全部情况，因而 <math>a_n=a_{n-1}+a_{n-2}</math>，初值 <math>a_0=1,a_1=1</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。
-形式幂级数 <math>A(z)=\sum_{n\ge0}a_nz^n</math> 把全部计数包装在一个对象中。按递推式逐项相减得到 <math>(1-z-z^2)A(z)=1</math>，故 <math>A(z)=1/(1-z-z^2)</math>。此处可以把 z 看作记录长度的记号，只讨论各次幂系数，不必先主张一个数值无穷级数在所有 z 上收敛。若要把它当作实际函数求值，才需要补充收敛半径。
+这种把“大小”记在指数、“数量”记在系数中的方法叫'''生成函数'''。这里它只是一个有限多项式，乘法的每一次取项都对应一个实际分配，不涉及无穷级数的收敛问题。
-递推关系是把复杂对象拆成较小对象，生成函数则把组合拆分翻译成代数运算。它们与[[函数]]和[[线性代数]]相连，但最重要的仍是先证明拆分没有遗漏与重叠。如果末块允许多种颜色，就要在递推系数中记录颜色选择，而不能机械套用同一数列。
+== 有重叠的类别怎样相加：容斥 ==
+在 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}
-<math display="block">|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|.</math>
+|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>
+逐个检查属于一个、两个、三个集合的元素，都恰好保留一次。这就是'''容斥原理'''。
-把三个不同字母重新放入三个有标号的位置，并要求没有字母留在原位，可以用容斥完整计算。全部排列有六个；固定某个字母不动，其余两个可交换，有两种，所以三项共减去六次。固定任意两个字母会迫使第三个也不动，三组两两交集各有一个，故加三；三者都固定只有一个，再减一。结果为 <math>6-6+3-1=2</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>n</math> 个相同物品分进 <math>k\ge1</math> 个不同盒子，允许空盒，隔板法给出 <math>\binom{n+k-1}{k-1}</math>。若每盒至少 <math>\ell_i</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>。初值和递推式合在一起，才确定整列答案。
-同时存在上界时，扣除下界以后必须同步调整上界，不能只减总数。例如六个球分三盒、每盒一至三个，令 <math>y_i=x_i-1</math>，得到总和为三且各项至多二。无上界时有十种；某项至少三只可能是该项为三、其余为零，共有三种，故实际为七种。与“允许空盒、每盒至多三个”的十种是不同问题。
+限制位置也可以转成已经解决的分配问题。八位二进制串恰含三个 1，有 <math>\binom83=56</math> 个。若 1 不能相邻，先在相邻两个 1 之间各放一个必需的 0；五个 0 已用掉两个，剩下三个可分到两端与两个内部间隙，共四个有标号的空隙。隔板法给出 <math>\binom63=20</math> 种。把这些零重新放回各空隙，就唯一恢复原串。
-也可用生成函数独立检查：单盒可放一至三个球，贡献 <math>z+z^2+z^3</math>，三个不同盒子相乘，所求是 <math>(z+z^2+z^3)^3</math> 中六次项系数。它由一、二、三的六种排列以及二、二、二这一种选择产生，共七。这里相乘是逐盒选择，指数相加记录总球数，系数统计产生同一总数的不同分配，正好对应计数对象。
+== 只问必然存在，不必逐一数出 ==
+人分到 12 个出生月份，若每个月至多一人，总人数最多为 12，与 13 矛盾。因此至少有两人的出生月份相同。这个结论与月份是否等可能无关，称为'''抽屉原理'''。
-== 历史、用途与概念边界 ==
+一般把 N 个对象放入正整数 k 个盒子，至少一盒的数量不小于 <math>\lceil N/k\rceil</math>，其中符号表示向上取整。若每盒数量都少于这个整数，总和便小于 N。
-计数问题长期存在于不同文化的历法、算术和游戏之中，组合数学没有一个单独的“发现者”。今天常称杨辉三角或 Pascal 三角的数表也具有多条历史线索。[https://mathshistory.st-andrews.ac.uk/Biographies/Yang_Hui/ MacTutor 的杨辉传记]介绍了杨辉 1261 年《详解九章算法》及其所引贾宪材料；贾宪的相关原著已不存，部分信息由杨辉记述保存；不同名称反映传播和记述传统，不宜据名称断言全世界最早的发现归属。
-现代组合数学不仅算排列数，还研究结构何时存在、怎样构造、最极端能达到什么规模。抽屉原理就说明：把 n+1 个对象放进 n 个盒子，至少一盒有两个对象。它给出存在性，但不一定告诉我们在大型数据中怎样快速找到目标。另一方面，可能对象数量巨大，也不意味着每个问题都必须枚举；递推、对称性和代数方法常可大幅压缩计算。
+计数用于[[概率]]时则要多一个条件：只有基本结果等可能，才能直接用“有利结果数除以全部结果数”。例如选委员会时，若所有三人组等可能，上面至少含一名乙组的概率才是 <math>31/35</math>。指定某人必选，会改变选择机制和样本空间。
-在[[概率]]中，只有等可能的基本结果才可以直接用“有利数量除以总数量”。在计算机程序中，计数可用于估计搜索空间、验证边界输入和分析算法，但应注意大整数溢出，分步计算组合数时也不要先算巨大阶乘再用浮点数相除。数学上的精确整数与机器里的有限精度是两个层次。
+== 历史 ==
+二项式系数表在不同数学传统中出现过。杨辉 1261 年《详解九章算法》记述了相关数表，并引用贾宪的方法；贾宪的相关原著已经散佚，部分内容由杨辉的记述保存。[https://mathshistory.st-andrews.ac.uk/Biographies/Yang_Hui/ MacTutor：杨辉]介绍了这些文献关系。
-== 二进制串的间隔核验 ==
+今天常用“杨辉三角”或“Pascal 三角”称呼这一数表。它把多项式展开、组合选择和格点路径联系到一起：同样的数字可以来自不同问题，而一一对应或分类计数解释了它们为何相同。
-八位二进制串中恰有三个 1，有 <math>\binom83=56</math> 个，因为只需选择三个位置；若不能有相邻的 1，可先把三个 1 排定，在相邻之间预留两个 0，再将剩下三个 0 放入四个空隙，得到 <math>\binom63=20</math> 个。两端空隙允许为空，内部空隙是在强制零之外继续添加，故这个对应是一一的。
-== 编者评注（AI 辅助） ==
+== 从“数出多少”到“必有一个” ==
-<div class="math-editorial-note"> 组合题最有价值的一步常发生在公式出现之前：给每个结果规定一种唯一的编码。遇到难题时，先列出三四个小例子，观察是否有重复描述，再决定用补集、分类、双射还是递推。建议保留两种能相互验证的计数方法；它们比单纯得到一个整数更能说明对象结构，也有助于发现题目中隐藏的顺序与重复条件。</div>
+[[抽屉原理]]用总数证明某一类必有重复。它不要求列出全部对象：例如 n 个整数的 n+1 个前缀和只有 n 种余数，因此存在非空连续一段，其和能被 n 整除。该条目逐步说明如何把“连续段”转成两个前缀的差，以及如何选择分类规则。
-== 参考来源与延伸阅读 ==
+== 参考资料 ==
-* [https://discrete.openmathbooks.org/dmoi3/sec_counting-binom.html Oscar Levin：二项式系数]；另见同书计数与生成函数章节。
+* [https://discrete.openmathbooks.org/dmoi3/sec_counting-binom.html Oscar Levin：二项式系数]。
-* [https://mathshistory.st-andrews.ac.uk/Biographies/Yang_Hui/ MacTutor：杨辉]，用于数表的历史背景。
+* [https://discrete.openmathbooks.org/dmoi3.html Oscar Levin，Discrete Mathematics: An Open Introduction]：计数、递推关系及生成函数。
-* [https://discrete.openmathbooks.org/dmoi3.html Oscar Levin，《Discrete Mathematics: An Open Introduction》第 1 章]：加乘原则、二项式系数与组合证明。
+* [https://mathshistory.st-andrews.ac.uk/Biographies/Yang_Hui/ MacTutor：杨辉]。
-* [[概率]] · [[图论]] · [[逻辑]]
+* 相关条目：[[集合]]、[[概率]]、[[图论]]、[[逻辑]]。
 [[分类:离散数学]]