A2-数学预备

数学预备 #

这讲讲什么：把主线反复使用、却从未系统解释的三件工具——求和号、数学归纳法、排列与逆序数——一次补齐
前置：会做整数四则运算；知道「集合」「函数」是什么意思。不需要任何线性代数知识
一句话：求和号是压缩记号，归纳法是多米诺骨牌，逆序数是给排列打分的那把尺。

---

一、为什么需要它 #

正文里会出现这样的句子：「设 $v=\sum_{j=1}^{n}a_jv_j$」「对 $n$ 用数学归纳法」「把列指标重排成自然顺序」。三处都默认你会三件事，但主线从没停下来讲。

分开说。

求和号。如果把 $a_1v_1+a_2v_2+\cdots+a_nv_n$ 一直写下去，$n$ 是字母时根本写不完。求和号把它压成一行，代价是你得熟悉几条改写规则。不熟悉的人会在「换标」「拆区间」「交换两个求和号」这三步上反复出错——而这三步在矩阵乘法与行列式展开里每次都要用。

数学归纳法。线性代数里大量结论形如「对任意 $n$」：$n$ 个向量的线性组合、$n$ 级矩阵的行列式、$n$ 维空间的性质。这类命题最标准的证法就是归纳法。不会用它，你会读不懂一半证明；更糟的是，你会看不出某处证明在偷偷用它。

排列与逆序数。行列式有三种讲法，其中「完全展开」那一种必须给每一项配一个正负号。这个号从哪来？来自把列指标重排成自然顺序要交换多少次。不讲排列，这一支就只能背公式。

三者关系还很紧：逆序数要靠求和号写出来，而「对换改变奇偶性」的标准证明就是一次归纳。 所以它们放在同一篇附录里。

读完这一篇，你应该能回答：

1. $\sum_{i=1}^{n}\sum_{j=1}^{i}$ 与 $\sum_{j=1}^{n}\sum_{i=1}^{j}$ 是不是同一个和？为什么？
2. 一个归纳证明只缺了起始步，会「证出」什么荒谬结论？
3. 排列 $5,3,1,4,2$ 的逆序数是多少？它是偶排列还是奇排列？

---

二、定义与最小例子 #

2.1 求和号 #

设 $m\le n$，$a_m,a_{m+1},\dots,a_n$ 是 $n-m+1$ 个数。把它们的和简记为

$$\sum_{i=m}^{n}a_i=a_m+a_{m+1}+\cdots+a_n$$

符号 $\sum$ 是拉丁字母 S 的变形，来自 sum。

最小例子（都动手算一遍）：

$$\sum_{i=1}^{4}i=1+2+3+4=10$$

$$\sum_{i=0}^{5}(6-i)x^{i}=6+5x+4x^{2}+3x^{3}+2x^{4}+x^{5}$$

第二个例子说明：被加项不必是 $a_i$ 这种单个字母，可以是 $i$ 的任何表达式，也可以带另一个字母 $x$。

撞名的典型场景：$s$ 行 $t$ 列的数表 $a_{i,j}$，第 $i$ 行的和是 $\sum_{j=1}^{t}a_{i,j}$。这里不能把 $j$ 改成 $i$，因为 $\sum_{i=1}^{t}a_{i,i}$ 的意思是 $a_{1,1}+a_{2,2}+\cdots+a_{t,t}$——那是主对角线，完全是另一个和。

多重求和。数表全部 $st$ 个数之和，可以先按行加，再把各行之和相加：

$$S=\sum_{i=1}^{s}\left(\sum_{j=1}^{t}a_{i,j}\right)$$

括号通常省掉，写成 $\sum_{i=1}^{s}\sum_{j=1}^{t}a_{i,j}$，叫二重求和。同理有 $p$ 重求和；若各层上限都是 $n$，可简写为

$$\sum_{i_1,i_2,\dots,i_p=1}^{n}a_{i_1,i_2,\dots,i_p}$$

带条件的求和。只加满足某条件的那些项时，把条件写在求和号下：

$$\sum_{1\le i<j\le n}a_{i,j}=a_{1,2}+a_{1,3}+a_{2,3}+a_{1,4}+\cdots+a_{n-1,n}$$

这里取的次序是「先固定 $i$，再把 $j$ 从 $i+1$ 走到 $n$」——这只是一种遍历次序，与结果无关。

空和约定。若没有任何指标满足条件，约定和为 $0$。例如 $\sum_{1\le i<j\le 1}a_{i,j}=0$：下界已经超过上界，一项都没有。

2.2 求积号（一句话带过） #

