Bóna · 枚举与解析组合学导论 · 第 4 章 排列的计数

4.2　排列的循环结构The cycle structure of permutations

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演 / 即时自测）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。

到目前为止，我们一直把排列（permutation）看作若干对象的线性顺序（linear order）。但这并不是看待排列的唯一方式，而别的方式会让排列变得更有趣。

本节目标把排列从“一排队伍”改看成“若干个首尾相接的环”。这能直接回答一个看起来与排列无关的计数问题：把 \(n\) 位客人安排到 \(k\) 张相同的圆桌旁，有多少种不同坐法？答案就是“恰有 \(k\) 个循环的 \(n\)-排列的个数”，记作 \(c(n,k)\)，称为第一类（无符号）Stirling 数。本节将给出它的递推式和一条一眼可算的公式。

4.2.1　第一类 Stirling 数

现在让我们回到“第二辆旅游大巴”的问题。回忆一下：那辆大巴上的 \(n\) 位游客选择去了一家全套服务的餐厅，他们围坐在 \(k\) 张相同的桌子旁。若在两种坐法中每个人的左邻都相同，则认为这两种坐法相同。这些游客一共有多少种不同的坐法？（注意我们以前在例 3.31 中考虑过这个问题，当时是用生成函数解决的。）

乍一看，甚至看不出这个问题与排列有什么关系。的确，按目前所学，排列是线性顺序；而这里桌子是圆形的。再者，排列中对象的先后顺序当然要紧，而这里所有桌子都是相同的。然而我们将要说明：这其实就是一个排列计数问题；我们只需把对“排列”的理解拓宽一点就能明白。

设 \(p=p_1p_2\cdots p_n\) 是一个排列。那么我们可以把 \(p\) 看成一个函数——事实上是一个双射（bijection）——它把 \([n]\) 映到 \([n]\)，即由 \(p(i)=p_i\)（对一切 \(i\in[n]\)）所定义的函数。这种看待排列的方式本身就有几个好处。其中之一是它给出了定义两个排列之乘积的自然方式。

定义 4.13 设 \(f\) 与 \(g\) 是两个排列，即两个从 \([n]\) 到 \([n]\) 的双射。则 \(fg\) 是由 \[fg(i)=g(f(i))\qquad(\text{对一切 } i\in[n])\] 所定义的排列。

换句话说，\(fg\) 就是把 \(f\) 与 \(g\) 当作函数所作的复合。

例 4.14 设 \(n=6\)，\(f=421563\)，\(g=361524\)。请读者自行验证 \(fg=563241\)，而 \(gf=134625\)。
把例 4.14 算一遍 先把一行记号读成函数。\(f=421563\) 表示 \(f(1)=4,\;f(2)=2,\;f(3)=1,\;f(4)=5,\;f(5)=6,\;f(6)=3\)；\(g=361524\) 表示 \(g(1)=3,\;g(2)=6,\;g(3)=1,\;g(4)=5,\;g(5)=2,\;g(6)=4\)。用 \(fg(i)=g(f(i))\)：
  1. \(fg(1)=g(f(1))=g(4)=5\)。
  2. \(fg(2)=g(f(2))=g(2)=6\)。
  3. \(fg(3)=g(f(3))=g(1)=3\)。
  4. \(fg(4)=g(f(4))=g(5)=2\)。
  5. \(fg(5)=g(f(5))=g(6)=4\)。
  6. \(fg(6)=g(f(6))=g(3)=1\)。
连起来 \(fg=563241\)，与书上一致。读者可同样验证 \(gf(i)=f(g(i))\) 得到 \(134625\)。

你也许会问：为什么我们定义 \(fg(i)=g(f(i))\)，而不是 \(fg(i)=f(g(i))\)？原因是我们希望按照函数相乘的书写顺序来逐个施加它们。在 \(g(f(i))\) 中，我们先把 \(f\) 作用于 \(i\)，再把 \(g\) 作用于 \(f(i)\)。

