auto_ai 知识库

Appearance

组合计数是离散数学的计算核心。本笔记覆盖基本计数法则（加法/乘法）、排列与组合（含多重集）、二项式定理与组合恒等式、非降路径模型。

基本计数法则（考点） ​

加法法则与乘法法则 ​

法则内容适用
加法法则事件 A 有 m 种方式，B 有 n 种方式，A 与 B 不重叠，则"A 或 B"有 m+n 种分类选取
乘法法则A 有 m 种，B 有 n 种且彼此独立，则"A 与 B"有 m×n 种分步选取
  • 分类处理：对方式集合划分后分别计数，用加法
  • 分步处理：把一种方式分解为独立步骤，用乘法
  • 分类与分步常结合使用（先分类每类内分步 / 先分步每步内分类）

典型应用 ​

  • 1400 = 2³·5²·7 的正因子个数 = (3+1)(2+1)(1+1) = 24
  • 1000! 末尾 0 的个数 = min(因子 2 个数, 因子 5 个数) = 249

排列与组合（核心考点） ​

选取问题的四类模型 ​

不重复重复
有序集合的排列 P(n,r)多重集的排列
无序集合的组合 C(n,r)多重集的组合

公式（必须背熟） ​

  • 排列数：P(n,r) = n!/(n−r)!（从 n 元集有序不重复选 r 个）
  • 组合数：C(n,r) = n!/(r!(n−r)!)（无序不重复选 r 个）
  • 环排列数：P(n,r)/r
  • 多重集全排列：n!/(n₁!n₂!…nₖ!)，其中 n = n₁+…+nₖ
  • 多重集组合（r ≤ nᵢ）：C(k+r−1, r)（等价于 x₁+…+xₖ = r 非负整数解个数）
  • 不相邻选取：从 {1,…,n} 选 k 个不相邻的数：C(n−k+1, k)

组合数性质 ​

  1. C(n,r) = C(n, n−r)（对称性）
  2. Pascal 公式：C(n,r) = C(n−1,r−1) + C(n−1,r)（杨辉三角）
  3. C(n,0) + C(n,1) + … + C(n,n) = 2ⁿ（子集总数）

二项式定理与组合恒等式 ​

二项式定理 ​

(x+y)ⁿ = Σ C(n,i)·xⁱ·yⁿ⁻ⁱ，i 从 0 到 n。

  • 应用：求展开式特定项的系数（如 (2x−3y)²⁵ 中 x¹²y¹³ 的系数 = C(25,13)·2¹²·(−3)¹³）

常用组合恒等式（考点） ​

恒等式名称/用途
Σ C(n,k) = 2ⁿ变下项求和（子集计数）
Σ k·C(n,k) = n·2ⁿ⁻¹变系数求和（级数求导）
Σ C(k,r) = C(n+1,r+1)变上项求和（分类计数）
C(n,r)·C(r,k) = C(n,k)·C(n−k,r−k)乘积转换式
Σ C(m,k)C(n,r−k) = C(m+n,r)积之和（Vandermonde）

证明方法：公式代入、组合分析（数同一个东西两次）、二项式定理、幂级数求导/积分、归纳法。

非降路径模型（重点） ​

  • (0,0) 到 (m,n) 的非降路径数 = C(m+n, m)
  • (a,b) 到 (m,n) 的非降路径数 = C(m+n−a−b, m−a)
  • (0,0) 到 (n,n) 不穿过对角线的非降路径数 = 2·C(2n−1,n) − …（Catalan 数相关，见递推章）

应用：证明恒等式、计数单调函数、栈的输出序列计数（进/出栈对应非降路径，输出数 = Catalan 数 Cₙ）。

多项式定理 ​

(x₁+…+xₜ)ⁿ 的展开：Σ [n!/(n₁!…nₜ!)]·x₁ⁿ¹…xₜⁿᵗ，求和对所有 n₁+…+nₜ=n 的非负整数解。

  • 多项式系数 n!/(n₁!…nₜ!) = 多重集全排列数 = 分球入盒方案数

一句话总结 ​

计数四步走：先判断"有序/无序、重复/不重复"选对公式，再想加法还是乘法；非降路径是万能计数模型（栈输出、单调函数都归它）；组合恒等式会证明会用。

相关概念 ​