组合数学
概述
组合数学（Combinatorics）研究有限或离散结构的计数、排列、组合与存在性问题。核心工具包括排列、组合、鸽巢原理、容斥原理、母函数、图论等。组合数学与概率论、数论紧密相连，是计算机科学算法分析的数学基础。
关键内容
- 排列组合：从 $n$ 个元素中取 $r$ 个的排列数 $P(n,r) = n!/(n-r)!$，组合数 $C(n,r) = \binom{n}{r} = n!/(r!(n-r)!)$
- 帕斯卡三角形：二项式系数的三角排列，$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$
- 容斥原理：计算并集大小 $|A \cup B| = |A| + |B| - |A \cap B|$，可推广至 $n$ 个集合
- 母函数：用幂级数编码计数问题，将组合等式转化为代数恒等式
- 应用：概率论（样本空间计数）、算法复杂度分析、密码学、通信编码