把 $+$ 换成 $\times$，$\sum$ 换成 $\prod$（P，来自 product）：

$$\prod_{i=1}^{n}a_i=a_1a_2\cdots a_n$$

规则逐条对应，只有一处不同：空积约定为 $1$，不是 $0$。理由见 2.4。

2.3 数学归纳法 #

原理。设 $P(n)$ 是关于整数 $n$ 的命题。若存在整数 $n_0$ 使

1. 起始步：$P(n_0)$ 成立；
2. 递推步：对每个整数 $n\ge n_0$，「若 $P(n)$ 成立，则 $P(n+1)$ 成立」；

那么对每个整数 $n\ge n_0$，$P(n)$ 都成立。

多米诺骨牌图景。把每个 $P(n)$ 想成竖着的一块骨牌。起始步是「推倒第一块」，递推步是「任何一块倒下都会撞倒下一块」。两条都满足，所有骨牌才全倒。少一条，链条就断在那里。

最小例子。证明对一切正整数 $n$，

$$1+3+5+\cdots+(2n-1)=n^{2}$$

取 $P(n)$ 为上式，$n_0=1$。

起始步：$n=1$ 时左边 $=1$，右边 $=1^2=1$，成立。

递推步：设 $P(n)$ 成立，即 $1+3+\cdots+(2n-1)=n^2$。要证 $P(n+1)$：

$$\begin{aligned}1+3+\cdots+(2n-1)+\bigl(2(n+1)-1\bigr)&=\bigl(1+3+\cdots+(2n-1)\bigr)+(2n+1)\\&=n^{2}+(2n+1)\\&=(n+1)^{2}\end{aligned}$$

第一行只是把 $n+1$ 对应的那一项补上去；第二行用了归纳假定；第三行是展开。于是 $P(n+1)$ 成立。由归纳法，命题对一切正整数 $n$ 成立。

2.4 为什么空和是 0、空积是 1 #

这两个约定常被当成「记号习惯」背下来，其实它们是被迫的。

关键在拆分律：若指标集合被分成两块互不相交的部分，则整块的和等于两块之和。设约束 $R_1,R_2$ 不可能同时满足，则

$$\sum_{R_1\ \text{或}\ R_2}a=\sum_{R_1}a+\sum_{R_2}a\tag{2.1}$$

现在取 $R_1$ 为空约束（没有任何指标满足它），$R_2$ 任意。那么「满足 $R_1$ 或 $R_2$」与「满足 $R_2$」是同一个条件，左边就是 $\sum_{R_2}a$。设空和为 $x$，由 (2.1) 得

$$\sum_{R_2}a=x+\sum_{R_2}a$$

对一切 $R_2$ 成立，故 $x=0$。空和只能是 $0$。

同样的推理对乘积给出 $x=x\cdot x$，即 $x\in\{0,1\}$。若取 $x=0$，则任何一块的积都成了 $0\cdot(\cdots)=0$，显然荒谬。所以空积只能是 $1$。

2.5 排列 #

设 $a_1,\dots,a_n$ 是 $n$ 个互不相同的文字。由它们作成的任何有序文字列 $a_{i_1},a_{i_2},\dots,a_{i_n}$（其中 $i_1,\dots,i_n$ 是 $1,\dots,n$ 的一个重排）叫这 $n$ 个文字的一个排列。

最常用的是 $1,2,\dots,n$ 的排列。例如 $n=5$ 时，$(3,2,5,1,4)$、$(1,2,3,4,5)$、$(5,4,3,2,1)$ 都是。

个数。第一个位置有 $n$ 种选法，第二个 $n-1$ 种，……，最后一个 $1$ 种，共

$$n!=n(n-1)\cdots 2\cdot 1=\prod_{i=1}^{n}i$$

个。这里用的正是 2.2 的求积号。

自然排列。把 $n$ 个互不相同的整数从小到大排好，得到的那个排列叫它们的自然排列。例如 $3,2,5,1,4$ 的自然排列是 $1,2,3,4,5$。原排列与它的差别，正是下面要量的东西。

2.6 逆序与逆序数 #

设 $c_1,\dots,c_n$ 是互不相同的整数构成的一个排列。若存在 $1\le i<j\le n$ 使 $c_i>c_j$，就说有序对 $(c_i,c_j)$ 是这个排列的一个逆序。

排列的逆序数 $\tau(c_1,\dots,c_n)$ 就是逆序的总个数。写成求和号：

$$\tau(c_1,\dots,c_n)=\sum_{1\le i<j\le n}\rho(c_i,c_j),\qquad \rho(u,v)=\begin{cases}1,&u>v\\ 0,&u\le v\end{cases}$$

