排列组合是数学中的核心内容，广泛应用于概率论、统计学、计算机科学等领域。本文将从基本概念出发，系统介绍排列组合的核心定理、符号体系及推导过程，为针对机器学习等算法原理理解打下数据基础。
一、基本概念与符号体系
加法原理与乘法原理
加法原理：若完成事件 AAA 有 mmm 种方法，完成事件 BBB 有 nnn 种方法，且 AAA 与 BBB 互斥，则完成 AAA 或 BBB 共有 m+nm + nm+n 种方法。乘法原理：若完成事件 AAA 有 mmm 种方法，完成事件 BBB 有 nnn 种方法，则依次完成 AAA 和 BBB 共有 m×nm \times nm×n 种方法。
阶乘（Factorial）
定义 n!=n×(n−1)×⋯×1n! = n \times (n-1) \times \cdots \times 1n!=n×(n−1)×⋯×1，并规定 0!=10! = 10!=1。阶乘是排列组合的基础。
二、排列（Permutation）
定义：从 nnn 个不同元素中取出 mmm 个（m≤nm \leq nm≤n），按特定顺序排列的方式数称为排列数，记作 AnmA_n^mAnm 或 P(n,m)P(n, m)P(n,m)。
公式推导：
第一个位置有 nnn 种选择，第二个位置剩下 n−1n-1n−1 种，依此类推，第 mmm 个位置有 n−m+1n - m + 1n−m+1 种选择。根据乘法原理：
Anm=n×(n−1)×⋯×(n−m+1)=n!(n−m)!
A_n^m = n \times (n-1) \times \cdots \times (n - m + 1) = \frac{n!}{(n - m)!}
Anm=n×(n−1)×⋯×(n−m+1)=(n−m)!n!
特殊情形：
全排列：当 m=nm = nm=n 时，Ann=n!A_n^n = n!Ann=n!。重复排列：允许元素重复时，排列数为 nmn^mnm。圆排列：将 nnn 个元素排成环形，因旋转对称性，排列数为 n!n=(n−1)!\frac{n!}{n} = (n-1)!nn!=(n−1)!。
三、组合（Combination）
定义：从 nnn 个不同元素中取出 mmm 个（m≤nm \leq nm≤n）不考虑顺序的方式数，记作 CnmC_n^mCnm 或 (nm)\dbinom{n}{m}(mn)。
公式推导：
组合数与排列数的关系为：
Cnm=Anmm!=n!m!(n−m)!
C_n^m = \frac{A_n^m}{m!} = \frac{n!}{m!(n - m)!}
Cnm=m!Anm=m!(n−m)!n!
推导逻辑：每个组合对应 m!m!m! 种排列（因排列考虑顺序），故需将排列数除以 m!m!m!。
核心性质：
对称性：Cnm=Cnn−mC_n^m = C_n^{n - m}Cnm=Cnn−m。递推公式：Cnm=Cn−1m−1+Cn−1mC_n^m = C_{n-1}^{m-1} + C_{n-1}^mCnm=Cn−1m−1+Cn−1m（帕斯卡定理）。
证明：考虑是否包含某一特定元素：
包含该元素：需从剩余 n−1n-1n−1 个中选 m−1m-1m−1 个，即 Cn−1m−1C_{n-1}^{m-1}Cn−1m−1。不包含该元素：需从剩余 n−1n-1n−1 个中选 mmm 个，即 Cn−1mC_{n-1}^mCn−1m。
由加法原理得证。
四、二项式定理
定理内容：对任意正整数 nnn，有
(a+b)n=∑k=0n(nk)an−kbk
(a + b)^n = \sum_{k=0}^n \dbinom{n}{k} a^{n-k} b^k
(a+b)n=k=0∑n(kn)an−kbk
证明（组合推导）：
展开 (a+b)n(a + b)^n(a+b)n 时，项 an−kbka^{n-k}b^kan−kbk 的系数等于从 nnn 个括号中选择 kkk 个取 bbb、其余取 aaa 的方式数，即 (nk)\dbinom{n}{k}(kn)。
五、扩展内容：重复元素的排列
若 nnn 个元素中有重复，各类别分别有 n1,n2,…,nkn_1, n_2, \dots, n_kn1,n2,…,nk 个相同元素（n1+n2+⋯+nk=nn_1 + n_2 + \cdots + n_k = nn1+n2+⋯+nk=n），则全排列数为：
n!n1! n2! ⋯ nk!
\frac{n!}{n_1! \, n_2! \, \cdots \, n_k!}
n1!n2!⋯nk!n!
推导：先视为全排列 n!n!n!，再对每类重复元素除以 ni!n_i!ni! 以消除顺序影响。
六、总结
排列组合的核心在于对“有序”与“无序”的区分：
排列强调顺序，公式为 n!(n−m)!\dfrac{n!}{(n - m)!}(n−m)!n!。组合忽略顺序，公式为 n!m!(n−m)!\dfrac{n!}{m!(n - m)!}m!(n−m)!n!。
其性质与定理（如二项式定理）在概率计算、多项式展开等领域具有重要应用。