我们要强调：正如上面的例子所示，\(fg\) 与 \(gf\) 一般并不相同；也就是说，排列的乘法不是可交换运算。

把排列看作函数还有另一个有用的性质：现在我们可以谈论一个排列的逆了。排列 \(p\) 的逆，记作 \(p^{-1}\)，就是双射 \(p\) 的逆映射。也就是说，若 \(p(i)=j\)，则 \(p^{-1}(j)=i\)。等价地，我们有 \(pp^{-1}=p^{-1}p=123\cdots n\)，即那个递增的排列，我们也称之为恒等排列（identity permutation）。

我们能够把排列相乘、能够取它们的逆，再加上若干其他重要性质，这就开辟了研究排列的新途径。这些内容中有许多属于群论（group theory），在那里全体 \(n\)-排列构成的集合被称为 \(n\) 次对称群（symmetric group），记作 \(S_n\)。虽然置换群理论超出了本书范围，但我们有时会用记号 \(S_n\) 来表示全体 \(n\)-排列的集合。

既然现在能把 \(n\)-排列相乘，特别地，我们就能谈论排列 \(p\) 的幂了。计算 \(p\) 的幂甚至比计算任意乘积更容易。事实上，我们只需画出 \(p\) 的短图（short diagram），观察当 \(p\) 被反复施加时 \([n]\) 中每个元素会变成什么。（函数 \(f:[n]\to[n]\) 的短图由 \(n\) 个点组成，代表 \([n]\) 的元素，外加 \(n\) 支箭头，代表 \(f\) 在 \([n]\) 上的作用。）

例 4.15 设 \(p=321645\)，让我们仔细观察一下 \(p^k\)（\(k=1,2,\cdots\)）。利用图 4.2 中 \(p\) 的短图，可得： 我们看到：元素 \(1\) 与 \(3\) 不断地在彼此之间交换，元素 \(2\) 始终保持不动，而元素 \(4,5,6\) 始终在它们三者之间循环地轮换。
1 3 循环 (1 3)：1→3→1 2 循环 (2)：不动点 4 6 5 循环 (4 6 5)：4→6→5→4
图 4.2　\(p=321645\) 的短图。每个点引出一支箭头指向它的像 \(p(i)\)。箭头自然地把 \([6]\) 分成三个互不相交的环：\((1\,3)\)、\((2)\)、\((4\,6\,5)\)。

一般地，若 \(p\) 是一个 \(n\)-排列，\(i\in[n]\)，则存在正整数 \(k\) 使得 \(p^k(i)=i\)。事实上，由鸽巢原理（pigeonhole principle），存在两个正整数 \(t\) 与 \(u\)，满足 \(t>u\) 且 \(p^t(i)=p^u(i)\)（因为 \(p^t(i)\) 只有 \(n\) 种可能取值，而 \(t\) 却有无穷多个）。这就意味着（为什么？）\(p^{\,t-u}(i)=i\)，于是令 \(k=t-u\)，命题得证。

为什么 \(p^t(i)=p^u(i)\) 能推出 \(p^{\,t-u}(i)=i\)因为 \(p\) 是双射，它有逆 \(p^{-1}\)。在 \(p^t(i)=p^u(i)\) 两边各作用 \(u\) 次 \(p^{-1}\)（即乘以 \(p^{-u}\)），左边变成 \(p^{\,t-u}(i)\)，右边变成 \(p^{\,0}(i)=i\)。所以 \(p^{\,t-u}(i)=i\)。