最小例子。取 $(3,2,5,1,4)$，把每对位置 $(i,j)$（$i<j$）查一遍：

对	$(3,2)$	$(3,5)$	$(3,1)$	$(3,4)$	$(2,5)$	$(2,1)$	$(2,4)$	$(5,1)$	$(5,4)$	$(1,4)$
是否逆序	是	否	是	否	否	是	否	是	是	否

逆序是 $(3,2),(3,1),(2,1),(5,1),(5,4)$，共 $5$ 个，所以 $\tau(3,2,5,1,4)=5$。

符号。定义排列的符号为

$$s(c_1,\dots,c_n)=(-1)^{\tau(c_1,\dots,c_n)}=\begin{cases}1,&\tau\ \text{为偶数}\\ -1,&\tau\ \text{为奇数}\end{cases}$$

逆序数为偶数时叫偶排列，为奇数时叫奇排列。自然排列的逆序数是 $0$，是偶排列，符号为 $1$。

---

三、几个必须自己算一遍的结论 #

3.1 求和号的四条改写规则 #

(a) 提出常数。与指标无关的因子可以提到求和号外：

$$\sum_{i=1}^{n}c\,a_i=c\sum_{i=1}^{n}a_i$$

但不能提出与指标有关的因子：$\sum_{i=1}^{n}i\,a_i\ne n\sum_{i=1}^{n}a_i$，左边每项系数都不同。

(b) 换标。只换字母，值不变：

$$\sum_{i=1}^{n}a_i=\sum_{j=1}^{n}a_j$$

真正有用的是平移换标。令 $j=i-1$，则 $i$ 从 $1$ 到 $n$ 时 $j$ 从 $0$ 到 $n-1$，且 $a_i=a_{j+1}$：

$$\sum_{i=1}^{n}a_i=\sum_{j=0}^{n-1}a_{j+1}$$

算个具体的：$\sum_{i=1}^{3}i^{2}=1+4+9=14$，而 $\sum_{j=0}^{2}(j+1)^{2}=1+4+9=14$。✓

(c) 拆区间。若 $m\le k<n$，则

$$\sum_{i=m}^{n}a_i=\sum_{i=m}^{k}a_i+\sum_{i=k+1}^{n}a_i$$

具体地，$\sum_{i=1}^{10}i=55$，而 $\sum_{i=1}^{4}i+\sum_{i=5}^{10}i=10+45=55$。✓

(d) 双重求和可交换次序。这是四条里最有用、也最容易用错的一条：

$$\sum_{i=1}^{s}\sum_{j=1}^{t}a_{i,j}=\sum_{j=1}^{t}\sum_{i=1}^{s}a_{i,j}\tag{3.1}$$

为什么。左边是「先按行加，再把各行之和相加」，右边是「先按列加，再把各列之和相加」。两者算的都是同一张数表上全部 $st$ 个数的总和，而数的加法满足结合律与交换律，所以按什么顺序加都一样。

验证。取 $s=3$、$t=2$，数表

$$A=\begin{pmatrix}1&2\\ 3&4\\ 5&6\end{pmatrix}$$

按行：$(1+2)+(3+4)+(5+6)=3+7+11=21$。按列：$(1+3+5)+(2+4+6)=9+12=21$。✓

$$\sum_{i=1}^{n}\sum_{j=1}^{i}a_{i,j}=\sum_{j=1}^{n}\sum_{i=j}^{n}a_{i,j}$$

左边枚举的是所有满足 $1\le j\le i\le n$ 的对 $(i,j)$。要把 $j$ 放外层，就得对每个固定的 $j$ 问「哪些 $i$ 配得上」——答案是 $j\le i\le n$。
记忆法：把不等式链重新读一遍，外层指标写在最左端，内层写在最右端。 这是唯一不会错的做法。

3.2 归纳法：一个必须算完的例子 #

证明对一切正整数 $n$，

$$\sum_{k=1}^{n}k=\frac{n(n+1)}{2}\tag{3.2}$$

取 $P(n)$ 为 (3.2)，$n_0=1$。

起始步。$n=1$ 时左边 $=1$，右边 $=\dfrac{1\cdot 2}{2}=1$。成立。

递推步。设 $P(n)$ 成立，即 $\sum_{k=1}^{n}k=\dfrac{n(n+1)}{2}$。要证 $P(n+1)$，即 $\sum_{k=1}^{n+1}k=\dfrac{(n+1)(n+2)}{2}$。

