排列

排列计数"从若干不同对象中选出并排成有序一列"的方案数，是组合计数的基础工具。

定义

从 $n$ 个不同元素中取 $k$ 个按顺序排成一列，称为 $n$ 取 $k$ 的排列，其数目为

$$P(n,k)=\frac{n!}{(n-k)!}=n(n-1)\cdots(n-k+1)$$

$k=n$ 时的排列称为全排列，数目为 $P(n,n)=n!$（见全排列）。

性质

• 递推 $P(n,k)=n\cdot P(n-1,k-1)$：先确定第一位（$n$ 种），再排剩下 $k-1$ 位
• 与组合的关系 $P(n,k)=k!\,\binom{n}{k}$，见组合

示例

从字母 A、B、C 中取 2 个排列：AB、AC、BA、BC、CA、CB，共 $P(3,2)=6$ 个。