1 基本概念
1.1 组合的定义
组合是指从若干个不同元素中选出若干个元素，而不考虑选取顺序的一种计数方式。若从 \(n\) 个不同元素中选出 \(k\) 个，所有不同选法的总数称为组合数。它关注的是“选了什么”，而不是“先后怎么选”。
1.2 与排列的区别
排列强调顺序，组合不强调顺序。比如从 3 个元素中选 2 个，若只看选出的元素，则 \(\{A,B\}\) 与 \(\{B,A\}\) 视为同一种组合；若看顺序，则它们是不同的排列。也正因为这一点，组合数通常小于对应的排列数。
1.3 组合数的记号
1.3.1 符号 \(C(n,k)\)
在初等数学中，组合数常记作 \(C(n,k)\)，读作“\(n\) 选 \(k\)”或“从 \(n\) 个中取 \(k\) 个”。其中 \(n\) 表示总元素数，\(k\) 表示选取的元素数。
1.3.2 符号 \(\binom{n}{k}\)
在较正式的数学写作中，组合数常写作 \(\binom{n}{k}\)，称为二项式系数。这一记号在代数、概率论和离散数学中非常常见，便于与二项式展开等内容直接对应。
1.4 组合数的直观理解
组合数可以理解为“从一组对象中挑选子集”的方法数。例如，从 5 个人里选 2 人组成小组，只要成员相同，就算同一种选择。直观上，它描述的是去掉顺序后的选择数量，因此常用于分组、抽样和事件统计。
2 公式与计算
2.1 基本公式
组合数的基本公式建立在“先按顺序排列，再除去顺序重复”的思想上。其标准结果为从 \(n\) 个不同元素中选 \(k\) 个的数量。
2.1.1 阶乘表示法
组合数满足 \[ \binom{n}{k}=\frac{n!}{k!(n-k)!}. \] 这里 \(n!\) 表示阶乘。该公式说明，先考虑从 \(n\) 个元素中排列出 \(k\) 个的方式，再除以 \(k!\) 消除同一组合内部的顺序差异。
2.1.2 递推计算法
组合数也可通过递推逐步计算。利用相邻层之间的关系，可以从较小的已知值推得较大的值。这种方法在手算、表格法和程序实现中都很常见。
2.2 特殊情形
2.2.1 选取 0 个元素
从任意 \(n\) 个元素中选 0 个，只有一种选法，即不选任何元素。因此 \[ \binom{n}{0}=1. \]
2.2.2 选取全部元素
从 \(n\) 个元素中选取全部 \(n\) 个，也只有一种选法，所以 \[ \binom{n}{n}=1. \]
2.2.3 选取超过范围的情况
若要选取的数量超过元素总数，即 \(k>n\)，则不存在合法选法，通常规定 \[ \binom{n}{k}=0. \] 这一约定有助于统一公式表达，尤其在递推和求和中很有用。
2.3 计算技巧
2.3.1 约分与化简
在实际计算中，直接套用阶乘公式可能会出现大数。常见做法是先将分子分母中的公共因子约去，再进行乘除运算，以减小计算量并避免中间结果过大。
2.3.2 计算机辅助计算
当 \(n\) 和 \(k\) 较大时，通常借助计算器、数学软件或编程语言中的组合函数完成计算。实际应用中还会结合高精度整数运算，避免浮点误差影响结果。
3 数学性质
3.1 对称性
组合数具有对称性： \[ \binom{n}{k}=\binom{n}{n-k}. \] 这表示“从 \(n\) 个元素中选 \(k\) 个”和“从 \(n\) 个元素中排除 \(n-k\) 个”是等价的。该性质常用于简化计算。
3.2 递推关系
3.2.1 帕斯卡恒等式
组合数满足著名的递推公式： \[ \binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}. \] 其含义是：从 \(n\) 个元素中选 \(k\) 个时，可以按“是否选中某个指定元素”分成两类来计数。
3.2.2 帕斯卡三角形
将组合数按行排列，就形成帕斯卡三角形。每个数都等于其上方两数之和，边缘全为 1。它不仅展示了递推规律，也直观反映了组合数的层次结构。
3.3 求和性质
3.3.1 二项式系数和
固定 \(n\) 时，所有二项式系数之和为 \[ \sum_{k=0}^{n}\binom{n}{k}=2^n. \] 这可以理解为：从 \(n\) 个元素中，每个元素都有“选或不选”两种状态，总方案数为 \(2^n\)。
3.3.2 交错求和性质
组合数还满足若干交错求和公式，例如带有正负号交替出现的求和在许多情形下会得到简洁结果。这类性质常用于代数化简和容斥类推导。
3.4 组合恒等式
3.4.1 Vandermonde 恒等式
Vandermonde 恒等式说明，不同集合中选取若干元素的组合数可以按选取来源分类求和。它是组合计数中常见的恒等式之一，常用于证明和变形。
3.4.2 其他常见恒等式
组合数还包括多种基础恒等式，如与阶乘、递推、对称性相关的变形关系。这些恒等式常出现在证明题、求和题和概率计算中，是组合工具箱的重要部分。
4 在概率论中的应用
4.1 等可能事件计数
在等可能模型中，常先计算样本空间的总数，再计算有利结果数。组合数是这类计数的核心工具，因为许多事件只与“选中了哪些对象”有关，而不取决于顺序。
4.2 古典概率模型中的组合数
在经典概率问题中，例如抽球、抽卡、选人或分组，组合数常用于统计所有可能的无序结果。通过“有利情况数 / 全部情况数”可以得到事件概率。
4.3 事件个数统计
4.3.1 至少发生一次的情形
“至少发生一次”常通过补集来处理。先计算“都不发生”的情况，再用总数减去它。组合数在统计补集事件的样本数时非常方便。
4.3.2 恰好发生 k 次的情形
当某个结果在多次试验中恰好出现 \(k\) 次时，通常需要先选出这 \(k\) 次出现的位置，再结合每次试验的具体结果数进行计数。组合数正是选择位置的工具。
4.4 二项分布中的组合数
二项分布的概率公式中直接包含组合数。若独立重复试验中成功概率固定，则“恰好成功 \(k\) 次”的概率由组合数乘以相应的概率因子构成，体现了组合计数与概率模型的紧密联系。
5 在代数中的应用
5.1 二项式定理
二项式定理将 \((a+b)^n\) 展开为若干项之和，其中每项的系数正是组合数： \[ (a+b)^n=\sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k. \] 因此，组合数在代数展开中承担系数的角色。
5.2 多项式展开
在更一般的多项式乘法和展开中，组合数同样用于描述不同项的出现次数。尤其在重复乘积的展开里，系数往往可通过组合计数得到。
5.3 组合数与系数提取
在幂级数或代数表达式中，某一项的系数经常可转化为组合数问题。通过分析选取各项的方式，可直接得到目标系数，形成“计数—系数”之间的对应。
5.4 生成函数中的角色
生成函数把组合数编码为形式幂级数的系数。许多组合恒等式、递推关系和计数问题，都可以通过生成函数统一处理，因此组合数在该方法中是基础元素之一。
6 在离散数学中的应用
6.1 子集计数
若一个集合有 \(n\) 个元素，则其大小为 \(k\) 的子集个数正是 \(\binom{n}{k}\)。因此，组合数是子集计数的标准结果，也构成集合论和离散数学中的基本公式。
6.2 图论中的选边问题
在图论中，若从若干条边中选出固定数量的边，或在完全图中统计某类子图的可能性，组合数常用于描述选取方式总数。它帮助将图结构问题转化为计数问题。
6.3 集合划分的基础计数
在一些集合划分和分组问题中，组合数用于先选出某一组成员，再继续处理剩余元素。尽管完整的划分计数往往更复杂，但组合数仍是最基础的起点。
6.4 容斥原理中的辅助计数
容斥原理常需要分别统计多个条件下的对象数量。组合数在这里用于选择参与某个条件的集合或事件子集，从而形成正负交替的计数表达。
7 相关拓展
7.1 广义组合数
广义组合数把组合数的定义推广到更多参数范围，例如允许参数取非整数或负整数时的形式表达。它常见于符号计算、解析展开和特殊函数的推导中。
7.2 重复组合
7.2.1 可重复选取的模型
若允许从同一类元素中重复选取，则问题不再是普通组合，而是重复组合。此时计数对象对应的是“带重复的无序选择”。
7.2.2 星与杠方法
星与杠方法是一种经典技巧，用于处理重复组合和整数解计数问题。它把“物品”和“分隔符”组合在一起，通过排列位置来表示方案数。
7.3 q-组合数
q-组合数是组合数的一个量子化推广，常出现在代数组合和有限域相关问题中。它在形式上保留了组合数的结构，但引入了参数 \(q\) 来反映更精细的计数信息。
7.4 组合数的矩阵与数表表示
组合数可以组织成矩阵或数表形式，常见的就是帕斯卡三角形。通过表格展示，不仅便于观察规律，也便于查表、递推和教学演示。
8 历史与发展
8.1 早期计数思想
组合思想在古代计数、分配和抽取问题中就已出现。早期数学家虽然未必使用现代记号，但已经掌握了“从若干对象中选取若干个”的基本思想。
8.2 帕斯卡三角形的演化
帕斯卡三角形并非由单一学者独立发现，而是在不同文化和时期中逐渐形成。它因结构清晰、规律明显而成为组合数最著名的表示方式之一。
8.3 近现代组合数学中的地位
进入近现代后，组合数不再只是初等算术工具，而成为组合数学、概率论、统计学和计算机科学中的基础概念。其应用范围不断扩展，并与代数、图论和离散结构形成紧密联系。
9 常见误区
9.1 把组合与排列混淆
最常见的错误是把组合和排列当成同一概念。实际上，是否考虑顺序是二者的根本区别；一旦顺序不同也算不同方案，就不应使用组合数。
9.2 忽略顺序是否重要
解题时若未先判断顺序是否影响结果，容易选错模型。应先明确题目是“选人”“分组”还是“排序”，再决定是否使用组合数。
9.3 边界条件处理错误
不少错误出现在 \(k=0\)、\(k=n\) 或 \(k>n\) 等边界情形上。正确处理这些特殊值，有助于保持公式统一并避免不合理结果。
9.4 计算时的约分失误
在手算组合数时，若不先约分就直接处理阶乘，容易造成中间数过大或漏算因子。更稳妥的方法是先化简再计算，尤其在较大数值下更为重要。