$$\begin{aligned}\sum_{k=1}^{n+1}k&=\left(\sum_{k=1}^{n}k\right)+(n+1)\\&=\frac{n(n+1)}{2}+(n+1)\\&=(n+1)\left(\frac{n}{2}+1\right)\\&=\frac{(n+1)(n+2)}{2}\end{aligned}$$

第一行按 3.1(c) 拆出最后一项；第二行用归纳假定；第三、四行是代数整理。于是 $P(n+1)$ 成立。

结论。由归纳法，(3.2) 对一切正整数 $n$ 成立。

3.3 归纳法：什么时候必须加强命题 #

这是归纳法真正的难点，也是主线证明里最常被跳过的一步。

设数列 $a_1,a_2,\dots$ 满足

$$a_1=1,\qquad a_2=1,\qquad a_n=a_{n-1}+2a_{n-2}\quad(n\ge 3)$$

猜出通项

$$a_n=\frac{2^{n}-(-1)^{n}}{3}\tag{3.3}$$

要证它对一切正整数 $n$ 成立。直接归纳会卡住。

起始步没问题：$n=1$ 时 $\dfrac{2-(-1)}{3}=1=a_1$ ✓；$n=2$ 时 $\dfrac{4-1}{3}=1=a_2$ ✓。

递推步卡在这里：设 $P(n)$ 成立，要证 $P(n+1)$。按递推式

$$a_{n+1}=a_n+2a_{n-1}$$

$a_n$ 可以用归纳假定替换，但 $a_{n-1}$ 不能——归纳假定只保证 $P(n)$ 成立，没保证 $P(n-1)$ 成立。式子推不下去。

解法：加强命题。令 $Q(n)$ 为「$P(n)$ 与 $P(n+1)$ 都成立」，$n_0=1$。

起始步：$Q(1)$ 就是 $P(1)$ 与 $P(2)$ 同时成立，上面已经验过，成立。

递推步：设 $Q(n)$ 成立，即 $P(n)$、$P(n+1)$ 都成立。要证 $Q(n+1)$，即 $P(n+1)$、$P(n+2)$ 都成立。前者由假定直接得到，只需证 $P(n+2)$：

$$\begin{aligned}a_{n+2}&=a_{n+1}+2a_{n}\\&=\frac{2^{n+1}-(-1)^{n+1}}{3}+2\cdot\frac{2^{n}-(-1)^{n}}{3}\\&=\frac{2^{n+1}+2\cdot 2^{n}}{3}+\frac{-(-1)^{n+1}-2(-1)^{n}}{3}\\&=\frac{4\cdot 2^{n}}{3}+\frac{(-1)^{n}-2(-1)^{n}}{3}\\&=\frac{4\cdot 2^{n}-(-1)^{n}}{3}\\&=\frac{2^{n+2}-(-1)^{n+2}}{3}\end{aligned}$$

第三行用了 $(-1)^{n+1}=-(-1)^{n}$，第四行用了 $2^{n+1}+2\cdot 2^{n}=4\cdot 2^{n}$；最后一行用了 $2^{n+2}=4\cdot 2^{n}$ 与 $(-1)^{n+2}=(-1)^{n}$。

于是 $Q(n+1)$ 成立。由归纳法，$Q(n)$ 对一切正整数 $n$ 成立，从而 $P(n)$ 对一切正整数 $n$ 成立。

3.4 逆序数：两个必须会算的数 #

(a) 倒序排列的逆序数是 $\dfrac{n(n-1)}{2}$

取 $(n,n-1,\dots,2,1)$。任取一对位置 $i<j$，第 $i$ 位是 $n+1-i$，第 $j$ 位是 $n+1-j$，而 $n+1-i>n+1-j$。所以每一对都是逆序。总对数是从 $n$ 个位置里取 $2$ 个：

$$\tau(n,n-1,\dots,1)=\binom{n}{2}=\frac{n(n-1)}{2}$$

这已是逆序数的最大值（每一对都逆序，不可能再有更多）。$n=5$ 时是 $10$。

(b) 一次相邻对换恰好改变逆序数 $1$

设排列 $c_1,\dots,c_n$，交换相邻的第 $i$ 位与第 $i+1$ 位。看每一对位置 $(u,v)$（$u<v$）：

• 若这一对既不涉及第 $i$ 位、也不涉及第 $i+1$ 位，这两个文字的先后次序没变，是否逆序也不变；
• 唯一可能变的是 $(c_i,c_{i+1})$ 这一对：交换后它们的先后次序颠倒。原来不是逆序，现在成了逆序；原来是，现在就不是。

所以逆序数加 $1$ 或减 $1$。一句话：$\tau$ 改变 $1$，于是符号 $s$ 变号。

(c) 一次任意对换也改变奇偶性

