1 基本概念
1.1 计数问题的定义
计数问题是指在给定规则或限制下，确定某类对象有多少种不同取法、排列方式或分配方案。此类问题通常关注“可行方案数”，而不是方案本身的具体内容。组合计数正是围绕这一目标建立起来的一套方法体系。
这类问题广泛存在于离散数学、概率论、信息科学和算法分析中。例如，统计密码可能的组成方式、计算抽取结果的种类、估计程序状态数量等，都属于典型的计数任务。
1.2 样本空间与事件数
在概率论中，样本空间表示一次随机试验的全部可能结果，而事件则是样本空间中的一个子集。若样本空间和事件都能被清楚地枚举，那么事件概率常可借助“事件数与样本空间数之比”来计算。
因此，组合计数不仅用于求“有多少种可能”，也用于比较“某事件对应多少种结果”。当样本空间中的结果等可能时，计数就成为概率计算的基础工具。
1.3 计数中的基本原则
组合计数的核心在于将复杂问题拆解为若干容易处理的部分，再通过基本原则重新组合结果。最常用的基础方法包括加法原理、乘法原理以及分类讨论法。
1.3.1 加法原理
若一个对象可以通过若干互不重叠的方式之一完成，而各方式的方案数分别为若干个数，那么总方案数等于这些方案数之和。加法原理适用于“分支互斥”的情形。
例如，一个人若可从三条互不相同的路线到达目的地，而每条路线的可选方案数已知，则总数可直接相加。
1.3.2 乘法原理
若一个过程需按顺序完成若干步，每一步的选择不会影响其他步的选择数，或者其影响已被明确计入，那么总方案数等于各步方案数的乘积。乘法原理是分步计数的基础。
它常用于“先选后排”“先分后配”之类的问题，也常见于密码组合、座位安排和多阶段抽样。
1.3.3 分类讨论法
当问题不便直接统一计数时，可按某种属性分成若干互斥类别，对每类分别求解后再合并。分类标准可以是对象类型、结构特征、是否满足某条件等。
分类讨论的关键在于划分完整且不重叠，既不能漏掉可能情况，也不能让同一对象重复落入多个类别。
1.4 计数模型的表示
为了更清晰地理解计数过程，常将问题转化为可视化或结构化模型。不同表示法适用于不同复杂度的问题，也有助于发现重复、遗漏或隐含限制。
1.4.1 集合表示法
集合表示法将所有对象看作集合中的元素，通过子集、笛卡尔积、映射等概念描述计数对象。这种方法简洁抽象，适合证明性论证。
例如，若将“选择方案”表示为某个集合的子集，则计数问题可转化为求幂集大小、组合数或映射数。
1.4.2 树状图表示法
树状图通过分层分支展示每一步选择的结果，适用于步骤较少、分支结构清晰的问题。它能直观呈现所有路径，也便于检查是否遗漏分支。
在排列、抽签或多轮试验中，树状图尤其有助于理解样本空间的展开方式。
1.4.3 表格与矩阵表示法
表格和矩阵可以用来整理双变量或多变量的计数信息，例如按行列分别记录两类选择。对于有规律的分布问题，这种表示方式便于观察模式和提取公式。
在某些组合推导中，矩阵还可用于描述状态转移或统计结果的结构。
2 排列与组合
2.1 排列
排列研究的是“有顺序的选取”。同样的元素，顺序不同通常就视为不同结果，因此排列问题往往比组合更强调位置和次序。
2.1.1 全排列
全排列是指把全部不同元素按一定顺序全部排出。若有 n 个互不相同的元素，其全排列数通常记为 n!。
阶乘在计数中极为常见，表示从第一位到最后一位依次安排时，每一步可选数逐步减少的乘积。
2.1.2 部分排列
部分排列是从 n 个元素中选出 k 个并按顺序排列。其结果数通常记为 A(n,k) 或 P(n,k)，反映“先选后排”的结构。
这类问题常出现在奖项名次、密码位数、座位安排等场景中。
2.1.3 重复元素的排列
当对象中存在相同元素时，直接按全排列计算会产生重复。此时需要除以相同元素内部的交换重复数，从而得到不同排列的个数。
例如，含有多个相同字母的单词，其不同排法数要考虑重复元素导致的等价情况。
2.2 组合
组合研究的是“无顺序的选取”。只要选出的元素集合相同，就视为同一种结果，不区分内部排列顺序。
2.2.1 无重复组合
从 n 个不同元素中选出 k 个，不允许重复选取时，方案数记为 C(n,k)。这类计数是最基础的组合模型之一。
组合数在抽样、分组和事件计数中都有直接应用。
2.2.2 有重复组合
若允许重复选取，则问题转化为“从若干类对象中可重复取若干次”。其计数方法通常与隔板法或非负整数解有关。
这种模型常用于分配相同物品、允许多次抽样或配料方案统计。
2.2.3 组合与选择问题
实际问题中，“选择”未必只是抽取元素，也可能是从类别、位置或状态中作出决定。组合的思想正是将这类“无序选择”统一纳入计数框架。
例如，选择课程、挑选队员、确定子任务，都可视为组合问题的变体。
2.3 排列与组合的关系
排列和组合都属于选取问题，但前者强调顺序，后者强调集合。两者之间可以相互转化，是计数中最基本的对应关系之一。
2.3.1 从排列到组合
若先从 n 个元素中选出 k 个，再将这 k 个元素全排列，则部分排列可看成“组合数与排列数的乘积”。这一转化有助于从更简单的组合视角理解排列。
2.3.2 组合数的对称性
组合数满足 C(n,k)=C(n,n-k)，意味着“选 k 个”与“留出 n-k 个”本质等价。这个性质在补集计数和对称化推导中十分常用。
2.3.3 组合恒等式初步
许多组合恒等式都可由“同一对象的不同选法”引出。例如，通过拆分选取过程或比较两种计数顺序，可以得到若干经典等式。
这类恒等式既是计算工具，也是理解组合结构的重要入口。
3 经典计数方法
3.1 分步计数法
分步计数法将一个复杂任务拆成多个连续步骤，再利用乘法原理求总数。它是处理组合问题最常见的方法之一。
3.1.1 顺序分步
当问题天然具有先后顺序时，可按照实际流程依次计数。每一步的选项数清晰，最终结果通过逐步相乘得到。
3.1.2 独立分步
若各步骤之间彼此独立，则每一步的计数不会影响其他步骤，乘法原理可直接应用。这种情形在密码构造、码位选择中很常见。
3.1.3 条件分步
当后续步骤的可选范围依赖前面结果时，仍可分步计数，只是每一步的方案数需要根据条件调整。此时关键是准确描述依赖关系。
3.2 分类计数法
分类计数法通过划分问题类型，将总体分解为若干易处理部分，再分别计数后汇总。
3.2.1 按对象分类
当不同对象本身具有不同属性时，可先按对象类型分类，再分别统计。比如按颜色、角色、编号范围分组计数。
3.2.2 按结构分类
某些对象的结构差异比对象本身更重要，例如按排列模式、图形形态或分布结构分类。这样往往更便于发现规律。
3.2.3 按性质分类
可依据是否满足某一性质进行分类，例如“含有指定元素”“满足奇偶限制”“是否连续”等。分类边界要明确，避免交叉重复。
3.3 容斥原理
容斥原理用于处理多个条件重叠的计数问题。其基本思想是：先把各条件分别计入，再减去重复部分，必要时继续加回更高层重叠。
3.3.1 两个集合的容斥
| 对两个集合 A 和 B，元素总数等于 | A | + | B | - | A∩B | 。这表明在分别统计时，被重复计算的交集必须扣除一次。 |
|---|
3.3.2 多个集合的容斥
当集合数量增多时，容斥公式会交替加减各层交集。虽然形式更复杂，但思想仍是纠正重复统计。
3.3.3 应用示例
容斥常用于“不满足某条件的对象个数”统计，例如至少缺少一个性质、多个限制同时存在的情形。它在抽屉式筛选、禁止模式计数中十分有效。
3.4 双计数法
双计数法是指对同一对象集合采用两种不同方式计数，再令结果相等，由此得到恒等式或结论。
3.4.1 同一对象的两种计数
一个经典思路是从“按个体看”和“按关系看”两种角度统计同一类对象。只要两种计数对象一致，就能建立等式。
3.4.2 经典恒等式证明
许多组合恒等式都可通过双计数法证明，如通过统计某类子集、路径或配对关系，得到自然的等式结构。
3.4.3 组合证明技巧
组合证明强调把代数式转化为“有多少种办法”的问题。其优点是直观、可视化，且常能给出比纯代数更深的理解。
4 常见计数对象
4.1 字符串与序列
字符串和序列是计数中的常见对象，通常由若干位置组成，每个位置放置某种符号或元素。
4.1.1 固定长度序列
长度固定时，每一位可独立选择的情况常可直接用乘法原理处理。若每位符号集相同，则计数尤其简明。
4.1.2 含重复元素序列
当序列中某些元素可重复出现，或者不同位置允许相同符号时，计数需考虑重复引起的结构变化。很多编码问题都属于这一类。
4.1.3 满足约束的序列
若序列需满足特定限制，如不出现相邻相同、某种符号数量有限、某些位置固定，则通常需结合分类、递推或容斥来计数。
4.2 集合与子集
集合问题关心元素是否被选择，而不在意顺序，因此常与组合数直接对应。
4.2.1 子集个数
一个含 n 个元素的集合，其子集总数为 2^n。这个结果来自每个元素都可“选或不选”的二元选择模型。
4.2.2 真子集与非空子集
真子集是不等于全集的子集，非空子集则排除了空集。它们的个数可在总子集数基础上作适当扣除。
4.2.3 特定大小子集
当要求子集恰含 k 个元素时，对应的数量就是组合数 C(n,k)。这是集合计数中最典型的结果之一。
4.3 函数与映射
函数计数研究从一个有限集合到另一个有限集合的对应方式，常用于抽象建模和结构分析。
4.3.1 单射计数
单射要求不同输入映射到不同输出，因此输出端资源不能重复占用。其计数往往体现“选择并排列”的结构。
4.3.2 满射计数
满射要求目标集合中的每个元素至少被映到一次。此类计数比单射更复杂，常需借助容斥原理或递推工具。
4.3.3 双射计数
双射是一一对应，输入和输出规模相同且彼此完全匹配。若两个有限集合之间存在双射，则它们的元素个数相等。
4.4 分配与分割
分配与分割问题研究有限资源如何分给若干对象，或者如何将一个整体拆成若干部分。
4.4.1 球入盒模型
“球入盒”是经典分配模型，球代表资源，盒代表接收对象。可根据球是否相同、盒是否有标记、是否允许空盒等条件形成不同计数模型。
4.4.2 资源分配问题
资源分配强调把有限数量的物品或名额分给若干接受者，常见于任务安排、席位分派和预算分配等抽象场景。
4.4.3 整数拆分
整数拆分是把一个正整数表示为若干正整数之和，且通常不考虑加数顺序。它在数论、生成函数和递推计数中都有重要地位。
5 高级计数工具
5.1 生成函数
生成函数把数列编码为一个形式幂级数，通过代数运算来反映计数关系。它是处理复杂递推和组合结构的重要工具。
5.1.1 普通生成函数
普通生成函数通常将数列 a_n 表示为 ∑a_nx^n。系数与计数对象一一对应，便于通过展开、乘法和取系数完成求解。
5.1.2 指数生成函数
指数生成函数常用于带标签的对象计数，形式上会引入 n! 作为归一化因子。它在排列结构、标号图和组合构造中尤其常见。
5.1.3 生成函数与递推
许多递推关系可转写为生成函数方程，进而借助代数方法求解。这样可以把离散递推转化为形式运算。
5.2 递推关系
递推关系通过若干前项描述后续项，是序列计数中非常自然的表达方式。
5.2.1 线性递推
线性递推指当前项可由若干固定前项线性组合得到。斐波那契型序列是这一类的典型代表。
5.2.2 组合递推
组合递推源于“最后一步怎么形成”的分析，常通过对对象末端状态分类来建立。它比纯代数递推更具结构解释性。
5.2.3 边界条件
递推若无初始值或边界条件，通常无法唯一确定结果。边界条件相当于计数起点，是递推闭合的必要部分。
5.3 递归与分治计数
递归与分治强调将大问题拆成同类小问题，适合规模化计数和算法分析。
5.3.1 递归构造
递归构造通过“先构造较小对象，再扩展到更大对象”的方式建立计数公式。这类方法特别适合树形、区间和分层结构。
5.3.2 子问题划分
分治思想要求将问题划分为若干彼此独立或弱相关的子问题，再合并结果。正确划分是保证计数准确的关键。
5.3.3 复杂度相关计数
在算法分析中，常需统计比较次数、交换次数或状态访问次数，这些都可视为计数问题。递归和分治模型常用于导出复杂度表达式。
5.4 鸽巢原理
鸽巢原理说明：若将更多对象放入更少容器中，则必有某个容器至少容纳两个对象。它是最直观也最常用的存在性原理之一。
5.4.1 基本形式
基本形式强调“多于容量时必有重合”。虽然结论简单，却能迅速证明某些重复或冲突的必然性。
5.4.2 强化形式
强化形式给出更精细的下界，例如若对象数远超容器数，则某容器中的对象数至少达到某个整数。它在精确估计中很有用。
5.4.3 计数中的应用
鸽巢原理常用于证明重复值、同类对象碰撞、必然相遇等结论，也可作为复杂计数问题中的辅助工具。
6 组合恒等式
6.1 二项式系数性质
二项式系数是组合计数中最基础的数列之一，许多恒等式都围绕它展开。
6.1.1 对称性
二项式系数具有 C(n,k)=C(n,n-k) 的对称结构，反映“选出 k 个”与“剔除 n-k 个”是等价的。
6.1.2 递推关系
组合数满足经典递推式 C(n,k)=C(n-1,k)+C(n-1,k-1)。这一关系可由是否包含某个固定元素来解释。
6.1.3 求和公式
组合数的某些求和能给出总子集数、路径数或其他整体计数结果。例如，固定 n 时对所有 k 求和，常可得到 2^n。
6.2 常见恒等式
组合恒等式往往源于结构分解、计数等价或代数展开。
6.2.1 范德蒙德恒等式
范德蒙德恒等式描述了两个组合数卷积的结果，常可理解为“从两组对象中分别选取若干个”的总计数。
6.2.2 二项式定理
二项式定理把 (x+y)^n 展开为若干项之和，其中系数正是组合数。它连接了代数展开与组合计数。
6.2.3 斯特林数相关恒等式
斯特林数用于描述集合划分和排列循环结构，因此与分组、分拆和层级结构计数密切相关。相关恒等式常出现在高阶组合分析中。
6.3 恒等式证明方法
组合恒等式可通过多种方式证明，不同方法往往体现不同的数学视角。
6.3.1 代数证明
代数证明通常依赖公式变形、代入和化简，步骤直接但有时不够直观。
6.3.2 组合证明
组合证明将等式解释为对同一对象的两种计数方式，通常更能揭示公式背后的含义。
6.3.3 生成函数证明
生成函数证明通过函数展开与系数比较来完成，适合处理较复杂的恒等式与递推关系。
7 概率中的应用
7.1 古典概率模型
古典概率模型假设样本空间中的基本结果等可能，此时概率可由计数直接计算。
7.1.1 等可能事件
等可能事件意味着每个基本结果出现的机会相同，因此事件概率可用事件所含结果数除以总结果数得到。
7.1.2 样本空间计数
样本空间大小是概率计算的分母，必须先明确所有基本结果的总数。组合计数为此提供了规范方法。
7.1.3 事件概率计算
一旦事件结果数可被准确统计，概率便可转化为简单分式。许多抽签、掷骰和抽样问题都适用这种思路。
7.2 条件概率中的计数
条件概率中的样本空间往往被限制在某个子集中，因此计数范围随条件而改变。
7.2.1 条件样本空间
条件样本空间只考虑满足前提条件的结果。此时总数不是原样本空间的大小，而是条件限定后的结果数。
7.2.2 事件交集计数
当多个条件同时存在时，需要统计它们的交集大小。容斥、分类和直接构造都可能派上用场。
7.2.3 互斥与独立情形
互斥事件不会同时发生，而独立事件的发生概率彼此不影响。两者在计数处理中含义不同，不能混淆。
7.3 随机实验建模
随机实验建模是把实际随机过程转化为可计数的离散模型，从而便于分析。
7.3.1 抽样问题
抽样问题关注从总体中取出若干对象的方式，通常要区分有放回与无放回、是否有序等条件。
7.3.2 排列选择模型
这类模型把“选谁”和“排什么顺序”合并考虑，适合座次、名次和队列构造等问题。
7.3.3 重复试验模型
重复试验模型描述同一实验多次独立进行的情形，常用于统计成功次数、首次发生位置或固定模式出现次数。
7.4 期望与方差的计数思路
许多随机变量的期望和方差可以通过计数方法求出，尤其适合“数一数有多少个满足条件的对象”这类变量。
7.4.1 指示变量法
指示变量把某个事件是否发生转化为 0 或 1。将多个指示变量相加后，问题就可转化为对各事件分别求期望。
7.4.2 期望的线性性
期望的线性性使得无需依赖事件之间独立，也能分别求和。这一性质在复杂计数型随机变量中极为有用。
7.4.3 计数型随机变量
计数型随机变量的取值通常表示“满足某性质的对象个数”。其分布、期望与方差常可直接从组合结构中推导。
8 典型问题与解题技巧
8.1 约束条件处理
实际计数问题往往带有多种限制，处理这些限制是解题的关键。
8.1.1 至少/至多问题
“至少”与“至多”常可通过分类或补集转化处理。若直接枚举较难，反向计数往往更简洁。
8.1.2 相邻与不相邻问题
相邻限制常通过插空法、分块法或排列修正来解决。不相邻问题则常与补集和容斥相关。
8.1.3 禁止出现问题
禁止某种模式出现时，可从“所有情况”中扣除“出现该模式的情况”，也可用递推逐步构造合法对象。
8.2 对称性与补集法
对称性和补集是简化计数的重要思路，常能把难题转化为更容易处理的等价问题。
8.2.1 正向计数
正向计数是直接统计符合条件的对象数，逻辑直观，适合结构清晰的问题。
8.2.2 反向计数
反向计数从补面入手，先统计不符合条件的对象，再从总数中扣除。这种方法在条件复杂时往往更有效。
8.2.3 补集转化
补集转化利用“事件与其补事件之和为全集”的关系，把难以直接处理的问题改写为易于统计的另一类问题。
8.3 构造性方法
构造性方法强调通过明确建立对象之间的对应关系来完成计数或证明。
8.3.1 映射构造
映射构造通过设计规则，把一个集合中的对象映到另一个集合。若映射性质清晰，常能直接导出计数结论。
8.3.2 一一对应
一一对应是最强的构造方式之一，能证明两个对象集合数量相同，并揭示其结构等价性。
8.3.3 组合解释
组合解释把抽象公式还原为具体选法、排法或分法，有助于理解公式为何成立，也便于记忆。
8.4 易错点
计数题看似机械，实际很容易因为细节处理不当而出错。
8.4.1 重复计数
重复计数是指同一对象被多次算入，常发生在分类不互斥或构造方式重叠时。解决时需检查类别边界是否清楚。
8.4.2 漏计问题
漏计往往由于忽略边界情况、特殊情形或隐藏限制。完整分类和逐项验证可减少这类错误。
8.4.3 顺序敏感性判断
判断一个问题是否与顺序有关，是排列还是组合的关键。若顺序不同应视为不同结果，则应使用排列思想；若只关心选取对象，则应使用组合思想。