组合数 组合数是组合数学中计数对象的基本工具，用于计算从 \( n \) 个不同元素中选取 \( k \) 个元素的方式数，记作 \( \binom{n}{k} \) 或 \( C(n, k) \)。其定义公式为： \[ \binom{n}{k} = \frac{n!}{k!(n-k) !}, \quad 0 \leq k \leq n. \] 若 \( k < 0 \) 或 \( k > n \)，则组合数定义为 0。 1. 核心思想与实例 组合数描述的是 不考虑顺序的选取 。例如，从集合 \(\{a, b, c\}\) 中选 2 个元素，可能的子集为 \(\{a,b\}, \{a,c\}, \{b,c\}\)，因此 \( \binom{3}{2} = 3 \)。 与之相对，排列数 \( P(n,k) = \frac{n!}{(n-k) !} \) 考虑顺序，例如 \((a,b)\) 和 \((b,a)\) 算作不同排列。 2. 组合恒等式 组合数满足一系列恒等式，反映了其内在对称性和递归关系： 对称性 ：\( \binom{n}{k} = \binom{n}{n-k} \)。 直观解释：从 \( n \) 个元素中选 \( k \) 个留下，等价于选 \( n-k \) 个移除。 递推关系（帕斯卡法则） ： \[ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}. \] 推导：固定一个元素，若包含它则从剩余 \( n-1 \) 个中选 \( k-1 \) 个（\( \binom{n-1}{k-1} \)），若不包含它则从剩余 \( n-1 \) 个中选 \( k \) 个（\( \binom{n-1}{k} \)）。 二项式定理 ： \[ (x+y)^n = \sum_ {k=0}^n \binom{n}{k} x^k y^{n-k}. \] 组合数 \( \binom{n}{k} \) 即二项式展开的系数，故得名“二项式系数”。 3. 推广与变体 多项式系数 ：若将 \( n \) 个元素分成大小分别为 \( k_ 1, k_ 2, \dots, k_ m \) 的组（\( \sum k_ i = n \)），分组方式数为： \[ \binom{n}{k_ 1, k_ 2, \dots, k_ m} = \frac{n!}{k_ 1! k_ 2! \cdots k_ m !}. \] 组合数 \( \binom{n}{k} \) 是 \( m=2 \) 时的特例（即 \( k_ 1 = k, k_ 2 = n-k \)）。 广义组合数 ：当 \( n \) 为实数时，通过伽马函数定义： \[ \binom{\alpha}{k} = \frac{\alpha (\alpha-1) \cdots (\alpha-k+1)}{k !}, \quad k \in \mathbb{N}. \] 用于生成函数或级数展开（如牛顿二项式定理）。 4. 组合解释与模型 组合数出现在多种问题中： 路径计数 ：在网格图中从 \((0,0)\) 走到 \((m,n)\) 的最短路径数为 \( \binom{m+n}{m} \)。 组合证明 ：通过构造双射证明恒等式（如用子集与二进制串对应证明 \( \sum_ {k=0}^n \binom{n}{k} = 2^n \)）。 5. 算法与计算 计算组合数需注意数值溢出。常用方法： 递归 ：利用帕斯卡法则，但效率低（\( O(2^n) \)）。 动态规划 ：预计算帕斯卡三角形，时间 \( O(n^2) \)，空间可优化。 质因数分解 ：对较大 \( n \)，分解分子分母的质因数后相消，避免除法误差。 通过以上步骤，组合数从基本定义扩展到应用与计算，成为组合数学的核心工具之一。