2. 排列

本节是选学内容. 不学本节不影响理解任何必学内容 (也就是, 未被声明为选学内容的节).

为方便, 我作一个新的定义.

定义 2.1 (排列). 设 $a_1$, $a_2$, $\dots$, $a_n$ 是互不相同的 $n$ 个文字. 我们说, 由这 $n$ 个文字作成的任何有序的文字列 $a_{i_1}$, $a_{i_2}$, $\dots$, $a_{i_n}$ (其中 $i_1$, $i_2$, $\dots$, $i_n$ 是互不相同的不超过 $n$ 的 $n$ 个正整数) 是 $a_1$, $a_2$, $\dots$, $a_n$ 的一个排列.

不难算出 $n$ 个互不相同的文字的排列的数目. 从 $a_1$, $a_2$, $\dots$, $a_n$ 里选一个为第 $1$ 个文字, 有 $n$ 个选法; 从剩下的 $n-1$ 个文字里选一个为第 $2$ 个文字, 有 $n-1$ 个选法; ……; 从剩下的 $2$ 个文字里选一个为第 $n-1$ 个文字, 有 $2$ 个选法; 从剩下的 $1$ 个文字里选一个为第 $n$ 个文字, 有 $1$ 个选法. 由分步乘法计数原理, 知数目为$$\begin{array}{r}n\cdot (n-1)\cdot \cdots \cdot 2\cdot 1.\end{array}$$不过, 在本书, 这不重要.

设文字列 I: $1$, $2$, $\dots$, $n$. 设 $i_1$, $i_2$, $\dots$, $i_n$ 是 $1$, $2$, $\dots$, $n$ 的一个排列. 我们去除文字列 I 的第 $i_1$, $i_2$, $\dots$, $i_{n-1}$ 个文字 (也就是, 去除 $i_1$, $i_2$, $\dots$, $i_{n-1}$), 且不改变文字的前后次序, 得文字列 II: $i_n$ (恰剩一个文字). 显然, $i_n$ 的位置 $f(i_n)=1$. 另一方面, 利用缺项定位公式, 有$$\begin{array}{r}f(i_n)=i_n-(\rho (i_n,i_1)+\cdots +\rho (i_n,i_{n-1})).\end{array}$$于是, 我们有

定理 2.2. 设 $i_1$, $i_2$, $\dots$, $i_n$ 是 $1$, $2$, $\dots$, $n$ 的一个排列; 也就是, 设 $i_1$, $i_2$, $\dots$, $i_n$ 是不超过 $n$ 的正整数, 且互不相同. 则$$\begin{array}{r}{i}_n-(\rho (i_n,i_1)+\rho (i_n,i_2)+\cdots +\rho (i_n,i_{n-1}))=1,\end{array}$$或$$\begin{array}{r}\rho (i_n,i_1)+\rho (i_n,i_2)+\cdots +\rho (i_n,i_{n-1})=i_n-1.\end{array}$$