现在让我们取使 \(p^k(i)=i\) 成立的最小正整数 \(k\)。那么，当我们画出 \(p\) 的图时，元素 \(i\) 会落在一个长度为 \(k\) 的环 \(C\) 上。由于 \(p\) 是双射，这个环必与 \(p\) 短图中其余的环互不相交。因此，若 \(j\in C\)，则 \(p(j)\in C\)，于是 \(p\) 把 \(C\) 中的元素在彼此之间置换。进一步地，\(p(j)\) 是 \(j\) 在 \(C\) 中的左邻，所以 \(p\) 把 \(C\) 中的元素循环地在彼此之间置换。因此称 \(C\) 为 \(p\) 的包含 \(i\) 的循环（cycle）。

若 \(C\) 的元素个数少于 \(n\)，则取一个不属于 \(C\) 的元素 \(i'\)。让 \(i'\) 扮演 \(i\) 的角色，重复上述过程，找出 \(p\) 的包含 \(i'\) 的循环 \(C'\)。由于 \(p\) 是双射，\(C'\) 与 \(C\) 互不相交。若 \(C\cup C'=[n]\) 则停止，否则继续这样做，直到整个集合 \([n]\) 被分解为互不相交的循环。所得到的循环集合 \(\{C,C',\cdots\}\) 称为 \(p\) 的循环分解（cycle decomposition）。

读者也许觉得我们在“耍赖”——在还没有证明每个排列 \(p\) 都有唯一的循环分解之前，就大谈循环分解。为打消这一顾虑，我们指出：只要知道了 \(p\)，就知道了对一切 \(i\in[n]\) 的 \(p(i)\)，因而可以画出 \(p\) 的整张图——它是被 \(p\) 唯一确定的。

动手：把排列拆成循环 以 \(p=321645\) 为例，按上面的过程一步步找循环（每次从“尚未用过的最小元素”起步）：
  1. 从 \(1\) 出发：\(1\xrightarrow{p}3\xrightarrow{p}1\)，回到了起点，得到循环 \((1\,3)\)。
  2. 下一个未用元素是 \(2\)：\(2\xrightarrow{p}2\)，立刻回到自身，得到不动点循环 \((2)\)。
  3. 下一个未用元素是 \(4\)：\(4\xrightarrow{p}6\xrightarrow{p}5\xrightarrow{p}4\)，得到循环 \((4\,6\,5)\)。
  4. 元素已全部用完，分解为 \((1\,3)(2)(4\,6\,5)\)，恰好 \(3\) 个循环。
注意：起步元素选谁、循环之间的先后顺序，都不影响“最终是哪些环”，因为每个元素的像 \(p(i)\) 是固定的。这正是“循环分解唯一”的直观来源。

如果我们想用一种便于看清循环的方式来书写一个排列，可以把同一循环中的元素按它们在循环里出现的顺序写进一对括号里。

例 4.16 用循环记号，排列 \(p=321645\) 可写成 \((1\,3)(2)(4\,6\,5)\)。

希望你此刻正在问：为什么我不写成 \((3\,1)(2)(5\,4\,6)\)，或者也许 \((6\,5\,4)(2)(3\,1)\)？这些记法以及其他记法也都是可以接受的，只要它们都正确地表明了每个元素的像是什么。（例如，\((4\,6\,5)\) 不能换成 \((4\,5\,6)\)，因为在前一个循环里 \(4\) 映到 \(6\)，而在后一个循环里 \(4\) 却映到 \(5\)。）当然，循环之间的顺序可以任意改变，每个循环也可以从任何元素开始写。然而，为清晰起见，定义一种对每个排列都唯一的“规范循环记号”，显然是有好处的。

定义 4.17 设 \(p\) 是一个排列。则 \(p\) 的规范循环记号（canonical cycle notation）的写法是：把每个循环都以其最大元素打头来书写，然后把各循环按其最大元素从小到大排列。
例 4.18 例 4.16 中排列 \(p\) 的规范循环记号是 \((2)(3\,1)(6\,5\,4)\)。
规范记号怎么排出来 拿 \(p=321645\) 的三个循环 \((1\,3)\)、\((2)\)、\((4\,6\,5)\)：
  1. 每个循环“最大元素打头”，再沿箭头续写：\((1\,3)\to(3\,1)\)；\((2)\to(2)\)；\((4\,6\,5)\) 中最大是 \(6\)，从 \(6\) 起 \(6\to5\to4\)，得 \((6\,5\,4)\)。
  2. 各循环的最大元素分别是 \(2,3,6\)，按从小到大排列循环。
  3. 得到唯一的规范记号 \((2)(3\,1)(6\,5\,4)\)。
（注：本书原文此处把这个 \(3\)-循环写成 \((6\,4\,5)\) 形式，是按相反方向读取循环；本页统一采用“括号内紧跟的下一个元素就是它的像”这一更常见约定，故写作 \((4\,6\,5)\)，与例 4.15 的 \(p(4)=6,\,p(6)=5,\,p(5)=4\) 以及图 4.2 完全一致。两种写法表示的是同一个排列 \(p=321645\)。）

读者现在大概已经注意到我们想把这一切引向何方了。我们已经表明：一个排列不仅可以看作一个线性顺序，也可以看作一个循环的集合。这正是开头那个问题所需要的——\(n\) 位游客围坐在 \(k\) 张相同圆桌旁有多少种坐法。回答这个问题的数如此重要，以至于它有自己的名字。

定义 4.19 恰有 \(k\) 个循环的 \(n\)-排列的个数记作 \(c(n,k)\)，称为第一类无符号 Stirling 数（signless Stirling number of the first kind）。
为什么“坐法 = 循环数”把每张圆桌看成一个循环：桌旁的人“按逆时针的左邻关系”首尾相接，正好就是一个 \(p(j)=\)（\(j\) 的左邻）的循环。两种坐法相同 \(\iff\) 每个人的左邻都相同 \(\iff\) 对应的循环集合相同 \(\iff\) 对应的排列 \(p\) 相同。所以“\(n\) 人围 \(k\) 桌的坐法数”就是“恰有 \(k\) 个循环的 \(n\)-排列数”，即 \(c(n,k)\)。

到此我们承诺：在本节末尾会解释为什么这里要用“无符号”（signless）这个神秘的形容词。而“Stirling 数”这个名字听起来或许就不那么意外了。的确，第二类 Stirling 数 \(S(n,k)\) 是把 \([n]\) 划分为 \(k\) 个块的方案数，而现在我们又听说第一类（无符号）Stirling 数是 \([n]\) 的、恰有 \(k\) 个循环的排列数。这两组数之间的联系其实比这强得多，我们也将在本节稍后说明。

注意，不限定循环个数时，全体 \(n\)-排列的个数当然等于 \[n!=\sum_{k=1}^{n}c(n,k),\] 这就解开了例 3.31 之谜。回忆在那个例子中，我们求出“\(n\) 人围坐在不指定数目的若干张圆桌旁”的坐法数恰为 \(n!\)。在当时看来这有点神秘，因为那时我们只把排列理解为线性顺序，而不是循环的并。

读者如今已是组合定义的老手，因此不会对下面的约定感到意外：对 \(k>n\) 我们设 \(c(n,k)=0\)，对正整数 \(n\) 设 \(c(n,0)=0\)，而 \(c(0,0)=1\)。

显然 \(c(n,n)=1\)，因为一个 \(n\)-排列 \(f\) 只有在每个循环都长度为 \(1\)（即对一切 \(i\) 都有 \(f(i)=i\)）时才能有 \(n\) 个循环——这正是 \([n]\) 上的恒等映射。\(c(n,1)\) 确定起来稍复杂，但我们在例 1.22 中本质上已经做过。请读者此刻先试着证明 \(c(n,1)=(n-1)!\)，再把自己的论证与上述例子中我们的论证相比较。

为什么 \(c(n,1)=(n-1)!\) 恰有 \(1\) 个循环，就是把 \(n\) 个人排成一张圆桌。
  1. 把规范记号里那唯一的循环以最大元素 \(n\) 打头。
  2. 余下的 \(n-1\) 个元素 \(\{1,2,\dots,n-1\}\) 依次填到 \(n\) 后面的 \(n-1\) 个位置上，是一个 \((n-1)\)-排列，有 \((n-1)!\) 种填法。
  3. 每种填法给出不同的循环，故 \(c(n,1)=(n-1)!\)。例如 \(c(3,1)=2!=2,\;c(4,1)=3!=6,\;c(5,1)=4!=24\)。

虽然一般情形下 \(c(n,k)\) 的显式公式是存在的，但它非常复杂，其证明也超出本书范围。我们将看到这并不算什么严重的问题，因为可以用别的办法极快地求出我们想要的 \(c(n,k)\)。为此，我们先证明关于这些数的一条三角递推。

定理 4.20 对一切满足 \(k\le n\) 的正整数 \(n,k\)，递推关系 \[\tag{4.6}c(n,k)=c(n-1,k-1)+(n-1)\,c(n-1,k)\] 成立。

我们可以在特例 \(k=1\) 下验证这个恒等式。这时我们知道 \(c(n,1)=(n-1)!\)，而右端 \(c(n-1,0)=0\)、\(c(n-1,1)=(n-2)!\)，于是右端等于 \((n-1)\cdot(n-2)!=(n-1)!\)，可见恒等式在此特例下确实成立。现在转向一般情形。

证明（定理 4.20）. 我们要证的只是：(4.6) 的右端也在计数那些恰有 \(k\) 个循环的 \([n]\) 的排列。设 \(p\) 是被 \(c(n,k)\) 计数的一个排列。那么 \(p\) 中的元素 \(n\) 要么自成一个循环，要么与其他元素同处一个循环。（这就如同最后进入餐厅的那位游客，要么坐到一张新桌，要么坐到已经有人的某张桌。） 把两种情形的计数合起来，即完成证明。♦
为什么“插入”恰有 \(n-1\) 种 第二种情形里 \(q\) 是 \([n-1]\) 的排列，共 \(n-1\) 个元素。把 \(n\) 插到“某元素的前面”，候选的“某元素”有 \(n-1\) 个，所以有 \(n-1\) 种插法。例如 \(q=(2\,1)(3)\)（即 \([3]\) 上 \(1\to2,2\to1,3\to3\)），把 \(4\) 插入（“插到 \(j\) 前”即令 \(4\to j\)）：插到 \(1\) 前得 \((2\,4\,1)(3)\)、插到 \(2\) 前得 \((2\,1\,4)(3)\)、插到 \(3\) 前得 \((2\,1)(3\,4)\)，得到 \(3\) 个互不相同、且循环个数仍为 \(2\) 的排列。这正是 \(n-1=3\)。

在习题 35 中，读者将被要求为例 3.37 那个神秘的结果给出一个不用生成函数的证明。像上面证明中所用的那种想法，对解那道习题会有帮助。

下面这条定理给出了一种确定 \(c(n,k)\) 的极其简单的方法。这就是我们承诺过的计算这些数的方法。

定理 4.21 对一切正整数 \(n\)，恒等式 \[\tag{4.7}\sum_{k=1}^{n}c(n,k)\,x^{k}=(x+n-1)(x+n-2)\cdots(x+1)\,x\] 成立。

换句话说，如果对某个固定的 \(n\) 需要这些数 \(c(n,k)\)，我们要做的只是展开乘积 \((x+n-1)(x+n-2)\cdots(x+1)x\)——对任何软件来说这都是小菜一碟——然后把所得多项式各项的系数读出来，那就是 \(c(n,k)\)。

例 4.22 设 \(n=3\)。则 \((x+2)(x+1)x=x^{3}+3x^{2}+2x\)，于是 \(c(3,3)=1,\;c(3,2)=3,\;c(3,1)=2\)。我们知道这些数是对的，因为：恰有三个循环的 \(3\)-排列只有一个（恒等排列，因为所有循环都必须是 \(1\)-循环）；恰有两个循环的 \(3\)-排列有三个（一个循环必是 \(1\)-循环、另一个是 \(2\)-循环——先选出那个 \(1\)-循环，剩下两个元素必构成 \(2\)-循环）；恰有一个循环的 \(3\)-排列有两个（我们可以选 \(1\) 的像，其余随之确定）。
把例 4.22 的三种排列列全 直接把 \(S_3\) 的 \(3!=6\) 个排列按循环个数分类，验证 \(2+3+1=6\)：
  1. \(1\) 个循环（\(c(3,1)=2\)）：\((3\,1\,2)\) 即 \(231\)，\((3\,2\,1)\) 即 \(312\)。
  2. \(2\) 个循环（\(c(3,2)=3\)）：\((2\,1)(3)=213\)，\((3\,1)(2)=321\)，\((3\,2)(1)=132\)。
  3. \(3\) 个循环（\(c(3,3)=1\)）：\((1)(2)(3)=123\)，即恒等排列。
合计 \(2+3+1=6=3!\)，与 \(\sum_k c(3,k)=n!\) 吻合。
证明（定理 4.21）. 注意右端可以写成简短形式 \((x+n-1)_n\)（这里 \((y)_m=y(y-1)\cdots(y-m+1)\) 是下降阶乘，取 \(y=x+n-1,\;m=n\) 即得 \((x+n-1)(x+n-2)\cdots x\)）。我们将对 \(n\) 作归纳来证明结论。 当 \(n=1\) 时，方程化为 \(x=x\)，结论显然成立。 现在假设结论对 \(n-1\) 成立，即 \[\sum_{k=1}^{n-1}c(n-1,k)\,x^{k}=(x+n-2)_{\,n-1}.\] 为得到 \((x+n-1)_n\)，即 (4.7) 的右端，我们把上式两边都乘以 \(x+n-1\)，得到 \[\sum_{k=1}^{n-1}c(n-1,k)\,x^{k+1}+(n-1)\sum_{k=1}^{n-1}c(n-1,k)\,x^{k}=(x+n-1)_n.\] 注意左端 \(x^{k}\) 的系数恰好是 \(c(n-1,k-1)+(n-1)\,c(n-1,k)\)，由定理 4.20 它等于 \(c(n,k)\)。（即便在特例 \(k=n\) 下也成立。）因此最后这个方程化为 \[\sum_{k=1}^{n}c(n,k)\,x^{k}=(x+n-1)_n,\] 归纳步骤得证。♦
第一类无符号 Stirling 数 \(c(n,k)\)（用 (4.7) 展开读系数） n＼k 12345 11 211 3231 461161 5245035101 每行之和 \(=n!\)：1, 2, 6, 24, 120；递推 \(c(n,k)=c(n-1,k-1)+(n-1)c(n-1,k)\)
例如 \(c(4,2)=c(3,1)+3\cdot c(3,2)=2+3\cdot3=11\)，\(c(5,2)=c(4,1)+4\cdot c(4,2)=6+4\cdot11=50\)，与展开 \((x+n-1)\cdots x\) 所得系数一致。

注意，即使 (4.7) 左端的求和从 \(k=0\)（而非 \(k=1\)）开始，等式仍然成立。事实上，这一替换只在 \(n=0\) 时改变左端的值，因为否则总有 \(c(n,0)=0\)。

现在到了揭示“第一类无符号 Stirling 数”与“第二类 Stirling 数”之间联系、并首先说清“无符号”这个形容词含义的时候了。

请回忆你在线性代数中学过的：全体实系数多项式的集合 \(V\) 构成实数域上的一个向量空间（vector space），而多项式的无穷集合 \(B=\{1,x,x^{2},\cdots\}\) 构成这个向量空间的一组基（basis）。万一你忘了这是什么意思，我们提醒一下：它的意思是 \(V\) 的每个元素都能唯一地写成 \(B\) 中元素的线性组合，且该线性组合的系数都是实数。

用这套术语来说，公式 (4.7) 告诉我们的是：当我们把多项式 \((x+n-1)_n\) 写成 \(B\) 中元素的（唯一）线性组合时，该线性组合的系数恰好就是按正确顺序排列的第一类无符号 Stirling 数。

现在让我们回顾第 2 章习题 11，我们相信读者早已做出。在那道习题中，我们证明了 \[\tag{4.8}x^{n}=\sum_{k=0}^{n}S(n,k)\,(x)_{k}.\] 换句话说，如果把 \(B\) 中的元素写成 \(V\) 的另一组基 \(B'=\{1,(x)_1,(x)_2,\cdots\}\)（其中 \((x)_k=x(x-1)\cdots(x-k+1)\) 为下降阶乘）中元素的线性组合，则其系数恰好就是按正确顺序排列的第二类 Stirling 数。

公式 (4.7) 与 (4.8) 听起来确实颇为相似，但可以看出它们并不是彼此“互逆”的——也就是说，并不是一个会“撤销”另一个所做的事。这是因为：一个把多项式 \((x+n-1)_n\) 用多项式 \(x^{n}\) 来表达，而另一个把多项式 \(x^{n}\) 表达出来，所用的不是多项式 \((x+n-1)_n\)，而是多项式 \((x)_k\)。下面的定义与命题将纠正这一点。

定义 4.23 对一切非负整数 \(n,k\)，设 \(s(n,k)=(-1)^{\,n-k}\,c(n,k)\)。这些数 \(s(n,k)\) 称为第一类 Stirling 数（Stirling numbers of the first kind）。

这就交代了 \(c(n,k)\) 名字里“无符号”这个形容词的来历。借助这一定义，还可以把 (4.7) 改写如下。

命题 4.24 对一切非负整数 \(n\)，有 \[\tag{4.9}\sum_{k=0}^{n}s(n,k)\,x^{k}=(x)_{n}.\]
把 (4.7)(4.8)(4.9) 串起来
  1. (4.7)：\(\sum_k c(n,k)x^k=(x+n-1)(x+n-2)\cdots x\)，系数全为正（无符号）。
  2. 定义 4.23 给系数加上交错符号：\(s(n,k)=(-1)^{n-k}c(n,k)\)。这等价于把 (4.7) 里的 \(x\) 处理成使每个因子变号，从而把 \((x+n-1)\cdots x\) 变成下降阶乘 \((x)_n=x(x-1)\cdots(x-n+1)\)。
  3. 于是得到 (4.9)：\(\sum_k s(n,k)x^k=(x)_n\)。现在它与 (4.8)（\(x^n=\sum_k S(n,k)(x)_k\)）才真正成为一对“互逆”的换基关系——一个把幂 \(x^n\) 换成下降阶乘 \((x)_k\)，另一个把下降阶乘 \((x)_n\) 换回幂 \(x^k\)。
小验证（\(n=3\)）：\((x)_3=x(x-1)(x-2)=x^3-3x^2+2x\)，故 \(s(3,3)=1,\,s(3,2)=-3,\,s(3,1)=2\)，正是 \((-1)^{3-k}c(3,k)\)。
即时自测
  1. 用循环记号写出 \(p=2413\)（即 \(p(1)=2,p(2)=4,p(3)=1,p(4)=3\)）的循环分解，并给出它的规范循环记号。它有几个循环？
  2. 利用递推 (4.6) 算出 \(c(6,2)\)（提示：先有 \(c(5,1)=24,\;c(5,2)=50\)）。
  3. 把 \((x+3)(x+2)(x+1)x\) 展开，读出 \(c(4,k)\)，并验证 \(\sum_{k} c(4,k)=4!\)。

返回 全书目录