设交换第 $i$ 位与第 $j$ 位（$i<j$）。有两种算法，都值得看。

算法一：拆成相邻对换。 先把第 $i$ 位的文字一路向右搬到第 $j$ 位，需 $j-i$ 次相邻对换。此时原来第 $j$ 位的文字被挤到第 $j-1$ 位，再把它一路向左搬到第 $i$ 位，需 $j-1-i$ 次。总共

$$(j-i)+(j-1-i)=2(j-i)-1$$

次，是个奇数。由 (b)，每做一次相邻对换符号变号一次，奇数次之后符号必定变号。✓

算法二：直接用符号的乘积式。 把符号写成

$$s(c_1,\dots,c_n)=\prod_{1\le u<v\le n}\operatorname{sgn}(c_v-c_u)$$

交换第 $i$、$j$ 两位后，逐个因子看：

• 两个位置都不涉及 $i,j$ 的因子：不变；
• 因子 $(i,j)$ 本身：$\operatorname{sgn}(c_j-c_i)$ 变成 $\operatorname{sgn}(c_i-c_j)$，正是原来的相反数。这是唯一单独变号的因子；
• 对夹在中间的每个 $m$（$i<m<j$），因子 $(i,m)$ 与 $(m,j)$ 会成对地互换角色。原来贡献 $\operatorname{sgn}(c_m-c_i)\operatorname{sgn}(c_j-c_m)$；交换后贡献 $\operatorname{sgn}(c_m-c_j)\operatorname{sgn}(c_i-c_m)$，而后者等于 $\bigl(-\operatorname{sgn}(c_j-c_m)\bigr)\bigl(-\operatorname{sgn}(c_m-c_i)\bigr)$，与原来完全相等。

所以整串乘积只多了一个 $-1$：$s$ 变号。✓

算法二的好处是顺手证明了「符号只依赖奇偶性」：它根本不数交换次数，因此不受「换法不同、次数不同」的困扰。

3.5 奇偶排列各占一半 #

设 $n\ge 2$。在 $1,\dots,n$ 的全部 $n!$ 个排列中，偶排列与奇排列的个数相等，都是 $\dfrac{n!}{2}$。

证。定义一个映射：把每个排列的前两位交换。由 3.4(c)，它把偶排列送到奇排列、奇排列送到偶排列。再注意它自己是自己的逆：交换两次回到原样。所以它是偶排列集合与奇排列集合之间的一一对应。两边个数相等，总数 $n!$，故各 $\dfrac{n!}{2}$。∎

这个结论在 37 讲会直接用：行列式完全展开式里，正项与负项恰好一样多。

---

四、几何直观 / 记忆钩子 #

4.1 求和号是一层 for 循环 #

$\sum_{i=1}^{n}a_i$ 读作「$i$ 从 $1$ 到 $n$，把 $a_i$ 累加」，就是一段循环。二重求和是嵌套循环：

$$\sum_{i=1}^{s}\sum_{j=1}^{t}a_{i,j}\quad\longleftrightarrow\quad\text{for }i=1..s:\ \text{for }j=1..t:\ \text{acc}\mathrel{+}=a_{i,j}$$

一旦这样看，(3.1) 立刻变得显然：交换两层循环的先后，不影响累加的总和——前提是内层循环的范围不依赖外层。而「上限依赖外层」的情形，正相当于内层循环边界由外层变量决定；那时交换就必须重算边界，这就是 3.1(d) 那条警告的来历。

4.2 归纳法是骨牌，加强命题是把骨牌加厚 #

标准归纳：一排骨牌，推倒第一块，每块撞倒下一块。

需要加强命题时（3.3 节），把 $P(n)$ 换成 $Q(n)$，即「$P(n)$ 与 $P(n+1)$」。这等价于每块骨牌加厚成「两块黏在一起」：一次倒下的推力变大了，代价是起始时要一次推倒两块。整排的覆盖范围没变，只是重新切分了骨牌。

同理还有强归纳法（见第六节）：不是「上一块撞下一块」，而是「所有已倒下的骨牌一起撞下一块」。凡是证明 $n$ 的情形要拆成更小情形的，都得用这个版本。

4.3 逆序数就是「数有几对站错了队」 #

把排列想象成 $n$ 个人按身高站成一排，但站乱了。逆序数 = 有多少对人是「高个子站在矮个子前面」。

• 站得完全正确（自然排列）：一对都没有，$\tau=0$。
• 完全反着站：每一对都错，$\tau=\binom{n}{2}$，这是最乱的情况。

这个图景还解释两件事：

