查看“︁组合数学”︁的源代码

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

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

== 从分步选择到排列 ==
先选主席，有 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> 种。把这些零重新放回各空隙，就唯一恢复原串。

== 只问必然存在，不必逐一数出 ==
13 人分到 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 三角”称呼这一数表。它把多项式展开、组合选择和格点路径联系到一起：同样的数字可以来自不同问题，而一一对应或分类计数解释了它们为何相同。

== 参考资料 ==
* [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：杨辉]。
* 相关条目：[[集合]]、[[概率]]、[[图论]]、[[逻辑]]。
[[分类:离散数学]]