组合计数 组合计数是组合数学的核心分支，研究对有限集合中满足条件的对象进行系统计数的方法。下面从基础概念到典型工具逐步展开说明。 1. 基本计数原理的延伸 在加法原理与乘法原理的基础上，组合计数进一步处理以下问题： 重复元素的排列 ：若集合中有重复元素（如单词 "MISSISSIPPI" 的字母），排列数为 \[ \frac{n!}{n_ 1! n_ 2! \cdots n_ k !}, \] 其中 \(n\) 为总字母数，\(n_ i\) 为第 \(i\) 类字母的重复次数。这一公式通过“去重”将多重集的排列转化为唯一计数。 圆排列 ：\(n\) 个不同对象的环形排列数为 \((n-1) !\)，因为固定一个对象的相对位置后可消除旋转对称性。 2. 分配问题与第二类斯特林数 将 \(n\) 个不同的球放入 \(k\) 个相同的盒子（每个盒子非空），方案数由 第二类斯特林数 \(S(n,k)\) 表示。其递推公式为： \[ S(n,k) = S(n-1,k-1) + k \cdot S(n-1,k), \] 边界条件为 \(S(n,1)=1\)，\(S(n,n)=1\)。例如，\(S(4,2)=7\) 对应将 4 个不同物体划分为 2 个非空子集的所有方法。 若盒子可空，则总方案数为 \(\sum_ {j=1}^k S(n,j)\)。 3. 生成函数：计数的代数化工具 生成函数将计数问题转化为形式幂级数的运算。例如： 整数拆分问题：将整数 \(n\) 拆分为若干正整数之和的方案数，对应生成函数 \[ P(x) = \prod_ {k=1}^\infty \frac{1}{1-x^k}. \] 组合数的生成函数：\( (1+x)^n = \sum_ {k=0}^n \binom{n}{k} x^k \) 是二项式系数的生成函数，可用于推导恒等式。 4. 容斥原理的计数应用（深化） 容斥原理处理带约束的计数，例如错位排列（Derangements）：\(n\) 个元素的排列中无元素在原始位置的方案数 \(D_ n\) 满足： \[ D_ n = n! \sum_ {k=0}^n \frac{(-1)^k}{k !}. \] 该公式通过容斥“至少一个元素在正确位置”的补集得到。 5. Pólya计数定理 处理对称性下的计数问题（如用 \(m\) 种颜色给正六面体的面着色）。定理形式为： \[ \text{方案数} = \frac{1}{|G|} \sum_ {g \in G} m^{c(g)}, \] 其中 \(G\) 是对称群，\(c(g)\) 是置换 \(g\) 的循环分解中循环的个数。此定理将Burnside引理与生成函数结合，统一处理对称性导致的等价类计数。 6. 组合结构中的渐进计数 对大规模问题，常需估计数量的渐进趋势，例如： 斯特林公式：\(n ! \sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n\) 卡特兰数渐进性：\(C_ n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}\) 此类分析揭示了组合函数随规模增长的主要规律。 组合计数的方法从初等排列组合延伸到生成函数、群作用与渐进分析，成为解决离散结构枚举问题的系统工具。