1. 逐个数右边更小的（2.6 的快速算法）为什么不会漏：每个「错对」恰好由它的左边那个人来数，一人一次。
2. 相邻对换只改 $1$：相邻两人换个位置，只影响他们这一对；其他人跟他们的相对次序完全没动。所以「乱度」只能变 $1$。

4.4 符号 $s$ 与函数 $\operatorname{sgn}$ 不是一个东西 #

初学最容易混的两个记号：

记号	定义在	取值
$\operatorname{sgn}(x)$	单个整数	$-1,0,1$（按 $x<0$、$x=0$、$x>0$）
$s(c_1,\dots,c_n)$	一个文字列	$-1$ 或 $1$（文字互不相同时）

反例：$s(0)=1$（只有一个文字的列，空积为 $1$），但 $\operatorname{sgn}(0)=0$；又 $s(-3)=1$，而 $\operatorname{sgn}(-3)=-1$。

一句话分清：$s$ 只看次序，$\operatorname{sgn}$ 只看大小。 建议把 $s(\cdot)$ 读成「排序分」，把 $\operatorname{sgn}(\cdot)$ 读成「正负号」。

---

五、常见误区 #

$$(n^{2}+1)+(2n+1)=(n+1)^{2}+1$$

看着完全正确。但 $P'(1)$ 是 $1=2$，起始步不成立。于是整个证明「证出」了一个假命题。
教训：每次写完递推步，回去看一眼起始步到底真不真。「显然成立」这四个字在这里最危险。

---

六、拓展（可选，可跳过） #

6.1 强归纳法 #

把递推步换成更强的假定：

设对每个整数 $n\ge n_0$ 都有「$P(n_0),P(n_0+1),\dots,P(n)$ 全都成立 $\Rightarrow P(n+1)$ 成立」，则 $P(n)$ 对一切 $n\ge n_0$ 成立。

它与标准归纳法逻辑等价（可以互相推出），但用起来方便得多：当 $P(n+1)$ 的证明需要用到某个更早的 $P(k)$ 而不只是 $P(n)$ 时，标准形式不够用，强形式刚好。

主线里典型的用法是「按维数归纳」：证 $n$ 维空间的性质时，往往要拆成一个更低维的子空间，再对它用归纳假定，而那个维数可能是 $n-2$ 甚至更小。

6.2 良序原理与三者的等价 #

良序原理：每个非空的正整数集合都有最小元。

它、强归纳法、标准归纳法三者逻辑等价。良序原理给出的证明常写成「反证 + 取最小反例」，读起来比归纳更短。例如 3.5 那种「配对」论证，也可以改写成「若存在反例，取最小的一个，再导出更小的反例」。

6.3 排列的循环分解 #

任何排列都能（不计次序地唯一）分解成若干个循环的复合。例如循环 $(1\,3\,5)$ 表示 $1$ 去 $3$ 的位置、$3$ 去 $5$ 的位置、$5$ 去 $1$ 的位置。

一个长 $k$ 的循环可写成 $k-1$ 次对换，所以排列的奇偶性 = 「$n$ 减去循环个数」的奇偶性。这个视角在群论里更自然，本课用不到，但看到「对换次数」时不妨想想它。

6.4 这三样在主线里的落点 #

1. 线性组合：$v=\sum_{j=1}^{n}a_jv_j$（04 讲）。这里 $a_j$ 是标量、$v_j$ 是向量，求和号加的是向量——向量加法同样满足结合律与交换律，所以 3.1 的四条规则一条不改就能用。
2. 矩阵乘法：$[AB]_{i,j}=\sum_{k=1}^{n}[A]_{i,k}[B]_{k,j}$（09 讲）。这是双重求和交换次序最重要的应用场景。
3. 行列式完全展开：$\det A=\sum_{(j_1,\dots,j_n)}s(j_1,\dots,j_n)[A]_{j_1,1}\cdots[A]_{j_n,n}$（37 讲）。一个式子里同时用上了本篇三件工具：求和号（遍历所有排列）、排列（$j_1,\dots,j_n$ 跑遍 $\operatorname{perm} n$）、逆序数（给每项定符号）。

---

七、自测（先做，再看答案） #

1. 计算 $\sum_{i=1}^{5}(2i-1)$ 与 $\sum_{j=2}^{6}(2j-3)$，比较两者。

2. 用归纳法证明：对一切正整数 $n$，$2^{n}>n$。

3. 求排列 $(4,1,3,5,2)$ 的逆序数，判断奇偶性。再说明把它换回自然排列至少要几次相邻对换。

4. 把 $\sum_{i=1}^{n}\sum_{j=i}^{n}a_{i,j}$ 改写成外层为 $j$ 的形式。

