permutation · P(n, k) = n! / (n−k)!

排列 P(n, k)

从 $n$ 个互不相同的元素里取出 $k$ 个排成一列，次序算数：同样三个字母，ABC 与 CBA 是两种不同的排列。这样的方案数记作排列数 $P(n, k)$ ，中文教材写作 $A_n^k$ ，英文另有 $^nP_k$ 的写法。它是乘法原理最直接的应用，逐格填，每填一格可选的元素就少一个。

1 · 逐格收缩的选法数

P(n, k) = n·(n−1)···(n−k+1)

把「取 $k$ 个排成一列」想成依次填 $k$ 个空位：第一格从全部 $n$ 个里挑，有 $n$ 种；挑走一个后第二格只剩 $n-1$ 种；到第 $k$ 格剩 $n-k+1$ 种。按乘法原理总数是这 $k$ 个数相乘：

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

图 1-1 ·

k

个空位各自的可选元素数。可拖动

n

与

k

，观察每格标注的可选数如何逐格收缩。

2 · 全部排列的枚举

enumerate · 全部排列

取前 $n$ 个大写字母作元素，枚举有序取 $k$ 个的全部 $P(n, k)$ 个排列。AB 与 BA 各占一席，这正是次序算数的含义。当 $k = n$ 时取的是全体元素的一个排列，方案数就是 $n!$ ，即全排列。

图 2-1 · 有序取

k

个的全部排列。可拖动

n

与

k

，对照枚举出的条数与

P(n, k)

的计算值。

排列数与「怎样把它们逐个生成出来」是两个问题。本页只数个数；按字典序求下一个排列、用回溯铺出选择树、以及给每个排列编号的康托展开，见算法系列排列生成。

3 · 参考文献

Permutation. Wikipedia. 排列的定义、 $P(n, k)$ 的推导与各种记号。https://en.wikipedia.org/wiki/Permutation
Factorial. Wikipedia. 阶乘 $n!$ ，以及 $P(n, n) = n!$ 的由来。https://en.wikipedia.org/wiki/Factorial