排列 vs 组合

概述

排列（Permutation）与组合（Combination）是计数理论中两个最基本的概念，核心区别在于是否考虑选取的顺序。排列关心”谁在哪个位置”，组合只关心”选了谁”。二者通过公式 $P(n,r)=C(n,r)\cdot r!$ 紧密联系。

定义

排列

从 $n$ 个不同元素中选取 $r$ 个进行有序排列的方式数，记为 $P(n,r)$： $P(n,r)=\frac{n!}{(n-r)!}$ 当 $r=n$ 时称为全排列，$P(n,n)=n!$。排列是乘法法则的直接应用：第1个位置有 $n$ 种选择，第2个有 $n-1$ 种，依此类推。

组合

从 $n$ 个不同元素中选取 $r$ 个的无序子集数，记为 $C(n,r)$ 或 $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$： $C(n,r)=\left(\genfrac{}{}{0ex}{}{n}{r}\right)=\frac{n!}{r!(n-r)!}$ 组合数具有对称性 $\left(\genfrac{}{}{0ex}{}{n}{r}\right)=\left(\genfrac{}{}{0ex}{}{n}{n-r}\right)$，即”选 $r$ 个”等价于”排除 $n-r$ 个”。

对比维度

维度	排列 $P(n,r)$	组合 $C(n,r)$
核心区别	考虑顺序	不考虑顺序
公式	$\frac{n!}{(n-r)!}$	$\frac{n!}{r!(n-r)!}$
直觉类比	选人并安排职位（主席、秘书…）	选人组成委员会（无职位区分）
对称性	无（$P(n,r)\ne P(n,n-r)$）	有（$\left(\genfrac{}{}{0ex}{}{n}{r}\right)=\left(\genfrac{}{}{0ex}{}{n}{n-r}\right)$）
递推关系	$P(n,r)=P(n-1,r)+r\cdot P(n-1,r-1)$	$\left(\genfrac{}{}{0ex}{}{n}{r}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{r}\right)$（帕斯卡恒等式）
与对方关系	$P(n,r)=C(n,r)\cdot r!$	$C(n,r)=\frac{P(n,r)}{r!}$
上界	$P(n,r)\le n^r$	$C(n,r)\le n^r/r!$
求和	无简单封闭求和公式	$\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)=2^n$
边界值	$P(n,0)=1$，$P(n,n)=n!$	$\left(\genfrac{}{}{0ex}{}{n}{0}\right)=\left(\genfrac{}{}{0ex}{}{n}{n}\right)=1$

关键区别

• 排列区分 $(a,b)$ 和 $(b,a)$ 为不同方案，组合将 $\{a,b\}$ 视为同一种方案
• 每个组合对应 $r!$ 个排列，因此排列数恒大于等于组合数（$r\ge 2$ 时严格大于）
• 组合数具有对称性而排列数没有——选 $r$ 个等价于排除 $n-r$ 个，但排列中顺序不同则结果不同
• 组合数是二项式系数的核心，排列数则更多出现在排列生成和概率计算中
• 排列的乘法结构 $P(n,r)=n\cdot P(n-1,r-1)$ 直接体现了乘法法则，组合的帕斯卡恒等式体现了”含/不含”的分类思想

联系

• 二者都基于乘法法则推导
• 核心转换公式：$P(n,r)=C(n,r)\cdot r!$，即”先选后排”
• 从 $\{a,b,c\}$ 中取 2 个：排列有 6 种 $(a,b),(a,c),(b,a),(b,c),(c,a),(c,b)$，组合有 3 种 $\{a,b\},\{a,c\},\{b,c\}$，恰好 $6=3\times 2!$
• 二者都是排列组合恒等式的研究对象
• 在概率计算中，等可能概率 $P(E)=|E|/|S|$ 的分母和分子都可能涉及排列或组合，取决于是否考虑顺序

参见

• 排列 — 有序选取的完整概念卡片
• 组合 — 无序选取的完整概念卡片
• 二项式系数 — $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ 的代数性质