5. 用归纳法证明：$n\ge 2$ 时，$\dfrac{1}{1\cdot 2}+\dfrac{1}{2\cdot 3}+\cdots+\dfrac{1}{(n-1)n}=1-\dfrac{1}{n}$。

答案（点开）

1. 第一个：$1+3+5+7+9=25$。第二个：$j=2$ 到 $6$，各项为 $1,3,5,7,9$，和也是 $25$。
两者相等并不奇怪：令 $j=i+1$，则 $2j-3=2(i+1)-3=2i-1$，上下限同步平移，正是 3.1(b) 的平移换标。

2. 取 $P(n)$ 为 $2^{n}>n$，$n_0=1$。
起始步：$2^{1}=2>1$ ✓。
递推步：设 $2^{n}>n$（$n\ge 1$）。则 $2^{n+1}=2\cdot 2^{n}>2n=n+n\ge n+1$，最后一个不等号用了 $n\ge 1$。故 $P(n+1)$ 成立。
（注意这一步必须用到 $n\ge 1$：若允许 $n=0$，则 $n+n\ge n+1$ 变成 $0\ge 1$，不成立。所以 $n_0$ 只能取 $1$。）

3. 逐个数右边比它小的：$4$ 右边有 $1,3,2$，$3$ 个；$1$ 右边没有，$0$ 个；$3$ 右边有 $2$，$1$ 个；$5$ 右边有 $2$，$1$ 个；$2$ 在末尾，$0$ 个。合计 $\tau=3+0+1+1+0=5$，是奇排列，符号为 $-1$。
自然排列是 $(1,2,3,4,5)$。至少需要 $5$ 次相邻对换：一次只能改 $1$，要从 $\tau=5$ 降到 $0$ 至少 $5$ 次。但也可以绕成 $7$ 次、$9$ 次——次数不唯一，奇偶性唯一（都是奇数次）。

4. 不等式链是 $1\le i\le j\le n$。外层写 $j$（最左），内层写 $i$：

$$\sum_{i=1}^{n}\sum_{j=i}^{n}a_{i,j}=\sum_{j=1}^{n}\sum_{i=1}^{j}a_{i,j}$$

验 $n=3$：左边加了 $a_{1,1},a_{1,2},a_{1,3},a_{2,2},a_{2,3},a_{3,3}$ 共 $6$ 项；右边 $j=1$ 给 $a_{1,1}$，$j=2$ 给 $a_{1,2},a_{2,2}$，$j=3$ 给 $a_{1,3},a_{2,3},a_{3,3}$，也是这 $6$ 项。✓

5. 取 $P(n)$ 为所给等式，$n_0=2$。
起始步：$n=2$ 时左边只有 $\dfrac{1}{1\cdot 2}=\dfrac12$，右边 $1-\dfrac12=\dfrac12$ ✓。
递推步：设 $n\ge 3$ 时 $P(n-1)$ 成立。则

$$\begin{aligned}\sum_{k=2}^{n}\frac{1}{(k-1)k}&=\left(\sum_{k=2}^{n-1}\frac{1}{(k-1)k}\right)+\frac{1}{(n-1)n}\\&=\left(1-\frac{1}{n-1}\right)+\frac{1}{(n-1)n}\\&=1-\frac{1}{n-1}\left(1-\frac{1}{n}\right)\\&=1-\frac{1}{n-1}\cdot\frac{n-1}{n}\\&=1-\frac{1}{n}\end{aligned}$$

这是把 $P(n-1)$ 当归纳假定，等价于标准形式的「$P(n)\Rightarrow P(n+1)$」。$n_0=2$ 的原因：$n=1$ 时被加项在 $k=1$ 处无意义（分母为 $0$），所以只能从 $n=2$ 起。

---

八、复习卡 #

