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

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

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

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

== 排列与组合的差别 ==
从 <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 章]：加乘原则、二项式系数与组合证明。
* [[概率]] · [[图论]] · [[逻辑]]
[[分类:离散数学]]