项	内容
求和号	$\sum_{i=m}^{n}a_i=a_m+\cdots+a_n$；$\sum$ 来自 sum
哑变量	$\sum_{i}a_i=\sum_{j}a_j$；嵌套时不能与别处字母撞名
提常数	$\sum c\,a_i=c\sum a_i$；$c$ 必须与指标无关
平移换标	$\sum_{i=1}^{n}a_i=\sum_{j=0}^{n-1}a_{j+1}$；指标、上下限、被加项三处同改
拆区间	$\sum_{i=m}^{n}=\sum_{i=m}^{k}+\sum_{i=k+1}^{n}$
换次序	$\sum_{i=1}^{s}\sum_{j=1}^{t}a_{i,j}=\sum_{j=1}^{t}\sum_{i=1}^{s}a_{i,j}$（上限互不依赖才成立）
上限依赖时	读不等式链：$\sum_{i}\sum_{j\le i}=\sum_{j}\sum_{i\ge j}$
空和 / 空积	空和 $=0$，空积 $=1$；由拆分律反解出来
归纳法	起始步 $P(n_0)$ + 递推步「$\forall n\ge n_0$：$P(n)\Rightarrow P(n+1)$」，缺一不可
归纳假定	递推步里可以拿 $P(n)$ 当已知用，这是全部「便宜」的来源
加强命题	推不动时把 $P(n)$ 换成 $Q(n)$：$P(n)\wedge P(n+1)$
强归纳	假定 $P(n_0),\dots,P(n)$ 全成立，再证 $P(n+1)$
排列	$1,\dots,n$ 的重排，共 $n!$ 个；自然排列是升序那个
逆序 / 逆序数	$i<j$ 而 $c_i>c_j$ 即一个逆序；$\tau=\sum_{i<j}\rho(c_i,c_j)$
快速算法	逐个数「右边比它小的有几个」，相加
符号	$s=(-1)^{\tau}$；$s=1$ 偶排列，$s=-1$ 奇排列
最大逆序数	$\tau(n,\dots,1)=\binom{n}{2}=\dfrac{n(n-1)}{2}$
相邻对换	逆序数改变恰好 $1$
任意对换	等于 $2(j-i)-1$ 次相邻对换，是奇数；故符号变号
奇偶各半	$n\ge 2$ 时偶排列与奇排列各 $\dfrac{n!}{2}$ 个
$s$ vs $\operatorname{sgn}$	$s$ 看次序（文字列，可含重复），$\operatorname{sgn}$ 看大小（单个整数）

---

九、出处与延伸（可选，不影响阅读） #

• 求和号、求积号、数学归纳法：主要依据《行列式入门》附录 B「求和号与数学归纳法」，印刷 p171 起。其中 B.1 求和号 p172–176（换标、多重求和、交换次序、带条件的求和、空和约定），B.2 求积号 p177–181（与求和号逐条对应，仅空积为 $1$），B.3 数学归纳法 p182–187（原理、标准例题、缺起始步与缺递推步的反例、需要加强命题的例题；p187 结尾另有一个「分解为不可约数之积」的强归纳例题）。
• 排列、逆序数、符号：同一本教材的 1.2「排列」印刷 p5（排列的定义与 $n!$ 的计数），1.4「逆序数与符号」印刷 p7–9（逆序、逆序数、$\operatorname{sgn}$、符号定义与 $s=(-1)^{\tau}$）。附录 C.2「排列」印刷 p214–219 从「对换」的角度重讲了一遍：对换与相邻对换的定义（p214）、「$\tau$ 次相邻对换可回到自然排列」的归纳证明（p214–216）、「对换改变符号」（p216）、「奇偶排列各半」（p217），以及它与行列式完全展开的关系（p217–219）。
• 另一套记号与讲法：《线性代数应该这样学》（第四版）第 9 章 9B 节把排列定义为 $\operatorname{perm} m$ 的元素，把符号直接定义为 $\operatorname{sign}(j_1,\dots,j_m)=(-1)^{N}$，其中 $N$ 是「$k$ 排在 $\ell$ 之后」的数对 $(k,\ell)$（$k<\ell$）的个数，并明确注出这个 $N$ 就是逆序数（印刷 p291）。同一节「交换排列中的两项」用「不符合自然顺序的数对个数净变化为奇数」来证明符号变号（印刷 p292），与本篇 3.4(c) 的算法二是同一思想的两种写法。
• 术语别名：逆序数 = 反序数 = inversion number，记法有 $\tau$、$N$、$\operatorname{inv}$ 等多种；排列的符号 = 排列的奇偶性符号，记法有 $s$、$\operatorname{sgn}$、$\operatorname{sign}$、$(-1)^{\tau}$；偶排列 = even permutation，奇排列 = odd permutation。「对换」在有的资料里叫「换位」或 transposition，「相邻对换」也叫「邻换」。
• 想深挖时可查：任何一本抽象代数教材的「对称群 $S_n$」一节，会讲本篇 6.3 提到的循环分解，并给出「$S_n$ 的换位子群就是交错群 $A_n$」这一结论——它正是「奇偶各半」的结构性解释。
• 一个提醒：本篇 2.6 把「偶排列 / 奇排列」作为术语引入，而《行列式入门》只用「符号为 $1$ / 符号为 $-1$」的说法。两者是同一件事，读其他资料时不必因为用词不同而怀疑自己。